=Paper=
{{Paper
|id=Vol-3009/abstract1
|storemode=property
|title=Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases (Abstract)
|pdfUrl=https://ceur-ws.org/Vol-3009/abstract1.pdf
|volume=Vol-3009
|authors=Leopoldo Bertossi
|dblpUrl=https://dblp.org/rec/conf/kr/Bertossi21
}}
==Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases (Abstract)==
https://ceur-ws.org/Vol-3009/abstract1.pdf
Second-Order Specifications and Quantifier Elimination
for Consistent Query Answering in Databases
(Abstract)
Leopoldo Bertossi
Universidad Adolfo Ibáñez
Faculty of Engineering and Sciences
and
Millennium Institute for Foundational Research on Data (IMFD)
Santiago, Chile
leopoldo.bertossi@uai.cl
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 spec-
ified 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.
1 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 re-
spect 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 Li-
cense Attribution 4.0 International (CC BY 4.0).
Second-Order Specifications and Elimination for Consistent Query Answering 29
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) language L(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 com-
plexity 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 consis-
tent 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 comput-
ing 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 seman-
tics 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 inves-
tigate 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.
30 Leopoldo Bertossi
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 in-
stance 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 (ā, f ), meaning “made false (deleted)”, (b) t?? in atoms
P (ā, 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 restric-
Second-Order Specifications and Elimination for Consistent Query Answering 31
tion 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, ā is a
consistent answer to Q, denoted, D |=c Q(ā), iff Π(D, FD) ∪ Π Q |=cs AnsQ (ā). In
general, Π Q will be a (stratified) non-recursive and normal Datalognot query Π Q with
answer predicate Ans Q (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 repre-
sented 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 ā, such that
Π Q ∪ Π(D, FD) |=cs Ans(ā), 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 reob-
tained via an explicit specification in classical SO predicate logic that is based on cir-
cumscription. 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
Vn Pi andPiX of the same arity.
Pi
Wn Here, (X̄ < P̄ ) means (X̄ ≤ P̄ ) ∧
(X̄ 6= P̄ ), i.e. i ∀x̄(X (x̄) → Pi (x̄)) ∧ i (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].
32 Leopoldo Bertossi
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)) ∧ (2)
∀xy((P (x, y) ∧ ¬Pf (x, y)) ≡ P?? (x, y)) ∧ (3)
∀xyz(P (x, y) ∧ P (x, z) ∧ y 6= z → (Pf (x, y) ∨ Pf (x, z))) ∧ (4)
¬∃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 predi-
cates 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 finally Ans.
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.
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))), (6)
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)) ∧ (7)
∀uv(¬U (u, v) ∨ Pf (u, v)) ∧ (Pf (s, t) ∧ ¬U (s, t))).
Second-Order Specifications and Elimination for Consistent Query Answering 33
The first conjunct in (7), with w = ∨(y, z) standing for (w = y ∨ w = z), can be
equivalently written as
∃f ∀r(∀x1 y1 z1 (¬κ(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((∀x1 y1 z1 (¬κ(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( ), (8)
¬U
where B( ¬U ) is formula B with predicate U replaced by ¬U ; and formulas A, B are:
U
A(x, r) : ∀yz(∀yz(¬κ(x, y, z)∨r 6= f (x, y, z)); and B(U ) : ∀x1 y1 z1 (¬κ(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
be equivalently replaced by B( A(x,r) U
) [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 equiva-
lent 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 equiv-
alent to a FO sentence, ψ, that is the conjunction of (1), (3), (4), and
∀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 entail-
ment:
ψ ∧ ∀x̄(AnsQ(x̄)) ≡ χ(x̄)) |= AnsQ(t̄), (10)
where χ is the FO definition of Ans Q 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.
34 Leopoldo Bertossi
However, and for example, it is not difficult to show [10] that for the query Q : P (x, y),
and any consistent answer ht1 , t2 i, 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é 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 elim-
ination 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 inves-
tigating 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 com-
patible 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 ICN17-
002.
References
[1] Abiteboul, S., Hull, R. and Vianu, V. Foundations of Databases. Addison-Wesley, 1995.
[2] Ackermann, W. Untersuchungen über das Eliminationsproblem der mathematischen Logik.
Mathematische Annalen, 1935, 110:390-413.
Second-Order Specifications and Elimination for Consistent Query Answering 35
[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 De-
pendencies 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 Mathe-
matics 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 Founda-
tions 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. Com-
munications 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 Engineer-
ing, 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 Confer-
ence 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 Semi-
Horn 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. Inter-
national Joint Conference on Artificial Intelligence, 2007, pp. 372-379.
[20] Ferraris, P., Lee, J. and Lifschitz, V. Stable Models and Circumscription. Artificial Intelli-
gence, 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 Artifi-
cial 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.
36 Leopoldo Bertossi
[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 Intelli-
gence, 1980, 13(1-2):27-39.
[30] Przymusinski, T. On the Declarative Semantics of Deductive Databases and Logic Pro-
grams. 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 Con-
ceptual 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 Representa-
tion. 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 Con-
straints. 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.