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 description logics (DLs) [2], and study the problem of explaining why an ontologymediated query (OMQ) is entailed from a given data source. Explainability is an essential ingredient of various application domains, and has been widely investigated in DLs under di erent names such as justi cations [9, 14], abduction [10, 5], and axiom pinpointing [1, 13, 11]. There has been only a few works for deriving 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]. Speci cally, we view explanations as minimal sets of assertions 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 j= (Q; T ), and no proper subset of E entails (Q; T ). Example 1. Consider an engine that might experience a overheat part1 part2 part3 part4 number of possible failures, leakage each caused by a fault of one of the constituent parts, pre- Fig. 1. Possible faults in di erent parts of a system. sented in Fig 1. We can model fault diagnosis as minimal explanations for OMQs. Let us de ne the ABox A = fFault (part i) j 1 i 4g [ Ast , where Ast = fcaused (overheat ; part i) j i 2 f1; 2gg[fcaused (leakage; part i) j i 2 f2; 3gg and the TBox T = f9caused :Fault v Failureg. The query Q = Failure(overheat ) ^ Failure(leakage) ^ V 2Ast speci es the observed failures together with the structural facts of the engine. Then, any MinEX for (Q; T )
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,
decide 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 de nitions and details [
E1 = fFault (part 2)g [ Ast; and E2 = fFault (part 1); Fault (part 3)g [ 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 fFault (part 1)g [ Ast nor the set fFault (part 2); Fault (part 4)g [ Ast are minimal 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 fE1; E2g 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 2 f1; 2; 3g, are all relevant, as they are all contained in some MinEX. { MinEX-Irrel: Let ffFault (part 1); Fault (part 3)g; fFault (part 4)gg be forbidden 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 forbidden set.
We conduct a thorough complexity analysis for the above-mentioned explanation 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 con rm the hardness 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 di erent satis ability 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 [