Vol-3194/paper57
Wolfgang Fahl
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3194/paper57 |
| wikidataid | Q117344958→Q117344958 |
| title | Explanations for Inconsistency-Tolerant Query Answering under Existential Rules |
| pdfUrl | https://ceur-ws.org/Vol-3194/paper57.pdf |
| dblpUrl | https://dblp.org/rec/conf/sebd/LukasiewiczMM22 |
| volume | Vol-3194→Vol-3194 |
| session | → |
Paper[edit]
| Paper | |
|---|---|
| edit
| |
| description | |
| id | Vol-3194/paper57 |
| wikidataid | Q117344958→Q117344958 |
| title | Explanations for Inconsistency-Tolerant Query Answering under Existential Rules |
| pdfUrl | https://ceur-ws.org/Vol-3194/paper57.pdf |
| dblpUrl | https://dblp.org/rec/conf/sebd/LukasiewiczMM22 |
| volume | Vol-3194→Vol-3194 |
| session | → |
Explanations for Inconsistency-Tolerant Query Answering under Existential Rules[edit]
Explanations for Inconsistency-Tolerant Query
Answering under Existential Rules⋆
(Discussion Paper)
Thomas Lukasiewicz1 , Enrico Malizia2 and Cristian Molinaro3
1
Department of Computer Science, University of Oxford, UK
2
DISI, University of Bologna, Italy
3
DIMES, University of Calabria, Italy
Abstract
Querying inconsistent knowledge bases has attracted a great deal of interest over the last decades. Also
explainability has recently become a prominent problem in AI, and explaining query answers allows users
to understand why a query is entailed. In this paper, we address the problem of explaining ontological
query answers in the existential rules setting under three popular inconsistency-tolerant semantics,
namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs semantics.
Keywords
Knowledge representation, Existential rules, Inconsistencies, Query answering, Explanations, Complexity
1. Introduction
Existential rules from the context of Datalog± [2] and description logics (DLs) [3] are popular
ontology languages. In real-world applications, it may very well be the case that the data are
inconsistent with the ontology. To provide meaningful answers to queries in the presence of
inconsistency, various inconsistency-tolerant semantics of query answering have been proposed.
In the ABox repair (AR) semantics, first developed for relational databases [4] and then
generalized for several DLs [5], a query answer is valid if it can be inferred from each of
the repairs of the knowledge base, that is, the inclusion-maximal consistent subsets of the
database. The intersection of repairs (IAR) [5] and the intersection of closed repairs (ICR) [6]
semantics have been introduced as approximations of the AR semantics (see also [7, 8, 9] for
other approximation approaches). An answer is considered to be valid under the IAR (resp.,
ICR) semantics if it can be inferred from the intersection of the repairs (resp., the intersection
of the closure of the repairs), along with the ontology.
Explainability has recently become a prominent problem in different areas of AI. In our
setting, explaining query answers allows users to understand not only what is entailed by an
SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
⋆
This is a short version of the AAAI-20 paper [1].
$ thomas.lukasiewicz@cs.ox.ac.uk (T. Lukasiewicz); enrico.malizia@unibo.it (E. Malizia);
cmolinaro@dimes.unical.it (C. Molinaro)
� 0000-0002-7644-1668 (T. Lukasiewicz); 0000-0002-6780-4711 (E. Malizia); 0000-0003-4103-1084 (C. Molinaro)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
�inconsistent knowledge base, but also why it is entailed. In this paper, we study explanations of
query entailment under inconsistency-tolerant semantics in the presence of existential rules.P
There have been various works on explanations for query answers under existential rules in
the consistent setting. Explaining query answers under existential rules was investigated in [10]
and under DL in [11]; preferred explanations in [12] and negative explanations in [13].
Explaining query answers under inconsistency-tolerant semantics has recently been addressed
in the literature. Arioua et al. [14] addressed the problem of explaining query entailment under
the ICR semantics in the presence of existential rules for which the Skolemized chase is finite.
Their definition of explanation is based on abstract argumentation. Their approach along
with interactive explanation methods based on dialectical approaches has been experimentally
evaluated by Hecham et al. [15]. Bienvenu et al. [16, 17, 18] considered the logic DL-Liteℛ .
They defined explanations for positive and negative answers under the brave, AR, and IAR
semantics, and investigated the data complexity of different related problems.
In this paper we investigate the complexity of query explanations under the AR, IAR, and
ICR semantics for a wide spectrum of Datalog± languages.
2. Preliminaries
We here briefly recall some basics on existential rules from the context of Datalog± [2].
General. We assume a set C of constants, a set N of labeled nulls, and a set V of variables. A
term 𝑡 is a constant, null, or variable. We assume a set of predicates, each associated with an arity.
An atom has the form 𝑝(𝑡1 , . . . , 𝑡𝑛 ), where 𝑝 is an 𝑛-ary predicate, and 𝑡1 , . . . , 𝑡𝑛 are terms. An
atom containing only constants is called fact. Conjunctions of atoms are also identified with
the sets of their atoms. An instance 𝐼 is a (possibly infinite) set of atoms defined over constants
and nulls. A database 𝐷 is a finite instance containing only constants. A homomorphism is a
substitution ℎ : C ∪ N ∪ V ↦→ C ∪ N ∪ V that is the identity on C and maps N to C ∪ N. With
a slight abuse of notation, homomorphisms are applied also to (sets/conjunctions of) atoms. A
conjunctive query (CQ) 𝑞 has the form ∃Y𝜑(X, Y), where 𝜑(X, Y) is a conjunction of atoms
without nulls. The answer to 𝑞 over an instance 𝐼, denoted 𝑞(𝐼), is the set of all |X|-tuples
t over C for which there is a homomorphism ℎ such that ℎ(𝜑(X, Y)) ⊆ 𝐼 and ℎ(X) = t. A
Boolean CQ (BCQ) 𝑞 is a CQ ∃Y𝜑(Y), i.e., all variables are existentially quantified; 𝑞 is true
over 𝐼, denoted 𝐼 |= 𝑞, if 𝑞(𝐼) ̸= ∅, i.e., there is a homomorphism ℎ with ℎ(𝜑(Y)) ⊆ 𝐼.
Dependencies. A tuple-generating dependency (TGD) 𝜎 is an FO formula ∀X∀Y 𝜙(X, Y) →
∃Z 𝑝(X, Z), where X, Y, and Z are pairwise disjoint sets of variables, 𝜙(X, Y) is a conjunction
of atoms, and 𝑝(X, Z) is an atom, all without nulls. An instance 𝐼 satisfies 𝜎, written 𝐼 |= 𝜎,
whenever there exists a homomorphism ℎ such that ℎ(𝜙(X, Y)) ⊆ 𝐼, then there exists ℎ′ ⊇ ℎ|X ,
where ℎ|X is the restriction of ℎ on X, such that ℎ′ (𝑝(X, Z)) ∈ 𝐼. A negative constraint (NC) 𝜈
is a first-order formula ∀X 𝜙(X) → ⊥, where X ⊆ V, 𝜙(X) is a conjunction of atoms without
nulls, and ⊥ denotes the truth constant false. An instance 𝐼 satisfies 𝜈, written 𝐼 |= 𝜈, if there
is no homomorphism ℎ such that ℎ(𝜙(X)) ⊆ 𝐼. Given a set Σ of TGDs and NCs, 𝐼 satisfies
Σ, written 𝐼 |= Σ, if 𝐼 satisfies each TGD and NC of Σ. For brevity, we omit the universal
quantifiers in front of TGDs and NCs, and use the comma (instead of ∧) for conjoining atoms.
�Table 1
Complexity of BCQ answering under existential rules [22]. All non-“in” entries are completeness results.
ℒ Data fp-comb. ba-comb. Comb.
0
L, LF, AF in ac np np pspace
S, SF in ac0 np np exp
A in ac0 np nexp nexp
G p np exp 2exp
F, GF p np np exp
WS, WA p np 2exp 2exp
For a TGD class C, C⊥ denotes the formalism obtained by combining C with arbitrary NCs.
Finite sets of TGDs and NCs are also called programs, and TGDs are also called existential rules.
The Datalog± languages ℒ that we consider to guarantee decidability are among the most
frequently analyzed in the literature, namely, linear (L) [2], guarded (G) [19], sticky (S) [20], and
acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [20] and
weakly acyclic TGDs (WA) [21], as well as their “full” (i.e., existential-free) proper restrictions
linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively,
and full TGDs (F) in general. We also recall the following further inclusions: L ⊂ G and
F ⊂ WA ⊂ WS. We refer to [22] for a more detailed overview.
Knowledge Bases. A knowledge base is a pair (𝐷, Σ), where 𝐷 is a database, and Σ is a program.
For a program Σ, Σ𝑇 and ΣNC denote the TGDs and NCs subsets, respectively, of Σ. The set
mods(KB ) of models of KB = (𝐷, Σ) is the set of instances {𝐼 | 𝐼 ⊇ 𝐷 ∧ 𝐼 |= Σ}; KB is
consistent if mods(KB ) ̸= ∅,⋂︀otherwise KB is inconsistent. The answer to a CQ 𝑞 w.r.t. KB is the
set of tuples ans(𝑞, KB ) = {𝑞(𝐼) | 𝐼 ∈ mods(KB )}. The answer to a BCQ 𝑞 is true, denoted
KB |= 𝑞, if ans(𝑞, KB ) ̸= ∅. Another way to define the existential rules semantics is via the
concept of the Chase (see, e.g., [23, 24]). The decision version of the CQ answering problem is:
for a knowledge base KB , a CQ 𝑞, and a tuple of constants t, decide whether t ∈ ans(𝑞, KB ).
Since CQ answering can be reduced in logspace to BCQ answering, we focus on BCQs. BCQ(ℒ)
denotes the problem of BCQ answering when restricted over programs belonging to ℒ.
Following Vardi [25], the combined complexity of BCQ answering considers the database,
the set of dependencies, and the query as part of the input. The bounded-arity-combined (or
ba-combined) complexity assumes that the arity of the underlying schema is bounded by an
integer constant. The fixed-program-combined (or fp-combined) complexity considers the sets of
TGDs and NCs as fixed; the data complexity also assumes the query fixed. Table 1 recalls the
complexity results of BCQ answering for the languages here considered [22].
A language ℒ is FO-rewritable if given any program Σ ∈ ℒ and any BCQ 𝑞, there exists an
FO-query 𝑞Σ such that, for all databases 𝐷 we have that (𝐷, Σ) |= 𝑞 iff 𝐷 |= 𝑞Σ . All languages
from Table 1 with ac0 data complexity are FO-rewritable.
Inconsistency-Tolerant Semantics. In classical BCQ answering, for an inconsistent knowl-
edge base KB (i.e., mods(KB ) = ∅), every query is entailed, as everything follows from a
contradiction. Clearly, the answers obtained in such cases are not meaningful. Three prominent
�inconsistency-tolerant semantics for query answering under existential rules are the ABox repair
(AR) semantics, its approximation by the intersection of repairs (IAR), and the intersection of
closed repairs (ICR) semantics [5, 6]; all three are based on the notion of repair.
A repair of a knowledge base KB = (𝐷, Σ) is an inclusion-maximal subset 𝑅 of 𝐷 such that
mods((𝑅, Σ)) ̸= ∅; Rep(KB ) is the set of all KB ’ repairs. The closure Cl (KB ) of KB is the set
of all facts built from constants in 𝐷 and Σ, entailed by 𝐷 and the TGDs of Σ. Let 𝑞 be a BCQ.
• KB entails 𝑞 under the ABox repair (AR) semantics, if (𝑅, Σ) |= 𝑞 for all 𝑅 ∈ Rep(KB ).
KB entails 𝑞 under the intersection of repairs (IAR) semantics, if (𝐷𝐼 , Σ) |= 𝑞, where 𝐷𝐼 =
• ⋂︀
{𝑅 | 𝑅 ∈ Rep(KB )}.
⋂︀ 𝑞 under the intersection of closed repairs (ICR) semantics, if (𝐷𝐶 , Σ) |= 𝑞, where
• KB entails
𝐷𝐶 = {Cl (𝑅, Σ) | 𝑅 ∈ Rep(KB )}.
Symmetrically, the concept of repair is linked to that of culprit. Intuitively, a culprit is a
minimal subset of 𝐷 that, together with Σ𝑇 entails some NC; a culprit for an NC is a “minimal
explanation” [10] (see below) of the NC. By deleting from 𝐷 a minimal hitting set [26, 27] of
facts 𝑆 intersecting all culprits, we obtain a repair 𝑅 = 𝐷 ∖ 𝑆.
We refer to [22, 28, 29] for more on the complexity of AR-/IAR-/ICR-query answering.
3. Explanations for Query Answers
An explanation for 𝑞 w.r.t. KB is a subset 𝐸 of 𝐷 such that (𝐸, Σ) is consistent and (𝐸, Σ) |= 𝑞.
A minimal explanation 𝐸, or MinEx, for 𝑞 w.r.t. KB is an explanation for 𝑞 w.r.t. KB that is
inclusion-minimal, i.e., there is no 𝐸 ′ ⊊ 𝐸 that is an explanation for 𝑞 w.r.t. KB . We now
introduce the notions of (minimal) explanation under the AR, IAR, and ICR semantics.
Definition 1. • An AR-explanation for 𝑞 w.r.t. KB is a set of explanations ℰ = {𝐸1 , . . . , 𝐸𝑛 }
for 𝑞 w.r.t. KB such that every repair of KB contains some 𝐸𝑖 .
• An IAR-explanation for 𝑞 w.r.t. KB is a singleton set of explanations ℰ = {𝐸} for 𝑞 w.r.t.
KB such that 𝐸 ⊆ 𝑅 for every repair 𝑅 ∈ Rep(KB ).
• An ICR-explanation for 𝑞 w.r.t. KB is a set of explanations ℰ = {𝐸1 , . . .⋂︀
, 𝐸𝑛 } for 𝑞 w.r.t. KB
such that each KB ’s repair contains an 𝐸𝑖 and (𝐸𝐶 , Σ) |= 𝑞, with 𝐸𝐶 = {Cl (𝐸𝑖 ) | 𝐸𝑖 ∈ ℰ}.
Definition 2. For any 𝑆 ∈ {AR, IAR, ICR}, an 𝑆-explanation ℰ = {𝐸1 , . . . , 𝐸𝑛 } for 𝑞 w.r.t.
KB is an 𝑆-minimal explanation, or 𝑆-MinEx, if every 𝐸𝑖 ∈ ℰ is a MinEx for 𝑞 w.r.t. KB , and
no ℰ ′ ⊊ ℰ is an 𝑆-explanation for 𝑞 w.r.t. KB .
Example 3. Consider the database 𝐷 = {Prof (𝑝, 𝑐𝑠), Postdoc(𝑝, 𝑚𝑎𝑡ℎ), Group(𝑔)}, assert-
ing that 𝑝 is a professor working in the 𝑐𝑠 department, 𝑝 is a postdoc working in the 𝑚𝑎𝑡ℎ
department, and 𝑔 is a research group. Consider also the following program Σ:
Prof (𝑋, 𝑌 ) → Researcher (𝑋), Prof (𝑋, 𝑌 ) → Dept(𝑌 ),
Postdoc(𝑋, 𝑌 ) → Researcher (𝑋), Postdoc(𝑋, 𝑌 ) → Dept(𝑌 ),
Prof (𝑋, 𝑌 ), Postdoc(𝑋, 𝑍) → ⊥,
expressing that Prof and Postdoc have Researcher as domain and Dept as range, and one
cannot be both a professor and a postdoc. Clearly, the knowledge base KB = (𝐷, Σ) is
�Table 2
Complexity of AR-, IAR-, and ICR-MinEx. All entries are completeness results. Hardness results for
AR and ICR in the data and fp-combined complexity also follow from inspection of a proof in [18].
AR- and ICR-MinEx IAR-MinEx
ℒ Data fp-comb. ba-comb. Comb. Data fp-comb. ba-comb. Comb.
L⊥ , LF⊥ , AF⊥ dp
dp
dp2 pspace in p dp Πp2 pspace
S⊥ , SF⊥ dp dp dp2 exp in p dp Πp2 exp
A⊥ dp dp pnexp
pnexp in p dp pnexp pnexp
G⊥ dp dp exp 2exp co-np dp exp 2exp
F⊥ , GF⊥ dp dp dp2 exp co-np dp Πp2 exp
WS⊥ , WA⊥ dp dp 2exp 2exp co-np dp 2exp 2exp
inconsistent, as 𝑝 violates the NC. The knowledge base admits the following two repairs:
𝐷′ = {Prof (𝑝, 𝑐𝑠), Group(𝑔)}, and 𝐷′′ = {Postdoc(𝑝, 𝑚𝑎𝑡ℎ), Group(𝑔)}. Their intersection
is 𝐷𝐼 = {Group(𝑔)}, while their closures’ intersection is 𝐷𝐶 = {Group(𝑔), Researcher (𝑝)}.
The BCQ ∃𝑋Group(𝑋) is entailed by KB under IAR (and thus also under ICR and AR).
The set {{Group(𝑔)}} is an IAR-minimal (as well as ICR- and AR-minimal) explanation for
the query w.r.t. KB . Indeed, Group(𝑔) is the fact in 𝐷𝐼 that entails the query.
The BCQ ∃𝑋Researcher (𝑋) is entailed by KB under ICR (and thus also under AR), but
not under IAR. The set {{Prof (𝑝, 𝑐𝑠)}, {Postdoc(𝑝, 𝑚𝑎𝑡ℎ)}} is an ICR-minimal (as well as
AR-minimal) explanation for the query w.r.t. KB . Indeed, Researcher (𝑝) is the fact in 𝐷𝐶 that
entails the query, and the reason why Researcher (𝑝) belongs to the closures of 𝐷′ and 𝐷′′ are
the facts Prof (𝑝, 𝑐𝑠) and Postdoc(𝑝, 𝑚𝑎𝑡ℎ) of 𝐷′ and 𝐷′′ , respectively.
The BCQ ∃𝑋Dept(𝑋) is entailed by KB only under AR. An AR-minimal explanation for
the query w.r.t. 𝐾𝐵 is {{Prof (𝑝, 𝑐𝑠)}, {Postdoc(𝑝, 𝑚𝑎𝑡ℎ)}}. Indeed, Prof (𝑝, 𝑐𝑠) is the fact of
𝐷′ entailing the query, while Postdoc(𝑝, 𝑚𝑎𝑡ℎ) is the fact of 𝐷′′ entailing the query. ◁
We will study the 𝑆-MinEx problems, for any 𝑆 ∈ {AR, IAR, ICR}, of recognizing 𝑆-
MinExes: for a knowledge base KB = (𝐷, Σ), a BCQ 𝑞, and a set ℰ ⊆ 𝒫(𝐷), with 𝒫(𝐷) being
the powerset of 𝐷, decide whether the set ℰ is an 𝑆-MinEx for 𝑞 w.r.t. KB .
4. Complexity Analysis
The first results imply most of the complexity upper-bounds of Table 2. The intuition behind
these theorems is as follows (for the details see [1]). Verifying that ℰ is an 𝑆-MinEx for 𝑞 w.r.t.
KB requires checking the following conditions: (1) that all 𝐸𝑖 ∈ ℰ are MinExes of 𝑞 w.r.t. KB
(which implies verifying that: (1a) all 𝐸𝑖 ∈ ℰ are consistent; (1b) all 𝐸𝑖 ∈ ℰ entail 𝑞; and (1c) all
𝐸𝑖 ∈ ℰ are minimal); (2) that all the repairs are “covered” by ℰ; and (3) verify that the “cover by
ℰ is minimal”, for which we borrow the concept of “critical vertex in a minimal hitting set” [30].
Theorem 4. Let ℒ be one of the Datalog± languages of this paper. If BCQ(ℒ) is in C, then
AR-MinEx and IAR-MinEx can be answered by the following sequence of checks:
• AR: a co-(npC ) check, an npC check, a linear number of C checks, and a linear number of
co-C checks.
�• IAR: a co-(npC ) check, a C check, and a linear number of co-C checks.
For the ICR case we need a slightly different proof. Verifying that a set ℰ = {𝐸1 , . . . , 𝐸𝑛 }
is an ICR-MinEx requires to check conditions (1), (2), and (3) as above, and the additional
condition that the intersection of the closure of all the 𝐸𝑖 ’s entails the query. Verifying the
latter can be reduced to ICR reasoning over a suitable knowledge base.
Theorem 5. Let ℒ be one of the Datalog± languages of this paper. If BCQ(ℒ) (resp., BCQ(ℒ)
under ICR) is in C (resp., in D), then ICR-MinEx can be answered by the following sequence of
checks: a co-(npC ) check, an npC check, a D check, and a linear number of co-C checks.
For the fp-combined setting we have tighter results thanks to these two observations. First,
in the fp-combined setting, for the Datalog± languages here considered, checking a set of facts
to be a repair is in p. Second, for the ICR case, we also need to notice that, in the fp-combined
setting, checking the intersection of the 𝐸𝑖 ’s closure to entail the query is in np.
Theorem 6. AR-/IAR-/ICR-MinEx is in dp in the fp-combined complexity for the Datalog±
languages of this paper.
The following result proves the p upper-bounds in Table 2. A key observation is that the
intersection of the repairs in the stated fragments is computable in polynomial time [22].
Theorem 7. IAR-MinEx from knowledge bases over L⊥ , A⊥ , and S⊥ is in p in the data complexity.
The upper-bounds found in the previous section are actually tight, and indeed we can show
matching lower-bounds. The co-np-hardness and Πp2 -hardness results for IAR are via reductions
from UnSat and from deciding the validity of a QBF ∀𝑋∃𝑌 𝜑(𝑋, 𝑌 ), respectively.
The pnexp -hardness results are obtained via a reduction from the following problem [22]:
given a triple (𝑚, TP 1 , TP 2 ), where 𝑚 is a number in unary, and TP 1 and TP 2 are two tiling
problems for the exponential square 2𝑛 × 2𝑛 , decide whether, for all initial tiling conditions 𝑤
of length 𝑚, TP 1 has no solution with 𝑤 or TP 2 has a solution with 𝑤.
The dp -hardness results in the data complexity for AR and ICR are via a reduction from
Minimal UnSat [31]: given a Boolean formula 𝜑, decide whether 𝜑 is minimally unsatisfiable,
i.e., if 𝜑 is unsatisfiable, and removing any clause from 𝜑 makes the formula satisfiable.
The dp2 -hardness results for AR and ICR are via a reduction from the problem of deciding
the validity of two QBFs Φ = ∃𝑋∀𝑌 ¬𝜑(𝑋, 𝑌 ) and Ψ = ∀𝑋∃𝑌 𝜓(𝑋, 𝑌 ). The reduction uses
the simplifying assumption that variables 𝑋 and 𝑌 of Φ and Ψ can be the same [32, 33].
The remaining hardness results follow from Is-MinEX’s hardness over consistent KBs [10].
5. Summary and Outlook
We have analyzed the problem of explaining query answers under three popular inconsistency-
tolerant semantics, for a wide range of existential rules, and under different complexity measures;
this work has recently been extended to negative query answers [34].
This paper opens up several avenues for further research, like analyzing the complexity
of other related problems, such as deciding if a fact is necessary or relevant. Inspired by the
�idea of exploring preferences over explanations [12], we can also consider how more elaborate
preference models can be included in this framework [35, 36, 37, 38, 39]. Moreover, in some
scenarios, knowing the existential rules needed to derive query answers may be useful as well.
Acknowledgments
This work was supported by the Alan Turing Institute under the UK EPSRC grant EP/N510129/1,
the AXA Research Fund, and the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1.
References
[1] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query
answering under existential rules, in: AAAI, 2020, pp. 2909–2916.
[2] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query
answering over ontologies, J. Web Sem. 14 (2012) 57–83.
[3] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The
Description Logic Handbook, 2nd ed., Cambridge University Press, 2007.
[4] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases,
in: PODS, 1999, pp. 68–79.
[5] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics
for description logics, in: RR, 2010, pp. 103–117.
[6] M. Bienvenu, On the complexity of consistent query answering in the presence of simple
ontologies, in: AAAI, 2012, pp. 705–711.
[7] S. Greco, C. Molinaro, Probabilistic query answering over inconsistent databases, Ann.
Math. Artif. Intell. 64 (2012) 185–207.
[8] S. Greco, C. Molinaro, I. Trubitsyna, Computing approximate query answers over incon-
sistent knowledge bases, in: IJCAI, 2018, pp. 1838–1846.
[9] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant
query answering under existential rules, in: KR, 2020, pp. 203–212.
[10] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers
under existential rules, in: IJCAI, 2019, pp. 1639–1646.
[11] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for ontology-
mediated query answering in description logics, in: ECAI, 2020, pp. 672–679.
[12] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations
for ontology-mediated queries under existential rules, in: AAAI, 2021, pp. 6262–6270.
[13] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Explanations for
negative query answers under existential rules, in: KR, 2020, pp. 223–232.
[14] A. Arioua, N. Tamani, M. Croitoru, Query answering explanation in inconsistent Datalog+/–
knowledge bases, in: DEXA, 2015, pp. 203–219.
[15] A. Hecham, A. Arioua, G. Stapleton, M. Croitoru, An empirical evaluation of argumentation
in explaining inconsistency-tolerant query answering, in: DL, 2017.
[16] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining query answers under inconsistency-
tolerant semantics over description logic knowledge bases, in: DL, 2015.
�[17] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining inconsistency-tolerant query answer-
ing over description logic knowledge bases, in: AAAI, 2016, pp. 900–906.
[18] M. Bienvenu, C. Bourgaux, F. Goasdoué, Computing and explaining query answers over
inconsistent DL-Lite knowledge bases, J. Artif. Intell. Res. 64 (2019) 563–644.
[19] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive
relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174.
[20] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query
answering problem, Artif. Intell. 193 (2012) 87–128.
[21] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: Semantics and query answering,
Theor. Comput. Sci. 336 (2005) 89–124.
[22] T. Lukasiewicz, E. Malizia, M. V. Martinez, C. Molinaro, A. Pieris, G. I. Simari, Inconsistency-
tolerant query answering for existential rules, Artif. Intell. 307 (2022) art. no. 103685.
[23] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger
graphs, VLDB Endow. 14 (2021) 943–956.
[24] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Exploiting equality generating dependen-
cies in checking chase termination, VLDB Endow. 9 (2016) 396–407.
[25] M. Vardi, The complexity of relational query languages, in: STOC, 1982, pp. 137–146.
[26] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, in: LICS, 2014, pp. 43:1–43:10.
[27] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions,
Inf. Comput. 197 (2005) 90–121.
[28] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query
answering in Datalog+/– under cardinality-based repairs, in: AAAI, 2019, pp. 2962–2969.
[29] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering
under inconsistency in Datalog± , in: IJCAI, 2018, pp. 1921–1927.
[30] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, SIAM J. Comput. 47 (2018) 456–492.
[31] C. H. Papadimitriou, D. Wolfe, The complexity of facets resolved, J. Comput. Syst. Sci. 37
(1988) 2–13.
[32] T. Lukasiewicz, E. Malizia, On the complexity of 𝑚CP-nets, in: AAAI, 2016, pp. 558–564.
[33] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ𝑃𝑘 based on
counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33.
[34] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under
inconsistency-tolerant semantics, in: IJCAI, 2022.
[35] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, Non-transferable utility coalitional games
via mixed-integer linear constraints, J. Artif. Intell. Res. 38 (2010) 633–685.
[36] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
[37] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636.
[38] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential
active integrity constraints, Expert Syst. Appl. 168 (2021) art. no. 114297.
[39] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, The complexity of the nucleolus in compact
games, ACM Trans. Comput. Theory 7 (2014) 3:1–3:52.
�
Explanations for Inconsistency-Tolerant Query Answering under Existential Rules[edit]
Explanations for Inconsistency-Tolerant Query
Answering under Existential Rules⋆
(Discussion Paper)
Thomas Lukasiewicz1 , Enrico Malizia2 and Cristian Molinaro3
1
Department of Computer Science, University of Oxford, UK
2
DISI, University of Bologna, Italy
3
DIMES, University of Calabria, Italy
Abstract
Querying inconsistent knowledge bases has attracted a great deal of interest over the last decades. Also
explainability has recently become a prominent problem in AI, and explaining query answers allows users
to understand why a query is entailed. In this paper, we address the problem of explaining ontological
query answers in the existential rules setting under three popular inconsistency-tolerant semantics,
namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs semantics.
Keywords
Knowledge representation, Existential rules, Inconsistencies, Query answering, Explanations, Complexity
1. Introduction
Existential rules from the context of Datalog± [2] and description logics (DLs) [3] are popular
ontology languages. In real-world applications, it may very well be the case that the data are
inconsistent with the ontology. To provide meaningful answers to queries in the presence of
inconsistency, various inconsistency-tolerant semantics of query answering have been proposed.
In the ABox repair (AR) semantics, first developed for relational databases [4] and then
generalized for several DLs [5], a query answer is valid if it can be inferred from each of
the repairs of the knowledge base, that is, the inclusion-maximal consistent subsets of the
database. The intersection of repairs (IAR) [5] and the intersection of closed repairs (ICR) [6]
semantics have been introduced as approximations of the AR semantics (see also [7, 8, 9] for
other approximation approaches). An answer is considered to be valid under the IAR (resp.,
ICR) semantics if it can be inferred from the intersection of the repairs (resp., the intersection
of the closure of the repairs), along with the ontology.
Explainability has recently become a prominent problem in different areas of AI. In our
setting, explaining query answers allows users to understand not only what is entailed by an
SEBD 2022: The 30th Italian Symposium on Advanced Database Systems, June 19-22, 2022, Tirrenia (PI), Italy
⋆
This is a short version of the AAAI-20 paper [1].
$ thomas.lukasiewicz@cs.ox.ac.uk (T. Lukasiewicz); enrico.malizia@unibo.it (E. Malizia);
cmolinaro@dimes.unical.it (C. Molinaro)
� 0000-0002-7644-1668 (T. Lukasiewicz); 0000-0002-6780-4711 (E. Malizia); 0000-0003-4103-1084 (C. Molinaro)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
�inconsistent knowledge base, but also why it is entailed. In this paper, we study explanations of
query entailment under inconsistency-tolerant semantics in the presence of existential rules.P
There have been various works on explanations for query answers under existential rules in
the consistent setting. Explaining query answers under existential rules was investigated in [10]
and under DL in [11]; preferred explanations in [12] and negative explanations in [13].
Explaining query answers under inconsistency-tolerant semantics has recently been addressed
in the literature. Arioua et al. [14] addressed the problem of explaining query entailment under
the ICR semantics in the presence of existential rules for which the Skolemized chase is finite.
Their definition of explanation is based on abstract argumentation. Their approach along
with interactive explanation methods based on dialectical approaches has been experimentally
evaluated by Hecham et al. [15]. Bienvenu et al. [16, 17, 18] considered the logic DL-Liteℛ .
They defined explanations for positive and negative answers under the brave, AR, and IAR
semantics, and investigated the data complexity of different related problems.
In this paper we investigate the complexity of query explanations under the AR, IAR, and
ICR semantics for a wide spectrum of Datalog± languages.
2. Preliminaries
We here briefly recall some basics on existential rules from the context of Datalog± [2].
General. We assume a set C of constants, a set N of labeled nulls, and a set V of variables. A
term 𝑡 is a constant, null, or variable. We assume a set of predicates, each associated with an arity.
An atom has the form 𝑝(𝑡1 , . . . , 𝑡𝑛 ), where 𝑝 is an 𝑛-ary predicate, and 𝑡1 , . . . , 𝑡𝑛 are terms. An
atom containing only constants is called fact. Conjunctions of atoms are also identified with
the sets of their atoms. An instance 𝐼 is a (possibly infinite) set of atoms defined over constants
and nulls. A database 𝐷 is a finite instance containing only constants. A homomorphism is a
substitution ℎ : C ∪ N ∪ V ↦→ C ∪ N ∪ V that is the identity on C and maps N to C ∪ N. With
a slight abuse of notation, homomorphisms are applied also to (sets/conjunctions of) atoms. A
conjunctive query (CQ) 𝑞 has the form ∃Y𝜑(X, Y), where 𝜑(X, Y) is a conjunction of atoms
without nulls. The answer to 𝑞 over an instance 𝐼, denoted 𝑞(𝐼), is the set of all |X|-tuples
t over C for which there is a homomorphism ℎ such that ℎ(𝜑(X, Y)) ⊆ 𝐼 and ℎ(X) = t. A
Boolean CQ (BCQ) 𝑞 is a CQ ∃Y𝜑(Y), i.e., all variables are existentially quantified; 𝑞 is true
over 𝐼, denoted 𝐼 |= 𝑞, if 𝑞(𝐼) ̸= ∅, i.e., there is a homomorphism ℎ with ℎ(𝜑(Y)) ⊆ 𝐼.
Dependencies. A tuple-generating dependency (TGD) 𝜎 is an FO formula ∀X∀Y 𝜙(X, Y) →
∃Z 𝑝(X, Z), where X, Y, and Z are pairwise disjoint sets of variables, 𝜙(X, Y) is a conjunction
of atoms, and 𝑝(X, Z) is an atom, all without nulls. An instance 𝐼 satisfies 𝜎, written 𝐼 |= 𝜎,
whenever there exists a homomorphism ℎ such that ℎ(𝜙(X, Y)) ⊆ 𝐼, then there exists ℎ′ ⊇ ℎ|X ,
where ℎ|X is the restriction of ℎ on X, such that ℎ′ (𝑝(X, Z)) ∈ 𝐼. A negative constraint (NC) 𝜈
is a first-order formula ∀X 𝜙(X) → ⊥, where X ⊆ V, 𝜙(X) is a conjunction of atoms without
nulls, and ⊥ denotes the truth constant false. An instance 𝐼 satisfies 𝜈, written 𝐼 |= 𝜈, if there
is no homomorphism ℎ such that ℎ(𝜙(X)) ⊆ 𝐼. Given a set Σ of TGDs and NCs, 𝐼 satisfies
Σ, written 𝐼 |= Σ, if 𝐼 satisfies each TGD and NC of Σ. For brevity, we omit the universal
quantifiers in front of TGDs and NCs, and use the comma (instead of ∧) for conjoining atoms.
�Table 1
Complexity of BCQ answering under existential rules [22]. All non-“in” entries are completeness results.
ℒ Data fp-comb. ba-comb. Comb.
0
L, LF, AF in ac np np pspace
S, SF in ac0 np np exp
A in ac0 np nexp nexp
G p np exp 2exp
F, GF p np np exp
WS, WA p np 2exp 2exp
For a TGD class C, C⊥ denotes the formalism obtained by combining C with arbitrary NCs.
Finite sets of TGDs and NCs are also called programs, and TGDs are also called existential rules.
The Datalog± languages ℒ that we consider to guarantee decidability are among the most
frequently analyzed in the literature, namely, linear (L) [2], guarded (G) [19], sticky (S) [20], and
acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [20] and
weakly acyclic TGDs (WA) [21], as well as their “full” (i.e., existential-free) proper restrictions
linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively,
and full TGDs (F) in general. We also recall the following further inclusions: L ⊂ G and
F ⊂ WA ⊂ WS. We refer to [22] for a more detailed overview.
Knowledge Bases. A knowledge base is a pair (𝐷, Σ), where 𝐷 is a database, and Σ is a program.
For a program Σ, Σ𝑇 and ΣNC denote the TGDs and NCs subsets, respectively, of Σ. The set
mods(KB ) of models of KB = (𝐷, Σ) is the set of instances {𝐼 | 𝐼 ⊇ 𝐷 ∧ 𝐼 |= Σ}; KB is
consistent if mods(KB ) ̸= ∅,⋂︀otherwise KB is inconsistent. The answer to a CQ 𝑞 w.r.t. KB is the
set of tuples ans(𝑞, KB ) = {𝑞(𝐼) | 𝐼 ∈ mods(KB )}. The answer to a BCQ 𝑞 is true, denoted
KB |= 𝑞, if ans(𝑞, KB ) ̸= ∅. Another way to define the existential rules semantics is via the
concept of the Chase (see, e.g., [23, 24]). The decision version of the CQ answering problem is:
for a knowledge base KB , a CQ 𝑞, and a tuple of constants t, decide whether t ∈ ans(𝑞, KB ).
Since CQ answering can be reduced in logspace to BCQ answering, we focus on BCQs. BCQ(ℒ)
denotes the problem of BCQ answering when restricted over programs belonging to ℒ.
Following Vardi [25], the combined complexity of BCQ answering considers the database,
the set of dependencies, and the query as part of the input. The bounded-arity-combined (or
ba-combined) complexity assumes that the arity of the underlying schema is bounded by an
integer constant. The fixed-program-combined (or fp-combined) complexity considers the sets of
TGDs and NCs as fixed; the data complexity also assumes the query fixed. Table 1 recalls the
complexity results of BCQ answering for the languages here considered [22].
A language ℒ is FO-rewritable if given any program Σ ∈ ℒ and any BCQ 𝑞, there exists an
FO-query 𝑞Σ such that, for all databases 𝐷 we have that (𝐷, Σ) |= 𝑞 iff 𝐷 |= 𝑞Σ . All languages
from Table 1 with ac0 data complexity are FO-rewritable.
Inconsistency-Tolerant Semantics. In classical BCQ answering, for an inconsistent knowl-
edge base KB (i.e., mods(KB ) = ∅), every query is entailed, as everything follows from a
contradiction. Clearly, the answers obtained in such cases are not meaningful. Three prominent
�inconsistency-tolerant semantics for query answering under existential rules are the ABox repair
(AR) semantics, its approximation by the intersection of repairs (IAR), and the intersection of
closed repairs (ICR) semantics [5, 6]; all three are based on the notion of repair.
A repair of a knowledge base KB = (𝐷, Σ) is an inclusion-maximal subset 𝑅 of 𝐷 such that
mods((𝑅, Σ)) ̸= ∅; Rep(KB ) is the set of all KB ’ repairs. The closure Cl (KB ) of KB is the set
of all facts built from constants in 𝐷 and Σ, entailed by 𝐷 and the TGDs of Σ. Let 𝑞 be a BCQ.
• KB entails 𝑞 under the ABox repair (AR) semantics, if (𝑅, Σ) |= 𝑞 for all 𝑅 ∈ Rep(KB ).
KB entails 𝑞 under the intersection of repairs (IAR) semantics, if (𝐷𝐼 , Σ) |= 𝑞, where 𝐷𝐼 =
• ⋂︀
{𝑅 | 𝑅 ∈ Rep(KB )}.
⋂︀ 𝑞 under the intersection of closed repairs (ICR) semantics, if (𝐷𝐶 , Σ) |= 𝑞, where
• KB entails
𝐷𝐶 = {Cl (𝑅, Σ) | 𝑅 ∈ Rep(KB )}.
Symmetrically, the concept of repair is linked to that of culprit. Intuitively, a culprit is a
minimal subset of 𝐷 that, together with Σ𝑇 entails some NC; a culprit for an NC is a “minimal
explanation” [10] (see below) of the NC. By deleting from 𝐷 a minimal hitting set [26, 27] of
facts 𝑆 intersecting all culprits, we obtain a repair 𝑅 = 𝐷 ∖ 𝑆.
We refer to [22, 28, 29] for more on the complexity of AR-/IAR-/ICR-query answering.
3. Explanations for Query Answers
An explanation for 𝑞 w.r.t. KB is a subset 𝐸 of 𝐷 such that (𝐸, Σ) is consistent and (𝐸, Σ) |= 𝑞.
A minimal explanation 𝐸, or MinEx, for 𝑞 w.r.t. KB is an explanation for 𝑞 w.r.t. KB that is
inclusion-minimal, i.e., there is no 𝐸 ′ ⊊ 𝐸 that is an explanation for 𝑞 w.r.t. KB . We now
introduce the notions of (minimal) explanation under the AR, IAR, and ICR semantics.
Definition 1. • An AR-explanation for 𝑞 w.r.t. KB is a set of explanations ℰ = {𝐸1 , . . . , 𝐸𝑛 }
for 𝑞 w.r.t. KB such that every repair of KB contains some 𝐸𝑖 .
• An IAR-explanation for 𝑞 w.r.t. KB is a singleton set of explanations ℰ = {𝐸} for 𝑞 w.r.t.
KB such that 𝐸 ⊆ 𝑅 for every repair 𝑅 ∈ Rep(KB ).
• An ICR-explanation for 𝑞 w.r.t. KB is a set of explanations ℰ = {𝐸1 , . . .⋂︀
, 𝐸𝑛 } for 𝑞 w.r.t. KB
such that each KB ’s repair contains an 𝐸𝑖 and (𝐸𝐶 , Σ) |= 𝑞, with 𝐸𝐶 = {Cl (𝐸𝑖 ) | 𝐸𝑖 ∈ ℰ}.
Definition 2. For any 𝑆 ∈ {AR, IAR, ICR}, an 𝑆-explanation ℰ = {𝐸1 , . . . , 𝐸𝑛 } for 𝑞 w.r.t.
KB is an 𝑆-minimal explanation, or 𝑆-MinEx, if every 𝐸𝑖 ∈ ℰ is a MinEx for 𝑞 w.r.t. KB , and
no ℰ ′ ⊊ ℰ is an 𝑆-explanation for 𝑞 w.r.t. KB .
Example 3. Consider the database 𝐷 = {Prof (𝑝, 𝑐𝑠), Postdoc(𝑝, 𝑚𝑎𝑡ℎ), Group(𝑔)}, assert-
ing that 𝑝 is a professor working in the 𝑐𝑠 department, 𝑝 is a postdoc working in the 𝑚𝑎𝑡ℎ
department, and 𝑔 is a research group. Consider also the following program Σ:
Prof (𝑋, 𝑌 ) → Researcher (𝑋), Prof (𝑋, 𝑌 ) → Dept(𝑌 ),
Postdoc(𝑋, 𝑌 ) → Researcher (𝑋), Postdoc(𝑋, 𝑌 ) → Dept(𝑌 ),
Prof (𝑋, 𝑌 ), Postdoc(𝑋, 𝑍) → ⊥,
expressing that Prof and Postdoc have Researcher as domain and Dept as range, and one
cannot be both a professor and a postdoc. Clearly, the knowledge base KB = (𝐷, Σ) is
�Table 2
Complexity of AR-, IAR-, and ICR-MinEx. All entries are completeness results. Hardness results for
AR and ICR in the data and fp-combined complexity also follow from inspection of a proof in [18].
AR- and ICR-MinEx IAR-MinEx
ℒ Data fp-comb. ba-comb. Comb. Data fp-comb. ba-comb. Comb.
L⊥ , LF⊥ , AF⊥ dp
dp
dp2 pspace in p dp Πp2 pspace
S⊥ , SF⊥ dp dp dp2 exp in p dp Πp2 exp
A⊥ dp dp pnexp
pnexp in p dp pnexp pnexp
G⊥ dp dp exp 2exp co-np dp exp 2exp
F⊥ , GF⊥ dp dp dp2 exp co-np dp Πp2 exp
WS⊥ , WA⊥ dp dp 2exp 2exp co-np dp 2exp 2exp
inconsistent, as 𝑝 violates the NC. The knowledge base admits the following two repairs:
𝐷′ = {Prof (𝑝, 𝑐𝑠), Group(𝑔)}, and 𝐷′′ = {Postdoc(𝑝, 𝑚𝑎𝑡ℎ), Group(𝑔)}. Their intersection
is 𝐷𝐼 = {Group(𝑔)}, while their closures’ intersection is 𝐷𝐶 = {Group(𝑔), Researcher (𝑝)}.
The BCQ ∃𝑋Group(𝑋) is entailed by KB under IAR (and thus also under ICR and AR).
The set {{Group(𝑔)}} is an IAR-minimal (as well as ICR- and AR-minimal) explanation for
the query w.r.t. KB . Indeed, Group(𝑔) is the fact in 𝐷𝐼 that entails the query.
The BCQ ∃𝑋Researcher (𝑋) is entailed by KB under ICR (and thus also under AR), but
not under IAR. The set {{Prof (𝑝, 𝑐𝑠)}, {Postdoc(𝑝, 𝑚𝑎𝑡ℎ)}} is an ICR-minimal (as well as
AR-minimal) explanation for the query w.r.t. KB . Indeed, Researcher (𝑝) is the fact in 𝐷𝐶 that
entails the query, and the reason why Researcher (𝑝) belongs to the closures of 𝐷′ and 𝐷′′ are
the facts Prof (𝑝, 𝑐𝑠) and Postdoc(𝑝, 𝑚𝑎𝑡ℎ) of 𝐷′ and 𝐷′′ , respectively.
The BCQ ∃𝑋Dept(𝑋) is entailed by KB only under AR. An AR-minimal explanation for
the query w.r.t. 𝐾𝐵 is {{Prof (𝑝, 𝑐𝑠)}, {Postdoc(𝑝, 𝑚𝑎𝑡ℎ)}}. Indeed, Prof (𝑝, 𝑐𝑠) is the fact of
𝐷′ entailing the query, while Postdoc(𝑝, 𝑚𝑎𝑡ℎ) is the fact of 𝐷′′ entailing the query. ◁
We will study the 𝑆-MinEx problems, for any 𝑆 ∈ {AR, IAR, ICR}, of recognizing 𝑆-
MinExes: for a knowledge base KB = (𝐷, Σ), a BCQ 𝑞, and a set ℰ ⊆ 𝒫(𝐷), with 𝒫(𝐷) being
the powerset of 𝐷, decide whether the set ℰ is an 𝑆-MinEx for 𝑞 w.r.t. KB .
4. Complexity Analysis
The first results imply most of the complexity upper-bounds of Table 2. The intuition behind
these theorems is as follows (for the details see [1]). Verifying that ℰ is an 𝑆-MinEx for 𝑞 w.r.t.
KB requires checking the following conditions: (1) that all 𝐸𝑖 ∈ ℰ are MinExes of 𝑞 w.r.t. KB
(which implies verifying that: (1a) all 𝐸𝑖 ∈ ℰ are consistent; (1b) all 𝐸𝑖 ∈ ℰ entail 𝑞; and (1c) all
𝐸𝑖 ∈ ℰ are minimal); (2) that all the repairs are “covered” by ℰ; and (3) verify that the “cover by
ℰ is minimal”, for which we borrow the concept of “critical vertex in a minimal hitting set” [30].
Theorem 4. Let ℒ be one of the Datalog± languages of this paper. If BCQ(ℒ) is in C, then
AR-MinEx and IAR-MinEx can be answered by the following sequence of checks:
• AR: a co-(npC ) check, an npC check, a linear number of C checks, and a linear number of
co-C checks.
�• IAR: a co-(npC ) check, a C check, and a linear number of co-C checks.
For the ICR case we need a slightly different proof. Verifying that a set ℰ = {𝐸1 , . . . , 𝐸𝑛 }
is an ICR-MinEx requires to check conditions (1), (2), and (3) as above, and the additional
condition that the intersection of the closure of all the 𝐸𝑖 ’s entails the query. Verifying the
latter can be reduced to ICR reasoning over a suitable knowledge base.
Theorem 5. Let ℒ be one of the Datalog± languages of this paper. If BCQ(ℒ) (resp., BCQ(ℒ)
under ICR) is in C (resp., in D), then ICR-MinEx can be answered by the following sequence of
checks: a co-(npC ) check, an npC check, a D check, and a linear number of co-C checks.
For the fp-combined setting we have tighter results thanks to these two observations. First,
in the fp-combined setting, for the Datalog± languages here considered, checking a set of facts
to be a repair is in p. Second, for the ICR case, we also need to notice that, in the fp-combined
setting, checking the intersection of the 𝐸𝑖 ’s closure to entail the query is in np.
Theorem 6. AR-/IAR-/ICR-MinEx is in dp in the fp-combined complexity for the Datalog±
languages of this paper.
The following result proves the p upper-bounds in Table 2. A key observation is that the
intersection of the repairs in the stated fragments is computable in polynomial time [22].
Theorem 7. IAR-MinEx from knowledge bases over L⊥ , A⊥ , and S⊥ is in p in the data complexity.
The upper-bounds found in the previous section are actually tight, and indeed we can show
matching lower-bounds. The co-np-hardness and Πp2 -hardness results for IAR are via reductions
from UnSat and from deciding the validity of a QBF ∀𝑋∃𝑌 𝜑(𝑋, 𝑌 ), respectively.
The pnexp -hardness results are obtained via a reduction from the following problem [22]:
given a triple (𝑚, TP 1 , TP 2 ), where 𝑚 is a number in unary, and TP 1 and TP 2 are two tiling
problems for the exponential square 2𝑛 × 2𝑛 , decide whether, for all initial tiling conditions 𝑤
of length 𝑚, TP 1 has no solution with 𝑤 or TP 2 has a solution with 𝑤.
The dp -hardness results in the data complexity for AR and ICR are via a reduction from
Minimal UnSat [31]: given a Boolean formula 𝜑, decide whether 𝜑 is minimally unsatisfiable,
i.e., if 𝜑 is unsatisfiable, and removing any clause from 𝜑 makes the formula satisfiable.
The dp2 -hardness results for AR and ICR are via a reduction from the problem of deciding
the validity of two QBFs Φ = ∃𝑋∀𝑌 ¬𝜑(𝑋, 𝑌 ) and Ψ = ∀𝑋∃𝑌 𝜓(𝑋, 𝑌 ). The reduction uses
the simplifying assumption that variables 𝑋 and 𝑌 of Φ and Ψ can be the same [32, 33].
The remaining hardness results follow from Is-MinEX’s hardness over consistent KBs [10].
5. Summary and Outlook
We have analyzed the problem of explaining query answers under three popular inconsistency-
tolerant semantics, for a wide range of existential rules, and under different complexity measures;
this work has recently been extended to negative query answers [34].
This paper opens up several avenues for further research, like analyzing the complexity
of other related problems, such as deciding if a fact is necessary or relevant. Inspired by the
�idea of exploring preferences over explanations [12], we can also consider how more elaborate
preference models can be included in this framework [35, 36, 37, 38, 39]. Moreover, in some
scenarios, knowing the existential rules needed to derive query answers may be useful as well.
Acknowledgments
This work was supported by the Alan Turing Institute under the UK EPSRC grant EP/N510129/1,
the AXA Research Fund, and the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1.
References
[1] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query
answering under existential rules, in: AAAI, 2020, pp. 2909–2916.
[2] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query
answering over ontologies, J. Web Sem. 14 (2012) 57–83.
[3] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider (Eds.), The
Description Logic Handbook, 2nd ed., Cambridge University Press, 2007.
[4] M. Arenas, L. E. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases,
in: PODS, 1999, pp. 68–79.
[5] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics
for description logics, in: RR, 2010, pp. 103–117.
[6] M. Bienvenu, On the complexity of consistent query answering in the presence of simple
ontologies, in: AAAI, 2012, pp. 705–711.
[7] S. Greco, C. Molinaro, Probabilistic query answering over inconsistent databases, Ann.
Math. Artif. Intell. 64 (2012) 185–207.
[8] S. Greco, C. Molinaro, I. Trubitsyna, Computing approximate query answers over incon-
sistent knowledge bases, in: IJCAI, 2018, pp. 1838–1846.
[9] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant
query answering under existential rules, in: KR, 2020, pp. 203–212.
[10] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers
under existential rules, in: IJCAI, 2019, pp. 1639–1646.
[11] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for ontology-
mediated query answering in description logics, in: ECAI, 2020, pp. 672–679.
[12] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations
for ontology-mediated queries under existential rules, in: AAAI, 2021, pp. 6262–6270.
[13] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Explanations for
negative query answers under existential rules, in: KR, 2020, pp. 223–232.
[14] A. Arioua, N. Tamani, M. Croitoru, Query answering explanation in inconsistent Datalog+/–
knowledge bases, in: DEXA, 2015, pp. 203–219.
[15] A. Hecham, A. Arioua, G. Stapleton, M. Croitoru, An empirical evaluation of argumentation
in explaining inconsistency-tolerant query answering, in: DL, 2017.
[16] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining query answers under inconsistency-
tolerant semantics over description logic knowledge bases, in: DL, 2015.
�[17] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining inconsistency-tolerant query answer-
ing over description logic knowledge bases, in: AAAI, 2016, pp. 900–906.
[18] M. Bienvenu, C. Bourgaux, F. Goasdoué, Computing and explaining query answers over
inconsistent DL-Lite knowledge bases, J. Artif. Intell. Res. 64 (2019) 563–644.
[19] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive
relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174.
[20] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query
answering problem, Artif. Intell. 193 (2012) 87–128.
[21] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: Semantics and query answering,
Theor. Comput. Sci. 336 (2005) 89–124.
[22] T. Lukasiewicz, E. Malizia, M. V. Martinez, C. Molinaro, A. Pieris, G. I. Simari, Inconsistency-
tolerant query answering for existential rules, Artif. Intell. 307 (2022) art. no. 103685.
[23] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger
graphs, VLDB Endow. 14 (2021) 943–956.
[24] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Exploiting equality generating dependen-
cies in checking chase termination, VLDB Endow. 9 (2016) 396–407.
[25] M. Vardi, The complexity of relational query languages, in: STOC, 1982, pp. 137–146.
[26] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, in: LICS, 2014, pp. 43:1–43:10.
[27] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions,
Inf. Comput. 197 (2005) 90–121.
[28] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query
answering in Datalog+/– under cardinality-based repairs, in: AAAI, 2019, pp. 2962–2969.
[29] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering
under inconsistency in Datalog± , in: IJCAI, 2018, pp. 1921–1927.
[30] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem
through logic, SIAM J. Comput. 47 (2018) 456–492.
[31] C. H. Papadimitriou, D. Wolfe, The complexity of facets resolved, J. Comput. Syst. Sci. 37
(1988) 2–13.
[32] T. Lukasiewicz, E. Malizia, On the complexity of 𝑚CP-nets, in: AAAI, 2016, pp. 558–564.
[33] T. Lukasiewicz, E. Malizia, A novel characterization of the complexity class Θ𝑃𝑘 based on
counting and comparison, Theor. Comput. Sci. 694 (2017) 21–33.
[34] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under
inconsistency-tolerant semantics, in: IJCAI, 2022.
[35] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, Non-transferable utility coalitional games
via mixed-integer linear constraints, J. Artif. Intell. Res. 38 (2010) 633–685.
[36] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142.
[37] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation over (m)CP-nets:
Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636.
[38] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential
active integrity constraints, Expert Syst. Appl. 168 (2021) art. no. 114297.
[39] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, The complexity of the nucleolus in compact
games, ACM Trans. Comput. Theory 7 (2014) 3:1–3:52.
�