Certain answers are a widely accepted semantics of query answering over incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on developing evaluation algorithms with correctness guarantees, that is, techniques computing a sound but possibly incomplete set of certain answers. In this paper, we show how novel evaluation algorithms with correctness guarantees can be developed leveraging conditional tables and the conditional evaluation of queries, while retaining polynomial time data complexity.
Incomplete information arises naturally in many database applications, such as data
integration [
A principled way of answering queries over incomplete databases is to compute certain answers, which are query answers that can be obtained from all the complete databases an incomplete database represents. This central notion is illustrated below. Example 1. Consider the database D consisting of the two unary relations R = fhaig and S = fh?ig, where ? is a null value. Under the missing value interpretation of nulls (i.e., a value for ? exists but is unknown), D represents all the databases obtained by replacing ? with an actual value.
A certain answer to a query is a tuple that belongs to the query answers for every database represented by D. For instance, consider the query $1=a(R), selecting the tuples in R whose first value is equal to a. The certain answers to the query are fhaig, because no matter how ? is replaced, the query answers always contain hai. 2
For databases containing (labeled) nulls, certain answers to positive queries can be easily computed in polynomial time by applying a “naive” evaluation, that is, treating nulls as standard constants. However, for more general queries with negation the problem becomes coNP-hard. To make query answering feasible in practice, one might resort to SQL’s evaluation, but unfortunately, the way SQL behaves in the presence of nulls may result in wrong answers.
Specifically, as evidenced in [
Assuming that R and S’s attribute is called A, the same query can be expressed in SQL as follows:
SELECT R.A FROM R WHERE NOT EXISTS (
SELECT * FROM S WHERE R.A = S.A )
However, the answer to the query above is hai, which is not a certain answer. The problem with the SQL semantics is that every comparison involving at least one null evaluates to the truth value unknown, then 3-valued logic is used to evaluate the classical logical connectives and, or, and not, and eventually only those tuples whose condition evaluates to true are kept.
Going back to the query above, the nested subquery compares ? with a, and since such a comparison evaluates to unknown (because a null is involved) then the result of the nested subquery is empty. As a consequence, the final result of the query is hai. 2
Thus, on the one hand, SQL’s evaluation is efficient but flawed, on the other hand,
certain answers are a principled semantics but with high complexity. One way of
dealing with this issue is to develop polynomial time evaluation algorithms computing
approximate certain answers. In this regard, there has been recent work on evaluation
algorithms with correctness guarantees, that is, techniques providing a sound but
possibly incomplete set of certain answers [
Example 3. Consider the database D of Example 1 and the query R $1=b(S). In
this case, the certain answers are fhaig. However, the approximation provided by the
approach in [
In this paper, we show how conditional tables and the conditional evaluation of
queries [
Example 4. Consider again the database D of Example 1 and the query R $1=b(S). The conditional evaluation of the query is carried out by applying the “conditional” counterpart of each relational algebra operator. Rather than returning a set of tuples, the conditional evaluation of a relational algebra operator returns pairs of the form ht; 'i, where t is a tuple and ' is an expression stating under which conditions t can be derived.
Considering the query above, first the conditional evaluation of $1=b(S) is performed, which gives h?; '0i, where '0 is the condition (? = b). Then, the conditional evaluation of the difference operator is carried out, yielding ha; '00i, where '00 is the condition (? 6= a) _ (? 6= b). 2
Conditions are valuable information that can exploited to determine which tuples are certain answers. For instance, from an analysis of '00 above, one can realize that the condition is always true—thus, hai is a certain answer. There might be different ways of evaluating tuples’ conditions. In this paper, we propose some strategies. 2
Basics. We assume the existence of the following disjoint countably infinite sets: a set Const of constants and a set Null of (labeled) nulls. Nulls are denoted by the symbol ? subscripted. A tuple t of arity k is an element of (Const [ Null)k, where k is a nonnegative integer. The i-th element of t is denoted as t[i], where 1 i k. Given a possibly empty ordered sequence Z of integers i1; : : : ; ih in the range [1::k], we use t[Z] to denote the tuple ht[i1]; : : : ; t[ih]i.
A relation of arity k is a finite set of tuples of arity k. A relational schema is a set of relation names, each associated with a non-negative arity. A database D associates a relation RD of arity k with each relation name R of arity k. With a slight abuse of notation, when the database is clear from the context, we simply write R instead of RD for the relation itself. The arity of R is denoted as ar (R). The sets of all constants and nulls occurring in a database D are denoted by Const(D) and Null(D), respectively. The active domain of D is adom(D) = Const(D) [ Null(D). If Null(D) = ;, we say that D is complete. Likewise, a relation is complete if it does not contain nulls.
A valuation is a mapping from Const [ Null to Const s.t. (c) = c for every c 2 Const. Valuations can be applied to tuples, relations, and databases in the obvious way. For instance, the result of applying to a database D, denoted (D), is the complete database obtained from D by replacing every null ?i with (?i).
The semantics of a database D is given by the set of complete databases f (D) j is a valuationg, also called possible worlds.
Query answering. We consider queries expressed with the relational algebra, that is, by means of the following operators: selection , projection , cartesian product , union [, intersection \, and difference . In the rest of the paper, a query is understood to be a relational algebra expression built up from the above operators, unless otherwise indicated. The result of evaluating a query Q on a database D, treating nulls as standard constants (i.e., every (labeled) null or constant is equal to itself and different from every other element of Const [ Null), is denoted as Q(D). A query Q returning k-tuples is said to be of arity k, and ar (Q) denotes its arity.
A widely accepted semantics of query answering relies on the notion of a
certain answer. The certain answers to a query Q on a database D are the tuples in
TfQ( (D)) j is a valuationg. Computing certain answers is coNP-hard (data
complexity), even when the same null cannot occur multiple times [
For query answering, we will use a more general notion first proposed in [
A query evaluation algorithm has correctness guarantees for a query Q if for every
database D it returns a subset of cert(Q; D) [
Syntax and semantics. Conditional tables have been proposed in [
A conditional tuple (c-tuple for short) of arity k (k 0) is a pair ht; 'i, where t is a tuple of arity k and ' 2 E . Notice that ' may involve nulls and constants not necessarily appearing in t—e.g., t is the tuple ha; ?1i and ' is the condition (?2 = c)^(?1 6= ?3).
A conditional table (c-table for short) of arity k is a finite set of c-tuples of arity k. A conditional database C associates a c-table RC of arity k with each relation name R of arity k. With a slight abuse of notation, when the conditional database is clear from the context, we simply write R instead of RC for the c-table itself.
The result of applying a valuation to a c-table T is (T ) = f (t) j ht; 'i 2 T and j= 'g: Thus, (T ) is the complete relation obtained from T by keeping only the c-tuples in T whose condition is satisfied by , and applying to such c-tuples. The set of complete relations represented by T is rep(T ) = f (T ) j is a valuationg:
Likewise, a conditional database C = fT1; : : : ; Tmg represents the following set of
complete databases: rep(C) = ff (T1); : : : ; (Tm)g j is a valuationg:
Conditional evaluation. Below we recall the conditional evaluation of a query over a
conditional database (see [
Let T1 and T2 be c-tables of arity n and m, respectively. In the definitions below, for the union and difference operators it is assumed that n = m. For projection, Z is a possibly empty ordered sequence of integers in the range [1::n]. For selection, is a Boolean combination of expressions of the form ($i = $j), ($i = c), ($i 6= $j), ($i 6= c), where 1 i; j n, and c 2 Const. The conditional evaluation of a relational algebra operator op is denoted as o_p. In the following, given two tuples t1 and t2 of arity n, we use (t1 = t2) as a shorthand for the condition V (t1[i] = t2[i]). i2[1::n] – Projection: _ Z (T1) = fht[Z]; 'i j ht; 'i 2 T1g: – Selection: _ (T1) = fht; '0i j ht; 'i 2 T1 and '0 = ' ^ (t)g;
where (t) is the condition obtained from by replacing every $i with t[i]. – Union: T1 [_ T2 = fht; 'i j ht; 'i 2 T1 or ht; 'i 2 T2g: – Difference: T1 _ T2 = fht1; '0i j ht1; '1i 2 T1 and '0 = '1 ^ 't1;T2 g; where 't1;T2 = V :('2 ^ (t1 = t2)).
ht2;'2i2T2 – Cartesian product: T1 _ T2 = fht1 t2; '1 ^ '2i j ht1; '1i 2 T1; ht2; '2i 2 T2g; where t1 t2 is the tuple obtained as the concatenation of t1 and t2.
The result of the conditional evaluation of a query Q over a conditional database C
is denoted as Q_ (C). Notice that Q_ (C) is a c-table. For a fixed query Q and a conditional
database C, Q_ (C) can be evaluated in polynomial time in the size of C (see [
W.l.o.g., in the rest of the paper we assume that every selection condition is a conjunction of expressions of the form ($i = $j), ($i = c), ($i 6= $j), and ($i 6= c). 3
In this section, we show how to exploit conditional tables to compute a sound (but possibly incomplete) set of certain answers with nulls. The basic idea is to rely on the conditional evaluation of the relational algebra operators, in order to keep track of how each tuple is derived during query evaluation, and then apply a strategy to evaluate conditions, so that each tuple is eventually associated with a truth value. Tuples that are associated with the condition true are certain answers with nulls.
We start by introducing an explicit conditional evaluation for intersection. In the previous section, we recalled the conditional evaluation of different relational algebra operators. Clearly, even if intersection was not reported, it can be expressed in terms of the other operators. Let T1 and T2 be c-tables of arity n. Then,
T1 \_ T2 = fht1; '0i j ht1; '1i 2 T1; ht2; '2i 2 T2; '0 = '1 ^ '2 ^ (t1 = t2)g: We slightly generalize c-tables to allow also unknown as a condition. Thus, from now on, E is the set of all expressions that can be built using the standard logical connectives with expressions, called atomic conditions, of the form ( = ), ( 6= ), true, false, and unknown, where ; 2 Const [ Null. We will discuss different strategies to “evaluate” conditions, that is, to reduce them to either true or false or unknown—as shown in the following, tuples having condition true are certain answers with nulls.
We assume the following strict ordering false < unknown < true. The three-valued evaluation of a condition ' 2 E , denoted eval ('), is defined inductively as follows: – eval ((
8>true = )) = <false >:unknown if = ; if 6= and ; otherwise: 8>true if 6= and ; – eval (( 6= )) = <false if = ;
>:unknown otherwise: – eval (('1 ^ '2)) = minfeval ('1) ; eval ('2)g. – eval (('1 _ '2)) = maxfeval ('1) ; eval ('2)g. 2 Const; 2 Const; 8>true if eval (') = false; < – eval ((:')) = false if eval (') = true;
>:unknown otherwise. – eval (v) = v for v 2 ftrue; unknown; falseg.
The basic idea of our first evaluation algorithm, which we call naive evaluation, is to
perform the three-valued evaluation of conditions after each relational algebra operator
is applied (that is, after its conditional evaluation). One interesting fact about the naive
evaluation is that it is equivalent to the evaluation algorithm of [
Given a c-tuple t = ht; 'i, with a slight abuse of notation, we use eval (t) to denote ht; eval (')i. Likewise, given a conditional table T , eval (T ) denotes feval (t) j t 2 T g.
To define the naive evaluation, we first provide the following definitions: Evaln(R) = eval (R) Evaln(Q1 [ Q2) = eval (Evaln(Q1) [_ Evaln(Q2)) Evaln(Q1 \ Q2) = eval (Evaln(Q1) \_ Evaln(Q2)) Evaln(Q1 Q2) = eval Evaln(Q1) _ Evaln(Q2) Evaln(Q1 Q2) = eval Evaln(Q1) _ Evaln(Q2) Evaln( (Q)) = eval ( _ (Evaln(Q)))
Evaln( Z (Q)) = eval ( _ Z (Evaln(Q)))
Given a relation R, we define the c-table R = fht; truei j t 2 Rg. Analogously, given a database D, we define D as the conditional database obtained from D by replacing every relation R of it with R. Here the basic idea is to convert a database D into a simple conditional database D where all conditions are true, so that D can be used as the starting point for the conditional evaluation of queries.
Given a query Q and a database D, we use Evaln(Q; D) to denote the result of evaluating Evaln(Q) over D. Finally, we define:
Evaltn(Q; D) = ft j ht; truei 2 Evaln(Q; D)g;
Evalnp(Q; D) = ft j ht; 'i 2 Evaln(Q; D) and ' 6= falseg: Example 5. Consider the database D consisting of the two unary relations R = fhaig and S = fh?1ig. Consider also the query Q5 = R S. The conditional database D consist of the two c-tables R = fha; trueig and S = fh?1; trueig. Then, Evaln(Q5; D) = eval eval R _ eval S = eval R _ S
= eval (fha; true ^ :(true ^ (a = ?1))ig) = fha; unknownig: Thus, Evaltn(Q5; D) = ; and Evalnp(Q5; D) = fhaig. 2
The following theorem states that the naive evaluation is equivalent to the
evaluation algorithm of [
Theorem 2. Evaln(Q; D) can be computed in polynomial time in the size of D, for every query Q and database D.
The naive evaluation presented above is somehow limited, since it does not use much the power of conditional tables, as shown in the following example. Example 6. Consider the database D of Example 5 and the query Q6 = R $1=b(S). Clearly, cert(Q6; D) = fhaig, as the selection returns either fhbig or ; in every possible world, and thus the result of the difference is fhaig in every possible world. However, the naive evaluation is not able to realize this aspect and behaves as follows: Evaln(Q6; D) = = eval eval R _ eval _ $1=b eval S = eval fha; trueig _ eval ( _ $1=b (fh?1; trueig)) = eval fha; trueig _ eval (fh?1; true ^ (?1 = b)ig) = eval fha; trueig _ fh?1; unknownig = eval (fha; true ^ :(unknown ^ (a = ?1))ig) = fha; unknownig: Thus, Evaltn(Q6; D) = ;. In this case, the crucial point is that eval _ $1=b eval S fh?1; unknownig, and the fact that ?1 can only be equal to b gets lost. = 2
The previous example suggests that equalities might be exploited to refine the evaluation of conditions, as illustrated in the following example.
Example 7. Consider again the database D of Example 5 and the query Q6 of Example 6. By “propagating” equalities into conditions and tuples after each relational algebra operator is conditionally evaluated, we get: fha; trueig _ _ $1=b(fh?1; trueig) = fha; trueig _ fh?1; true ^ (?1 = b)ig = fha; trueig _ fhb; unknownig = fha; true ^ :(unknown ^ (a = b))ig = fha; trueig:
Thus, we can conclude that hai is a certain answer with nulls. Recall that cert(Q6; D) = fhaig and Evaltn(Q6; D) = ;. 2
In the previous example, it is interesting to notice that the selection returns the ctuple hb; unknowni, meaning that the only tuple that can be returned (in some cases) is hbi, and thus providing more accurate information than the naive evaluation. 4
Certain answers are a principled manner to answer queries on incomplete databases. Since their computation is a coNP-hard problem, recent research has focused on polynomial time algorithms providing under-approximations. Leveraging conditional tables, we have shown how new approximation algorithms can be developed.
We are currently working on more refined evaluation strategies which better exploit
the power of conditional tables, with the aim of computing more certain answers with
nulls. For instance, conditions might be rewritten into a more suitable form (e.g.,
conjunctive normal form or disjunctive normal form [