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.
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 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.
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.
Complexity of BCQ answering under existential rules [22]. All non-"in" entries are completeness results.
Data fp-comb. ba-comb. Comb.
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.
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
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 ac 0 data complexity are FO-rewritable. Inconsistency-Tolerant Semantics. In classical BCQ answering, for an inconsistent knowledge 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.
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.
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. 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 ICRand 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 .
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]. • IAR: a co-(np C ) 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. 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 d p 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 Π p 2 -hardness results for IAR are via reductions from UnSat and from deciding the validity of a QBF ∀𝑋∃𝑌 𝜑(𝑋, 𝑌 ), respectively.
The p nexp -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 d p -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 d p 2 -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].
We have analyzed the problem of explaining query answers under three popular inconsistencytolerant 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.
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.