The ability to handle incomplete information is fundamental in many areas, including data integration, data exchange, inconsistent databases, and the Semantic Web. In such areas, it is often impossible to describe the domain of interest in a full, comprehensive way, so the aim of an incomplete database is to concisely represent a (potentially infinite) number of completions. Incomplete information is usually represented by allowing placeholders for unknown values, which are called “nulls”. An incomplete database I with such nulls then represents a set of databases with complete information, called representations of I, each of which is obtained by replacing nulls by actual values.
One of the most important problems associated to databases is query answering.
Since an incomplete database I can have several representations, the aim in this context
is to find the “certain answers” to a query Q, that is, an incomplete database I0 that
precisely represents the answers to Q over all the representations of I. Unfortunately,
this is possible only in restricted settings, which allow for the so called strong
representation systems [
In this paper, we make initial steps in the study of the complexity of the problem of computing certain answers as objects. In particular, we concentrate on the widely studied setting of union of conjunctive queries with inequalities and incomplete databases under the open-world assumption, and we provide positive and negative results. On the positive side, we show that in this case the certain answers to a query can be computed. On the negative side, we show that this computation can be costly, as the certain answers can be of exponential size even if we restrict to conjunctive queries with inequalities over binary relations.
We assume countably infinite disjoint sets of constants, denoted by Const, and of nulls, denoted by Null. A relational schema (or just schema) is a set of relation names with associated arities. An incomplete database I over is an assignment of a k-ary relation RI over (Const[Null) to each k-ary name R in . Sets of constants and nulls that occur in I are denoted by Const(I) and Null(I), respectively, and their union, called an active domain, is denoted by adom(I). A complete database is an incomplete database without nulls. In what follows, we use I, I1, I2, I0, : : : to denote incomplete databases, and D, D1, D2, D0, : : : to denote complete databases.
The semantics of an incomplete database I is defined in terms of its representations,
which are complete databases that are considered as possible interpretations of I [
A homomorphism from an incomplete database I1 to an incomplete database I2 is
a function h : adom(I1) ! adom(I2) that is the identity on Const(I1) and such that
h(I1) I2 (we define h(I) analogously to v(I) before). We write I1 7! I2 if there
is a homomorphism from I1 to I2, and I1 7! I, for a set I of incomplete databases,
if I1 7! I2 for each I2 2 I. Then a characterization of is given by the following
statement [
I1
(1)
As customary, a query Q over a schema is a function that assigns to each complete
database D of a complete database Q(D). Moreover, given an incomplete database I,
the certain answers as object (or certain answers, for short) to Q over I, denoted by
cert(Q; I), is defined [
where ans(Q; I) = fQ(D) j D 2 [[I]]g: Notice that two greatest lower bounds I1, I2 of ans(Q; I) are equivalent in terms of the information ordering: I1 I2 and I2 I1; thus, we can choose any greatest lower bound of ans(Q; I) as the certain answer to Q over I. 3
In this section, we focus on the problem of computing cert(Q; I) for a union of
conjunctive queries Q with inequalities (UCQ6=) and an incomplete database I. It is assumed
that a reader is familiar with the syntax of such queries as well as their semantics (i.e.,
the definition of Q(D)). Complete proofs of the results below can be found in [
The first issue we have to deal with when computing cert(Q; I) is the fact that ans(Q; I) may be infinite. The following proposition overcomes this limitation by showing that it is not necessary to consider the entire set ans(Q; I) when computing cert(Q; I), but instead one can consider just a finite subset of it.
Proposition 1. Let Q be a UCQ6= over a schema and I an incomplete database over . Then there exists D ans(Q; I) such that D is finite and cert(Q; I) is a greatest lower bound of D.
In fact, from the proof of Proposition 1, it is possible to obtain a simple exponentialtime algorithm that, given a UCQ6= Q and an incomplete database I, returns a set D ans(Q; I) such that cert(Q; I) 2 glb(D), where each D 2 D is of linear size in the size of I. We denote such D by anscan(Q; I).
Now, given a finite set D, it is known (see, e.g., [
RI = f a1 b1; : : : ; ak
bk j (a1; : : : ; ak) 2 RI1 ; (b1; : : : ; bk) 2 RI2 g; here a a = a for all a 2 Const [ Null and a b is a fresh null na;b for all different a; b 2 Const [ Null. It immediately follows that Const(I) Const(I1) \ Const(I2). Note that the product is associative and commutative (up to renaming of nulls). For D = fD1; : : : ; Dng, we denote by Q D the product D1 Dn. The following picture illustrates this notion for a schema consisting of a single binary relation: a
b c I1 a b I2 nb;a
a nc;b
I1
I2 na;b b nc;a By combining Proposition 1 with the algorithm for computing anscan(Q; I), we obtain an algorithm for computing a certain answer.
Proposition 2. Let Q be a UCQ6= over a schema and I and incomplete database over . Then cert(Q; I) can be computed as Q anscan(Q; I).
Finally, in the following theorem, which is the main result of this note, we prove that the certain answers as objects can be of exponential size, even if we restrict to the case of conjunctive queries over binary relations.
Theorem 1. There exists a family of incomplete databases In, for n 2 N, and a conjunctive query Q with inequality such that the size of the smallest cert(Q; In) grows exponentially in the size of In.
Proof. (Sketch) For a natural number m, consider the complete database
Zm = fZ(d1; d2); : : : ; Z(dm 1; dm); Z(dm; d1)g; where d1; d2; : : : ; dm are (distinct) constants, encoding a directed cycle of length m.
Let n be a natural number, and let p1; : : : ; pn be the first n prime numbers. We define In to be the incomplete database containing – disjoint cycles Zp1 ; : : : ; Zpn , – for a constant ai, i = 1; ::; n, the pairs R(ci; ai) for each constant ci in Zpi , – for constants b1 and bn, the pairs P (a1; b1) and P (an; bn), and – for nulls l1; : : : ; ln 1, the pairs P (ai; li) and P (ai+1; li) for 1 i n 1. Below we depict I5:
Z2 Z3 Z5 Z7 Z11 P a1 b1
R a2
R a3
R a4
R P
P l1
P
P l2
P
P l3
P
P l4
R a5
P b5 Consider the query Q(x; y) = 9z(Z(x; y) ^ R(x; z) ^ R(y; z) ^ Q6=(z)); where
Q6=(z) = 9u9v(P (z; u) ^ P (z; v) ^ (u 6= v)):
(minimal) each binary relation Cpi = f(c; d) j Z(c; d) 2 Zpi g, for 1 i ans(Q; In), and any other relation in ans(Q; In) subsumes one of them. Let Zn = fCp1 ; : : : ; Cpn g. We define a directed cycle of nulls of size p1 n, is in pn Z = fZ(n1; n2); : : : ; Z(np1 pn 1; np1 pn ); Z(np1 pn ; n1)g:
Claim. Any of certain answers cert(Q; In) is in glb(Zn).
The proof of the claims relies on (minimal), while the construction of Z and the proof of the second claim rely on the fact that Cpi are cycles of prime length. Indeed, Z is (isomorphic to) the product of all Cpi , as the product of a pair of directed cycles of sizes k1 and k1, when k1 and k2 are co-prime numbers, is a directed cycle of the size k1 k2.
From the above claims, it follows that Z and cert(Q; In) are homomorphically
equivalent. It is well-known from graph theory that every graph that is homomorphically
equivalent to a directed cycle has to contain that cycle. Hence, the minimal certain
answer cert(Q; In) is of exponential size in the size of In. (We observe that the size of
In is polynomially bounded in n, as pn < cn2, for a constant c [