Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases

Abstract

Consistent answers to a query from a possibly inconsistent database are answers that are simultaneously retrieved from every possible repair of the database. Repairs are consistent instances that minimally differ from the original inconsistent instance. It has been shown before that database repairs can be specified as the stable models of a disjunctive logic program. We show how to use the repair programs to transform the problem of consistent query answering into a problem of reasoning w.r.t. a theory written in second-order predicate logic. We show how a first-order theory can be obtained instead by applying second-order quantifier elimination techniques.

Introduction

Integrity constraints (ICs) on databases are expected to be satisfied by the instances of the given schema S . If an instance does not satisfy the ICs, it is said to be inconsistent, and becomes only partially semantically correct. Consistent query answering (CQA) attempts to characterize and compute answers to a query that are consistent with respect to (w.r.t.) a given set of ICs [ 5, 8, 15, 11 ]. Informally, a tuple of constants t¯ is a consistent answer from an instance D to a query Q(x¯) w.r.t. a set of ICs IC if t¯ can be obtained as a usual answer to Q from every repair of D. Here, a repair is a consistent instance for the schema S that differs from D by a minimal set of database atoms under set inclusion [ 5 ].

It has been shown [ 6, 13 ] that repairs can be specified as the stable models of a disjunctive logic program [ 22 ] Π , by a so-called repair program. In this way, CQA becomes a problem of reasoning with program Π . Logic programs with stable model semantics are also called answer-set programs [ 22 ], and their stable models are also called answer sets. Answer-set programming has become a powerful paradigm and tool for the specification and solution of hard combinatorial problems [ 12 ].

Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

Ideally, consistent answers to a query Q from a database instance D should be obtained by posing a new query Q0 to D, as an ordinary query that is, hopefully, easy to evaluate against D. This is the case, for example, when Q0 is a query expressed in the first-order (FO) languageL(S). Some classes of queries and ICs with this property have been already identified [ 5, 14, 21 ]; and many more by Wijsen in a series of papers on conjunctive queries and key constraints [ 1 ]. C.f. [ 36 ] and [ 37 ] for excellent surveys, and [ 23 ] for more recent results and references.

The main result for CQA for conjunctive queries (CQs) under key constraints (KCs), tells us that one can syntactically classify and decide CQs in terms of their data complexity for CQA.1 A trichotomy appears: a CQ can be FO-rewritable, or in PTIME (L-complete), or coNP-complete. There are queries for these three classes. For the first class, the rewriting can be computed, in which case, it is possible to compute the consistent answers in polynomial time. It is worth emphasizing that there are CQs for which CQA can be done in polynomial time, but provably not via FO-rewriting [ 35, 34 ]. This opens the question about the right logical language for a rewriting, if any.

At the other extreme, repair programs provide a general mechanism for computing consistent answers. Actually, the data complexity of CQA can be as high as the data complexity of cautious query evaluation from disjunctive logic programs under the stable model semantics, namely Π2P -complete [ 16, 14 ]. Apart from providing the right expressive power and complexity for dealing with repairs and CQA, the semantics of answer-set programming is a non-monotonic, non-classical logical semantics, which is particularly suitable for applications in databases, through the implicit use of the closed-world assumption [ 32 ], and the minimality of models under set inclusion. This last feature is useful in relation to the minimality of database repairs.

In those cases where a FO rewriting for CQA is possible, one can transform the problem of CQA into one of reasoning in classical predicate logic, because the original database can be “logically reconstructed” as a FO theory [ 32 ]. In this work we investigate how repair programs can be used to generate a theory written in classical logic from which CQA can be captured as logical entailment. This theory can be written in second-order or first-order predicate logic. We start by trying to achieve the former, by providing specifications of database repairs in second-order (SO) predicate logic. They are obtained by applying recent results on the specification in SO logic of the stable models of a logic program [ 19, 20 ] -in our case, a repair program- and older results on their characterization as the models of a circumscriptive theory [ 29 ] for the case of disjunctive stratified programs [ 30, 31 ]. This circumscription can be specified in SO predicate logic [ 25, 33 ].

In order to achieve a FO specification, for some cases related to queries and KCs, we apply techniques for SO quantifier elimination that have been introduced in [ 17 ]. In this way it is possible to obtain a FO specification of the database repairs. This transforms CQA into a problem of logical reasoning in FO logic. We illustrate by means of an example how to obtain a FO rewriting for CQA under a KC. We illustrate the SO quantifier elimination technique. Generalizing the methodology to more general cases is left for future investigation. C.f. Section 5), where we also discuss the possibility 1 As usual in databases, all the complexity results in this paper are about data complexity, i.e. in terms of the size of the database instance. of obtaining rewritings in fixed-point logic, when it is provably the case that no FO rewriting exists. This paper is an excerpt from [ 9 ]. In [ 10 ] one can find an extended and updated version of both the latter and this paper, containing all the details and much more. 2

Database Repairs and Repair Programs

Consider a database instance D and a set of integrity constraints (ICs), that is a set Σ of sentences in the first-order language of predicate logic associated to the database schema. The database may not satisfy Σ in which case we say that D is inconsistent. The database can be repaired by inserting or deleting full tuples into/from D, in such a way that the resulting instance becomes consistent. A (minimal) repair of D is an instance D0 that satisfiesΣ and minimally differs from D under set inclusion, i.e. DΔD0, the symmetric set difference, is minimal under set inclusion [ 5, 11 ]. For monotone ICs (they are never violated by tuple deletions), like the ones we will consider below, the repairs are always maximal-subsets (subinstances) of D. The repairs of an inconsistent database can be specified by means of answer-set programs (c.f. [ 11 ] for details and references). Those are the repair programs.

Repair programs use annotation constants in an extra argument for each of the database predicates. More precisely, for each n-ary P ∈ S, we make a copy P , which is (n + 1)-ary [ 13 ]. Here, we need only the following annotations, with its intended semantics: (a) f in atoms P (a¯, f ), meaning “made false (deleted)”, (b) t?? in atoms P (a¯, t??), meaning “true in repair”.

Example 1. The relational schema S contains predicate P (X, Y ), and the functional dependency (FD) X → Y , actually a KC, stating that the first attribute functionally determines the second. It can be expressed as the first-order (FO) sentence

FD : ∀x∀y∀z(P (x, y) ∧ P (x, z) → y = z).

The database instance D = {P (a, b), P (a, c), P (d, e)} is inconsistent since the first two tuples jointly violate the FD. We have two repairs: D1 = {P (a, b), P (d, e)} and D2 = {P (a, c), P (d, e)}. The query Q1(y) : ∃xP (x, y) has the consistent answer (e), whereas the query Q2(x) : ∃yP (x, y) has (a), (d) as consistent answers. They are standard answers from both repairs. These repairs can be specified as the stable models of the following repair program Π(D, FD ): 1. Original database facts: P (a, b), P (a, c), P (d, e). 2. The repair rule: P (x, y, f ) ∨ P (x, z, f ) ← P (x, y), P (x, z), y 6= z.

It specifies that whenever the FD is violated, as captured by the rule body (the RHS), then one (and only one if possible) of the two tuples involved in the violation has to be made false (deleted), as captured by the disjunctive rule head (LHS). 3. Annotations constant t?? is used to read off the atoms in a repair, saying that whichever atom was in the original instance and not deleted stays in the repair:

P (x¯, t??) ← P (x¯), not P (x¯, f ).

For simplicity, and from now on, we use new predicates Pf ( , ) for P ( , , f ), P??( , ) for P ( , , t??). The repairs are in one-to-one correspondence with the restriction of the stable models to the predicates of the form P?? [ 13 ]. In this example, they are: D1 = {P??(a, b), P??(d, e)} and D2 = {P??(a, c), P??(d, e)}.

In order to obtain the consistent answers to a FO query Q, a query program ΠQ, containing a query-answer predicate AnsQ, is combined with the repair program Π(D, FD ). Next, as is common with ASPs, we can use the cautious entailment semantics from ASP, denoted |=cs , which means that the right-hand side is true in all the stable models of the program on the left-hand side.

The extension of the answer predicate AnsQ in the intersection of all stable models of Π := Π(D, FD ) ∪ ΠQ contains exactly the consistent answers. That is, a¯ is a consistent answer to Q, denoted, D |=c Q(a¯), iff Π(D, FD ) ∪ ΠQ |=cs AnsQ(a¯). In general, ΠQ will be a (stratified) non-recursive and normal Datalognot query ΠQ with answer predicate AnsQ(x¯) appearing only in rule heads [ 1, 27 ].

Example 2. (ex. 1 cont.) A possible query is Q(x, y) : P (x, y), which can be represented by the simple query program ΠQ: Ans(x, y) ← P??(x, y). This program is combined with 1.-3. above, and the consistent answers to Q are those tuples a¯, such that ΠQ ∪ Π(D, FD ) |=cs Ans(a¯), obtaining the only consistent answer is (d, e). 3

Second-Order Specification of Repairs

In [ 19, 20 ], the stable model semantics of logic programs introduced in [ 22 ] is reobtained via an explicit specification in classical SO predicate logic that is based on circumscription. First, the program Π is transformed into (or seen as) a FO sentence ψ(Π). Next, the latter is transformed into a SO sentence Φ(Π). Here, ψ(Π) is obtained from Π as follows: (a) Replace every comma by ∧, and every not by ¬. (b) Turn every rule Head ← Body into the formula Body → Head . (c) Form the conjunction of the universal closures of those formulas.

Now, given a FO sentence ψ (e.g. the ψ(Π) above), a SO sentence Φ is defined as ψ ∧ ¬∃X¯ ((X¯ < P¯) ∧ ψ◦(X¯ )), where P¯ is the list of all predicates P1, ..., Pn in ψ that are going to be circumscribed,2 and X¯ is a list of distinct predicate variables XP1 , ..., XPn , with Pi and XPi of the same arity. Here, (X¯ < P¯) means (X¯ ≤ P¯) ∧ (X¯ 6= P¯), i.e. Vin ∀x¯(XPi (x¯) → Pi(x¯)) ∧ Win(XPi 6= Pi). XPi 6= Pi stands for ∃x¯i(Pi(x¯i) ∧ ¬XPi (x¯i)).

ψ◦(X¯ ) is defined recursively as follows: (a)Pi(t1, ..., tm)◦ := XPi (t1, ..., tm). (b) (t1 = t2)◦ := (t1 = t2). (c) ⊥◦:=⊥. (d) (F G)◦ := (F ◦ G◦) for ∈ {∧, ∨}. (e) (F → G)◦ := (F ◦ → G◦) ∧ (F → G). (f) (QxF )◦ := QxF ◦ for Q ∈ {∀, ∃}. Notice that we assume there is no explicit logical negation in formulas. Instead, a formula of the form ¬χ is assumed to be represented as (χ → ⊥), with ⊥ standing for an always false propositional formula.

The Herbrand models of the SO sentence Φ(Π) associated to ψ(Π) correspond to the stable models of the original program Π [ 19 ]. We can see that Φ(Π) is similar to a parallel circumscription of the predicates in program Π w.r.t. the FO sentence ψ(Π) 2 In circumscription, some predicate may be minimized, others may stay flexible (or variable) to accommodate to the minimization of others, and some may stay fixed [ 25 ]. associated to Π [ 29, 26 ]. In principle, the transformation rule (e) above could make formula Φ(Π) differ from a circumscription.

Now, let D be a relational database, Πr the repair program without the database facts. From now on Π = D ∪ Πr ∪ ΠQ. Πr depends only on the integrity constraints, and includes definitions for the annotation predicates. The only predicates shared by Πr and ΠQ are of the form P??, which appear only in the rule bodies of ΠQ. These predicates produce a splitting of the combined program [ 28 ], which allows us to analyze separately Πr and ΠQ. The latter can be translated into classical logic by predicate completion, or a prioritized circumscription [ 30 ]. If the query is FO, we can use query itself.

Example 3. (ex. 2 cont.) Leaving aside many details that can be found in [ 10 ], we obtain the following SO formula Φ(Π) that captures the stable models of the original program: ∀xy(P (x, y) ≡ (x = a ∧ y = b) ∨ (x = a ∧ y = c) ∨ (x = d ∧ y = e)) ∧ (1) ∀xy(P??(x, y) ≡ Ans(x, y)) ∧ ∀xy((P (x, y) ∧ ¬Pf (x, y)) ≡ P??(x, y)) ∧ ∀xyz(P (x, y) ∧ P (x, z) ∧ y 6= z → (Pf (x, y) ∨ Pf (x, z))) ∧ ¬∃Uf ((Uf < Pf ) ∧ ∀xyz(P (x, y) ∧ P (x, z) ∧ y 6= z → (Uf (x, y) ∨ Uf (x, z))). (5) Here, Uf < Pf stands for the formula ∀xy(Uf (x, y) → Pf (x, y)) ∧ ∃xy(Pf (x, y) ∧ ¬Uf (x, y)). In this sentence, the minimizations of the predicates P, P?? and Ans are expressed as their predicate completion. Predicate Pf is minimized via (5).

We obtain the SO sentence for program Π as a parallel circumscription of the predicates in the repair program seen as a FO sentence. The circumscription actually becomes a prioritized circumscription [ 25 ] given the stratified nature of the repair program: first the database predicate is minimized, next Pf , next P??, and finallyAns.

Generalizations of the result in the previous example can be found in [ 10 ]. In the following we concentrate on the problem of possibly turning this SO reasoning problem into one at the FO level. (2) (3) (4) (6) (7) 4

From Second-Order to First-Order CQA

In this section we discuss the possibility of obtaining a FO rewriting of the original query as posed to the repair program. We do this through the analysis of the SO sentence obtained in Example 3, concentrating on the SO sentence (5). In the rest of this section many details are missing. They can be all found in [ 10 ], the extended version of this work.

Sentence (5) can be expressed as

¬∃Uf ((Uf < Pf ) ∧ ∀xyz(κ(x, y, z) → (Uf (x, y) ∨ Uf (x, z))), where κ(x, y, z) is the formula P (x, y) ∧ P (x, z) ∧ y 6= z. For simplicity, we use U instead of Uf . We will apply to (6) the SO quantifier elimination techniques in [ 17 ]. The negation of (6) turns out to be -after several steps [ 10 ]- logically equivalent to: ∃st∃U ( ∀xyz(¬κ(x, y, z) ∨ U (x, y) ∨ U (x, z)) ∧

∀uv(¬U (u, v) ∨ Pf (u, v)) ∧ (Pf (s, t) ∧ ¬U (s, t))). The first conjunct in (7), with w = ∨(y, z) standing for (w = y ∨ w = z), can be equivalently written as ∃f ∀r(∀x1y1z1(¬κ(x1, y1, z1) ∨ f (x1, y1, z1) = ∨(y1, z1)) ∧

∀xyz(¬κ(x, y, z)∨r 6= f (x, y, z)∨U (x, r))), where ∃f is a quantification over functions. Formula (7) becomes: ∃st∃f ∃U ∀x∀r((∀x1y1z1(¬κ(x1, y1, z1) ∨ f (x1, y1, z1) = ∨(y1, z1)) ∧ ∀yz(¬κ(x, y, z) ∨ r 6= f (x, y, z) ∨ U (x, r))) ∧

∀uv(¬U (u, v) ∨ Pf (u, v)) ∧ (Pf (s, t) ∧ ¬U (s, t))).

We are ready to apply Ackermann’s Lemma [ 2, 3 ], with the last formula written as: U ∃st∃f ∃U ∀x∀r((A(x, r) ∨ U (x, r)) ∧ B( ¬U where B( ¬UU ) is formula B with predicate U replaced by ¬U ; and formulas A, B are: A(x, r) : ∀yz(∀yz(¬κ(x, y, z)∨r 6= f (x, y, z)); and B(U ) : ∀x1y1z1(¬κ(x1, y1, z1)∨ f (x1, y1, z1) = ∨(y1, z1)) ∧ ∀uv(U (u, v) ∨ Pf (u, v)) ∧ (Pf (s, t) ∧ U (s, t))).

Formula B is positive in U , then the whole subformula in (8) starting with ∃U can

U be equivalently replaced by B( A(x,r) ) [17, lemma 1], getting rid of the SO variable U , and obtaining: ∃st∃f ∀xyz((¬κ(x, y, z) ∨ f (x, y, z) = ∨(y, z)) ∧ (¬κ(x, y, z) ∨ Pf (u, f (x, y, z))) ∧ (Pf (s, t) ∧ (x 6= s ∨ ¬κ(x, y, z) ∨ t 6= f (x, y, z)))).

Unskolemizing, getting rid of function variable f , we obtain ∃st∀xyz∃w((¬κ(x, y, z) ∨ w = ∨(y, z)) ∧ (¬κ(x, y, z) ∨ Pf (u, w))∧ (Pf (s, t) ∧ (x 6= s ∨ ¬κ(x, y, z) ∨ t 6= w))), which is equivalent to the negation of (6). Negating again, we obtain a formula equivalent to (6): ∀st(Pf (s, t) → ∃xyz(κ(x, y, z) ∧ ∀w[(w 6= y ∧ w 6= z)∨

¬Pf (x, w) ∨ (x = s ∧ t = w)]).

The formula in the square bracket inside can be equivalently replaced by ((w = y ∨ w = z) ∧ Pf (x, w)) → (s = x ∧ t = w).

So, we obtain ∀st(Pf (s, t) → ∃xyz(κ(x, y, z) ∧ (Pf (x, y) → s = x ∧ t = y) ∧ (Pf (x, z) → s = x ∧ t = z))).

Due to the definition ofκ(x, y, z), it must hold y 6= z. In consequence, we obtain: ∀st(Pf (s, t) → ∃z(κ(s, t, z) ∧ ¬Pf (s, z))).

Summing up, the SO sentence for the repair program Π(D, IC ) is logically equivalent to a FO sentence, ψ, that is the conjunction of (1), (3), (4), and ), (8) ∀st(Pf (s, t) → ∃z(κ(s, t, z) ∧ ¬Pf (s, z))), (9) which says, in particular, that whenever there is a conflict between two tuples, one of them must be deleted, and for every deleted tuple due to a violation, there must be a tuple with the same key value that has not been deleted. Thus, not all mutually conflicting tuples can be deleted.

Coming back to CQA, for consistent answers t¯, we now have classical FO entailment: ψ ∧ ∀x¯(AnsQ(x¯)) ≡ χ(x¯)) |= AnsQ(t¯), (10) where χ is the FO definition of AnsQ in terms of the P?? predicate. This is not FO query rewriting in the sense of obtaining a FO query to be posed to the original database. However, and for example, it is not difficult to show [ 10 ] that for the queryQ : P (x, y), and any consistent answer ht1, t2i, this is equivalent to having:

D |= P (t1, t2) ∧ ¬∃z(P (t1, z) ∧ z 6= t2). (11) The query rewriting on the RHS of in (11) is one of those obtained in [ 5 ] using a completely different and more general resolution-based rewriting methodology. 5

Towards Fixed-Point Logic

As described in Section 1, there are syntactic classes of CQs for which consistent query answering can be done in polynomial time in data complexity. For one class, this can be done via FO query rewriting. For a different class, its queries provably do not admit a first-order rewriting. Even more, one can decide if a CQ falls in this case or not [ 36, 37 ].

For example, the Boolean conjunctive query Q : ∃x∃y(R(x, y) ∧ S(y, x)), with the first attributes of R and S as keys for them, is a query in the second class in that it can be consistently answered in polynomial time, but no FO rewriting for it exists. Results of this kind are established in [ 35, 34 ] by means of the notions of Hanf-locality and Ehrenfeucht-Fra¨ıss e´ games for FO-logic [ 24 ].

This opens the ground for investigating two problems: 1. Apply the second-order quantifier elimination technique in [ 17 ], that we applied in this work, with the purpose of recovering the FO rewritings for the whole class of queries that admit FO consistent rewritings (as determined by Wijsen [ 35 ]). 2. Identify and obtain logical languages that can be used for rewriting the queries in the second class, in such a way that query answering for the rewritten query can be done in polynomial time.

For the second problem, it would be interesting to see if second-order quantifier elimination could be applied to second-order specification of Section 3, in such a way that the resulting query is expressed, not in FO logic, but in fixed-point logic, which would lead to a polynomial-time answer [ 24 ]. Actually, in [ 18 ], the authors have been able to eliminate second-order quantifiers, obtaining fixed-point formulas. It is worth investigating if this is a way to obtain polynomial-time, logical, but non-FO, rewritings for CQA. This undertaking is not a priori impossible. The existence of non-FO rewritable but PTIME-complete queries (in data) already identified [ 35, 23 ] is in principle compatible with the PTIME-completeness of fixed-point logic (in data) [ 16 ]. Acknowledgements: Useful comments from anonymous reviewers for a previous and the submitted version of this paper are much appreciated. Leopoldo Bertossi has been partially funded by the ANID - Millennium Science Initiative Program - Code ICN17002.

References

[1] Abiteboul , S. , Hull , R. and Vianu , V. Foundations of Databases. Addison-Wesley, 1995 .

[2] Ackermann , W. Untersuchungen u¨ber das Eliminationsproblem der mathematischen Logik . Mathematische Annalen , 1935 , 110 : 390 - 413 .

[3] Ackermann , W. Solvable cases of the Decision Problem. North-Holland Pub . Co., 1954 .

[4] Alviano , M. , Morak , M. and Pieris , A. Stable Model Semantics for Tuple-Generating Dependencies Revisited . Proc. PODS , 2017 , pp. 377 - 388 .

[5] Arenas , M. , Bertossi , L. and Chomicki , J. Consistent Query Answers in Inconsistent Databases. Proc. ACM Symposium on Principles of Database Systems , ACM Press, 1999 , pp. 68 - 79 .

[6] Barcelo , P. and Bertossi , L. Logic Programs for Querying Inconsistent Databases . Proc. Practical Aspects of Declarative Languages , Springer LNCS 2562, 2003 , pp. 208 - 222 .

[7] Bertossi , L. and Schwind , C. Database Repairs and Analytic Tableaux . Annals of Mathematics and Artificial Intelligence , 2004 , 40 ( 1-2 ): 5 - 35 .

[8] Bertossi , L. Consistent Query Answering in Databases . In ACM Sigmod Record , June 2006 , 35 ( 2 ): 68 - 76 .

[9] Bertossi , L. From Database Repair Programs to Consistent Query Answering in Classical Logic (extended abstract) . Proc. Alberto Mendelzon International Workshop on Foundations of Data Managemente (AMW) , 2009 . CEUR Workshop Proceedings , Vol. 450 , 2009 .

[10] Bertossi , L. Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases . Posted as Corr arXiv Paper 2108.08423 , 2021 .

[11] Bertossi , L. Database Repairing and Consistent Query Answering . Synthesis Lectures on Data Management , Morgan & Claypool Publishers, 2011 .

[12] Brewka , G. , Eiter , T. and Truszczynski , M. Answer Set Programming at a Glance . Communications of the ACM , 2011 , 54 ( 12 ): 92 - 103 .

[13] Caniupan-Marileo , M. and Bertossi , L. The Consistency Extractor System: Answer Set Programs for Consistent Query Answering in Databases . Data and Knowledge Engineering , 2010 , 69 ( 6 ): 545 - 572 .

[14] Chomicki , J. and Marcinkowski , J. Minimal-Change Integrity Maintenance using Tuple Deletions . Information and Computation , 2005 , 197 ( 1-2 ): 90 - 121 .

[15] Chomicki , J. Consistent Query Answering: Five Easy Pieces . Proc. International Conference on Database Theory , Springer LNCS 4353, 2007 , pp. 1 - 17 .

[16] Dantsin , E. , Eiter , T. , Gottlob , G. and Voronkov, A. Complexity and Expressive Power of Logic Programming . ACM Computing Surveys , 2001 , 33 ( 3 ): 374 - 425 .

[17] Doherty , P. , Lukaszewicz , W. and Szalas , A. Computing Circumscription Revisited . A Reduction Algorithm . Journal of Automated Reasoning , 1997 , 18 ( 3 ): 297 - 336 .

[18] Doherty , P. , Lukaszewicz , W. and Szalas , A. A Reduction Result for Circumscribed SemiHorn Formulas . Fundamenta Informaticae , 1996 , 28 ( 3-4 ): 261 - 271 .

[19] Ferraris , P. , Lee , J. and Lifschitz , V. A New Perspective on Stable Models . In Proc. International Joint Conference on Artificial Intelligence , 2007 , pp. 372 - 379 .

[20] Ferraris , P. , Lee , J. and Lifschitz , V. Stable Models and Circumscription. Artificial Intelligence , 2011 , 175 ( 1 ): 236 - 263 .

[21] Fuxman , A. and Miller , R. First-Order Query Rewriting for Inconsistent Databases . J. Computer and Systems Sciences , 2007 , 73 ( 4 ): 610 - 635 .

[22] Gelfond , M. , Lifschitz , V. Classical Negation in Logic Programs and Disjunctive Databases . New Generation Computing, 1991 , 9 ( 3 /4): 365 - 385 .

[23] Koutris , P. and Wijsen , J. First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys . Proc. PODS 2020 , pp. 113 - 129 .

[24] Libkin , L. Elements of Finite Model Theory . Springer, 2004 .

[25] Lifschitz , V. Computing Circumscription . Proc. International Joint Conference on Artificial Intelligence , Morgan Kaufmann, 1985 , pp. 121 - 127 .

[26] Lifschitz , V. Circumscription . In Handbook of Logic in Artificial Intelligence and Logic Programming , Vol. 3 . Oxford University Press, 1994 , pp. 297 - 352 .

[27] Lloyd , J.W. Foundations of Logic Programming . Springer Verlag, 1987 .

[28] Lifschitz , V. and Turner , H. Splitting a Logic Program . Proc. International Conference on Logic Programming , MIT Press, 1994 , pp. 23 - 37 .

[29] McCarthy , J. Circumscription - A Form of Non-Monotonic Reasoning . Artificial Intelligence , 1980 , 13 ( 1-2 ): 27 - 39 .

[30] Przymusinski , T. On the Declarative Semantics of Deductive Databases and Logic Programs . In Foundations of Deductive Databases and Logic Programming , J. Minker (ed.), Morgan Kaufmann Publishers Inc., 1988 , pp. 193 - 216 .

[31] Przymusinski , T. Stable Semantics for Disjunctive Programs . New Generation Computing, 1991 , 9 ( 3 /4): 401 - 424 .

[32] Reiter , R. Towards a Logical Reconstruction of Relational Database Theory . In On Conceptual Modelling, M.L. Brodie , J. Mylopoulos and J.W. Schmidt (eds.), Springer, 1984 , pp. 191 - 233 .

[33] Van Hermelen , F. , Lifschitz , V. and Porter , B . (eds.) Handbook of Knowledge Representation. Elsevier , 2008 .

[34] Wijsen , J. A Remark on the Complexity of Consistent Conjunctive Query Answering under Primary Key Violations . Information Processing Letters , 2010 , 110 : 950 - 955 .

[35] Wijsen , J. On the Consistent Rewriting Of Conjunctive Queries under Primary Key Constraints . Information Systems , 2009 , 34 : 578 - 601 .

[36] Wijsen , J. A Survey of the Data Complexity of Consistent Query Answering under Key Constraints . Proc. FoIKS 2014 , LNCS 8367, pp. 62 - 78 .

[37] Wijsen , J . Foundations of Query Answering on Inconsistent Databases. SIGMOD Record , 2019 , 48 ( 3 ): 6 - 16 .