Missing values in theoretical models of incomplete database are often represented with marked nulls, while in SQL databases missing values are all denoted by the same syntactic NULL object. Even practical algorithm to approximate certain answers (answers which are true regardless of how incomplete information is interpreted) are often developed in the model with marked nulls. However computing certain answers for marked nulls is co-NP complete even for the most simple queries when inequalities are allowed. In this short paper we study the tractability of certain answers for SQL nulls in a fragment of relational algebra where selection with inequalities is permitted. We de ne the fragment and present an algorithm to compute certain answers. We also show that if we add even small features to the fragment, computing certain answers becomes intractable. This study emphasises the necessity of a speci c certain answers approximation scheme for SQL nulls and o ers ideas to design it.
Introduction
The standard way of answering queries on incomplete databases is to compute
certain answers: those that do not depend on the interpretation of unknown data.
However, evaluating certain answers for core relational algebra is co-NP
complete in data complexity [
We consider incomplete databases with nulls interpreted as missing
information [
A valuation v on a database D is a map v : N ull(D) ! Const that assigns constant values to nulls occurring in the database. By v(D) we denote the result of replacing each ?i with v(?i) in D. A relational query Q of arity k takes a complete database D and returns a bag of k-tuples over Const(D). If such a query Q is asked on an incomplete database D, to answer it we compute for each t 2 (Const [ N ull(D))k the bag of certain answers denoted (Q; D) which verify : #(t; (Q; D)) =
min
v a valuation
#(v(t); Q(v(D))):
Where
#(t; R) =
n if t 2n R
0 if t 2= R
and we use t 2n R to say that t has a multiplicity n in the bag R [
In order to add boolean queries to relational algebra we add the operator ; such that for any complete database D and any query Q, ;(Q)(D) = ; if Q(D) = ; and ;(Q)(D) = f()g otherwise. 2
Relational algebra fragment with e
cient evaluation
Our goal is to nd a fragment for which we can build an e cient algorithm
to compute all certain answers. As a motivation we take inspiration from the
hierarchical queries from probabilistic databases [
Q1 :=Q1 \ Q1 j Q1 [ Q1 j Q2 :=Q2 [ Q2 j (Q2) j (Q1) j (Q2) j R (Q1) j R Note that the only di erence between the two classes is that Q1 allows intersection while Q2 does not. We denote by Q1 resp. Q2 the set of query induced by the grammar Q1 resp. Q2. Based on them we de ne the class RAH : Q0 := Q0 [ Q0 j Q1 n Q2 j (Q0) j (Q0) j ;(Q0) j R
A relational algebra query is called non-repeating if every relation symbol
occurs at most once [
Our main result is : Theorem 1. For every query Q 2 RAH;NR and every database D computing (Q; D) is tractable.
We now outline the proof of Theorem 1. As the restricted hierarchical fragment of relational algebra imposes that every binary operation in selection conditions is between attributes of the same relation or constants, then for each query in the fragment we can build an equivalent query where selection occurs only on relation symbols.
Lemma 1 For every Q 2 RAH there exists Q0 2 RAH such that jQ0j = O(jQj) and for every complete database D, (Q; D) = (Q0; D) and every selection operator of Q0 occurs on a relation symbol.
Now we show that for Q1 2 Q1 computing (Q1; D) is tractable. One starts by applying the lemma 1 to push every selection operator. Its queries are now given by : Q1 := Q1 \ Q1 j Q1 [ Q1 j (R) j (Q1) j R. Then computation is done inductively by the following rules : #(t; (Q \ Q0; D)) =min(#(t; (Q; D)); #(t; (Q0; D))) #(t; (Q [ Q0; D)) =#(t; (Q; D)) + #(t; (Q0; D)) #(t; ( #(t; (R; D)) =#(t; R)
X (Q); D) = u; (u)=t
#(u; (Q; D)) 8 #(t; R) if 8v a valuation; v(t) = t ^ (t) #(t; ( (R); D)) = < 1 if 9v a valuation; v(t) 6= t ^ is a valid formulae : 0 otherwise Therefore for every query Q 2 Q1, the evaluation of (Q; D) is tractable. The computation rules above are sound and complete only because the relations hence the nulls can not repeat.
Then we show how to evaluate (Q0; D). Informally in order to evaluate Q0 one has to compute the possible answers of Q2 which match an element of Q1. But rst notice that as intersection is not allowed in Q2 we can push the projection operators : Lemma 2 For every Q 2 Q2 there exists Q0 2 Q2 such that jQ0j = O(jQj) and for every complete database D, Q(D) = Q0(D) and every projection operator of Q0 occurs on a relation symbol, or on a selection operator over a relation symbol.
Then from lemmas 1 and 2 we just have to consider queries of the form: Q0 = Q1 n S R ( R (R)) with Q1 2 Q1 ^ Q2 2 Q2
R2Q2 For every R 2 Q2; 8t 2 R we build a set: +Q1;R (t) = fu 2 (Q1; D) j 9v a valuation; R(v(t)) ^
R (v(t)) = v(u)g As the relations hence the nulls can not repeat, (Q1; D) can be computed independently of Q2 and is at most of the size of D, then for each R, the set +Q1;R can be built in polynomial time.
Moreover for every u 2 (Q1; D) we build a bag: 8t 2 (Const [ N ull) ; #(t; *Q2 (u)) =
X R2fR2Q2ju2+Q1;R(t)g #(t; R) Here, *Q2 (u) is the bag of elements in S R which unify with u 2 (Q1; D). R2Q2 Then a tuple u belongs to certain answers of Q0 if and only if the multiplicity of u in (Q1; D) is higher than the number of elements in *Q2 (u). Proposition 1 Let Q0 = Q1 n SR2Q2 Then #(u; (Q0; D)) = max(0; j *Q2 (u)j of (Q0; D) is tractable.
R (
R (R)) with Q1 2 Q1 ^ Q2 2 Q2. #(u; (Q1; D))), and the evaluation
However there exists a query Q0 such that 8u; #(u; (Q0; D)) = 0 and ( ;(Q0); D)) 6= ;. In order to compute ( ;(Q0); D), we want to check if there exists a matching between (Q1; D)) and the elements that unify with it. Proposition 2 Let Q0 = Q1 n SR2Q2 ( R (R)) with Q1 2 Q1 ^ Q2 2 Q2. Then ( ;(Q0); D) = ; if and only if there exists an injective function m : ( ;(Q1); D) ! S R such that 8t 2 ( ;(Q1); D); m(t) 2*Q2 (t).
R2Q2
m is a 2DM matching, and the evaluation of
( ;(Q0); D) is tractable [
Extending the fragment In this section we discuss the di culties of extending the fragment RH;NR to obtain tractable evaluation of certain answers.
Proposition 3 For each of the following extensions of RH;NR : { allowing cross-product. { allowing repetition of relation symbols. { allowing intersection on the right-hand side of the Q1 n Q2 operator. { allowing di erence on the right-hand side of the Q1 n Q2 operator. the data complexity of evaluating certain answers is co-NP hard. 4
Conclusions In this paper we have exhibited a fragment for which computing certain answers for SQL nulls is tractable. We have also shown that adding features to the fragment quickly lead to intractability. The next question that arises is toward maximality, in order to nd a dichotomic property for certain answers with SQL nulls one would have to consider equivalently expressive classes of query. As soon as we fully understand what leads to intractability we will be able to design a more accurate approximation scheme for SQL nulls.