--- title: "Explanations for Query Answers under Existential Rules" authors: - "İsmail İlkan Ceylan" - "Thomas Lukasiewicz" - "Enrico Malizia" - "Andrius Vaicenavičius" doi: "10.24963/ijcai.2019/227" url: "https://ijcai.org/proceedings/2019/227" pdf: "https://ijcai.org/proceedings/2019/0227.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "1639-1646" track: "Main track" keywords: - "Knowledge Representation and Reasoning: Description Logics and Ontologies" - "Knowledge Representation and Reasoning: Logics for Knowledge Representation" - "Knowledge Representation and Reasoning: Knowledge Representation Languages" --- # Explanations for Query Answers under Existential Rules İsmail İlkan Ceylan, Thomas Lukasiewicz, Enrico Malizia, Andrius Vaicenavičius *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 1639-1646. DOI: [10.24963/ijcai.2019/227](https://doi.org/10.24963/ijcai.2019/227) ## Abstract Ontology-mediated query answering is an extensively studied paradigm, which aims at improving query answers with the use of a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for query answers. Surprisingly, however, explaining answers for ontology-mediated queries has received little attention for ontology languages based on existential rules. In this paper, we close this gap, and study the problem of explaining query answers in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations under existential rules. ## Full text ## 1 Introduction Ontology-based data access (OBDA) is a popular paradigm in knowledge representation and reasoning [Poggi et al., 2008]. The main goal is to facilitate access to possibly heterogeneous and incomplete data sources based on a logical theory. This is achieved via an ontology that enriches the user query, typically a union of conjunctive queries, with commonsense knowledge. In this framework, the ontology and the user query are viewed as two components of one composite query, called ontologymediated query (OMQ) [Bienvenu et al., 2014]. The task of evaluating such queries is then called ontology-mediated query answering (OMQA). Ontology languages are mostly fragments of first-order logic (FOL), which result from a simple trade-off between the expressivity of the language and the computational complexity of reasoning in the language. As a form of first-order entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for query answers. Explanations are widely considered as an essential component of scientific progress. The fact that many recent artificial intelligence systems operate mostly as a black box has led some serious concerns; see, e.g., [Došilovi´c et al., 2018], for a recent survey. ∗Contact Author Description logics (DLs) [Baader et al., 2007] and existential rules [Calì et al., 2012b; Calì et al., 2013; Calì et al., 2012a], together, encompass the most widely used knowledge representation languages in the context of ontology-mediated query answering. Ontologies have found applications in data exchange [Fagin et al., 2005], medical diagnosis [BertaudGounot et al., 2012], and life sciences [Bard and Rhee, 2004], all of which can potentially benefit from explanations. In fact, there has been a significant amount of interest in tracking down and understanding the causes of various types of entailments in DL ontologies. A prominent approach is to identify explanations in terms of a subset of the axioms in the ontology [Kalyanpur et al., 2007; Baader and Suntisrivaraporn, 2008]. The benefit of this approach is that it allows us to abstract away from the particular proof technique used to derive an entailment, and hence to pinpoint the sets of axioms that are responsible for an entailment. Such explanation sets are, furthermore, required to be minimal with respect to some order, like subset, cardinality, or preference order. These explanations are called justifications [Kalyanpur et al., 2007; Horridge et al., 2008; Suntisrivaraporn et al., 2008], and the overall approach is also known as axiom pinpointing in the DL literature [Horridge et al., 2009; Baader and Suntisrivaraporn, 2008]. Earlier work on axiom pinpointing, however, is exclusively based on standard reasoning tasks, and hence on deriving explanations based on the axioms of the ontology. Indeed, there is very little work in the direction of explaining query entailments. To date, the only works in explaining query answers is given for the DL-Lite family of languages [Borgida et al., 2008; Bienvenu et al., 2019], as we elaborate later, in detail. Surprisingly, explanations are not studied in the context of existential rules. In the present paper, we close this gap and study the problem of explaining query answers under existential rules. More specifically, given an OMQ, we are interested in explaining this compound query in terms of the minimal satisfying subsets of a given database. Such a minimal subset of the database is called a minimal explanation, or simply MinEX. Incorporating ideas from axiom pinpointing [Peñaloza and Sertkaya, 2017], we introduce a class of problems based on the notion of minimal explanation. We conduct a detailed complexity analysis for each of the problems introduced, and provide a host of complexity results that cover a representative set of existential rules. Our results extend naturally to other existential rule languages. All the proof details can be found in the extended version of this paper available from the authors. ## 2 Preliminaries We give a brief overview on existential rules and the paradigm of ontology-mediated query answering [Calì et al., 2012b; Calì et al., 2013; Calì et al., 2012a], and also give some complexitytheoretic background relevant to our study. ## 2.1 First-Order Logic We consider a relational vocabulary consisting of mutually disjoint, possibly infinite sets R, V, and C of predicates, variables, and constants, respectively. A term is either a constant or a variable. An atom is an expression of the form p(t1, . . . , tn), where p is an n-ary predicate, and t1, . . . , tn are terms. A ground atom (or fact) has only constants as terms. A first-order formula is built as usual from atoms over the given vocabulary, truth constants ⊤, ⊥, operators ¬, ∨, ∧, →, and quantifiers ∃, ∀. A quantifier-free formula is a formula that does not use quantifiers. A variable in a formula is quantified (or bound), if it is in the scope of a quantifier; otherwise, it is free. A sentence is a formula without any free variables. The semantics of FOL is given by means of interpretations I = (∆I , ·I ), where ∆I is a possibly infinite domain, and ·I is an interpretation function that maps every constant a to a domain element aI ∈ ∆I , every predicate p with arity n to a relation pI ⊆ (∆I )n . A sentence Φ is satisfied by an interpretation I, if I |= Φ, where |= is the standard first-order entailment relation. A (first-order) theory Σ is a (finite) set of first-order formulas. An interpretation I is a model of a theory Σ, denoted I |= Σ, if I satisfies all Φ ∈ Σ. Σ entails a sentence Φ, written Σ |= Φ, if all models of Σ are also models of Φ. ## 2.2 Existential Rules A tuple-generating dependency (TGD) is a first-order formula of the form where Φ(X) is a conjunction of atoms, called the body of the TGD, and Ψ(X,Y) is a conjunction of atoms, called the head of the TGD. Classes of TGDs are also known as existential rules, or Datalog± languages in the literature. A program (or an ontology) is a finite set Σ of TGDs. TGDs can express the inclusion and join dependencies of databases. In its general form, however, reasoning with TGDs is undecidable [Beeri and Vardi, 1981], but there are a plethora of decidable fragments of TGDs. We review some known (syntactic) restrictions on TGDs that ensure decidability (and even tractability in most cases). A TGD is guarded, if there exists a body atom that contains (or "guards") all body variables. The class of guarded TGDs, denoted G, is defined as the family of all possible sets of guarded TGDs. A key subclass of guarded TGDs are the linear TGDs with just one body atom. The class of linear TGDs is denoted by L. It is easy to verify that L ⊂ G. Stickiness enforces the following property: variables that appear more than once in a body (i.e., join variables) must always be propagated (or "stick") to the inferred atoms [Calì et al., 2012b]. A TGD that enjoys this property is called sticky, and the class of sticky TGDs is denoted by S. Weak stickiness generalizes stickiness by considering only "harmful" variables, and defines the class WS of weakly sticky TGDs. Observe that S ⊂ WS. Table 1: Complexity of OMQA under existential rules. | L | Data | fp-comb. | ba-comb. | Comb. | |-----------|--------|------------|------------|---------| | L, LF, AF | ≤ AC0 | NP | NP | PSPACE | | S, SF | ≤ AC0 | NP | NP | EXP | | A | ≤ AC0 | NP | NEXP | NEXP | | G | P | NP | EXP | 2EXP | | F, GF | P | NP | NP | EXP | | WS, WA | P | NP | 2EXP | 2EXP | A set of TGDs is acyclic and belongs to the class A if its predicate graph is acyclic. Equivalently, an acyclic set of TGDs can be seen as a non-recursive set of TGDs. A set of TGDs is weakly acyclic, if its predicate graph enjoys a certain acyclicity condition, which guarantees the existence of a finite canonical model; the associated class is denoted WA. It is known that A ⊂ WA ⊂ WS [Calì et al., 2012b]. The class of full TGDs do not contain any existentially quantified variables. The corresponding class is denoted by F. Restricting full TGDs to satisfy linearity, guardedness, stickiness, or acyclicity yields the classes LF, GF, SF, and AF, respectively. It is known that F ⊂WA [Fagin et al., 2005]. ## 2.3 Ontology-Mediated Query Answering A database D is a finite set of facts over a (finite) relational vocabulary. A conjunctive query (CQ) is an existentially quantified formula ∃XΦ(X,Y), where Φ(X,Y) is a conjunction of atoms over the set of variables X and Y; a union of conjunctive queries (UCQ) is a disjunction of CQs (over the same free variables). A query is Boolean if it is a sentence. The paradigm of ontology-mediated query answering generalizes query answering over databases by incorporating additional background knowledge in terms of an ontology. Formally, an ontology-mediated query (OMQ) is a pair (Q,Σ), where Q is a Boolean query, and Σ is an ontology. Given a database D and an OMQ (Q,Σ), we say that D entails the OMQ (Q,Σ), denoted D |= (Q,Σ), if for all models I |= Σ ∪ D it holds that I |= Q, where |= is first-order entailment under the standard name assumption. Ontologymediated query answering (OMQA) is the task of deciding whether D |= (Q,Σ) for a given database D and an OMQ (Q, Σ). A key paradigm in OMQA is the FO-rewritability of queries: an OMQ (Q,Σ) is FO-rewritable, if there exists a Boolean UCQ QΣ such that, for all databases D that are consistent relative to Σ, we have that D |= (Q, Σ) iff D |= QΣ. In this case, QΣ is called an FO-rewriting of (Q,Σ). A class of programs L is FO-rewritable, if it admits an FO-rewriting for any UCQ and program in L. All languages from Table 1 with AC0 data complexity are FO-rewritable. In our complexity analysis, we make the standard assumptions [Vardi, 1982]: the combined complexity of query answering is calculated by considering all the components, i.e., the database, the program, and the query, as part of the input. The bounded-arity combined complexity (or simply ba-combined complexity) assumes that the maximum arity of the predicates in R is bounded by an integer constant. The fixed-program combined complexity (or simply fp-combined complexity) is calculated by considering the ontology as fixed. Finally, the data complexity is calculated by considering the database as the input, i.e., everything else is fixed. Table 1 summarizes the known complexity results for OMQA in the different classes of TGDs that we consider. The most relevant complexity classes for our analysis and their relations are given as follows: where DExp denotes the class NEXP ∧ CONEXP. ## 3 Explanations for Query Answers In our framework, an explanation is given in terms of a set of database facts, and we are interested in a minimal set of facts that entail a given OMQ. The following definition is a natural extension of those related to axiom pinpointing [Peñaloza and Sertkaya, 2017] to ontology-mediated query answering. Definition 1 (MinEX). For a database D and an OMQ (Q, Σ), where Σ is a set of existential rules, and Q is a query, an explanation for (Q, Σ) in D is a subset E ⊆ D of facts such that E |= (Q, Σ). A minimal explanation E, or MinEX, for (Q, Σ) in D is an explanation for (Q, Σ) in D that is subsetminimal, i.e., there is no proper subset E′ ⊊ E that is an explanation for (Q, Σ) in D. When the OMQ (Q, Σ) and the database D are clear from the context, we simply speak about MinEXs without explicitly mentioning (Q, Σ) or D. We provide a running example that will be used along the paper to illustrate the different problems studied. Briefly stated, the notion of minimal explanations and the associated problems are closely related to minimal hitting set problems [Gainer-Dewar and Vera-Licona, 2017; Gottlob and Malizia, 2018], which appears naturally in several domains. Our running example is from the field of computational biology, motivated by experimental design for protein networks [Klamt et al., 2009; Ramadan et al., 2004]. Example 2. Let us consider the protein containment scenario illustrated in Figure 1. In this example, we are interested in identifying proteins p1, . . . , p6 in relation to the complexes c1, c2, and c3. We want to find a minimal subset of proteins that covers all complexes, i.e., a minimal subset of proteins that has at least one representative from each complex. We can express this problem as an OMQ in a way that every answer to this problem is in bijection with a minimal explanation of the OMQ as follows. We define the database: Figure 1: Protein containment in complexes, where proteins are given as p1, . . . , p6 and complexes c1, c2, and c3 are color-coded (as shown on the left-hand side). ![Image](https://ijcai.org/proceedings/2019/fulltext/227/image_000000_c607ab78099c6deaf1bda5758c174324efcbe5131ab0551509b38e6fd12ee8c3.png) which encodes the set of proteins, and the OMQ {Qp, Σp}: The ontology encodes the relation between proteins and complexes, and the query asks whether all complexes c1, c2, and c3 are covered. Consider now a subset E ⊆ Dp. Then, it is easy to verify that E |= (Qp,Σp) iff E |= {covered(ci),Σp}, for every complex ci. Thus, MinEXs for {Qp, Σp} in Dp are in bijection with minimal protein covers of complexes. We focus on this running example throughout the paper due to its simplicity. ## 4 RecognizingMinimal Explanations In this section, we study the fundamental decision problem for MinEXs of deciding whether a given subset of a database is a minimal explanation. This is a natural decision version of the search problem of finding a MinEX. Problem: IS-MINEX(UCQ,L) Input: A database D, an OMQ (Q, Σ), where Q is a UCQ and Σ is from the class L of TGDs, and a set of facts E ⊆ D. Question: Is E a MinEX for (Q, Σ) in D? IS-MINEX is the most basic problem that is studied in this paper, and serves as a baseline for the other problems. As all the remaining problems studied, IS-MINEX is parametrized with a query language. Let us illustrate this problem in our running example. Example 3. Recall the database Dp. Observe that the subsets of the database Dp are MinEXs for the OMQ (Qp, Σp), and give the minimal protein covers of complexes. However, {protein(p4), protein(p5), protein(p6)} is not a MinEX, as it does not cover all complexes and thus does not entail (Qp,Σp). The set {protein(p1), protein(p2), protein(p3)} entails (Qp,Σp), but it is not a MinEX, since it is not minimal (i.e., protein(p2) can be removed without affecting the satisfaction). Table 2: Complexity results for IS-MINEX(UCQ,L). | L | Data | fp-comb. | ba-comb. | Comb. | |-----------|--------|------------|------------|---------| | L, LF, AF | ≤ P | DP | DP | PSPACE | | S, SF | ≤ P | DP | DP | EXP | | A | ≤ P | DP | DExp | DExp | | G | P | DP | EXP | 2EXP | | F, GF | P | DP | DP | EXP | | WS, WA | P | DP | 2EXP | 2EXP | First, we present a general algorithm for deciding IS-MINEX(UCQ,L). Assume that OMQA in L is in the class C. Then, IS-MINEX(UCQ,L) can be decided by one C check and a polynomial number of co-C checks as follows: testing whether E is a MinEX involves checking whether E entails (Q, Σ), and checking whether E is minimal. The entailment can be checked with a single call to C. To check minimality of E, it is enough to show that removing any element e of E gives a set that does not entail (Q, Σ). Therefore, we need to carry out a polynomial number of non-entailment checks, each in co-C. Hence, we state the following result. Theorem4. IS-MINEX(UCQ,L) can be decided by a single C check, followed by a polynomial number of co-C checks, where C is the complexity of OMQA in L. As a consequence of Theorem 4, we are able to claim all membership results given in Table 2. For example, OMQA in the language G is NP-complete. That is, we need to make an NP test (entailment) followed by polynomially many CONP tests (non-entailment) to decide IS-MINEX(UCQ, G). Clearly non-entailment tests can also be combined into a single CONP test, which implies that the overall procedure is in DP. Similar arguments apply to other languages considered. Therefore, in the rest of this section, we only need to show that these upper bounds are also matching lower bounds for IS-MINEX, as shown in Table 2. First, we show that IS-MINEX(UCQ, L) is DP-hard in fp-combined complexity even for FO-rewritable languages. Theorem 5. IS-MINEX(UCQ,L) is DP-hard for languages L ∈ {LF, AF, SF} in fp- and ba-combined complexity. This result implies that IS-MINEX(UCQ,L) is DP-hard for all considered languages in fp-, ba- combined complexity as a consequence of the inclusions between the languages. This result is obtained by a reduction from the canonical DP-complete problem SAT-UNSAT, which asks, given two 3CNF formulas, whether the first is satisfiable, and the second is unsatisfiable. In the construction, the database contains facts encoding satisfying assignments of clauses for both formulas and facts enforcing the consistency of the assignments. There is an additional fact, which is a kind of jolly, allowing to satisfy the second formula, bypassing the constraints of the consistency in the assignments. In this way, the jolly is required in a MinEX iff the second formula is not satisfiable. The program is empty, therefore, it applies to all languages. The query ensures that there exists a MinEX iff the first formula is satisfiable and the second is unsatisfiable. Note that many hardness results are a consequence of the hardness of OMQA in the given languages; see, e.g., Table 1. The only case that is not covered by the given results is hence IS-MINEX(UCQ, A) in ba- and combined complexity. The matching lower bound is shown in the following result. Theorem 6. IS-MINEX(UCQ, A) is DExp -hard in ba-combined complexity. This reduction is from a DExp -complete problem, inspired by the construction given in [Eiter et al., 2016]. The problem is a variant of the tiling problem, which is NEXP-complete. Formally, given a tuple (w1,w2,TP1,TP2), where w1 and w2 are initial tiling conditions, and TP1 and TP2 are two tiling problems for the exponential square 2n × 2n , decide whether TP1 has no solution with w1, and TP2 has a solution with w2. The main intuition behind the proof is as follows. We encode the tiling problem in the program Σ. This program is designed in such a way that, together with a database encoding the adjacency rules and the initial condition, Σ entails an atom tiling i iff TPi has a solution with wi. The construction ensures the following. If TP1 has a solution with w1, then tiling 1 can be derived from the rules in Σ1 , and hence there is no need to include the atom tiling 1 in E to entail the query. Hence, E is a MinEX iff TP1 has no solution with w1 and TP2 has a solution with w2. We observe that IS-MINEX remains tractable in data complexity. In all other cases, IS-MINEX has either the same computational complexity as OMQA (for deterministic classes) or has a higher computational complexity (for non-deterministic classes). This concludes our analysis for IS-MINEX. ## 5 Set of All Minimal Explanations In this section, we analyze the problem of deciding whether a given set of subsets of a database is the set of all MinEXs. Problem: ALL-MINEX(UCQ, L) Input: A database D, an OMQ (Q, Σ), where Q is a UCQ and Σ is from the class L of TGDs, and a set E ⊆ P(D). Question: Is E the set of all MinEXs for (Q, Σ) in D? Example 7. Suppose that we are interested in knowing whether a given set of proteins are all possible minimal covers of complexes. Consider the set E given as: It is easy to verify that E is precisely the set of all MinEXs for (Qp, Σp) in Dp. As before, we start with a rather general result for ALL-MINEX(UCQ,L), where by C, we represent the complexity of OMQA in L. We show that it is sufficient to perform a polynomial number of C checks and a single co-(NPC ) check. More specifically, given a set E of subsets of the database, to decide ALL-MINEX(UCQ, L), we can proceed as follows. We perform a polynomial number of C checks to decide whether all sets in E entail (Q, Σ). Then, we need to decide whether all sets in E are minimal, and there is no MinEX that is not in E. This holds if there is no E′ ⊆ D entailing (Q, Σ) such that E′ ̸⊆ E for all E ∈ E. The complement task of guessing a set E′ such that E′ ̸⊆ E for all E ∈ E and that entails (Q, Σ) is in NPC , and thus the task of checking whether all sets in E are minimal, and there is no MinEX, which is not included in E, is in co-(NPC ). Table 3: Complexity results for ALL-MINEX(UCQ, L). | L | Data | fp-comb. | ba-comb. | Comb. | |-----------|--------|------------|------------|---------| | L, LF, AF | ≤ P | DP | DP | PSPACE | | S, SF | ≤ P | DP | DP | EXP | | A | ≤ P | DP | DExp | DExp | | G | CONP | DP | EXP | 2EXP | | F, GF | CONP | DP | DP | EXP | | WS, WA | CONP | DP | 2EXP | 2EXP | Theorem 8. ALL-MINEX(UCQ,L) can be decided by a polynomial number of C checks, followed by a single co-(NPC ) check, where C is the complexity of OMQA in L. Importantly, Theorem 8 gives a tight upper bound for all results in Table 3, apart from the data complexity results for FO-rewritable languages. In fact, we show that, ALL-MINEX(UCQ,L) is feasible in polynomial time provided that L is FO-rewritable, which is summarized in the next result. Theorem 9. Let L be a FO-rewritable language over existential rules. Then, computing all MinEXs for a OMQ (Q, Σ) in a database D over L is feasible in polynomial time in data complexity. To prove this result, it suffices to consider the FO-rewriting of the program, and show that determining minimal subsets of a database that entail the rewritten query can be done in polynomial time. It remains to show the hardness results presented in Table 3. As before, we note that some of the lower bounds immediately follow from the complexity of OMQA in the respective language. We show that ALL-MINEX(UCQ, GF) is CONP-hard in data complexity, by a reduction from UNSAT, by borrowing ideas from [Lukasiewicz et al., 2018]. Theorem 10. ALL-MINEX(UCQ, GF) is CONP-hard in data complexity. This implies that ALL-MINEX(UCQ,L) is CONP-hard in data complexity for all languages L ∈ {G, F,WS,WA}, due to the language inclusions GF ⊂ G, F, WS, WA. The following result settles the hardness results for ALL-MINEX(UCQ,L) in fp-, ba-, and combined complexity. In particular, we have that the complexity of ALL-MINEX(UCQ, L) and IS-MINEX(UCQ, L) match for all considered languages L in fp-, ba-, and combined complexity. The hardness results for ALL-MINEX(UCQ, L) are an adaptation of the proofs for IS-MINEX(UCQ, L) in most cases, and hence we omit the details. Theorem 11. The fp-combined, ba-combined, and combined complexity hardness results in Table 3 hold for ALL-MINEX(UCQ, L). Table 4: Complexity results for MINEX-IRREL(UCQ,L) and for SMALL-MINEX(UCQ, L). | L | Data | fp-comb. | ba-comb. | Comb. | |-----------|--------|------------|------------|---------| | L, LF, AF | ≤ P | NP | NP | PSPACE | | S, SF | ≤ P | NP | NP | EXP | | A | ≤ P | NP | NEXP | NEXP | | G | NP | NP | EXP | 2EXP | | F, GF | NP | NP | NP | EXP | | WS, WA | NP | NP | 2EXP | 2EXP | This result concludes our complexity analysis for ALL-MINEX(UCQ, L). ## 6 Explanations Excluding Forbidden Sets The next problem that we consider is the one of finding a minimal explanation that does not include a given sets of facts. Let F be a set of subsets of a database D, which intuitively encodes a set of invalid configurations: elements of F may be known to be erroneous, or we may want to avoid them for some other reason, depending on the application. Thus, we are interested in finding whether there is an explanation that is not a superset of any of the sets in F, as formalized next. Problem: MINEX-IRREL(UCQ, L) Input: A database D, an OMQ (Q, Σ), where Q is a UCQ and Σ is from the class L of TGDs, and a set F ⊆ P(D). Question: Is there a MinEX E for (Q,Σ) in D such that F ̸⊆ E, for every F ∈ F? Example 12. Suppose that the set encodes the configurations of proteins that are not allowed to be in a cover. In this case, {protein(p3), protein(p4)} is a MinEX, since it is a cover that does not contain any configuration from F. MINEX-IRREL(UCQ,L) can be decided as follows. Let C be an oracle for query answering over L. To decide the existence of a MinEX not including the "forbidden" sets, it is sufficient to guess such a subset of a database and then check whether it entails the OMQ using an oracle C. This can be carried out in NPC . Note that there is no need to check minimality as, if there is a subset E of a database that does not contain any of "forbidden" sets and entails the OMQ, then E has a minimal subset with these properties (due to monotonicity of the entailment relation). Theorem 13. MINEX-IRREL(UCQ,L) can be decided in NPC , where C is the complexity of OMQA in L. If C = NP (resp., C = NEXP), then MINEX-IRREL(UCQ,L) is also complete for NP (resp., NEXP). This result above gives a tight upper bound for all results in Table 4, apart from the data complexity results for FOrewritable languages. For these languages, we know by Theorem 9 that it is possible to compute the set of all MinEXs in polynomial time. But then, we can also find a MinEX that does not contain as a subset any of the "forbidden" sets in polynomial time. Table 5: Complexity results for MINEX-REL(UCQ,L) and for LARGE-MINEX(UCQ, L). | L | Data | fp-comb. | ba-comb. | Comb. | |----------------------------------|----------------------|-------------------------|-----------------------------|---------------------------------| | L, LF, AF S, SF A G F, GF WS, WA | ≤ P ≤ P ≤ P NP NP NP | ΣP2 ΣP2 ΣP2 ΣP2 ΣP2 ΣP2 | ΣP2 ΣP2 P NEXP EXP ΣP2 2EXP | PSPACE EXP P NEXP 2EXP EXP 2EXP | Theorem 14. Let L be a FO-rewritable language over existential rules. Then, finding a MinEX for an OMQ (Q, Σ) in a database D over L that does not contain any of the sets in F is feasible in polynomial time in data complexity. This result implies that MINEX-IRREL(UCQ,L) can be decided in polynomial-time in data complexity for FOrewritable languages L. The obvious next step is to understand the behavior of the languages that are not FO-rewritable. Our next result states that MINEX-IRREL(UCQ,L) is NP-hard for all such languages. The NP-hardness is obtained via a reduction from the NP-complete problem PATH WITH FORBIDDEN PAIRS [Gabow et al., 1976; Garey and Johnson, 1990]: decide whether there exists a path between two vertices in a graph avoiding a set of given pairs of edges. We encode the reachability in the rules, while in the database we have the facts for the graph edges. The forbidden sets naturally encode the set of forbidden pairs of edges. Theorem 15. MINEX-IRREL(UCQ, GF) is NP-hard in data complexity. The hardness results of MINEX-IRREL(UCQ,L) in the fp-combined, ba-combined, and combined complexity follow from the hardness of OMQA in the respective languages. All result are summarized in Table 4. ## 7 Explanations Including Distinguished Facts We now investigate the problem of deciding whether there is a minimal explanation including a given fact. Problem: MINEX-REL(UCQ, L) Input: A database D, an OMQ (Q, Σ), where Q is a UCQ and Σ is from the class L of TGDs, and a fact ψ ∈ D. Question: Is there a MinEX E for (Q,Σ) in D such that ψ ∈ E? Example 16. Suppose that we are interested in covers that contain the protein ψ = protein(p6) which is a distinguished fact. Observe, for example, that {protein(p1), protein(p6)} and {protein(p2), protein(p4), protein(p6)} are MinEXs for {Qp, Σp} in Dp, containing the fact ψ. To check the existence of a MinEX that contains a distinguished fact ψ, we can guess a candidate MinEX E, containing ψ and then use an oracle for IS-MINEX(UCQ,L) to check whether E is a MinEX. This gives us a naive method to decide MINEX-REL(UCQ, L). Theorem 17. MINEX-REL(UCQ,L) can be decided by a computation in NP IS-MINEX(UCQ,L) . Theorem 17 covers all membership results given in Table 5 for MINEX-REL(UCQ,L) apart from the data complexity results for FO-rewritable languages. For these languages, it is a straightforward consequence of Theorem 9 that finding a MinEX containing a distinguished fact is in polynomial time. Theorem 18. Let L be a FO-rewritable language over existential rules. Then, finding a MinEX for an OMQ (Q,Σ) in a database D over L that contains a fact ψ is feasible in polynomial time in data complexity. As before, we again obtain a hardness result for languages that are not FO-rewritable: MINEX-REL(UCQ,L) is NPcomplete in data complexity for these languages L. Theorem 19. MINEX-REL(UCQ, GF) is NP-hard in data complexity. To proof is via a reduction from the NP-complete problem PATH-VIA-NODE [Lapaugh and Papadimitriou, 1984]: given a graph, decide whether there is a path between two vertices passing through a third vertex. The construction is quite similar to the one used to show the NP-hardness of MINEX-IRREL(UCQ, GF) in data complexity. Theorem 20 shows that the complexity of MINEX-REL(UCQ,L) goes at least one level higher in the polynomial hierarchy, if we focus on fp-combined and ba-combined complexity. The reduction is from QBFCNF 2,∀,¬ which is known to be ΣP2 -complete: given a quantified Boolean formula Φ = ∃X∀Y ¬φ(X, Y ), where φ is a 3CNF formula, decide whether Φ is valid. The reduction is obtained by using the idea of the 'jolly' introduced in the proof of the DP-hardness in the fp-combined complexity of IS-MINEX(UCQ, L). Theorem 20. MINEX-REL(UCQ,L) is ΣP2 -hard for languages L ∈ {LF, AF, SF} in fp- and ba-combined complexity. MINEX-REL(UCQ, L) is also ΣP2 -hard in the fp-combined and ba-combined complexity for all other languages considered as a result of language inclusions. Our final result concerns the class A: we show that MINEX-REL(UCQ, A)is P NEXP -hard in these cases, by a reduction from the following P NEXP -complete problem that is the complement of a problem in [Eiter et al., 2016]: given a triple (m,TP1,TP2), where m is an integer in unary notation, and TP1 and TP2 are two tiling problems for the exponential square 2n × 2n , decide whether there exists an initial condition w of length m, such that TP1 has no solution with w, and TP2 has a solution with w. The proof extends the ideas used for the DExp -hardness proof of IS-MINEX. Theorem 21. MINEX-REL(UCQ, A) is P NEXP -hard in bacombined complexity. The other hardness results in Table 5 follow from the hardness of query answering in the respective languages. ## 8 Cardinality-Based Explanation Problems In this section, we deal with cardinality-related problems for minimal explanations. Briefly, these problems are helpful when we want to find out whether there is a MinEX smaller or larger than a given size. Problem: SMALL-MINEX(UCQ,L) Input: A database D, an OMQ (Q, Σ), where Q is a UCQ and Σ is from the class L of TGDs, and an integer n ≥ 1. Question: Is there a MinEX E for (Q,Σ) in D such that |E| ≤ n? Problem: LARGE-MINEX(UCQ,L) Input: A database D, an OMQ(Q, Σ), where Q is a UCQ and Σ is from the class L of TGDs, and an integer n ≥ 1. Question: Is there a MinEX E for (Q,Σ) in D such that |E| ≥ n? Example 22. Let us take n = 2. Then, there is a MinEX for (Qp,Σp) in Dp smaller and larger than n. On the other hand, if we take n = 4, then there is a MinEX smaller than n, but there is no MinEX larger than n, since all MinEXs for {Qp, Σp} in Dp are of size at most 3. Most of the proofs of the results for the problems SMALL-MINEX(UCQ,L) and LARGE-MINEX(UCQ,L) are a result of adaptations of the proofs given for MINEX-IRREL(UCQ,L) and MINEX-REL(UCQ,L), respectively. Hence, we omit the details here. Theorem 23. The complexity results in Table 4 and Table 5 hold for SMALL-MINEX(UCQ,L) and LARGE-MINEX(UCQ,L), respectively. ## 9 RelatedWork The study of explanations and diagnosis in logical formalisms dates back to Reiter [1987]. From a broader perspective, our study can be seen as a form a logical abduction, but our results clearly differ from those in propositional abduction [Eiter and Gottlob, 1995]. In this work, we focus on ontology languages, and build on axiom pinpointing [Kalyanpur et al., 2007; Baader and Suntisrivaraporn, 2008; Peñaloza and Sertkaya, 2017]. In axiom pinpointing, an entailment is explained in terms of a minimal set of ontological axioms. Such explanations are called justifications in the DL literature [Horridge et al., 2008; Horridge et al., 2009]. Axiom pinpointing is extensively studied in DLs, and some implementations exist [Kalyanpur et al., 2007; Sebastiani and Vescovi, 2009]. Most of the existing approaches to explanations focus on classical reasoning tasks and the associated types of entailments. The problem of explaining query entailments has only been investigated for the DL-Lite family of languages [Borgida et al., 2008]. Our work provides a different framework inspired by axiom pinpointing and the associated problems. Another work for explaining query answers for the DL-Lite family is given in the context of consistent query answering [Bienvenu et al., 2019]. Our minimal explanations can be seen analogous to the notion of causes studied in [Bienvenu et al., 2019]. There are many differences in our approach, though. We are interested in explaining query entailments in the most general fashion (even if there is no inconsistency), and present a unifying perspective for tasks that require explanations. The only work related to explanations in existential rules is given in [Ceylan et al., 2017], where explanations for OMQs under existential rules are studied, but this study is relative to probabilistic databases and hence of a very different flavor. There are interesting model-theoretic connections with our framework and more basic formalisms. For instance, for most of the languages that we study, we can define disjunctive Datalog programs [Eiter et al., 1997] such that every minimal model of a disjunctive Datalog program will be in bijection with a minimal explanation. These model-theoretic connections are very important, as they reveal the power of the studied problems in terms of well-studied languages. ## 10 Summary and Outlook In this paper, we have started a new direction of research by translating several decision problems from axiom pinpointing to provide explanations for OMQs. We have studied the problem of explaining query answers in terms of minimal subsets of database facts, and provided a thorough complexity analysis for several decision problems associated with minimal explanations under existential rules. The problems investigated in this paper are also closely related to minimal hitting set problems, which have a number of applications in fault diagnosis, computational biology, and data mining [Gainer-Dewar and Vera-Licona, 2017; Gottlob and Malizia, 2018]. Indeed, many important problems in practice (such as protein covers) can be naturally formulated in our framework in terms of ontology-mediated queries, and we hope that our work will be a basis for encoding and solving problems in various application domains of ontologies. There are many interesting directions for future work, including the study of other ontology languages. We also aim to explore the model-theoretic connections to other formalisms, and make a more fine-grained complexity analysis. There are many other types of problems encountered in the context of explanations, which are also a subject of future study. ## Acknowledgments We are thankful to the anonymous reviewers of this paper. This work was supported by the Alan Turing Institute under the UK EPSRC grant EP/N510129/1, and by the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1. ## References 1. [Baader and Suntisrivaraporn, 2008] Franz Baader and Boontawee Suntisrivaraporn. Debugging SNOMED CT using axiom pinpointing in the description logic EL+. In Proc. KR-MED, 2008. 2. [Baader et al., 2007] Franz Baader, Diego Calvanese, Deb- orah L. McGuinness, Daniele Nardi, and Peter F. Patel- Schneider, editors. The Description Logic Handbook: The- ory, Implementation, and Applications. Cambridge Univer- sity Press, 2nd edition, 2007. 3. [Bard and Rhee, 2004] Jonathan B. L. Bard and Seung Y. Rhee. Ontologies in biology: Design, applications and future challenges. Nat. Rev. Genet., 5:213-222, 2004. 4. [Beeri and Vardi, 1981] Catriel Beeri and Moshe Y. Vardi. The implication problem for data dependencies. In Proc. ICALP, pages 73-85, 1981. 5. [Bertaud-Gounot et al., 2012] Valérie Bertaud-Gounot, Régis Duvauferrier, and Anita Burgun. Ontology and medical diagnosis. Inform. Health Soc. Care, 37(2):51-61, 2012. 6. [Bienvenu et al., 2014] Meghyn Bienvenu, Balder Ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data ac- cess: A study through disjunctive Datalog, CSP, and MM- SNP. ACM Trans. Database Syst., 39(4):33:1-33:44, 2014. 7. [Bienvenu et al., 2019] Meghyn Bienvenu, Camille Bour- gaux, and François Goasdoué. Computing and explaining query answers over inconsistent DL-Lite knowledge bases. J. Artif. Intell. Res., 64:563-644, 2019. 8. [Borgida et al., 2008] Alexander Borgida, Diego Calvanese, and Mariano Rodriguez-Muro. Explanation in the DL-Lite family of description logics. In Proc. OTM, pages 1440- 1457, 2008. 9. [Calì et al., 2012a] Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. J. Web Semant., 14:57-83, 2012. 10. [Calì et al., 2012b] Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193:87-128, 2012. 11. [Calì et al., 2013] Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering un- der expressive relational constraints. J. Artif. Intell. Res., 48:115-174, 2013. 12. [Ceylan et al., 2017] İsmail İlkan Ceylan, Stefan Borgwardt, and Thomas Lukasiewicz. Most probable explanations for probabilistic database queries. In Proc. IJCAI, pages 950-956, 2017. 13. [Došilović et al., 2018] Filip Karlo Došilović, Mario Brčić, and Nikica Hlupić. Explainable artificial intelligence: A survey. In Proc. MIPRO, pages 210-215, 2018. 14. [Eiter and Gottlob, 1995] Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput., 24(6):1278-1304, 1995. 15. [Eiter et al., 1997] Thomas Eiter, Georg Gottlob, and Heikki Mannila. Disjunctive datalog. ACM Trans. Database Syst., 22(3):364-418, 1997. 16. [Eiter et al., 2016] Thomas Eiter, Thomas Lukasiewicz, and Livia Predoiu. Generalized consistent query answering under existential rules. In Proc. KR, pages 359-368, 2016. 17. [Fagin et al., 2005] Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: se- mantics and query answering. TCS, 336(1):89-124, 2005. 18. [Gabow et al., 1976] Harold N. Gabow, Shachindra N. Ma- heshwari, and Leon J. Osterweil. On two problems in the generation of program test paths. IEEE Trans. Softw. Eng., SE-2(3):227-231, 1976. 19. [Gainer-Dewar and Vera-Licona, 2017] Andrew Gainer- Dewar and Paola Vera-Licona. The minimal hitting set generation problem: Algorithms and computation. SIAM J. Discrete Math., 31(1):63-100, 2017. 20. [Garey and Johnson, 1990] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1990. 21. [Gottlob and Malizia, 2018] Georg Gottlob and Enrico Mal- izia. Achieving new upper bounds for the hypergraph du- ality problem through logic. SIAM J. Comput., 47(2):456- 492, 2018. 22. [Horridge et al., 2008] Matthew Horridge, Bijan Parsia, and Ulrike Sattler. Laconic and precise justifications in OWL. In Proc. ISWC, pages 323-338, 2008. 23. [Horridge et al., 2009] Matthew Horridge, Bijan Parsia, and Ulrike Sattler. Explaining inconsistencies in OWL ontolo- gies. In Proc. SUM, pages 124-137, 2009. 24. [Kalyanpur et al., 2007] Aditya Kalyanpur, Bijan Parsia, Matthew Horridge, and Evren Sirin. Finding all justifi- cations of OWL DL entailments. In Proc. ISWC/ASWC, pages 267-280, 2007. 25. [Klamt et al., 2009] Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. Hypergraphs and cellular networks. PLOS Comput. Biol., 5(5):e1000385, 2009. 26. [Lapaugh and Papadimitriou, 1984] Andrea S. Lapaugh and Christos H. Papadimitriou. The even-path problem for graphs and digraphs. Networks, 14(4):507-513, 1984. 27. [Lukasiewicz et al., 2018] Thomas Lukasiewicz, Enrico Mal- izia, and Cristian Molinaro. Complexity of approximate query answering under inconsistency in Datalog+/-. In Proc. IJCAI, pages 1921-1927, 2018. 28. [Peñaloza and Sertkaya, 2017] Rafael Peñaloza and Barış Sertkaya. Understanding the complexity of axiom pin- pointing in lightweight description logics. Artif. Intell., 250:80-104, 2017. 29. [Poggi et al., 2008] Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenz- erini, and Riccardo Rosati. Linking data to ontologies. In Journal on Data Semantics X, pages 133-173. Springer- Verlag, 2008. 30. [Ramadan et al., 2004] Emad Ramadan, Arijit Tarafdar, and Alex Pothen. A hypergraph model for the yeast protein complex network. In Proc. IPDPS, 2004. 31. [Reiter, 1987] Raymond Reiter. A theory of diagnosis from first principles. Artif. Intell., 32(1):57-95, 1987. 32. [Sebastiani and Vescovi, 2009] Roberto Sebastiani and Michele Vescovi. Axiom pinpointing in lightweight description logics via Horn-SAT encoding and conflict analysis. In Proc. CADE, pages 84-99, 2009. 33. [Suntisrivaraporn et al., 2008] Boontawee Suntisrivaraporn, Guilin Qi, Qiu Ji, and Peter Haase. A modularization- based approach to finding all justifications for OWL DL entailments. In Proc. ASWC, pages 1-15, 2008. 34. [Vardi, 1982] Moshe Y. Vardi. The complexity of relational query languages. In Proc. STOC, pages 137-146, 1982.