Explanations for Negative Query Answers under Inconsistency-Tolerant Semantics

1 Introduction

In real ontology-based applications involving large amounts of data, possibly from different sources, inconsistency might naturally arise. To provide meaningful answers to users' queries even in such circumstances, different inconsistency-tolerant semantics of query answering have been proposed, mainly in the context of existential rules and description logics (DLs).

The ABox repair (AR) semantics is one of the most popular inconsistency-tolerant semantics; it was developed for relational databases [Arenas et al., 1999] and generalized for several DLs [Lembo et al., 2010]. Two other popular semantics introduced later on are the intersection of repairs (IAR) [Lembo et al., 2010] and the intersection of closed repairs (ICR) [Bienvenu, 2012] semantics. Besides being AR semantics' natural under-approximations, they are relevant in practice as they are amenable to preprocessing, since the intersection of the (closed) repairs can be computed offline, and then standard query answering can be employed online. In fact, the latter approach has been used to implement the IAR semantics [Lembo et al., 2015], while for the ICR semantics, it has been observed in [Bienvenu and Bourgaux, 2016].

The above semantics' complexity is rather well-understood in the literature (see, e.g., [Lembo et al., 2010; Bienvenu, 2012; Bienvenu and Rosati, 2013; Bienvenu et al., 2014; Lembo et al., 2015; Bienvenu and Bourgaux, 2016] for inconsistencytolerant query answering in DLs, and, e.g., [Eiter et al., 2016; Lukasiewicz et al., 2018; 2019; 2022] for inconsistencytolerant query answering under existential rules).

Explainability has recently started to play a prominent role in different areas of AI. Explaining ontological query answers allows users to understand not only what is or is not entailed by a knowledge base under a particular semantics, but also why. It has recently been investigated under both DLs and existential rules [Arioua et al., 2015; Bienvenu et al., 2015; 2016; 2019; Hecham et al., 2017; Ceylan et al., 2019; 2020a; 2020b; 2021; Lukasiewicz et al., 2020]. Bienvenu et al. [2015; 2016; 2019] considered the description logic DL-LiteR and defined explanations for positive and negative answers under the brave, AR, and IAR semantics, providing a data complexity analysis of different related problems. Lukasiewicz et al. [2020] considered explanations of positive query answers in the inconsistent setting under existential rules. Although DLs are popular ontology formalisms, rule-based ones are well-suited for data intensive applications, as they admit higher-arity relations, naturally occurring in standard relational databases.

Explaining query answers under inconsistency-tolerant semantics includes the problem of explaining query nonentailment. Despite the importance of this problem, however, its complexity has received less attention in the literature so far. The only existing work focusing on this problem is [Bienvenu et al., 2019]. In this paper, we continue this line of research. Rather than showing which facts inside the database are in conflict with the entailment of the query, as in [Bienvenu et al., 2019], our notions of explanation are based on showing how fact removals, needed to restore consistency, cause the query non-entailment. Besides the AR and IAR semantics, we consider the ICR semantics as well. We carry out a thorough complexity analysis for a wide spectrum of Datalog± languages under the data, fixed-program-combined, bounded-arity-combined, and combined complexity measures.

2 Preliminaries

In this section, we briefly recall some basics on existential rules from the context of Datalog± [Calì et al., 2012a].

General. We assume a set Cof constants, a set Nof labeled nulls, and a set V of variables. A term t is a constant, null, or variable. We also assume a set of predicates, each associated with an arity, i.e., a non-negative integer. An atom has the form p(t1, . . . , tn), where p is an n-ary predicate, and t1, . . . , tn are terms. An atom containing only constants is also called a fact. Conjunctions of atoms are often identified with the sets of their atoms. An instance I is a (possibly infinite) set of atoms p(t), where t is a tuple of constants and nulls. A database D is a finite instance that contains only constants. A homomorphism is a substitution h : 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) q has the form ∃Yϕ(X,Y), where ϕ(X,Y) is a conjunction of atoms without nulls. The answer to q over an instance I, denoted q(I), is the set of all tuples t over C for which there is a homomorphism h such that h(ϕ(X, Y)) ⊆ I and h(X) = t. A Boolean CQ (BCQ) q is a CQ ∃Yϕ(Y), i.e., all variables are existentially quantified; for BCQs, the only possible answer is the empty tuple. A BCQ q is true over I, denoted I |= q, if q(I) ̸= ∅, i.e., there is a homomorphism h with h(ϕ(Y)) ⊆ I.

Dependencies. A tuple-generating dependency (TGD) σ is a first-order formula ∀X∀Y (φ(X, Y) → ∃Z p(X, Z)), where X, Y, and Z are pairwise disjoint sets of variables, φ(X, Y) is a conjunction of atoms, and p(X,Z) is an atom, all without nulls; φ(X,Y) is the body of σ, denoted body(σ), while p(X,Z) is the head of σ, denoted head(σ). For clarity, we consider single-atom-head TGDs; however, our results extend to TGDs with a conjunction of atoms in the head. An instance I satisfies σ, written I |= σ, if the following holds: whenever there exists a homomorphism h such that h(φ(X,Y)) ⊆ I, then there exists h′ ⊇ h|X, where h|X is the restriction of h on X, such that h′ (p(X, Z)) ∈ I. A negative constraint (NC) ν is a first-order formula ∀X(φ(X) →⊥), where X ⊆ V, φ(X) is a conjunction of atoms without nulls, called the body of ν and denoted body(ν), and ⊥ denotes the truth constant false. An instance I satisfies ν, written I |= ν, if there is no homomorphism h such that h(φ(X)) ⊆ I. Given a set Σ of TGDs and NCs, I satisfies Σ, written I |= Σ, if I 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. Given a class of TGDs C, we denote by C⊥ 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) [Calì et al., 2012a], guarded (G) [Calì et al., 2013], sticky (S) [Calì et al., 2012b], and acyclic TGDs (A), along with the "weak" (proper) generalizations weakly sticky (WS) [Calì et al., 2012b] and weakly acyclic TGDs (WA) [Fagin et al., 2005], 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 [Lukasiewicz et al., 2022] for a more detailed overview.

Knowledge Bases. A knowledge base is a pair (D,Σ), where D is a database, and Σ is a program. For a program Σ, ΣT and ΣNC denote the subsets of Σ containing the TGDs and NCs of Σ, respectively. The set of models of KB = (D, Σ), denoted mods(KB), is the set of instances {I | I ⊇ D ∧ I |= Σ}. We say that KB is consistent if mods(KB) ̸= ∅, otherwise KB is inconsistent. The answer to a CQ q relative to KB is the set of tuples ans(q,KB) = ⋂{q(I) | I ∈ mods(KB)}. The answer to a BCQ q is true, denoted KB |= q, if ans(q,KB) ̸= ∅. A different, however equivalent, way to define ontological query answering is via the concept of the Chase (see, e.g., [Calì et al., 2013; Tsamoura et al., 2021], and references therein). The decision version of CQ answering is: given a knowledge base KB, a CQ q, and a tuple of constants t, decide whether t ∈ ans(q,KB). Since CQ answering can be reduced in LOGSPACE to BCQ answering, we focus on BCQs. We denote by BCQ(L) the problem of BCQ answering when restricted over programs belonging to L.

Following Vardi (1982), 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 complexity results of BCQ answering for the languages considered in this paper [Lukasiewicz et al., 2022].

Computational Complexity. For space reasons, we do not include preliminaries on computational complexity, which we assume the reader to be familiar with; we just recall that D P2 = ΣP2 ∧ΠP2 is the class of problems that are a conjunction of a problem in ΣP2 and one in ΠP2 .

Inconsistency-Tolerant Semantics. Three prominent inconsistency-tolerant semantics for ontology-based 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 [Lembo et al., 2010; Bienvenu, 2012]; all three are based on the notion of repair, which is a maximal consistent subset of the database.

Let KB = (D, Σ) be a knowledge base. A repair of KB is an inclusion-maximal subset R of D such that mods(R, Σ) ̸= ∅; Rep(KB) denotes the set of all repairs of KB. In general, there might be inconsistent KBs not admitting any repair. This is the case when Σ itself is "incoherent", that is, there is no database B such that mods(B,Σ) ̸= ∅-observe that, by monotonicity, this is equivalent to mods(∅,Σ) = ∅. In such a case, even deleting the entire database would not be enough to gain back consistency. In the rest of the paper, we assume that the program of an inconsistent KB is never "incoherent". The closure Cl (KB) of KB, which we denote also as Cl (D, Σ), is the set of all facts built from constants in D and Σ, entailed by D and the TGDs of Σ. Let q be a BCQ:

• KB entails q under the ABox repair (AR) semantics, denoted KB |=AR q, if (R, Σ) |= q for all R ∈ Rep(KB).
• KB entails q under the intersection of repairs (IAR) semantics, denoted KB |=IAR q, if (DI,Σ) |= q, where

DI = ⋂{R | R ∈ Rep(KB)}.

• KB entails q under the intersection of closed repairs (ICR) semantics, denoted KB |=ICR q, if (DC,Σ) |= q, where DC = ⋂{Cl (R, Σ) | R ∈ Rep(KB)}.

We refer to [Lukasiewicz et al., 2018; 2022] for more on the complexity of AR-/IAR-/ICR-query answering.

3 Explanations for Negative Query Answers

In the rest of this section, KB = (D, Σ) is a KB and q a BCQ. The next definition recalls and extends the one of (minimal) explanation for query entailment by a KB [Ceylan et al., 2019].

Definition 3.1. An explanation for q w.r.t. KB is a subset E of D such that (E, Σ) is consistent and (E, ΣT ) |= q.

A minimal explanation E, or MinEx, for q w.r.t. KB is an explanation for q w.r.t. KB that is inclusion-minimal, i.e., there is no E′ ⊊ E that is an explanation for q w.r.t. KB.

Unlike the definition of (minimal) explanations in [Ceylan et al., 2019], we require consistency, as in our setting KBs can be inconsistent. The above concept of minimal explanations is equivalent to that of causes in [Bienvenu et al. 2016; 2019].

Definition 3.2. A repair deletion of KB is a subset C of D such that (D \ C, Σ) is consistent and, for every proper subset C ′ of C, (D \ C ′ , Σ) is inconsistent.

Note that minimality is included in the definition of repair deletion, which hence is a repair's complement; when the KB is consistent, the empty set is the only repair deletion.

Example 3.3. Consider the database

asserting that p is a professor, a reader, chair (of some department), dean, and pro vice-chancellor. Consider also the program Σ consisting of the following TGDs ΣT :

and the following NCs ΣNC :

The TGDs assert that a professor can be elected for 1 year; a professor who is also chair, or a reader who is also pro vicechancellor, can be elected for 3 years; and finally someone who can be elected for Y years can be elected. The NCs assert that one cannot be a professor and a reader at the same time, or dean and chair, and a reader cannot be dean.

The knowledge base KB = (D, Σ) is inconsistent and admits the three repairs R1, R2, R3, below, whose corresponding repair deletions are the sets C1, C2, C3, respectively.

We now define the explanations for query non-entailment by a knowledge base under the AR, IAR, and ICR semantics.

Our explanation definitions aim at showing what happens in the reparation process, in terms of fact deletions, causing the query non-entailment under the considered inconsistencytolerant semantics; to this aim, these explanations are given only in terms of pieces of MinExes for the query (lost during the reparation). From this perspective, our definitions and the ones by Bienvenu et al. [2019] are conceptually complementary, as the latter propose explanations in terms of database facts left untouched by the reparation process and that are inconsistent with the MinExes for the query; these explanations might not include pieces of the query MinExes at all. To give an example, to explain AR non-entailment, both explanation notions witness the presence of a repair R not entailing the query: Bienvenu et al. [2019] explanations provide facts F left in the repair R that are inconsistent with every MinEx for the query, whereas we provide facts E outside the repair R (deleted during the reparation) that intersect every MinEx for the query-here, F is a subset of a repair obtained by a deletion that is a superset of E.

In this respect, our notions of explanation for non-entailment under inconsistency-tolerant semantics are akin to the one defined for non-entailment of a query by a consistent knowledge base, as they both focus on "missing" facts needed to entail the query: in the consistent case, the missing facts were never in the database; in the inconsistent case, the missing facts become missing due to the reparation process' deletions.

The two perspectives can be thought to emerge from two symmetrical scenarios. In a first scenario, the query is not entailed when instead it was expected to be. In this case, knowing the facts left in the repair that are inconsistent with the MinExes, and hence preventing the query entailment, can be useful to "restore" the expected behavior of the KB (e.g., removing some of those facts might yield query entailment).

Symmetrically, there is the scenario in which the query is not entailed and this was expected/desired. In this context, knowing the facts discarded by the reparation process (whose deletion yields the desired non-entailment), as provided by our explanations, can be helpful.

Examples illustrating our notions of explanation are provided after their the formal definitions, which are now given.

Intuitively, a query q is entailed by a knowledge base under the AR semantics if every repair has a MinEx for q. An explanation for KB ̸|=AR q provides a set C of facts witnessing the non-entailment of q by some repair: a minimal way to restore consistency needs to delete C from D, which leaves no MinEx for q in the repair yielded by the removal of (a superset of) C.

Definition 3.4. An explanation for KB ̸|=AR q is a set E = {C}, where C is a subset of a repair deletion of KB such that, for every MinEx E for q w.r.t. KB, E ∩ C ̸= ∅.

Example 3.5. Consider the knowledge base KB of Example 3.3 and the query q1 = CanBeElectedFor(p, 3), asking whether p can be elected for 3 years. It is easy to see that q1 is not entailed by KB under the AR semantics. An explanation for KB ̸|=AR q1 is E1 = {C}, where C = {Reader(p), Chair(p)}. This explanation says that deleting (at least) C from D is one way to restore consistency that leaves no MinEx for q1 (i.e., there is a repair not entailing q1).

Intuitively, a query q is entailed by a knowledge base under the IAR semantics if the repairs have a MinEx for q in common. An explanation for KB ̸|=IAR q provides sets of facts C1, . . . , Cn explaining why no such common MinEx exists. In particular, whatever MinEx E for q is considered among all those in the database, a minimal way of restoring consistency needs to delete fromD some Ci intersecting E, which is then lost in the repair yielded by the removal of (a superset of) Ci.

Definition 3.6. An explanation for KB ̸|=IAR q is a set E = {C1, . . . , Cn}, with n ≥ 1, where the Cis are subsets of repair deletions of KB such that, for every MinEx E for q w.r.t. KB, there exists a Ci such that E ∩ Ci ̸= ∅.

Example 3.7. Consider the knowledge base KB of Example 3.3 and the query q2 = ∃XCanBeElected(X), asking whether there is someone who can be elected. Query q2 is not entailed by KB under the IAR semantics. An explanation for KB ̸|=IAR q2 is E2 = {C1, C2}, where C1 = {Prof (p)} and C2 = {Reader(p)}. This explanation says that deleting (at least) C1 or C2 from D are two ways to restore consistency; however, each MinEx for q2 is lost either when deleting C1 or C2 (and thus there is no MinEx for q2 common to all repairs).

Intuitively, a query q is entailed by a knowledge base under the ICR semantics if the closures of the repairs have a MinEx for q in common. An explanation for KB ̸|=ICR q provides sets of facts C1, . . . ,Cn explaining why no such common MinEx exists. In particular, whatever MinEx E for q is considered among all those in the closure of the database, there is a minimal way of restoring consistency that needs to delete some Ci from D, and by doing so every way of deriving E is lost in the repair yielded by the removal of (a superset of) Ci. Given a finite set of facts E, qE denotes the BCQ ∧f∈E f.

Definition 3.8. An explanation for KB ̸|=ICR q is a set E = {C1, . . . , Cn}, with n ≥ 1, where the Cis are subsets of repair deletions of KB such that, for every MinEx E for q w.r.t. (Cl (KB), Σ), there exists a Ci such that, for every MinEx X for qE w.r.t. KB, X ∩ Ci ̸= ∅.

Note here that (Cl (KB), Σ) might be inconsistent, however every MinEx E for q w.r.t. (Cl(KB),Σ), as well as every MinEx X for qE w.r.t. KB, must be consistent (by definition of MinEx). Nonetheless, there might be MinExes E for q w.r.t. (Cl (KB), Σ) that do not admit any (consistent) MinEx for qE; such a MinEx E, however, cannot belong to the intersection of the repairs' closures, because if there is no (consistent) MinEx for qE, then E cannot appear in the closure of any repair.

Example 3.9. Consider Example 3.3's knowledge base KB and the query q3 = ∃X, Y CanBeElectedFor (X, Y ), asking if there is someone who can be elected for some years, is not entailed by KB under the ICR semantics. The MinExes for q3 in the closure of the database are E1 = {Prof (p)}, E2 = {Reader(p), PVC(p)}, E3 = {CanBeElectedFor(p, 1)}, and E4 = {CanBeElectedFor(p, 3)}. An explanation for KB ̸|=ICR q3 is E3 = {C1, C2}, where C1 = {Prof (p)} and C2 = {Reader(p),Chair(p)}. This explanation says that deleting (at least) C1 or C2 from D are two ways of restoring consistency; however, each Ei above cannot be derived anymore when deleting C1 or C2 (thus, there is no MinEx for q3 common to all repair closures). In fact, E1 and E3 cannot be derived when C1 is deleted, while E2 and E4 cannot be derived when C2 is deleted. It is particularly interesting to note why E4 is not derived when C2 is deleted fromD: the two (minimal) ways of deriving E4, namely X1 = {Prof (p), Chair(p)} and X2 = {Reader(p), PVC(p)}, are lost, and while the former is a MinEx for E4, and hence an explanation for q3, it is only a non-minimal explanation for q3.

Definition 3.10. For each S ∈ {AR, IAR, ICR}, an explanation E = {C1, . . . ,Cn} for KB ̸|=S q is minimal iff there is no explanation for KB ̸|=S q that can be derived from E by deleting facts from some Ci or by replacing a pair of distinct Ci and Cj with Ci ∪ Cj .

The two conditions in the previous definition aims at making "minimal" both the facts in each Ci and the overall number of Cis in E. Notice that if an explanation E contains a "redundant" Ci, that is, E \ {Ci} is an explanation, then E is not minimal according to the definition above, as we can delete all facts from Ci and still get an explanation, that is, E ′ = E \ {Ci} ∪ {∅} is an explanation. In fact, even E ′ is not minimal, as the empty set can be merged with any other Cj in E ′ , yielding the (possibly minimal) explanation E \ {Ci}.

The next proposition states that explanations for query nonentailment by a KB under an inconsistency-tolerant semantics exist iff the query is not entailed under that semantics.

Proposition 3.11. For each S ∈ {AR, IAR, ICR}, an explanation for KB ̸|=S q exists iff KB ̸|=S q.

A natural decision counterpart of the problem of computing minimal explanations for KB ̸|=S q, where S ∈ {AR, IAR, ICR}, is deciding the existence of a minimal explanation for KB ̸|=S q. In light of Proposition 3.11, the complexity of the latter problem equals the complexity of inconsistency-tolerant reasoning, which has already been investigated in the literature. Thus, in this paper, we focus on the following decision problems: deciding whether a set of sets of facts is a minimal explanation for KB ̸|=S q, for each S ∈ {AR, IAR, ICR}.

Problem: S-MINEX̸|=(L), with S ∈ {AR, IAR, ICR}. Input: A knowledge base KB = (D, Σ) with Σ ∈ L, a BCQ q, and E ⊆ P(D), with P(D) being the powerset of D. Question: Is E a minimal explanation for KB ̸|=S q?

In the following, for a knowledge base KB = (D, Σ) and a query q, we assume that (a) KB ̸|=S q and (b) D contains a MinEx for q, which is equivalent to require that there is at least one repair entailing the query-in the literature, this is the socalled brave semantics. Assumption (a) ensures that, if a set E is recognized as not being a minimal explanation for KB ̸|=S q, then this cannot be due to KB |=S q. Assumption (b) rules out that KB ̸|=S q holds simply because there is no way for the repairs (resp., their intersection, the intersection of their closure) to entail the query. It can be shown that the knowledge base does not contain any MinEx for q if and only if our minimal explanations are E = {∅}, for all semantics AR, IAR, and ICR. This is in line with our explanation definitions' spirit, as we want to explain how deletions cause the query non-entailment under the considered inconsistency-tolerant semantics; if the query is not entailed due to the absence of MinExes for it, then the inconsistency-tolerant semantics are not directly involved in the query non-entailment. However, all the results in the paper hold even if we remove either of the aforementioned assumptions or both.

4 Complexity Analysis

Our complexity results are summarized in Table 2. We first discuss membership, and then hardness results.

In the theorem statements, L is any of the languages considered in this paper, unless otherwise specified.

4.1 Membership Results

The following theorem provides upper bounds for the AR and IAR semantics. For each semantics, we employ a general procedure using an oracle for BCQ answering that applies to all languages and complexity measures considered here. The resulting upper bounds are always tight except for the fpcombined complexity of all languages and the data complexity of FO-rewritable languages (namely, L⊥, A⊥, S⊥, and their specializations), for which we need more refined statements.

Theorem 4.1. If BCQ(L) is in the complexity class C in the combined (resp., ba-combined, fp-combined, data) complexity, then AR-/IAR-MINEX̸|=(L) can be answered in the combined (resp., ba-combined, fp-combined, data) complexity by the following set of checks:

(a) an NPC check, and

(b) a co-(NPC) check.

In the previous theorem, to decide whether a set E = {C1, . . . , Cn} is a minimal explanation for KB ̸|=IAR q, an NPC check is needed to verify that each Ci is a subset of a repair deletion and no fact can be removed from any Ci (this ensures the minimality of each Ci by exploiting the concept of critical vertex in minimal hitting sets [Gottlob and Malizia, 2018], as a repair deletion is a minimal hitting set of all the culprits, which are minimal inconsistent subsets of the database), while a co-(NPC) check is needed to verify that every MinEx for q intersects some Ci and no two distinct Ci and Cj can be merged into a single set. The procedure to answer AR-MINEX̸|=(L) is a special case where E is first checked to be a singleton, and then simpler conditions need to be verified (because of the presence of only one element in E), which nonetheless yield the same upper bounds of IARMINEX̸|=(L). Membership in P NEXP for A⊥ in the combined and ba-combined complexity (for both AR and IAR) follows from the collapse of the strong exponential hierarchy, i.e., for any k ≥ 0, (ΣPk )NEXP = P NEXP [Hemachandra, 1989]-this will also apply to the ICR semantics in Theorems 4.2 and 4.3.

Focusing on the ICR semantics, we employ, again, a general procedure that applies to all languages considered here. In contrast to the AR and IAR semantics, this procedure uses an oracle for BCQ answering under the ICR semantics and applies only to the combined complexity. For the other complexity measures, we devise different procedures. We denote by ICR(L) the problem of BCQ answering under the ICR semantics when restricted over programs belonging to L. The combined complexity of ICR(L) is the same as the one reported in the last column of Table 2 [Lukasiewicz et al., 2022].

Theorem 4.2. If ICR(L) is in the complexity class D in the combined complexity, then ICR-MINEX̸|=(L) can be answered in the combined complexity by the following set of checks:

In the previous theorem, to decide whether a set E = {C1, . . . , Cn} is a minimal explanation for KB ̸|=ICR q, we can verify that each Ci is a subset of a repair deletion and no two distinct Ci and Cj can be merged into a single set in the same way as done for AR-/IAR-MINEX̸|=(L). The crucial difference is when we need to verify that (a) no fact can be removed from any Ci, which requires an NPD check, and (b) for every MinEx E for q w.r.t. (Cl(KB),Σ), there exists a Ci such that, for every MinEx X for qE w.r.t. KB, X ∩ Ci ̸= ∅, which requires a co-(NPD) check. A (naïve) procedure to verify the first condition (resp., the complement of the second one), would require guessing a MinEx for q w.r.t. (Cl (KB), Σ), which can have exponential size, and such an approach would not yield tight upper bounds. To obtain upper bounds matching the lower ones, we reduce verifying such conditions to ICR reasoning over a suitable knowledge base.

In contrast, in the ba-combined (resp., fp-combined, data) complexity, a MinEx for q w.r.t. (Cl (KB), Σ) can be guessed in NP, as Cl(KB) is of polynomial size, since predicates' arities are bounded (resp., the program is fixed), which yields the following upper bounds for all languages considered.

Theorem 4.3. If BCQ(L) is in the complexity class C in the ba-combined (resp., fp-combined, data) complexity, then ICR-MINEX̸|=(L) can be answered in the ba-combined (resp., fp-combined, data) complexity by the following set of checks: (a) an NPC check, and (b) a co-(NPC) check.

The results presented so far provide tight upper bounds for all languages we consider in the combined and ba-combined complexity. In the fp-combined complexity, for all languages and inconsistency-tolerant semantics, we need the following theorem to obtain tight upper bounds.

Theorem 4.4. For S ∈ {AR, IAR, ICR}, S-MINEX̸|=(L) is in D P in the fp-combined complexity.

The membership results in the previous theorem derive from the same procedures used in the combined and ba-combined complexity with additional observations. First, consistency checking is in P in the fp-combined complexity. Second, to check query entailment, the certificate witnessing query entailment can be guessed by the Turing machine solving the original problem. Finally, for the ICR-MINEX̸|=(L) problem, a MinEx for q w.r.t. (Cl (KB), Σ) can be guessed in NP because Cl (KB) has polynomial size.

The previous theorem provides tight upper bounds also in the data complexity for all languages but L⊥, A⊥, S⊥, and their specializations. For such languages, leveraging their FOrewritability, we obtain the following tighter upper bound for all inconsistency-tolerant semantics.

Theorem 4.5. For S ∈ {AR, IAR, ICR}, for L ∈ {L⊥, A⊥, S⊥}, S-MINEX̸|=(L) is in P in the data complexity.

4.2 Hardness Results

Hardness results are stated for the most specific languages they apply to (and then hold for all generalizations, of course).

The following theorem establishes all D P -hardness results in Table 2 in the data and fp-combined complexity for GF⊥ and its generalizations. We use a reduction from the classical D P -complete problem SAT-UNSAT, that is, given two Boolean formulas ϕ and ψ in 3CNF, decide whether ϕ is satisfiable and ψ is unsatisfiable. For all inconsistency-tolerant semantics, from an instance of SAT-UNSAT, we derive a suitable knowledge base, a query, and a candidate minimal explanation E = {C}. Roughly speaking, deciding satisfiability of ϕ is encoded into deciding whether C is a subset of a repair deletion, while deciding unsatisfiability of ψ is encoded into deciding whether C intersects all MinExes for the query.

Theorem4.6. For S ∈ {AR, IAR, ICR}, S-MINEX̸|=(GF⊥) is D P -hard in the data complexity.

The remaining D P -hardness results in the fp-combined complexity are established by the following theorem, which holds by another (more involved) reduction from SAT-UNSAT.

Theorem 4.7. For S ∈ {AR, IAR, ICR}, for L ∈ {LF⊥, AF⊥, SF⊥}, S-MINEX̸|=(L) is D P -hard in the fp-combined complexity.

The D P2 -hardness results in Table 2 in the ba-combined complexity are established by the following theorem via a reduction from the prototypical D P2 -hard problem: given two independent quantified Boolean formulas Φ = ∃X∀Y ¬ϕ(X, Y ) and Ψ = ∀X∃Y ψ(X, Y ), decide whether Φ and Ψ are both valid-here, ϕ and ψ are 3CNF formulas, and, to simplify the reduction even more, ϕ and ψ can also be assumed to have the same variables X and Y and the same number of clauses [Lukasiewicz and Malizia, 2017, Theorem 3.9].

Theorem 4.8. For S ∈ {AR, IAR, ICR}, for L ∈ {LF⊥, AF⊥, SF⊥}, S-MINEX̸|=(L) is D P2 -hard in the ba-combined complexity.

The hardness results for A⊥ in the ba-combined and combined complexity require a dedicated analysis. We give a reduction from the following P NEXP -complete problem [Lukasiewicz et al., 2022]: given a triple (m, TP1, TP2), where m is a number in unary, and TP1 and TP2 are two instances of the tiling problem for the exponential square 2n × 2n , decide whether for every initial tiling condition w of length m, TP1 has no solution with w or TP2 has solution with w.

Theorem 4.9. For S ∈ {AR, IAR, ICR}, S-MINEX̸|=(A⊥) is P NEXP -hard in the ba-combined complexity.

Finally, the remaining lower bounds in Table 2 in the bacombined and combined complexity are established by reducing standard BCQ answering to our problems.

Theorem 4.10. For S ∈ {AR, IAR, ICR}, for any language L without NCs considered in this paper, BCQ(L) is reducible in polynomial time to S-MINEX̸|=(L⊥) in the ba-combined, and combined complexity.

5 Summary and Outlook

Explaining AI decisions and dealing with inconsistent knowledge have both garnered a lot of attention. In this paper, we have analyzed the problem of explaining query non-entailment by a knowledge base, providing a thorough complexity analysis for three popular inconsistency-tolerant semantics, a wide range of existential rules, and different complexity measures.

A direction for future work is analyzing the complexity of other related problems, such as deciding whether a fact is necessary (i.e., belonging to every minimal explanation) or relevant (i.e., belonging to at least one minimal explanation), as done by Bienvenu et al. [2016; 2019] for DL-LiteR. Also, it would be interesting to investigate other notions of explanations for query (non-)entailment, e.g., explanations providing facts together with NCs, or more general explanation notions encompassing the consistent and the inconsistent settings.

Acknowledgments

This work was supported by the Alan Turing Institute under the EPSRC grant EP/N510129/1, by the AXA Research Fund, and by the EPSRC grant EP/R013667/1. We thank the anonymous reviewers for their insightful and helpful comments.