Inconsistency-tolerant semantics provide meaningful answers to queries posed on possibly inconsistent knowledge bases. Recently, explainability has also become a prominent problem in diferent areas. While the complexity of inconsistency-tolerant semantics is rather well-understood, not much attention has been paid yet to the problem of explaining query answers when inconsistencies may exist. Recent work on existential rules in the inconsistent setting has focused only on understanding why a query is entailed. In this paper, we address another important problem, which is explaining why a quernyotisentailed under an inconsistency-tolerant semantics. In particular, we consider three popular semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs. We discuss recently introduced notions of explanations for this purpose along with a complexity analysis for a wide range of existential rule languages and for several complexity measures.
CEUR ISSN1613-0073
In real ontology-based applications involving large amounts of data, possibly from diferent sources, inconsistency might naturally arise. To provide meaningful answers to users’ queries even in such circumstances, diferent 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 databas1e]sa[nd generalized for several DL2s].[ Two other popular semantics introduced later on are tihnteersection of repairs (IAR) [2] and theintersection of closed repairs (ICR) [3] semantics. Besides beingAR 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 ofline, and then standard query answering can be employed online. In fact, the latter approach has been used to implementIAthRe semantics [4], while for the ICR semantics, it has been observed in5][.
The above semantics’ complexity is rather well-understood in the literature (see, 2e,.g., [ 3, 6, 7, 4, 5] for inconsistency-tolerant query answering in DLs, and, e.8g,.9,,[10, 11, 12] for inconsistency-tolerant query answering under existential rules).
Explainability has recently started to play a prominent role in diferent 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 awlhsoy. It has recently been investigated under both DLs and existential rule1s3[, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]. [14, 15, 16] considered the description logic DL-Lℛiteand defined explanations for positive and negative answers under the brave,AR, and IAR semantics, providing a data complexity analysis of diferent related problems. Although DLs are popular ontology formalisms, rule-based ones are well-suited for data-intensive applications due to their favorable computational properties and expressiveness, especially when considering practical schema modeling, where higher-arity can often be handled through reification [24]. [22] considered explanations of positive query answers in the inconsistent setting under existential rules.
Explaining query answers under inconsistency-tolerant semantics includes the problem of explaining querynon-entailment, which was studied for DLs in16[]. Here, we deal with the problem under existential rules, discussing the notions introduced25i]na[long with the complexity analysis therein. Rather than showing which facts inside the database are in conflict with the entailment of the query, as in16[], our notions of explanation are based on showing how fact removals, needed to restore consistency, cause the query non-entailment. Besides the AR andIAR semantics, we consider theICR semantics as well. The complexity analysis that we discuss concern a wide spectrum of Datal±olganguages under diferent complexity measures.
In this section, we briefly recall some basics on existential rules from the context of Da±ta[l2o6]g. General. We assume a setC of constants, a setN of labeled nulls, and a setV of variables. A term is a constant, null, or variable. We also assume a sperteodficates, each associated with an arity, i.e., a non-negative integer. Aantom has the form( 1, … , ), where is an -ary predicate, and 1, … , are terms. An atom containing only constants is also calflaecdt. aConjunctions of atoms are often identified with the sets of their atoms. An instance is a (possibly infinite) set of atoms( t), where t is a tuple of constants and nulls.dAatabase is a finite instance that contains only constants. hAomomorphism is a substitutionℎ ∶ C ∪ N ∪ V → C ∪ N ∪ V that is the identity onC and mapsN to C ∪ N. With a slight abuse of notation, homomorphisms are applied also to (sets/conjunctions of) atoms.cAonjunctive query (CQ) has the form∃Y( X, Y), where ( X, Y) is a conjunction of atoms without nulls. Tahneswer to over an instance, denoted( ) , is the set of all tupletsover 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; for BCQs, the only possible answer is the empty tuple. A BC Qis true over , denoted ⊧ , if ( ) ≠ ∅ , i.e., there is a homomorphismℎ with ℎ(( Y)) ⊆ .
Dependencies. A tuple-generating dependency (TGD) is a first-order formula of the following form: ∀X∀Y (( X, Y) → ∃Z ( X, Z)), where X, Y, andZ are pairwise disjoint sets of variables, ( X, Y) is a conjunction of atoms, an(dX, Z) is an atom, all without null(s;X, Y) is the body of , denotedbody( ) , while( X, Z) is the head of , denotedhead( ) . For clarity, we consider single-atom-head TGDs; however, our results extend to TGDs with a conjunction of atoms in the head. An instance satisfies , written ⊧ , if the following holds: 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, called the body of and denotedbody() , and⊥ denotes the truth constanftalse. An instance satisfies , written ⊧ , if there isno homomorphismℎ such thatℎ(( X)) ⊆ . For 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 ∧o)f for conjoining atoms. For a class of TGDsℂ, ℂ⊥ denotes the formalism obtained by combiniℂngwith arbitrary NCs. Finite sets of TGDs and NCs are also callperdograms, and TGDs are also callexdistential rules.
The Datalog± languages here considered guaranteeing decidability are among the most frequently analyzed in the literature: lineLa)r[2(6], guarded (G) [27], sticky (S) [28], and acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticWkyS)( [28] and weakly acyclic TGDs W(A) [29], as well as their “full” (i.e., existential-free) proper restrictions linear full L(F), guarded fullG(F), sticky fullS(F), and acyclic full TGDAsF(), respectively, and full TGDs (F) in general. Recall thaLt:⊂ G andF ⊂ WA ⊂ WS. A more detailed overview is in12[]. Knowledge Bases. A knowledge base is a pair (, Σ ), where is a database, andΣ is a program. For a programΣ, Σ andΣNC denote the subsets ofΣ containing the TGDs and NCs of Σ, respectively. The set ofmodels of KB = (, Σ ), denotedmods(KB), is the set of instances { ∣ ⊇ ∧ ⊧ Σ} . We say thatKB is consistent if mods(KB) ≠ ∅, otherwiseKB is inconsistent. The answer to a CQ relative toKB is the set of tuplesans(, KB) = ⋂{( ) ∣ ∈ mods(KB)}. The answer to a BCQ is true, denotedKB ⊧ , if ans(, KB) ≠ ∅. A diferent, however equivalent, way to define ontological query answering is via the concept of tChhease (see, e.g., [27, 30], and references therein). The decision versionCoQf answering is: given a knowledge basKeB, a CQ , and a tuple of constantts, decide whethert ∈ ans(, KB). Since CQ answering can be reduced inlogspace to BCQ answering, we focus on BCQs. We denote by BCQ)(the problem of BCQ answering when restricted over programs belonging t.o
Following Vardi3[
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 dp2 = Σ2 ∧ Πp2 is the class of problems that are a conjunction of a problemΣp2inand one inΠp2.
p Inconsistency-Tolerant Semantics. Three prominent inconsistency-tolerant semantics for ontology-based query answering are thAeBox repair (AR) semantics, its approximation by the intersection of repairs (IAR), and theintersection of closed repairs (ICR) semantics [2, 3]; all three are based on the notion orfepair, which is a maximal consistent subset of the database.
Let KB = (, Σ ) be a knowledge base. Arepair of KB is an inclusion-maximal sub setof such thatmods(, Σ) ≠ ∅ ; Rep(KB) denotes the set of all repairs oKfB. Symmetrically, repairs have also been defined viaculprits, which are inclusion-minimal subsets oftriggering an NC. Repairs are hence obtained by deleting fro mminimal hitting sets of all culpri3ts2,[33, 34].
In general, there might be inconsistent KBnsot admitting any repair. This is the case when Σ itself is “incoherent”, that is, there is no datab asesuch thatmods(, Σ) ≠ ∅ —observe that, by monotonicity, this is equivalent tmoods(∅, Σ) = ∅. In such a case, even deleting the entire database would not be enough to gain back consistency. For this reason, in the rest of the paper, we assume that the program of an inconsistent KB is never “incoherent”. Tclhoesure Cl(KB) of KB, which we denote also aCsl(, Σ) , is the set of all facts built from constant s inandΣ, entailed by and the TGDs ofΣ. Let be a BCQ: • KB entails under the ABox repair (AR) semantics, denotedKB ⊧AR , if (, Σ ) ⊧ for all ∈ Rep(KB). • KB entails under theintersection of repairs (IAR) semantics, denotedKB ⊧IAR , if ( , Σ) ⊧ , where = ⋂ { ∣ ∈ Rep(KB)}. • KB entails under the intersection of closed repairs (ICR) semantics, denotedKB ⊧ICR , if ( , Σ) ⊧ , where = ⋂ {Cl(, Σ) ∣ ∈ Rep(KB)}.
We refer to [9, 12] for more on the complexity oAfR-/IAR-/ICR-query answering.
In the rest of this sectionK,B = (, Σ ) is a KB and a BCQ.
Definition 3.1. A repair deletionof KB is a subset of such that ( ∖ , Σ for every proper subset ′ of , ( ∖ ′, Σ) is inconsistent. ) is consistent and, Example 3.2. Consider the database = { Prof (), Reader (), Chair (), Dean(), PVC()}, asserting that is a professor, a reader, chair (of some department), dean, and pro vice-chancellor. Consider also the program Σ consisting of the TGDs Σ and the NCs ΣNC reported below: Σ = {Prof ( ) →
ΣNC = {Prof ( ), Reader ( ) → ⊥, Prof ( ), Chair ( ), →
Reader ( ), PVC( ) →
Dean( ), Chair ( ) → ⊥, Dean( ), Reader ( ) → ⊥}
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 vice-chancellor, can be elected for 3 years; and finally someone who can be elected for 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 = (, Σ ) is inconsistent and admits the three repairs 1, 2, 3, below, whose corresponding repair deletions are the sets 1, 2, 3, respectively.
1 = {PVC(), Chair (), Prof ()} 1 = {Reader (), Dean()} 2 = {PVC(), Chair (), Reader ()} 2 = {Prof (), Dean()} 3 = {PVC(), Dean(), Prof ()} 3 = {Reader (), Chair ()} .
The next definition introduces (minimal) explanations for query entailment by a1K8B,2[3]. Definition 3.3. An explanationfor w.r.t. KB is a subset of such that (, Σ ) is consistent and (, Σ ) ⊧ . A minimal explanatio n, 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.
Unlike (minimal) explanations i1n8][, we require consistency, as here KBs can be inconsistent. The above concept of minimal explanations is equivalent to thcaatuosfes in [15, 16].
We now define the explanations for query non-entailment by a knowledge base under the AR, IAR, andICR 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 inconsistency-tolerant semantics; to this aim, these explanations are given only in terms of pieces of query MinExes (lost during the reparation). From this perspective, our definitions and the ones by Bienvenu et a[l1.6] 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 query MinExes; these explanations might not include pieces of the query MinExes at all. To give an example, to explAaiRnnon-entailment, both explanation notions witness the presence of a repair not entailing the query: Bienvenu et a[l1.6] explanations provide facts left in the repair that are inconsistent with every query MinEx, whereas we provide facts outside the repair (deleted during the reparation) that intersect every query MinEx—here, is a subset of a repair obtained by a deletion that is a superset .of
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 bcyoansistent 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.
Below, we formally define our notions of explanations, which we aid by illustrating examples.
Intuitively, a query is entailed by a knowledge base under tAhRe semantics if every repair has a MinEx for . An explanation foKrB⊧ A̸R provides a set of facts witnessing the nonentailment of by some repair: a minimal way to restore consistency needs to deleftreom , which leaves no MinEx fo r in the repair yielded by the removal of (a superset of.) Definition 3.4. An explanation forKB⊧ A̸R is a set ℰ = {} , where is a subset of a repair deletion of KB such that, for every MinEx for w.r.t. KB, ∩ ≠ ∅ .
Example 3.5. Consider the knowledge base KB of Theorem 3.2 and the query 1 = CanBeElectedFor(, 3) , asking whether can be elected for 3 years. It is easy to see that 1 is not entailed by KB under the AR semantics. An explanation for KB⊧ A̸R 1 is ℰ1 = {} , where = { Reader(), Chair()} . This explanation says that deleting (at least) from is one way to restore consistency that leaves no MinEx for 1 (i.e., there is a repair not entailing 1).
Intuitively, a query is entailed by a knowledge base under tIhAeR semantics if the repairs have a MinEx for in common. An explanation foKrB⊧I̸AR provides sets of fact s 1, … , explaining why no such common MinEx exists. In particular, whatever MinEfxor is considered among all those in the database, a minimal way of restoring consistency needs to delete from some intersecting , which is then lost in the repair yielded by the removal of (a superset of) , and hence does not appear in the intersection of the repairs. Definition 3.6. An explanation foKrB⊧I̸AR is a set ℰ = { 1, … , }, with ≥ 1 , where the s are subsets of repair deletions of KB such that, for every MinEx for w.r.t. KB, there exists a such that ∩ ≠ ∅.
Example 3.7. Consider the knowledge base KB of Theorem 3.2 and the query 2 = ∃ CanBeElected( ) , asking whether there is someone who can be elected. Query 2 is not entailed by KB under the IAR semantics. An explanation for KB⊧I̸AR 2 is ℰ2 = { 1, 2}, where 1 = {Prof ()} and 2 = {Reader ()} . This explanation says that deleting (at least) 1 or 2 from are two ways to restore consistency; however, each MinEx for 2 is lost either when deleting 1 or 2 (and thus there is no MinEx for 2 common to all repairs).
Intuitively, a query is entailed by a knowledge base under tIhCeR semantics if theclosures of the repairs have a MinEx for in common. An explanation foKrB⊧I̸CR provides sets of facts 1, … , explaining why no such common MinEx exists. In particular, whatever Mi n Efoxr is considered among all those in tchloesure of the database, there is a minimal way of restoring consistency that needs to delete so mefrom , and by doing so every way of derivin gis lost in the repair yielded by the removal of (a superset o f), and hence does not appear in the intersection of the repairs’ closures. Given a finite set of fac ts, denotes the BCQ⋀ ∈ . Definition 3.8. An explanation foKrB⊧I̸CR is a set ℰ = { 1, … , }, with ≥ 1 , where the s are subsets of repair deletions of KB such that, for every MinEx for w.r.t. (Cl(KB), Σ), there exists a such that, for every MinEx for w.r.t. KB, ∩ ≠ ∅.
Notice that(Cl(KB), Σ) might be inconsistent, but every MinEx for w.r.t. (Cl(KB), Σ), and every MinEx for w.r.t. KB, must be consistent (by definition of MinEx). Nonetheless, there might be MinExes for w.r.t. (Cl(KB), Σ) not admitting any (consistent) MinEx fo r w.r.t. KB; such a MinEx , however, cannot belong to the intersection of the repairs’ closures, because if there is no (consistent) MinEx fo r , then cannot appear in the closure of any repair. Example 3.9. Consider Theorem 3.2’s KB and the query 3 = ∃ , CanBeElectedFor ( , ) , asking if there is someone who can be elected for some years, is not entailed by KB under the ICR semantics. The MinExes for 3 in the closure of the database are 1 = {Prof ()} , 2 = {Reader (), PVC()} , 3 = {CanBeElectedFor (, 1)} , and 4 = {CanBeElectedFor (, 3)} . An explanation for KB⊧I̸CR 3 is ℰ3 = { 1, 2}, where 1 = {Prof ()} and 2 = {Reader (), Chair ()} . This explanation says that deleting (at least) 1 or 2 from are two ways of restoring consistency; however, each above cannot be derived anymore when deleting 1 or 2 (thus, there is no MinEx for 3 common to all repair closures). In fact, 1 and 3 cannot be derived when 1 is deleted, while 2 and 4 cannot be derived when 2 is deleted. It is particularly interesting to note why 4 is not derived when 2 is deleted from : the two (minimal) ways of deriving 4, namely 1 = {Prof (), Chair ()} and 2 = {Reader (), PVC()} , are lost, and while the former is a MinEx for 4, and hence an explanation for 3, it is only a non-minimal explanation for 3.
L⊥, LF⊥, AF⊥
S⊥, SF⊥
A⊥
G⊥
F⊥, GF⊥ WS⊥, WA⊥
Data fp-comb. ba-comb. iiinnn ppp dddppp pnddepp22xp dp dp exp ddpp ddpp 2edxp2p
Comb. pspace exp pnexp 2exp exp 2exp
Definition 3.10. For each ∈ { AR, IAR, ICR}, an explanation ℰ = { 1, … , } for KB⊧S̸ is minimalif there is no explanation for KB⊧S̸ that can be derived from ℰ by deleting facts from some or by replacing a pair of distinct and with ∪ .
The two conditions in the previous definition aims at making “minimal” both the facts in each and the overall number of s in ℰ. Notice that if an explanatioℰncontains a “redundant” , that is, ℰ ∖ { } is an explanation, theℰn is not minimal according to the definition above, as we can delete all facts fr o mand still get an explanation, thatℰis′,= ℰ ∖ { } ∪ {∅} is an explanation. In fact, eveℰn ′ is not minimal, as the empty set can be merged with any ot h er in ℰ ′, yielding the (possibly minimal) explanatiℰon∖ { }.
In this paper, we focus on the following decision problems.
Problem: -MinEx⊧ (̸ ), with ∈ { AR, IAR, ICR}.
Input: A knowledge baseKB = (, Σ ) with Σ ∈ , a BCQ , andℰ ⊆ () , with () being the powerset of .
Question: Is ℰ a minimal explanation foKrB⊧S̸ ?
Our complexity results are summarized in Tab1l.eThe complexity ranges from membership in p to 2exp-completeness. For details on how the results have been derived, we refer the reader to [25]. Here we focus on the main takeaways the complexity analysis provides.
First, notice that the three inconsistency-tolerant semantics have the same complexity across all languages and all complexity measures considered in this paper. This is not the case when explaining positive query answers (cf2.2[]): in such a setting, theAR andICR have the same complexity, which is in turn at least as high as the one of ItAhRe semantics.
In the following, we compare explanations for negative and positive query answers (both under inconsistency-tolerant semantics) in terms of the complexity of deciding whether a given set of sets of facts is a minimal explanation, naming the two settings “negative” and “positive”.
The complexity for theAR andICR semantics does not change under the two settings except for the data complexity of first-order rewritable languages (nameLl⊥y,, S⊥, A⊥, and their sublanguages), which is inp for the negative setting and idsp-complete for the positive one. Thus, the complexity of the positive setting is at least as high as the one of the negative setting.
As for the IAR semantics, the complexity does not change under the two settings except for (i) the data complexity oLf⊥ and its generalizations, whichcios-np-complete for the positive setting anddp-complete for the negative one(i;i) the bounded-arity combined complexity Fof , ⊥ L⊥, S⊥, and their specializations, which Πisp2-complete for the positive setting anddp2-complete for the negative one. Thus, in contrast to thAeR andICR semantics, for theIAR semantics the complexity might increase when moving from the positive to the negative setting.
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 diferent complexity measures.
A direction for future work is analyzing the complexity of other related problems, such as deciding whether a fact insecessary (i.e., belonging to every minimal explanationr)eolervant (i.e., belonging to at least one minimal explanation), as don1e5b,1y6[] for DL-Liteℛ. 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. Or considering preferences over repairs, similar to what is done in10[, 11], by also introducing more elaborate mode3l5s, [36, 37, 38], where constraints and compact representations can be consider3e9d,4[0, 41, 42, 43, 44].
Enrico Malizia’s work was supported by the European Union – NextGenerationEU programme, through the Italian Ministry of University and Research (MUR) PRIN 2022-PNRR grant P2022KHTX7 “DISTORT”—CUP: J53D23015000001, under the Italian “National Recovery and Resilience Plan” (PNRR), Mission 4 Component 1.
Cristian Molinaro’s work was supported by the Italian Ministry of University and Research (MUR) PRIN 2022 grant 2022XERWK9 “S-PIC4CHU - Semantics-based Provenance, Integrity, and Curation for Consistent, High-quality, and Unbiased data science”— CUP: H53C24000990006.
Cristian Molinaro acknowledges the support of the PNRR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, under the NRRP MUR program funded by the NextGenerationEU.
The authors have not employed any Generative AI tools. [2] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics for description logics, in: Proc. RR, 2010, pp. 103–117. [3] M. Bienvenu, On the complexity of consistent query answering in the presence of simple ontologies, in: Proc. AAAI, 2012, pp. 705–711. [4] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant query answering in ontology-based data access, J. Web Sem. 33 (2015) 3–29. [5] M. Bienvenu, C. Bourgaux, Inconsistency-tolerant querying of description logic knowledge bases, in: Reasoning Web, 2016, pp. 156–202. [6] M. Bienvenu, R. Rosati, Tractable approximations of consistent query answering for robust ontology-based data access, in: Proc. IJCAI, 2013, pp. 775–781. [7] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: Proc. AAAI, 2014, pp. 996–1002. [8] T. Eiter, T. Lukasiewicz, L. Predoiu, Generalized consistent query answering under existential rules, in: Proc. KR, 2016, pp. 359–368. [9] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering under inconsistency in Datalog+/–, in: Proc. IJCAI, 2018, pp. 1921–1927. [10] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query answering in Datalog+/– under cardinality-based repairs, in: Proc. AAAI, 2019, pp. 2962–2969. [11] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of inconsistency-tolerant query answering in datalog+/– under preferred repairs, in: Proc. KR, 2023, pp. 472–481. [12] 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) 103685. [13] A. Arioua, N. Tamani, M. Croitoru, Query answering explanation in inconsistent Datalog+/– knowledge bases, in: Proc. DEXA, 2015, pp. 203–219. [14] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining query answers under inconsistencytolerant semantics over description logic knowledge bases, in: Proc. DL, 2015. [15] M. Bienvenu, C. Bourgaux, F. Goasdoué, Explaining inconsistency-tolerant query answering over description logic knowledge bases, in: Proc. AAAI, 2016, pp. 900–906. [16] 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. [17] A. Hecham, A. Arioua, G. Stapleton, M. Croitoru, An empirical evaluation of argumentation in explaining inconsistency-tolerant query answering, in: Proc. DL, 2017. [18] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers under existential rules, in: Proc. IJCAI, 2019, pp. 1639–1646. [19] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Explanations for negative query answers under existential rules, in: Proc. KR, 2020, pp. 223–232. [20] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavicius, Explanations for ontologymediated query answering in description logics, in: Proc. ECAI, 2020, pp. 672–679. [21] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavicius, Preferred explanations for ontology-mediated queries under existential rules, in: Proc. AAAI, 2021, pp. 6262–6270. [22] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for inconsistency-tolerant query answering under existential rules, in: Proc. AAAI, 2020, pp. 2909–2916. [23] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Explanations for query answers under existential rules, Artif. Intell. 341 (2025) 104294. [24] A. Calì, D. Calvanese, G. D. Giacomo, M. Lenzerini, A formal framework for reasoning on
UML class diagrams, in: Proc. ISMIS, volume 2366, Springer, 2002, pp. 503–513. [25] T. Lukasiewicz, E. Malizia, C. Molinaro, Explanations for negative query answers under inconsistency-tolerant semantics, in: Proc. IJCAI, 2022, pp. 2705–2711. [26] A. Calì, G. Gottlob, T. Lukasiewicz, A general Datalog-based framework for tractable query answering over ontologies, J. Web Sem. 14 (2012) 57–83. [27] A. Calì, G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, J. Artif. Intell. Res. 48 (2013) 115–174. [28] A. Calì, G. Gottlob, A. Pieris, Towards more expressive ontology languages: The query answering problem, Artif. Intell. 193 (2012) 87–128. [29] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: semantics and query answering,
Theor. Comput. Sci. 336 (2005) 89–124. [30] E. Tsamoura, D. Carral, E. Malizia, J. Urbani, Materializing knowledge bases via trigger graphs, Proc. VLDB Endow. 14 (2021) 943–956. [31] M. Y. Vardi, The complexity of relational query languages, in: Proc. STOC, 1982, pp.
137–146. [32] J. Chomicki, J. Marcinkowski, Minimal-change integrity maintenance using tuple deletions,
Inf. Comput. 197 (2005) 90–121. [33] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, in: Proc. LICS, 2014, pp. 43:1–43:10. [34] G. Gottlob, E. Malizia, Achieving new upper bounds for the hypergraph duality problem through logic, SIAM J. Comput. 47 (2018) 456–492. [35] T. Lukasiewicz, E. Malizia, On the complexity ofCP-nets, in: Proc. AAAI, 2016, pp.
558–564. [36] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation omve)CrP(-nets:
Pareto and majority voting, Artif. Intell. 272 (2019) 101–142. [37] T. Lukasiewicz, E. Malizia, Complexity results for preference aggregation omve)CrP(-nets:
Max and rank voting, Artif. Intell. 303 (2022) art. no. 103636. [38] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract argumentation, in: Proc. IJCAI, 2022, pp. 2517–2524. [39] 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. [40] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query answering under existential rules, Artif. Intell. 312 (2022) 103772. [41] M. Calautti, L. Caroprese, S. Greco, C. Molinaro, I. Trubitsyna, E. Zumpano, Existential active integrity constraints, Expert Syst. Appl. 168 (2021) 114297. [42] 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. [43] E. Malizia, L. Palopoli, F. Scarcello, Infeasibility certificates and the complexity of the core in coalitional games, in: Proc. IJCAI, 2007, pp. 1402–1407. [44] G. Greco, E. Malizia, L. Palopoli, F. Scarcello, On the complexity of compact coalitional games, in: Proc. IJCAI, 2009, pp. 147–152.