Consistent query answering (CQA) is about formally characterizing and computing semantically correct answers to queries posed to a database that may fail to satisfy certain integrity constraints. In this paper, we revisit the decidability status of consistent query answering by considering different parameters of the problem as input to the decision problem. More specifically, we obtain some new results about the undecidability and combined complexity of CQA.
Consistent query answering (CQA) is about formally characterizing and computing semantically correct answers to queries posed to a database that may fail to satisfy certain integrity constraints (ICs). This problem was brought into the main stream research on foundations of databases by [3]. Informally, a consistent answer to a query Q posed to a relational database instance D that may not satisfy a set IC of integrity constraints is as a usual answer to Q that can be obtained from every minimal repair of D. A minimal repair D ′ of D satisfies IC and minimally departs from D (after enforcing the ICs). Different repair semantics can be obtained by playing with different notions of distance between database instances. In this paper, we stick to the original distance introduced and studied in [3]: A repair of D makes minimal under set inclusion the set of tuples in (D D ′ ) ∪ (D ′ D), i.e., the symmetric set difference. In particular, this assumes that IC violations are solved by insertions or deletions of whole database tuples. For recent surveys of CQA we refer to [7,13].
The complexity of CQA problem, i.e., of deciding if a tuple is a consistent answer to a query under a given set of ICs, has been investigated in several papers and under several repairs semantics [11,12,27,18,8,21,28,2,23]. As expected most all the complexity results have been about data complexity, i.e., in terms of the size of the original instance D. Few results have been presented on combined complexity, where other parameters are also taken into account, e.g. size of the query or of the set of ICs. There are also few results about undecidability of CQA. Exceptions in this direction are [11,8]; and both refer to a form of combined undecidability, i.e., without a fixed query and a fixed set of ICs. We do not elaborate more on [8], because the repair semantics is different from the one investigated in this paper. Furthermore, the results in [8] heavily rely on having denial constraints that involve numerical attributes.
However, some results in [11] are highly relevant in our context. The framework there considers a combination of key constraints (KCs) and inclusion dependencies (IDs). In case of inconsistency, KCs are repaired via tuple deletions; but IDs are repaired only by insertion of tuples. If the original instance is consistent wrt the KCs, then inconsistencies are solved by insertion of whole tuples, which can happen in possibly many different ways, and only constrained by the KCs. The new tuples can take values in the database domain associated to the schema. In this case, the repairs minimize the set of inserted tuples wrt set inclusion.
It is proved in [11] that CQA is undecidable. This result is obtained by reduction from the problem of deciding entailment of dependencies from a set of functional dependencies (FDs) and inclusion dependencies: F ∪ I |= δ? Here, F and I are sets of FDs and IDs, respectively, and δ is a dependency. This problem is undecidable [1, theorem 9.2.4]. A careful examination of the proof in [11, theorems 3.2, 3.4], shows that the reduction in it requires, in essence, generating for the combination of F , I and δ an ad hoc combination of KCs, IDs, a query and a database instance. In consequence, the undecidability result involves as input to the problem all the three natural parameters of CQA, namely the ICs, the query and the instance. The set I is actually a cyclic set of IDs.
In this paper, we revisit the decidability status of consistent query answering by considering different parameters of the problem as input to the decision problem. We obtain some new results about the undecidability and combined complexity of CQA. More specifically, we prove that CQA is undecidable for all the combinations of the possible inputs (instance, ICs, query) to the problem depending upon the parameters that are left fixed. We also establish the decidability of CQA for a broad class of universal ICs, with the combination of instance, ICs, and query as the input. Furthermore, we study the combined complexity on data and ICs (fixed query) for this class of dependencies.
If we start from a database schema S, including a countably infinite database domain U , we may consider the first-order language L(S) based on the predicates in S and the constants for the elements of U . Database instances for schema S are Herbrand structures with domain U and finite extensions for the interpretations of the predicates in S. In consequence, a database instance D can be identified with a set of ground atoms R( t), with R ∈ S and t a finite sequence of elements of U of the same length as the arity of R. The active domain of D, denoted by dom(D), is the finite set that contains all the elements of U that appear in D.
We also allow built-in predicates in L(S), like =, =, <, etc., that have fixed and predefined extensions in a database instance.
An integrity constraint (IC) over a database schema S is a first-order sentence in L(S). In particular, a universal IC is a sentence of the form ∀x ψ, where ψ does not contain any quantifiers. We use IC to denote a set of integrity constraints, and we assume that IC is consistent in the sense that there is some database instance that makes it true, but not necessarily by the one at hand. It is always the case that in CQA, and also in this paper, we consider database instances that may not satisfy the given set of ICs. Notice that the extensions of the built-in predicates do not contribute to ∆, because they have fixed extensions, identical in every database instance. Queries are formulas of L(S). If a query is a sentence, i.e., it has not free variables, it is called a Boolean query. We assume that queries and ICs satisfy the usual syntactic safety conditions [25] that make them domain independent [17,24]. This means that they can be evaluated or checked against the active domain of the database instance.
For a query Q(x), with free variables in x, and a database instance D, a tuple t of constants of U is an answer to Q in D iff D |= Q[ t], i.e., Q is true in D when the variables in x are replaced by the corresponding values in t.
). Given a set of integrity constraints, a (ground) tuple t is a consistent answer to a query Q(x) in a database instance D wrt a set of integrity constraints IC , denoted
The Decision Problem of CQA
The computational problem of retrieving consistent answers to a query from a possibly inconsistent database can be studied by concentrating on the decision problem of consistent query answering. Actually, this gives rise to several decision problems depending on which of the natural parameters involved are considered to be fixed and which are considered to be a part of the input. The most basic decision problems of CQA are the following. (b) For a database instance D and a consistent set IC of integrity constraints:
) is the problem of CQA in data, where the ICs and the query are fixed -the parameters of the problem-and the database is variable, i.e., the input. The data complexity [26] of CQA is precisely the complexity of this problem, for different classes of parameters IC, Q. As common in database research, this is the problem that has been investigated the most. This problem is decidable for all common classes of ICs and queries, and tight complexity bounds have been established [11, 12,
We may consider combined versions of the CQA decision problem. For example, for a given Boolean query Q:
IC is a set of ICs and D |= IC Q}, (1) and, more generally,
In what follows, when we refer to {d}-CQA(Q, IC ), we mean d-CQA(Q, IC ), as in Definition 4; the same for ic and q. The complexity of {d , q}-CQA(IC ) is usually called combined complexity of CQA (with fixed ICs). It is measured in terms of the size of both the database and the query. In the case of {q, ic, d}-CQA, the instance, the query and the set of ICs become part of the input. All this decision problems can also be stated for queries with free variables, say Q(x), and tuples t of constants in U , asking if t is a consistent answer. Since the schema has the constants in U , we may restrict ourselves to Boolean queries. As already indicated above, it holds: Proposition 1 ( [11]). {d, q, ic}-CQA is undecidable.
2
The proof of this proposition given in [11] uses key constraints and cyclic sets of referential integrity constraints (RICs) [1]. The existential quantifiers of the RICs are satisfied by picking up values from the underlying database domain U . We should mention that, in [10], {q, ic, d}-CQA was made decidable for this type of ICs by considering repairs based on introduction of null values as used in SQL databases. Those null values are used for the existential variables in the RICs. Actually, the decidability follows in [10] from the use of disjunctive Datalog programs with stable model semantics [19,15] to specify the repairs of the original instance wrt universal ICs and RICs, including those considered in [11]. These repair programs have been used before [5,20,6], and they provide an upper bound of Π P 2 for the time complexity of d-CQA(Q, IC ) [14]. This is also a lower bound since CQA can be Π P 2 -complete in data [12].
Now we turn to some of the other decision problems for CQA. Clearly, for Y ⊆ X ⊆ {d, ic, q}, if X-CQA is decidable, then also Y-CQA is decidable, but not necessarily the other way around. We first consider the problem of CQA in integrity constrains.
Proposition 2. There exist a database instance D and a Boolean query Q such that ic-CQA(D, Q) is undecidable.
Proof. Let S be a database schema that contains a binary predicate E and a unary predicate P . Consider the instance D of S whose extension for P is {P (a)}, where a is an element of U , and whose extension for E is ∅. Now we address the problem of CQA in queries, that is, when queries are the input of the problem. The complexity of this decision problem is the query complexity of CQA [26].
Proposition 3. There exists a database instance D and a consistent set IC of integrity constraints such that q-CQA(D, IC ) is undecidable.
Proof. Let S be a database schema containing a unary predicate P , a binary predicate E, a ternary predicate F and built-in predicate ≤ that is interpreted in such a way that (U, ≤) is isomorphic to (N, ≤). Then let D be the empty instance of S, and IC be a set consisting of the following integrity constraints:
Consider SAT := {ψ ∈ L({E}) | ψ is satisfiable}. As mentioned in the proof of Proposition 2, this problem is undecidable over finite graphs. Next we show that the restriction of SAT to finite graphs can be reduced to the complement of q-CQA(D, IC ). In fact, we prove that ψ ∈ SAT iff ¬ψ ∈ q-CQA(D, IC ). Assume that ψ ∈ SAT , and let D ′ be a database instance over {E} satisfying ψ. Define a database instance D ⋆ over S as follows. The interpretation of E in D ⋆ coincides with the interpretation of E in D ′ . Let t1 , . . ., tm be the tuples in the interpretation of E in D ′ , and assume that a 1 , . . ., a m are the first m elements of U according to linear order ≤. Then the interpretations of P and F in D ⋆ are {a m } and {( ti , a i ) | 1 ≤ i ≤ m}, respectively. It is straightforward to prove that D ⋆ |= IC . Furthermore, D ⋆ is a repair of D since no proper subset of D ⋆ satisfies IC . Thus, given that D ⋆ |= ψ, we conclude that D |= IC ¬ψ and, therefore, ¬ψ / ∈ q-CQA(D, IC ). The other implication is immediate, which concludes the proof of the proposition.
2
Finally, we also consider the case when integrity constraints and queries are considered to be fixed.
Proposition 4. There exist a Boolean query Q and a consistent set IC of integrity constraints such that d -CQA(Q, IC ) is undecidable.
Proof. We will reduce to the complement of our problem the halting problem for deterministic Turing machines with empty string on an infinite unidirectional tape with alphabet 0, 1, B (blank). The integrity constraints will codify the dynamics of the machine, and the database instance will contain the transition function δ of the machine. Repairing the instance wrt the dynamics of the machine corresponds to making the machine compute. The initial and final states are q 0 , q f , respectively. We need the following predicates:
1. Head (t, p): At time t the head is at position with number p of the tape. 2. State(t, q): At time t the state is q.
3. Conf a (t, p): At time t and position p the symbol read is a. Here, a = B; and a blank is represented by the absence of 0 or 1. 4. δ a,a ′ ,R (q, q ′ ): Being at state q, reading a causes, according to the transition function δ, to write a ′ , move to the right (R) and jump to state q ′ . There are similar predicates, L, for left. 5. Succ(n, n ′ ): For natural numbers n, n ′ , it holds that n ′ is the successor of n. This predicate can be defined using the built-in predicate <, and its definition can be part of IC . Thus, we also assume that the database schema contains a built-in predicate < that is interpreted in such a way that (U, <) is isomorphic to (N, <).
Assume that a 0 is the first element of U according to linear order <. Then IC contains the following sentences:
(a) Head (a 0 , a 0 ) and State(a 0 , q 0 ). (b) ∀p(¬Conf 0 (a 0 , p) ∧ ¬Conf 1 (a 0 , p)). This formula states that that we start with a blank tape. In general, we represent with ¬Conf 0 (t, p) ∧ ¬Conf 1 (t, p) the fact that at time t in position p there is a blank.
(c) For a = B and a ′ = B:
There is a similar sentence for δ a,a ′ ,R . If a is B, in the previous formula Conf a (t, p) is replaced by ¬Conf 0 (t, p) ∧ ¬Conf 1 (t, p), obtaining:
Similar formulas are obtained when a ′ = B. (d) For every a = B:
The query Q is ¬∃t State(t, q f ). All these elements determine a particular decision problem of the form q-CQA(IC , Q), parameterized by IC and Q. Now, we show that this problem is undecidable by reduction from the halting problem.
For a machine M , the database instance D(M ) corresponds to the transition function δ by means of the δ-predicates above and their contents. The other relations are empty. It holds that M halts at state q f iff D(M ) |= IC Q. In fact: (⇒) In this case, there is a repair D(M ) ′ corresponding to the finite computation of M , i.e., it contains all the configuration tuples that lead to the final state. For this repair, it holds that D(M ) ′ |= Q. Thus, D(M ) |= IC Q.
(⇐) Assume M does not halt at state q f . We have two cases: First, assume that M does not halt (at any state). The infinite computation does not generate a repair, because repairs have finite relations. In this case, repairs can be obtained by deletion of tuples from D(M ), and then they correspond to sub-function of the original δ. None of the computations related to such a repair can reach state q f , because they represent subcomputation of the original machine (the determinism of the machine is crucial here). In this case, all the repairs satisfy Q and, therefore D(M ) |= IC Q. In the second case, M halts at a state different from q f . A similar argument as in the previous case can be applied.
2
It is important to notice that the proof of Proposition 4 relies on the availability of a built-in linear order. Also, in this proof we use universal ICs except for the definition of the successor function. However, this definition, namely ∀m∀n(Succ(m, n) ↔ m < n ∧ ¬∃j(m < j ∧ j < n)), as an IC does not contain "repairable" predicates, i.e., database predicates. Thus, one could also rely on the availability of a built-in successor predicate to prove this proposition, avoiding the use of non-universal constraints. The propositions above have been established for the single input cases in Definition 4. However, several possible inputs can be combined, as in ( 1) and (2). From Propositions 2, 3 and 4, we obtain: Theorem 1 (Undecidability of consistent query answering). For every nonempty subset X of {d, q, ic}, there are cases where X-CQA is undecidable. The cases depend upon the parameters of the problem, i.e., on {d, q, ic} X. 2
In this section, we concentrate on a particular but common class of ICs. Definition 5. An integrity constraint is a safe universal IC if both:
(a) It is logically equivalent to a sentence of the form
where ∀ represents the universal closure of the formula, xi , ȳj are tuples of variables, the P i , Q j are database predicates, and ψ is a formula that mentions only the built-in predicates. (b) Each variable in an xi or ψ in (3) appears in some ȳj .
2
The second condition is the safety condition that guarantees domain independence [17,24]. It is easy to see that, according to this definition, the ICs in Proposition 4 are not safe, nor domain independent.
Theorem 2. For finite sets IC of safe universal ICs, and Boolean queries Q, the problem of CQA, i.e., {(D, Q, IC ) | D |= IC Q}, is decidable.
Proof. We may assume that the sentences in IC are in the clausal form (3). This representation for ICs allows us to determine all the repairs of a database that does not satisfy them: From the domain independence condition, the finitely many tuples that participate in a violation and whose modification may lead to a restoration of the consistency of the database, can be obtained by posing to D, for each IC (3), the domain independent query about the set of violating tuples:
Repairs are obtained by deleting Q j -ground tuples and/or inserting P i -ground tuples. In this way, the finitely many repairs can be computed. Then, the query Q can be evaluated in every single repair. If for all of them it becomes true, the answer is yes, otherwise, is no. 2
Notice that the decision algorithm in the proof of Theorem 2 requires the computation all of possible repairs; and we know that there may be exponentially many of them in the size of the database [4]. This decidability result extends similar implicit results [5,20,6,10] that guarantee decidability for certain syntactic classes of universal ICs. Their syntax makes them safe, and then, also domain independent. This is obtained from the representation of repairs as stable models of disjunctive logic programs. A direct proof of decidability of {d, ic, q}-CQA for this class of universal constraints plus RICs can be found in [10] (existential variables are satisfied with an SQL null). Decidability of {d, ic, q}-CQA is proved in [11] for sets of non-conflicting key constrains and inclusion dependencies.
In the following, we study a form of combined complexity of CQA, where the input consists of the database and the ICs. 3 This is a special case of the general {d, ic}-CQA problem in (1) where only universal, domain independent ICs are considered in the input. Proof. (a) We prove that the complement of CQA(Q) belongs to 2-NEXP, that is, we prove that there exists a non-deterministic Turing machine M that works in double exponential time and accepts the complement of CQA(Q). Let D be a database instance and ϕ a safe universal IC. In order to verify whether (D, ϕ) ∈ CQA(Q), Turing machine M first transforms ϕ into an equivalent IC ψ of the form (3), then it guesses a repair D ′ of D wrt ψ, and finally it checks whether D ′ |= Q (which implies that D |= {ϕ} Q). Sentence ψ can be of exponential size in the size of ϕ, and it takes exponential time to generate this formula. Checking that D ′ is a repair of D can be done in exponential time in the size of ψ and D, because it might be necessary to compare D ′ for inclusion with exponentially many candidates (see the proof of Theorem 2). Finally, verifying that D ′ |= Q can be done in polynomial time in the size of D ′ since Q is assumed to be a fixed query. Thus, we conclude that M works in double exponential time in the size of ϕ and D.
(b) Let P be a unary predicate and a ∈ U . Next we prove that the complement of CQA(Q) is NEXP -hard, where Q is the Boolean query P (a). More precisely, next we provide a reduction from SAT for the Bernays-Schoenfinkel's syntactic class of first-order formulas (BSC ) to the complement of CQA(Q). The former problem is decidable and NEXP -complete [22, chapter 20].
Consider a schema S, and let χ: ∃x 1 • • • ∃x n ∀ȳ ψ(x 1 , . . . , x n , ȳ) ∈ L(S), with ψ quantifier free, be an instance for BSC . Without loss of generality, assume that S does not contain unary predicate P . If χ is satisfiable, then it is satisfiable in the universe U = {1, . . . , n}. In consequence, a sentence in BSC is satisfiable iff it is satisfiable in a finite structure (actually with finite universe), which allows us to use this result in our context.
Let a 1 , . . ., a n be pairwise distinct elements from U , which are all distinct from a, U 1 , . . ., U n be unary predicates not contained in S ∪ {P }, and D be the empty database instance over S ∪ {U 1 , . . . , U n , P }. Furthermore, let ϕ be the conjunction of: U i (a j ), ( 5)
The first two sentences make sure that each U i contains exactly one element of U . If χ is satisfiable, then there will be a repair where each of the U 1 , ..., U n will contain exactly one element of U and nothing else, and P will be empty. In that repair, the query P (a) will be false and, thus, D |= {ϕ} P (a). On the other hand, if χ is not satisfiable, then no matter how U 1 , . . ., U n and the relations in S are populated, sentence
x n ) → ∀ȳ ψ(x 1 , . . . , x n , ȳ)
will not be satisfied. Therefore, all the repairs of D will include element a into P in order to satisfy (6), which implies that D |= {ϕ} P (a). Hence, we conclude that χ is satisfiable iff D |= {ϕ} P (a). The IC ϕ is clearly universal, but we have to check safety. The first two conjuncts obviously are. For the third conjunct, due to the universal quantification on x 1 , ..., x n and their occurrence in the predicates U 1 , ..., U n , the only source of non-safety could be formula ψ. There is no reason for ψ to be safe. However, for the purpose of establishing our complexity lower-bound, we may restrict ourselves to a subclass of sentences in BSC that still is NEXP -hard, namely sentences that encode bounded tiling problems. Those sentences turn out to be safe (cf. [9, theorem 6.2.21] for details). 42
⋆ M. Arenas was supported by FONDECYT grant 1090565. ⋆⋆ Faculty Fellow of the IBM Center for Advanced Studies. Also affiliated to the University of Concepcion, Chile.