Explanations for Negative Query Answers under Existential Rules⋆

Abstract

Ontology-mediated query answering is an extensively studied paradigm, where the conceptual knowledge provided by an ontology is leveraged towards more enhanced querying of data sources. A major advantage of ontological reasoning is its interpretability, which allows one to derive explanations for query answers. Indeed, explanations have a long history in knowledge representation, and have also been investigated for ontology languages based on description logics and existential rules. Existing works on existential rules, however, merely focus on understanding why a query is entailed, i.e., explaining positive query answers. In this paper, we continue this line of research and address another important problem, namely, explaining why a query is not entailed under existential rules, i.e., explaining negative query answers. We consider various problems related to explaining non-entailments from the abduction literature, and also introduce new problems. For all considered problems, we give a detailed complexity analysis for a wide range of existential rule languages and complexity measures.

Keywords

• eol>Ontologies
• Existential rules
• Negative query answering
• Explanations
• Computational complexity

1. Introduction

Ontology-based query answering enhances querying of data sources with an ontology encoding domain knowledge. The idea is to view the ontology and the user query as a composite query, called ontology-mediated query (OMQ), and the task of evaluating such queries is called ontology-mediated query answering (OMQA) [ 2 ]. OMQA is an important paradigm in knowledge representation with many application areas. Description logics (DLs) [ 3 ] and existential rules [ 4, 5 ] are two families of languages commonly used to formulate ontologies.

With the increasing demand for more explainable systems, explanations for OMQA have recently seen a surge in interest. The most basic problem is explaining why a query is entailed, i.e., explaining positive query answers. This problem has been studied for ontology languages based on DLs [ 6, 7, 8, 9 ] and existential rules [ 10 ]. The main idea is viewing an explanation as a set of database facts, which, together with the ontology, are suficient to entail the query.

The complementary problem of explaining why a query is not entailed, i.e., explaining negative query answers, has only been studied for DLs [ 11 ], where the problem is modeled as an abduction task. Abduction has been studied for several formalisms, such as propositional logic [ 12 ], logic programs [ 13 ], default theories [ 14 ], probabilistic temporal logic [ 15 ], and DLs [ 16, 17, 11 ]. The closest work to ours is [ 11 ]: for a given query that is not entailed from the knowledge base, find a set of assertions (avoiding inconsistencies) such that, when added to the ABox, the entailment holds.

In our paper, we continue this line of research, and address the problem of explaining negative answers in OMQA based on existential rules (rather than DLs) as underlying ontology languages. We provide a precise complexity picture of various computational tasks for a wide range of existential rule languages and under diferent complexity measures.

2. Preliminaries

We briefly recall some basics on existential rules from the context of Datalog ± [ 5 ]. 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 ℎ : ∪ N ∪ V ↦→ ∪ N ∪ V that is the identity on and maps N to ∪ 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 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. Classes of TGDs are also known as existential rules, or Datalog± languages in the literature. 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 ifrst-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)) ⊆ . A program (or ontology) is a finite set Σ of TGDs and NCs. An instance 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. For a TGD class C, C⊥ denotes the formalism obtained by combining C with arbitrary NCs.

The Datalog± languages ℒ we consider guaranteeing decidability are among the most frequently analyzed in the literature, namely, linear (L) [ 5 ], guarded (G) [ 4 ], sticky (S) [ 18 ], and acyclic TGDs (A), along with the “weak” (proper) generalizations weakly sticky (WS) [ 18 ] and weakly acyclic TGDs (WA) [ 19 ], 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 [ 20 ] for a more detailed overview.

Ontology-Mediated Query Answering. An ontology-mediated query (OMQ) is a pair (, Σ), where is a query, and Σ is an ontology. Let ℒ be a Datalog± language. If Σ ∈ ℒ, we say that (, Σ) is an ℒ-OMQ. For a database and an OMQ (, Σ), the set mods(, Σ) of models of (, Σ) is the set of instances { | ⊇ ∧ |= Σ}; entails (, Σ), denoted |= (, Σ), if |= for every ∈ mods(, Σ). A diferent way to define the existential rules semantics is via the concept of the Chase (see, e.g., [ 18, 21 ]). We say that (, Σ) is consistent if mods(, Σ) ̸= ∅, otherwise (, Σ) is inconsistent. Ontology-mediated query answering (OMQA) is the task of deciding whether |= (, Σ) for a given database and an OMQ (, Σ). When OMQA(ℒ) is restricted to the case where (, Σ) is consistent, we talk of consistent-OMQA(ℒ).

Following Vardi [ 22 ], 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 as fixed; the data complexity also assumes the query fixed. Table 1 summarizes the complexity results for OMQA in the diferent TGD classes here considered; OMQA(ℒ) denotes the OMQA problem when restricted over ontologies belonging to ℒ.

An OMQ (, Σ) is FO-rewritable, if there exists a query Σ such that, for all databases , we have that |= (, Σ) if |= Σ. In this case, Σ is an FO-rewriting of (, Σ). A class of programs ℒ is FO-rewritable, if it admits an FO-rewriting for every query and program in ℒ. All languages from Table 1 with ac0 data complexity are FO-rewritable. 3. Explanations for Negative Query Answers In this section, we formally define (minimal) explanations for negative query answers in OMQA along with several computational problems for them.

Definition 1. Let be a database, let (, Σ) be an OMQ, with ̸|= (, Σ), and let be a ifnite set of facts. An explanation for ̸|= (, Σ) w.r.t. is a subset of such that (∪, Σ) is consistent and ∪ |= (, Σ). A minimal explanation (or MinEX ) for ̸|= (, Σ) w.r.t. is an explanation for ̸|= (, Σ) w.r.t. that is inclusion-minimal, i.e., no set ′ ⊊ is an explanation for ̸|= (, Σ) w.r.t. .

We now introduce the problems. A constraint on the input of all the problems is that the database and the ℒ-OMQ (, Σ) are such that ̸|= (, Σ).

The first problem is deciding whether a set of facts is a minimal explanation.

Problem: Is-MinEX̸|=(ℒ).

Input: A database , an ℒ-OMQ (, Σ), a finite set of facts , and ⊆ . Question: Is a MinEX for ̸|= (, Σ) w.r.t. ?

Another problem is deciding whether there exists a minimal explanation.

Problem: MinEX-Exists̸|=(ℒ).

Input: A database , an ℒ-OMQ (, Σ), and a finite set of facts .

Question: Is there a MinEX for ̸|= (, Σ) w.r.t. ?

Two other problems are recognizing relevant and necessary facts. A fact is relevant (resp., necessary) for ̸|= (, Σ) w.r.t. if appears in at least one (resp., in every) MinEX for ̸|= (, Σ) w.r.t. .

Problem: MinEX-Rel̸|=(ℒ).

Input: A database , an ℒ-OMQ (, Σ), a finite set of facts , and a fact . Question: Is relevant for ̸|= (, Σ) w.r.t. ? Problem: MinEX-Nec̸|=(ℒ).

Input: A database , an ℒ-OMQ (, Σ), a finite set of facts , and a fact . Question: Is necessary for ̸|= (, Σ) w.r.t. ?

The problems introduced so far are those commonly studied in the context of abductive reasoning and negative answer explanations (see, e.g., [ 11 ]). We here introduce two novel problems. The first asks whether a set ′ of facts contains exactly all the relevant facts. This set is particularly interesting, as ′ can be seen as a minimal over-approximation of all MinEXs, i.e., for every MinEX , it holds that ⊆ ′, and ′ is the smallest set enjoying this property. Problem: MinEX-AllRel̸|=(ℒ).

Input: A database , an ℒ-OMQ (, Σ), a finite set of facts , and ′ ⊆ . Question: Does ′ contain exactly all the relevant facts for ̸|= (, Σ) w.r.t. ?

The second novel problem that we consider asks whether a set ′ contains exactly all the necessary facts. Interestingly, ′ can be seen as a maximal under-approximation of all MinEXs, i.e., for every MinEX , it holds that ′ ⊆ , and ′ is the biggest set enjoying this property. Problem: MinEX-AllNec̸|=(ℒ).

Input: A database , an ℒ-OMQ (, Σ), a finite set of facts , and ′ ⊆ . Question: Does ′ contain exactly all the necessary facts for ̸|= (, Σ) w.r.t. ? 4. Is-MinEX̸|=and MinEX-Exists̸|= We start with Is-MinEX̸|=(ℒ), i.e., deciding whether a given set of facts is a minimal explanation for a negative query answer. The following theorem proves all upper bounds in Table 2. The intuition behind the result is: deciding whether a set of facts is a MinEX requires to carry out essentially three tasks: (1) deciding whether ( ∪ , Σ) is consistent; (2) deciding whether ∪ |= (, Σ); and (3) deciding whether is inclusion-minimal.

Theorem 2. For any language ℒ here considered, if OMQA(ℒ) is in in the combined (resp., ba-comb., fp-comb., data) complexity, then Is-MinEX̸|=(ℒ) can be decided with a check and a linear number of co- checks in the combined (resp., ba-comb., fp-comb., data) complexity.

All the hardness results for Is-MinEX̸|=(ℒ) in Table 2 descend from the hardness of deciding minimal explanations of positive query answers [ 10 ].

We now focus on MinEX-Exists̸|=(ℒ), i.e., deciding the existence of (minimal) explanations for negative query answers. The following theorem proves all the upper bounds in Table 2, but the np and p ones, that need tighter statements. Intuitively, to decide whether there exists a minimal explanation for a negative query answer, it sufices to check whether there is any explanations for the negative query answers, i.e., there is no need to double check the minimality. Theorem 3. For any language ℒ here considered, if OMQA(ℒ) is in in the combined (resp., ba-comb., fp-comb., data) complexity, then MinEX-Exists̸|=(ℒ) is in np in the combined (resp., ba-comb., fp-comb., data) complexity.

In the fp-combined setting, for the Datalog± languages here considered, checking whether a set of facts is consistent is feasible in p, because the negative constraints are fixed. This allows to obtain the following tighter result.

Theorem 4. MinEX-Exists̸|=(ℒ) is in np in the fp-combined complexity for all the languages ℒ here considered. Data fp-comb. ba-comb. Comb. iiinnndddpppppp ddddddpppppp222222 p2endddexexppp222xppp pp22seepneexxaexxxppcpppe

For FO-rewritable languages, the MinEXs for positive query answers when the query and the program are fixed can be computed in polynomial time [ 10 ]. By using this property, we can obtain the p upper bounds in Table 2.

Theorem 5. If ℒ is FO-rewritable language, then MinEX-Exists̸|=(ℒ) is in p in the data complexity.

For the hardness results, the np-hardness results in the data complexity are via a reduction from Sat; the hardness results in the fp-comb., ba-comb., and combined complexity, but the Σp2-hardness and the pnexp-hardness, are obtained via a reduction from OMQA(ℒ) to MinEX-Exists̸|=(ℒ); the Σp2-hardness and the pnexp-hardness results are shown, respectively, via reductions from QBF validity and from the problem ETP [ 23 ]: 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 . 5. MinEX-Rel̸|=and MinEX-AllRel̸|= We start by looking at the problem MinEX-Rel̸|=(ℒ) of deciding whether a fact is relevant. The following theorem proves all the upper bounds in Table 3, but those in the data complexity for FO-languages. Intuitively, to decide whether is relevant, it sufices to guess a set of facts containing (feasible in np), and then, via an oracle call, check that is a minimal explanation. Theorem 6. For any language ℒ here considered, if Is-MinEX̸|=(ℒ) is in in the combined (resp., ba-comb., fp-comb., data) complexity, then MinEX-Rel̸|=(ℒ) is in np in the combined (resp., ba-comb., fp-comb., data) complexity.

By a consideration similar to that for Theorem 5 we obtain the following.

Theorem 7. If ℒ is FO-rewritable language, then MinEX-Rel̸|=(ℒ) is in p in the data complexity.

All the hardness results for MinEX-Rel̸|=(ℒ) in Table 3 descends from the hardness of deciding the fact relevance in MinEXs of positive query answers [ 10 ].

We now analyze the problem MinEX-AllRel̸|=(ℒ) of deciding whether a set contains all and only the relevant facts. The following theorem proves all the upper bounds in Table 3. Intuitively, ′ is the set of all and only the relevant facts if all facts in ′ are relevant and all facts outside ′ are not relevant.

Theorem 8. For any language ℒ here considered, if MinEX-Rel̸|=(ℒ) is in in the combined (resp., ba-comb., fp-comb., data) complexity, then MinEX-AllRel̸|=(ℒ) can be decided with a check and a co- in the combined (resp., ba-comb., fp-comb., data) complexity.

As for the hardness, the dp-hardness and the dp2-hardness results are shown via reductions, respectively, from the Sat-Unsat problem and its generalization to the second level, i.e., decide the validity of two QBF formulas Φ = ∃∀ ¬(, ) and Ψ = ∀∃ (, ) (to simplify the reduction, and are assumed to be the same in and [ 24 ]). The remaining hardness results are obtained via a reduction from MinEX-Exists̸|=(ℒ) to MinEX-AllRel̸|=(ℒ). 6. MinEX-Nec̸|=and MinEX-AllNec̸|= We now focus on the problem MinEX-Nec̸|=(ℒ) of deciding whether a fact is necessary. The following theorem proves all upper bounds in Table 4, but the co-np and p ones. Intuitively, we can disprove that a fact is necessary by checking that there is a (non-necessarily minimal) explanation excluding .

Theorem 9. For any language ℒ here considered, if OMQA(ℒ) is in in the combined (resp., ba-comb., fp-comb., data) complexity, then MinEX-Nec̸|=(ℒ) is in co-(np) in the combined (resp., ba-comb., fp-comb., data) complexity.

By a consideration similar to that for Theorem 4 we obtain the following.

Theorem 10. For any language ℒ here considered, MinEX-Nec̸|=(ℒ) is in co-np in the fp-combined complexity.

By a consideration similar to that for Theorem 5 we obtain the following.

Theorem 11. If ℒ is FO-rewritable language, then MinEX-Nec̸|=(ℒ) is in p in the data complexity.

The hardness results of MinEX-Nec̸|=(ℒ) can be proven via a reduction from the complement of MinEX-Exists̸|=(ℒ) to MinEX-Nec̸|=(ℒ).

We now study the problem MinEX-AllNec̸|=(ℒ) of deciding whether a set contains all and only the necessary facts. The following theorem proves all upper bounds in Table 4. Intuitively, ′ is the set of all and only the necessary facts if all facts in ′ are necessary and all facts outside ′ are not necessary.

Theorem 12. For any language ℒ here considered, if MinEX-Nec̸|=(ℒ) is in in the combined (resp., ba-comb., fp-comb., data) complexity, then MinEX-AllNec̸|=(ℒ) can be decided by a check in and a check in co- in the combined (resp., ba-comb., fp-comb., data) complexity.

As for the hardness, the dp-hardness and the dp2-hardness results are shown via reductions from the Sat-Unsat problem and its second level generalization (see above), respectively. The remaining hardness results are proven via a reduction from MinEX-Exists̸|=(ℒ) to the complement of MinEX-AllNec̸|=(ℒ).

7. Summary and Outlook

We have addressed the problem of explaining why a query is not entailed in OMQA under existential rules. We have conducted a detailed complexity analysis for various explanation problems, for a wide range of existential rule languages and under diferent complexity measures.

Our work on explaining OMQA has been extended to the inconsistent setting [ 25, 26 ] and to preferred explanations [27]. The explanation notion, in line with the inconsistent setting above, can also be extended to the cases of cardinality-based repairs [28], generalized repairs [29], preferred repairs [30, 31], probabilistic approaches [32, 33], and repairs based on value updates [34]. Inspired by the idea of exploring preferences over explanations, we can also consider how more elaborate preference models can be included in this framework [35, 36, 37, 38]. Another interesting direction for future work is actually computing all explanations or relevant/necessary facts.

Acknowledgments References

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. [27] İ. İ. Ceylan, T. Lukasiewicz, E. Malizia, C. Molinaro, A. Vaicenavičius, Preferred explanations for ontology-mediated queries under existential rules, in: Proc. AAAI, 2021, pp. 6262–6270. [28] 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. [29] T. Lukasiewicz, E. Malizia, C. Molinaro, Complexity of approximate query answering under inconsistency in Datalog± , in: Proc. IJCAI, 2018, pp. 1921–1927. [30] S. Flesca, F. Furfaro, F. Parisi, Preferred database repairs under aggregate constraints, in:

Proc. SUM, 2007, pp. 215–229. [31] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Preference-based inconsistency-tolerant query answering under existential rules, Artif. Intell. 312 (2022) art. no. 103772. [32] M. Calautti, S. Greco, C. Molinaro, I. Trubitsyna, Query answering over inconsistent knowledge bases: A probabilistic approach, Theor. Comput. Sci. 935 (2022) 144–173. [33] J. Grant, F. Parisi, A. Parker, V. S. Subrahmanian, An agm-style belief revision mechanism for probabilistic spatio-temporal logics, Artif. Intell. 174 (2010) 72–104. [34] G. Alfano, S. Greco, C. Molinaro, I. Trubitsyna, An approximation algorithm for querying inconsistent knowledge bases, Intell. Syst. Appl. (2022) art. no. 200146. [35] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On preferences and priority rules in abstract argumentation, in: Proc. IJCAI, 2022, pp. 2517–2524. [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] 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.

References

[1] İ. İ. Ceylan , T. Lukasiewicz , E. Malizia , C. Molinaro , A. Vaicenavičius , Explanations for negative query answers under existential rules , in: Proc. KR , 2020 , pp. 223 - 232 .

[2] M. Bienvenu , B. T. Cate , C. Lutz , F. Wolter , Ontology-based data access: A study through disjunctive Datalog, CSP, and MMSNP , ACM T. Database Syst. 39 ( 2014 ) 33 : 1 - 33 : 44 .

[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] A. Calì , G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints , J. Artif. Intell. Res . 48 ( 2013 ) 115 - 174 .

[5] A. Calì , G. Gottlob, T. Lukasiewicz , A general Datalog-based framework for tractable query answering over ontologies , J. Web Sem . 14 ( 2012 ) 57 - 83 .

[6] M. Horridge , B. Parsia , U. Sattler, Laconic and precise justifications in OWL , in: Proc. ISWC , 2008 , pp. 323 - 338 .

[7] R. Peñaloza , B. Sertkaya , Understanding the complexity of axiom pinpointing in lightweight description logics , Artif. Intell . 250 ( 2017 ) 80 - 104 .

[8] A. Borgida , D. Calvanese , M. Rodriguez-Muro , Explanation in the DL-Lite family of description logics , in: Proc. OTM , 2008 , pp. 1440 - 1457 .

[9] İ. İ. Ceylan , T. Lukasiewicz , E. Malizia , A. Vaicenavičius , Explanations for ontologymediated query answering in description logics , in: Proc. ECAI , 2020 , pp. 672 - 679 .

[10] İ. İ. Ceylan , T. Lukasiewicz , E. Malizia , A. Vaicenavičius , Explanations for query answers under existential rules , in: Proc. IJCAI , 2019 , pp. 1639 - 1646 .

[11] D. Calvanese , M. Ortiz , M. Šimkus , G. Stefanoni, Reasoning about explanations for negative query answers in DL-Lite , J. Artif . Intell. Res . 48 ( 2013 ) 635 - 669 .

[12] T. Eiter , G. Gottlob, The complexity of logic-based abduction , J. ACM 42 ( 1995 ) 3 - 42 .

[13] T. Eiter , G. Gottlob, N. Leone , Semantics and complexity of abduction from default theories , Artif. Intell . 90 ( 1997 ) 177 - 223 .

[14] T. Eiter , G. Gottlob, N. Leone , Abduction from logic programs: Semantics and complexity , Theor. Comput. Sci . 189 ( 1997 ) 129 - 177 .

[15] C. Molinaro , A. Sliva , V. S. Subrahmanian , Super-solutions: Succinctly representing solutions in abductive annotated probabilistic temporal logic , ACM Trans. Comput. Log . 15 ( 2014 ) 18 : 1 - 18 : 35 .

[16] J. Du , K. Wang , Y. Shen , A tractable approach to ABox abduction over description logic ontologies , in: Proc. AAAI , 2014 , pp. 1034 - 1040 .

[17] S. Klarman , U. Endriss , S. Schlobach, ABox abduction in the description logic ℒ , J. Autom. Reasoning 46 ( 2011 ) 43 - 80 .

[18] A. Calì , G. Gottlob , A. Pieris , Towards more expressive ontology languages: The query answering problem , Artif. Intell . 193 ( 2012 ) 87 - 128 .

[19] R. Fagin , P. G. Kolaitis , R. J. Miller , L. Popa , Data exchange: Semantics and query answering , Theor. Comput. Sci . 336 ( 2005 ) 89 - 124 .

[20] 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 .

[21] E. Tsamoura , D. Carral , E. Malizia , J. Urbani , Materializing knowledge bases via trigger graphs , Proc. VLDB Endow . 14 ( 2021 ) 943 - 956 .

[22] M. Y. Vardi , The complexity of relational query languages , in: Proc. STOC , 1982 , pp. 137 - 146 .

[23] T. Eiter , T. Lukasiewicz , L. Predoiu, Generalized consistent query answering under existential rules , in: Proc. KR , 2016 , pp. 359 - 368 .

[24] T. Lukasiewicz , E. Malizia , A novel characterization of the complexity class Θ based on counting and comparison , Theor. Comput. Sci . 694 ( 2017 ) 21 - 33 .

[25] T. Lukasiewicz , E. Malizia , C. Molinaro , Explanations for inconsistency-tolerant query answering under existential rules , in: Proc. AAAI , 2020 , pp. 2909 - 2916 .

[26] T. Lukasiewicz , E. Malizia , C. Molinaro , Explanations for negative query answers under inconsistency-tolerant semantics , in: Proc. IJCAI , 2022 , pp. 2705 - 2711 .