On the Decidability of Consistent Query Answering Marcelo Arenas1,⋆ and Leopoldo Bertossi2,⋆⋆ 1 Pontificia Universidad Católica de Chile, Department of Computer Science, Santiago, Chile. Email: marenas@ing.puc.cl 2 Carleton University, School of Computer Science, Ottawa, Canada. Email: bertossi@scs.carleton.ca Abstract. Consistent query answering (CQA) is about formally char- acterizing 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 answer- ing 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. 1 Introduction Consistent query answering (CQA) is about formally characterizing and com- puting 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 se- mantics 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 r D′ ) ∪ (D′ r 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, ⋆ M. Arenas was supported by FONDECYT grant 1090565. ⋆⋆ Faculty Fellow of the IBM Center for Advanced Studies. Also affiliated to the Uni- versity of Concepcion, Chile. 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 frame- work there considers a combination of key constraints (KCs) and inclusion de- pendencies (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 con- sistent 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 answer- ing 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 prob- lem 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. 2 Preliminaries 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 =, 6=, <, 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. Definition 1. A database instance D is consistent with respect to IC if D satisfies IC , denoted by D  IC; and inconsistent, otherwise. 2 Definition 2 ([3]). (a) The distance ∆(D1 , D2 ) between database instances D1 , D2 is the symmetric difference (D1 r D2 ) ∪ (D2 r D1 ). (b) For a fixed instance D and instances D′ , D′′ : D′ ≤D D′′ iff ∆(D, D′ ) ⊆ ∆(D, D′′ ). (c) For a given database instances D, we say that an instance D′ is a repair of D wrt IC iff D′  IC and D′ is ≤D -minimal in the class of database instances that satisfy IC . 2 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̄. Definition 3 ([3]). 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 D |=IC Q[t̄], if for every repair D′ of D wrt IC , D′  Q[t̄]. If Q is Boolean, then yes is the consistent answer if for every repair D′ of D, D′  Q; otherwise the consistent answer is no. 2 3 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. Definition 4. (a) For a Boolean query Q and a consistent set IC of integrity constraints: d -CQA(Q, IC ) := {D | D is a database instance and D |=IC Q}. (b) For a database instance D and a Boolean query Q: ic-CQA(D, Q) := {IC | IC is a consistent set of ICs and D |=IC Q}. (b) For a database instance D and a consistent set IC of integrity constraints: q-CQA(D, IC ) := {Q | Q is a Boolean query and D |=IC Q}. 2 Problem d -CQA(Q, IC ) 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, 27, 18, 8, 21, 28, 2, 23]. We may consider combined versions of the CQA decision problem. For ex- ample, for a given Boolean query Q: {d, ic}-CQA(Q) := {(D, IC ) | D is a database instance, IC is a set of ICs and D |=IC Q}, (1) and, more generally, {d, q, ic}-CQA := {(D, Q, IC ) | D is a database instance, Q is a Boolean query, IC is a set of ICs and D |=IC Q}. (2) 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 Π2P for the time complexity of d-CQA(Q, IC ) [14]. This is also a lower bound since CQA can be Π2P -complete in data [12]. 4 Undecidability of CQA 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 ∅. Further- more, consider the Boolean query Q : ¬P (a); and the problem SAT := {ψ ∈ L({E}) | ψ is satisfiable}. This problem is undecidable over finite graphs [16, sec. 7.2.1], and can be reduced to the complement of ic-CQA(D, Q) as follows: Given a first-order sentence ψ ∈ L({E}), define a set of integrity constraints IC by {ψ ↔ ∃xP (x)}. It is easy to check that ψ ∈ SAT iff D 6|=IC Q. 2 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 com- plexity 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: ∃xP (x), ∀u∀v(E(u, v) ↔ ∃yF (u, v, y)), ∀x∀y(P (x) ∧ y ≤ x → ∃u∃vF (u, v, y)). 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 ¬ψ 6∈ 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 t̄1 , . . ., t̄m be the tuples in the interpretation of E in D′ , and assume that a1 , . . ., am are the first m elements of U according to linear order ≤. Then the interpretations of P and F in D⋆ are {am } and {(t̄i , ai ) | 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 6|=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 in- tegrity 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 dy- namics of the machine, and the database instance will contain the transition function δ of the machine. Repairing the instance wrt the dynamics of the ma- chine corresponds to making the machine compute. The initial and final states are q0 , qf , 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 6= 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 a0 is the first element of U according to linear order <. Then IC contains the following sentences: (a) Head (a0 , a0 ) and State(a0 , q0 ). (b) ∀p(¬Conf 0 (a0 , p) ∧ ¬Conf 1 (a0 , 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 6= B and a′ 6= B:  ∀t∀t′ ∀q∀q ′ ∀p∀p′ State(t, q) ∧ Head (t, p) ∧ Conf a (t, p) ∧ δa,a′ ,L (q, q ′ ) ∧ Succ(t, t′ ) ∧ Succ(p′ , p) →  Conf a′ (t′ , p) ∧ Head (t′ , p′ ) ∧ State(t′ , q ′ ) . 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:  ′ ′ ′ ∀t∀t ∀q∀q ∀p∀p State(t, q) ∧ Head (t, p) ∧ ¬Conf 0 (t, p) ∧ ¬Conf 1 (t, p) ∧ δB,a′ ,L (q, q ′ ) ∧ Succ(t, t′ ) ∧ Succ(p′ , p) →  ′ ′ ′ ′ ′ Conf a′ (t , p) ∧ Head (t , p ) ∧ State(t , q ) . Similar formulas are obtained when a′ = B. (d) For every a 6= B: ∀t∀t′ ∀p∀p′ (Head (t, p) ∧ p 6= p′ ∧ Succ(t, t′ ) → (Conf a (t, p′ ) ↔ Conf a (t′ , p′ ))). The query Q is ¬∃t State(t, qf ). All these elements determine a particular deci- sion 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 qf iff D(M ) 6|=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 )′ 6|= Q. Thus, D(M ) 6|=IC Q. (⇐) Assume M does not halt at state qf . 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 qf , 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 qf . 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 availabil- ity 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 con- tain “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} r X. 2 5 Combined Decidability and Complexity of CQA 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 m _ n _ ∀( Pi (x̄i ) ∨ ¬Qj (ȳj ) ∨ ψ), (3) i=1 j=1 where ∀ represents the universal closure of the formula, x̄i , ȳj are tuples of variables, the Pi , Qj are database predicates, and ψ is a formula that mentions only the built-in predicates. (b) Each variable in an x̄i or ψ in (3) appears in some ȳj . 2 The second condition is the safety condition that guarantees domain indepen- dence [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: n ^ m ^ V (ȳ1 , . . . , ȳn ) :- Qj (ȳj ) ∧ ¬ψ ∧ ¬Pi (x̄i ). j=1 i=1 Repairs are obtained by deleting Qj -ground tuples and/or inserting Pi -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 com- putation 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. Theorem 3. (a) For every Boolean query Q, CQA(Q) := {(D, ϕ) | ϕ is a safe universal IC and D |={ϕ} Q} is in co-2-NEXP. (b) There are Boolean queries for which the same problem is co-NEXP-hard. 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, ϕ) 6∈ 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′ 6|= Q (which implies that D 6|={ϕ} 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′ 6|= 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]. 3 Other cases of combined complexity for CQA around key constraints and inclusion dependencies can be found in [11]. Consider a schema S, and let χ: ∃x1 · · · ∃xn ∀ȳ ψ(x1 , . . . , xn , ȳ) ∈ 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 a1 , . . ., an be pairwise distinct elements from U , which are all distinct from a, U1 , . . ., Un be unary predicates not contained in S ∪ {P }, and D be the empty database instance over S ∪ {U1 , . . . , Un , P }. Furthermore, let ϕ be the conjunction of: n ^   ∀x∀y Ui (x) ∧ Ui (y) → x = y , (4) i=1 ^n _n Ui (aj ), (5) i=1 j=1   ∀x1 · · · ∀xn U1 (x1 ) ∧ · · · ∧ Un (xn ) → ∀ȳ ψ(x1 , . . . , xn , ȳ) ∨ P (a). (6) The first two sentences make sure that each Ui contains exactly one element of U . If χ is satisfiable, then there will be a repair where each of the U1 , ..., Un 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 6|={ϕ} P (a). On the other hand, if χ is not satisfiable, then no matter how U1 , . . ., Un and the relations in S are populated, sentence   ∀x1 · · · ∀xn U1 (x1 ) ∧ · · · ∧ Un (xn ) → ∀ȳ ψ(x1 , . . . , xn , ȳ) 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 6|={ϕ} 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 quantifi- cation on x1 , ..., xn and their occurrence in the predicates U1 , ..., Un , 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).4 2 4 In particular, due to the bounded domain to be tiled, for each instance we do not need to go beyond a finite numerical domain U . The same would happen if we were encoding computations of Turing machines that are bounded in time. References [1] Abiteboul, S., Hull, R. and Vianu, V. Foundations of Databases. Addison-Wesley, 1995. [2] Afrati, F. and Kolaitis, Ph. Repair Checking in Inconsistent Databases: Algo- rithms and Complexity. Proc. of the International Conference on Database Theory (ICDT 09), 2009, pp. 31-41. [3] Arenas, M., Bertossi, L. and Chomicki, J. Consistent Query Answers in Incon- sistent Databases. Proc. ACM Symposium on Principles of Database Systems (PODS 99), 1999, pp. 68-79. [4] Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V. and Spinrad, J. Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science, 2003, 296(3): 405-434. [5] Arenas, M., Bertossi, L. and Chomicki, L. Answer Sets for Consistent Query Answering in Inconsistent Databases. Theory and Practice of Logic Programming, 2003, 3(4-5):393-424. [6] Barcelo, P., Bertossi, L. and Bravo, L. Characterizing and Computing Semanti- cally Correct Answers from Databases with Annotated Logic and Answer Sets. Chapter in Semantics of Databases, Springer LNCS 2582, 2003, pp. 1-27. [7] Bertossi, L. Consistent Query Answering in Databases. In ACM Sigmod Record, 2006, 35(2):68-76. [8] Bertossi, L., Bravo,L., Franconi, E. and Lopatenko, A. The Complexity and Ap- proximation of Fixing Numerical Attributes in Databases Under Integrity Con- straints. Information Systems, 2008, 33(4):407-434. [9] Börger, E., Grädel, E. and Gurevich, Y. The Classical Decision Problem. Springer, 1997. [10] Bravo, L. and Bertossi, L. Semantically Correct Query Answers in the Pres- ence of Null Values. Proc. EDBT International Workshop on Inconsistency and Incompleteness in Databases (IIDB 06). Springer LNCS 4254, 2006, pp. 336-357. [11] Cali, A., Lembo, D. and Rosati, R. On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases. Proc. ACM Symposium on Principles of Database Systems (PODS 03), 2003, pp. 260-271. [12] Chomicki, J. and Marcinkowski, J. Minimal-Change Integrity Maintenance Using Tuple Deletions. Information and Computation, 2005, 197(1-2):90-121. [13] Chomicki, J. Consistent Query Answering: Five Easy Pieces. Proc. International Conference on Database Theory (ICDT 07), Springer LNCS 4353, 2007, pp. 1-17. [14] Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. Complexity And Expressive Power Of Logic Programming. ACM Computer Surveys, 2001, 33(3):374-425. [15] Eiter, T., Gottlob, G. and Mannila, H. Disjunctive Datalog. ACM Transactions on Database Systems, 1997, 22(3):364-418. [16] Ebbinghaus, H.-D. and Flum, J. Finite Model Theory. 2nd edition, Springer, 1999. [17] Fagin, R. Horn Clauses and Database Dependencies. Journal of the ACM, 1982, 29(4):952–985. [18] Fuxman, A. and Miller, R. First-Order Query Rewriting for Inconsistent Databases. Journal of Computer and System Sciences, 2007, 73(4):610-635. [19] Gelfond, M. and Lifschitz, V. Classical Negation in Logic Programs and Disjunc- tive Databases. New Generation Computing, 1991, 9:365-385. [20] Greco, G., Greco, S. and Zumpano, E. A Logical Framework for Querying and Repairing Inconsistent Databases. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6):1389-1408. [21] Lopatenko, A. and Bertossi, L. Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics. Proceed- ings of the International Conference of Database Theory (ICDT 07), Springer LNCS 4353, 2007, pp. 179-193. [22] Papadimitriou, Ch. Computational Complexity. Addison-Wesley, 1994. [23] Staworko, S. and Chomicki, J. Consistent Query Answering in the Presence of Universal Constraints. Information Systems, 2010, 35(1):1-22. [24] Ullman, J. Principles of Database and Knowledge-Base Systems, Vol. I. Computer Science Press, 1988. [25] Van Gelder, A. and Topor, R. Safety and Correct Translation of Relational Calculus Formulas. Proceedings of the Sixth ACM Symposium on Principles of Database Systems (PODS 87). ACM Press, 1987, pp. 313-327. [26] Vardi, M. The Complexity of Relational Query Languages. Proc. ACM Symposium on Theory of Computing (STOC 82), 1982, pp. 137-146. [27] Wijsen, J. Database Repairing Using Updates. ACM Transactions on Database Systems, 2005, 30(3):722-768. [28] Wijsen, J. On the Consistent Rewriting of Conjunctive Queries Under Primary Key Constraints. Information Systems, 2009, 34(7):578-601.