Explanations for Inconsistency-Tolerant Query Answering under Existential Rules⋆

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

• eol>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 diferent 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 diferent 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.

ℒ L, LF, AF in ac0

S, SF in ac0

A in ac0

G p

F, GF p WS, WA p 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 (, Σ) |= if |= Σ. All languages from Table 1 with ac0 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. • 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 )}. • KB entails under the intersection of closed repairs (ICR) semantics, if ( , Σ) |= , where = ⋂︀{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()}, asserting 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 (, ) Postdoc(, ) → Researcher (), Postdoc(, ) → Dept ( ), → 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 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 diferent 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 inconsistencytolerant semantics, for a wide range of existential rules, and under diferent 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. [17] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining inconsistency-tolerant query answering 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, Inconsistencytolerant 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 dependencies 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.

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 inconsistent 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 ontologymediated 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 inconsistencytolerant semantics over description logic knowledge bases , in: DL, 2015 .