The problem of computing the certain answer to a conjunctive query over a relational instance subject to primary key constraints is a classical hard problem in database research. On the theoretical side, we present a decomposition and pruning strategy that reduces, in polynomial time, the original problem to a collection of smaller problems of the same sort that can be solved independently. From a practical perspective, we discuss an experiment on large data sets that shows the e ectiveness of the overall technique and its implementation in ASP.
Integrity constraints provide means for ensuring that database evolution does
not result in a loss of consistency or in a discrepancy with the intended model of
the application domain. A relational database that do not satisfy some of these
constraints is said to be inconsistent. In practice it is not unusual that one has
to deal with inconsistent data [
In this paper, we adopt the second approach { which has been proposed
by [
CQA under primary keys is coNP-complete in data complexity [
In this paper, we show that logic programming can still be e ectively used
for computing consistent answers over large relational databases. We describe
a decomposition strategy that reduces (in polynomial time) the computation of
the consistent answer to a CQ over a database subject to primary key constraints
into a collection of smaller problems of the same sort. At the core of the strategy
is a cascade pruning mechanism that dramatically reduces the number of key
violations that have to be handled to answer the query. Moreover, we implement
the new strategy using Answer Set Programming (ASP) [
We are given two disjoint countably in nite sets of terms denoted by C and V and called constants and variables, respectively. We denote by X sequences of variables X1; : : : ; Xn, and by t sequences of terms t1; : : : ; tn. We also denote by [n] the set f1; : : : ; ng, for any n > 1.
A (relational ) schema is a triple hR; ; i where R is a nite set of relation symbols (or predicates), : R ! N is a function associating an arity to each predicate, and : R ! 2N is a function that associates, to each r 2 R, a nonempty set of positions from [ (r)], which represents the primary key of r. Moreover, for each relation symbol r 2 R and for each position i 2 [ (r)], r[i] denotes the i-th attribute of r. Throughout, let = hR; ; i denote a relational schema. An atom (over ) is an expression of the form r(t1; : : : ; tn), where r 2 R, and n = (r). An atom is called a fact if all of its terms are constants of C. Conjunctions of atoms are often identi ed with the sets of their atoms. For a set A of atoms, the variables occurring in A are denoted by var (A). A database D (over ) is a nite set of facts over . Given an atom r(t) 2 D, we denote by ^t the sequence tj (r). We say that D is inconsistent (w.r.t. ) if it contains two di erent atoms of the form r(t1) and r(t2) such that ^t1 = ^t2. Otherwise, it is consistent. A repair R of D (w.r.t. ) is any maximal consistent subset of D. The set of all the repairs of D is denoted by rep(D; ). A substitution is a mapping : C [ V ! C [ V which is the identity on C. Given a set A of atoms, (A) = fr( (t1); : : : ; (tn)) : r(t1; : : : ; tn) 2 Ag. The restriction of to a set S C [ V, is denoted by jS . A conjunctive query (CQ) q (over ) is an expression of the form 9Y '(X; Y), where X [ Y are variables of V, and ' is a conjunction of atoms (possibly with constants) over . To highlight the free variables of q, we often write q(X) instead of q. If X is empty, then q is called a Boolean conjunctive query (BCQ). Assuming that X is the sequence X1; : : : ; Xn, the answer to q over a database D, denoted q(D), is the set of all n-tuples ht1; : : : ; tni 2 Cn for which there exists a substitution such that ('(X; Y)) D and (Xi) = ti, for each i 2 [n]. A BCQ is true in D, denoted D j= q, if hi 2 q(D). The consistent answer to a CQ q(X) over a database D (w.r.t. ), denoted ans(q; D; ), is the set of tuples TR2rep(D; ) q(R). Clearly, ans(q; D; ) q(D) holds. A BCQ q is consistently true in a database D (w.r.t.
), denoted D j= q, if hi 2 ans(q; D; ). 3
We present a strategy suitable for computing the consistent answer to a CQ over
an inconsistent database subject to primary key constraints. The new strategy
reduces in polynomial time that problem to a collection of smaller ones of the
same sort. Given a database D over a schema , and a BCQ q, we identify a set
F1; : : : ; Fk of pairwise disjoint subsets of D, called fragments, such that: D j= q
i there is i 2 [k] such that Fi j= q. At the core of our strategy we have: (1) a
cascade pruning mechanism to reduce the number of \crucial" inconsistencies,
and (2) a technique to identify a suitable set of fragments from any (possibly
unpruned) database. For the sake of presentation, we start with principle (2).
(Proofs are given in [
Given a database D, a key component K of D is any maximal subset of D such that if r1(t1) and r2(t2) are in K, then both r1 = r2 and ^t1 = ^t2 hold. Namely, K collects only atoms that agree on their primary key. Hence, the set of all key components of D, denoted by comp(D; ), forms a partition of D. If a key component is a singleton, then it is called safe; otherwise it is con icting. Let comp(D; ) = fK1; : : : ; Kng. It can be veri ed that rep(D; ) = ffa1; : : : ; ang : a1 2 K1; : : : ; an 2 Kng. Let us now x throughout this section a BCQ q over . For a repair R 2 rep(D; ), if q is true in R, then there is a substitution such that (q) R. But since R D, it also holds that (q) D. Hence, sub(q; D) = f jvar(q) : is a substitution and (q) Dg is an overestimation of the substitutions that map q to the repairs of D.
Inspired by the well-known notions of con ict-hypergraph and con ict-join graph, we now introduce the notion of con ict-join hypergraph. Given a database D, the con ict-join hypergraph of D (w.r.t. q and ) is denoted by HD = μ2(q) r1(1,2) r1(1,3) μ3(q) μ4(q) hD; Ei, where D are the vertices, and E are the hyperedges partitioned in Eq = f (q) : 2 sub(q; D)g and E = fK : K 2 comp(D; )g. A bunch B of vertices of HD is any minimal nonempty subset of D such that, for each e 2 E, either e B or e \ B = ; holds. Intuitively, every edge of HD collects the atoms in a key component of D or the atoms in (q), for some 2 sub(q; D). Moreover, each bunch collects the vertices of some connected component of HD. An example follows to x these preliminary notions.
Example 1. Consider the schema = hR; ; i, where R = fr1; r2g, (r1) = (r2) = 2, and (r1) = (r2) = f1g. Consider also the database D = fr1(1; 2); r1(1; 3); r2(4; 1); r2(5; 1), r2(5; 2)g, and the BCQ q = r1(X; Y ); r2(Z; X). The con icting components of D are K1 = fr1(1; 2); r1(1; 3)g and K3 = fr2(5; 1), r2(5; 2)g, while its safe component is K2 = fr2(4; 1)g. The repairs of D are R1 = fr1(1; 2); r2(4; 1); r2(5; 1)g, R2 = fr1(1; 2); r2(4; 1); r2(5; 2)g, R3 = fr1(1; 3); r2(4; 1); r2(5; 1)g, and R4 = fr1(1; 3); r2(4; 1); r2(5; 2)g. Moreover, sub(q; D) contains the substitutions: 1 = fX 7! 1; Y 7! 2; Z 7! 4g, 2 = fX 7! 1; Y 7! 3; Z 7! 4g, 3 = fX 7! 1; Y 7! 2; Z 7! 5g, and 4 = fX 7! 1; Y 7! 3; Z 7! 5g. The con ict-join hypergraph HD = hD; Ei is as in Figure 1. Solid (resp., dashed) edges form the set E (resp., Eq). Since 1 maps q to R1 and R2, and 2 maps q to R3 and R4, we conclude that D j= q. Finally, D is the only bunch of HD. tu
In Example 1 we observe that K3 can be safely ignored in the evaluation of q. In fact, even if both 3(q) and 4(q) contain an atom of K3, 1 and 2 are su cient to prove that q is consistently true. This might suggest to focus only on the set F = K1 [ K2, and on its repairs fr1(1; 2); r2(4; 1)g and fr1(1; 3); r2(4; 1)g. Also, since F j= q, F represents the \small" fragment of D that we need to evaluate q. The practical advantage of considering F instead of D should be already clear: (1) the repairs of F are smaller than the repairs of D; and (2) F has less repairs than D. We are now ready to introduce the notion of fragment. Consider a database D. For any set C comp(D; ) of key components of D, we say that the set F = SK2C K is a (well-de ned ) fragment of D. According to this notion, the set F = K1 [ K2 in Example 1 is a fragment of D. The following theorem, states a useful property that holds for any fragment.
Theorem 1. Consider a database D, and two fragments F1 F1 j= q, then F2 j= q.
F2 of D. If
Note that D is indeed a fragment of itself. Hence, if q is consistently true, then there is always the fragment F = D such that F j= q. But now the question is: How can we identify a convenient set of fragments of D? The naive way would be to use as fragments the bunches of HD. Soundness is guaranteed by Theorem 1. Regarding completeness, we rely on the following result. Theorem 2. Consider a database D. If D j= HD such that B j= q. q, then there is a bunch B of
By combining Theorems 1 and 2 we are able to reduce, in polynomial time, the original problem into a collection of smaller ones of the same sort. However, this technique alone is not su cient to deal with large data sets. Indeed, it involves the entire database by considering all the bunches of the con ict-join hypergraph. We now introduce an algorithm that can realize that K3 is \redundant" in Example 1. Formally, a key component K of a database D is redundant (w.r.t. q) if for each fragment F of D, F j= q implies F n K j= q. In practice, a key component is redundant independently from the fact that some other key component is redundant or not. More formally, given a database D and a set C of redundant components of D, it holds that D j= q i D n SK2C K j= q. Therefore, if we can identify all the redundant components of D, then after removing from D all these components, what remains is either: (1) a nonempty set of (minimal) bunches, each of which entails consistently q whenever D j= q; or (2) the empty set, whenever D 6j= q. More formally: given a database D, each key component of D is redundant i D 6j= q.
However, assuming that ptime 6= np, any algorithm for the identi cation of all the redundant components of D cannot be polynomial because, otherwise, we would have a polynomial procedure for solving the original problem. Our goal is therefore to identify su cient conditions to design a pruning mechanism that detects in polynomial time as many redundant con icting components as possible. To give an intuition of our pruning mechanism, we look again at Example 1. Actually, K3 is redundant because it contains an atom, namely r2(5; 2), that is not involved in any substitution (see Figure 1). Assume now that this is the criterion that we use to identify redundant components. Since we know that D j= q i D n K3 j= q, this means that we can now forget about D and consider only D0 = K1 [ K2. But once we focus on sub(q; D0), we realize that it contains only 1 and 2. Then, a smaller number of substitutions in sub(q; D0) w.r.t. those in sub(q; D) motivates us to reapply our criterion. Indeed, there could also be some atom in D0 not involved in any of the substitutions of sub(q; D0). This is not the case in our example since the atoms in D0 are covered by 1(q) or 2(q). However, in general, in one or more steps, we can identify more and more redundant components. We can now state the main result of this section. Theorem 3. Consider some con ict-join hypergraph HD = hD; Ei, and a key component K of D. If K n Se2Eq e 6= ;, then K is redundant.
As discussed just before Theorem 3, an indirect e ect of removing a redundant component K from D is that all the substitutions in the set S = f 2 sub(q; D) : (q) \ K 6= ;g can be in a sense ignored. In fact, sub(q; D n K) = sub(q; D) n S. Whenever a substitution can be safely ignored, we say that it is unfounded. Let us formalize this new notion. Consider a database D. A substitution of sub(q; D) is unfounded if: for each fragment F of D, F j= q implies that, for each repair R 2 rep(F; ), there exists a substitution 0 2 sub(q; R) di erent from such that 0(q) R. We now show how to detect as many unfounded substitutions as possible.
Theorem 4. Consider a database D, and some 2 sub(q; D). If there exists a redundant component K of D such that (q) \ K 6= ;, then is unfounded.
Clearly, Theorem 4 alone is not helpful since it relies on the identi cation of redundant components. However, if combined with Theorem 3, it forms the desired cascade pruning mechanism. For example, both substitutions 3 and 4 in Example 1 are unfounded, since K3 is redundant. 4
Benchmark Setup. The assessment of our approach was done using a benchmark
employed in [
The scalability of Pruning is studied in detail for each query in Figures 2(df), each plotting the average execution times per group of queries of the same theoretical complexity. It is worth noting that Pruning scales almost linearly in all queries, and independently from the complexity class of the query. This is because Pruning can identify and deal e ciently with the con icting fragments.
We now analyze the performance of Pruning from the perspective of a
measure called overhead, which was employed in [
Database size 0 1 2 3 4 5 6 7 8 9 10
Database size 0 1 2 3 4 5 6 7 8 9 10
Database size
(a) Overhead (co-NP)
(b) Overhead (P)
(c) Overhead (FO)
(d) Scalability (co-NP)
(e) Scalability (P)
(f) Scalability (FO)
is time needed for computing the consistent answer of Q, and tplain is the time
needed for a plain execution of Q where the violation of integrity constraints are
ignored. Note that the overhead measure is independent of the hardware and the
software employed, since it relates the computation of CQA to the execution of a
plain query on the same system. Thus it allows for a direct comparison of Pruning
with other methods having known overheads. Following what was done in [
Logic programming approaches to CQA were recently considered not
competitive [