Explanations for Ontology-Mediated Query Answering in Description Logics (Extended Abstract)? İsmail İlkan Ceylan1 , Thomas Lukasiewicz1 , Enrico Malizia2 , and Andrius Vaicenavičius1 1 University of Oxford, Department of Computer Science, UK firstname.lastname@cs.ox.ac.uk 2 King’s College London, Department of Informatics, UK enrico.malizia@kcl.ac.uk Ontology-mediated query answering (OMQA) [12, 3] emerged as a paradigm for accessing data sources through a logical theory. In this paper, we focus on de- scription logics (DLs) [2], and study the problem of explaining why an ontology- mediated query (OMQ) is entailed from a given data source. Explainability is an essential ingredient of various application domains, and has been widely investi- gated in DLs under different names such as justifications [9, 14], abduction [10, 5], and axiom pinpointing [1, 13, 11]. There has been only a few works for deriv- ing explanations for OMQA in DLs [4, 5]. Here we provide an abridged report of our paper on explaining OMQA in DLs that appeared at ECAI 2020 [8]. Our study is based on the framework that has been recently developed for existential rules [7]. Specifically, we view explanations as minimal sets of as- sertions from an ABox which satisfy the ontology-mediated query, and study a variety of problems based on such explanations. Formally, given a consistent knowledge base K = (T , A) where T is a TBox and A is an ABox, and a query Q, we say that a subset E ⊆ A is a minimal explanation (MinEX) for the OMQ (Q, T ) in A if E |= (Q, T ), and no proper subset of E entails (Q, T ). Example 1. Consider an en- overheat part 1 part 2 part 3 part 4 gine that might experience a number of possible failures, leakage each caused by a fault of one of the constituent parts, pre- Fig. 1. Possible faults in different parts of a system. sented in Fig 1. We can model fault diagnosis as minimal ex- planations for OMQs. Let us define the ABox A = {Fault(part i ) | 1 ≤ i ≤ 4} ∪ Ast , where Ast = {caused (overheat, part i ) | i ∈ {1, 2}}∪{caused (leakage, part i ) | i ∈ {2, 3}} and the TBox T = {∃caused V .Fault v Failure}. The query Q = Failure(overheat) ∧ Failure(leakage) ∧ ψ∈Ast ψ specifies the observed failures together with the structural facts of the engine. Then, any MinEX for (Q, T ) ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Com- mons License Attribution 4.0 International (CC BY 4.0) 2 Ceylan et al. in A is a minimal subset of Fault concept assertions, together with all assertions in Ast , that lead to overheat and leakage. In particular, MinEXs for (Q, T ) in A correspond to minimal covers of the graph in Figure 1. We study four decision problems related to minimal explanations: (i) given a set, decide whether it is a minimal explanation (Is-MinEX), (ii) given a set of sets, decide whether it is the set of all minimal explanations (All-MinEX), (iii) given a distinguished assertion, decide whether it is contained in some minimal explanation (MinEX-Rel), and (iv) given a set of forbidden sets, de- cide whether there is a minimal explanation not containing any forbidden sets (MinEX-Irrel). We illustrate these problems on our running example, and refer to the original publication, for formal definitions and details [8]. Example 2. Let us consider the following subsets of the ABox E1 = {Fault(part 2 )} ∪ Ast , and E2 = {Fault(part 1 ), Fault(part 3 )} ∪ Ast , on our running example and the explanation problems: – Is-MinEX: Both E1 and E2 are MinEXs for the OMQ (Q, T ), since they are both minimal and entail the OMQ. On the other hand, neither the set {Fault(part 1 )} ∪ Ast nor the set {Fault(part 2 ), Fault(part 4 )} ∪ Ast are min- imal explanations, as the former does not entail the OMQ and the latter is not minimal. – All-MinEX: It is easy to see that the set {E1 , E2 } is the set of all MinEXs for the OMQ in A, i.e., there are not other minimal explanations. – MinEX-Rel: Observe that the assertions Fault(part i ), i ∈ {1, 2, 3}, are all relevant, as they are all contained in some MinEX. – MinEX-Irrel: Let {{Fault(part 1 ), Fault(part 3 )}, {Fault(part 4 )}} be forbid- den sets of assertions. We need to decide whether there exists an explanation that does not contain any of these sets. The answer is yes, since E1 is a MinEX that does not contain any of these sets. Notice, however, E2 contains a forbid- den set. We conduct a thorough complexity analysis for the above-mentioned expla- nation problems for a large class of OMQs. In our data complexity analysis, we show that all these problems are tractable for DL-Lite and DL-LiteR . Other tractability results in the data complexity are given for Is-MinEX for EL, ELI, and Horn-SHOIQ. All the other results in the data complexity confirm the hard- ness of deriving explanations, as we almost always observe an increase in the complexity in comparison to the complexity of OMQA. This is largely due to an extra complexity introduced for ensuring minimality. The hardness results for most of these problems are shown by the reductions from different satisfia- bility problems. In the combined complexity, we observe that the complexity is typically dominated by the complexity of OMQA. The closest work to our study is the framework developed for existential rules [7]. Membership results, in most cases, follow from this earlier work, but hardness results are significantly different, especially for logics such as ALC. Explanations for Ontology-Mediated Query Answering 3 Explanations for OMQA in DLs have been studied earlier for DL-Lite [4]. Our work is complementary to explaining negative answers to OMQs in DLs [5], which was recently also studied in the context of existential rules [6]. References 1. Franz Baader and Boontawee Boontawee Suntisrivaraporn. Debugging SNOMED CT using axiom pinpointing in the description logic EL+ . In Proc. KR-MED, 2008. 2. Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Pe- ter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Imple- mentation, and Applications. Cambridge University Press, 2nd edition, 2007. 3. Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology- based data access: A study through Disjunctive Datalog, CSP, and MMSNP. ACM Trans. Database Syst., 39(4), 2014. 4. Alexander Borgida, Diego Calvanese, and Mariano Rodriguez-Muro. Explanation in the DL-Lite family of description logics. In Proc. OTM, 2008. 5. Diego Calvanese, Magdalena Ortiz, Mantas Šimkus, and Giorgio Stefanoni. Rea- soning about explanations for negative query answers in DL-Lite. J. Artif. Intell. Res., 48(1), 2013. 6. İsmail İlkan Ceylan, Thomas Lukasiewicz, Enrico Malizia, Cristian Molinaro, and Andrius Vaicenavičius. Explanations for negative query answers under existential rules. In Proc. KR, 2020. 7. İsmail İlkan Ceylan, Thomas Lukasiewicz, Enrico Malizia, and Andrius Vaice- navičius. Explanations for query answers under existential rules. In Proc. IJCAI, 2019. 8. İsmail İlkan Ceylan, Thomas Lukasiewicz, Enrico Malizia, and Andrius Vaice- navičius. Explanations for ontology-mediated query answering in description logics. In Proc. ECAI, 2020. 9. Aditya Kalyanpur, Bijan Parsia, Matthew Horridge, and Evren Sirin. Finding all justifications of OWL DL entailments. In Proc. ISWC, 2007. 10. Szymon Klarman, Ulle Endriss, and Stefan Schlobach. ABox abduction in the description logic ALC. J. Auto. Reas., 46(1), 2011. 11. Rafael Peñaloza and Barış Sertkaya. Understanding the complexity of axiom pin- pointing in lightweight description logics. Artif. Intell., 250, 2017. 12. Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Mau- rizio Lenzerini, and Riccardo Rosati. Linking data to ontologies. In J. Data Sem. X, volume 4900 of LNCS. Springer-Verlag, 2008. 13. Roberto Sebastiani and Michele Vescovi. Axiom pinpointing in lightweight de- scription logics via Horn-SAT encoding and conflict analysis. In Proc. CADE, 2009. 14. Boontawee Suntisrivaraporn, Guilin Qi, Qiu Ji, and Peter Haase. A modularization-based approach to finding all justifications for OWL DL entail- ments. In Proc. ASWC, 2008.