Explaining Query Answers under Inconsistency-Tolerant Semantics over Description Logic Knowledge Bases (Extended Abstract)

-

The problem of querying description logic (DL) knowledge bases (KBs) using database-style queries (in particular, conjunctive queries) has been a major focus of recent DL research. Since scalability is a key concern, much of the work has focused on lightweight DLs for which query answering can be performed in polynomial time w.r.t. the size of the ABox. The DL-Lite family of lightweight DLs [ 10 ] is especially popular due to the fact that query answering can be reduced, via query rewriting, to the problem of standard database query evaluation.

Since the TBox is usually developed by experts and subject to extensive debugging, it is often reasonable to assume that its contents are correct. By contrast, the ABox is typically substantially larger and subject to frequent modi cations, making errors almost inevitable. As such errors may render the KB inconsistent, several inconsistency-tolerant semantics have been introduced in order to provide meaningful answers to queries posed over inconsistent KBs. Arguably the most well-known is the AR semantics [ 17 ], inspired by work on consistent query answering in databases (cf. [ 4 ] for a survey). Query answering under AR semantics amounts to considering those answers (w.r.t. standard semantics) that can be obtained from every repair, the latter being de ned as an inclusion-maximal subset of the ABox that is consistent with the TBox. A more cautious semantics, called IAR semantics [ 17 ] queries the intersection of the repairs and provides a lower bound on AR semantics. The brave semantics [ 7 ], which considers the answers holding in some repair, provides a natural upper bound. This extended abstract presents our work [ 6 ] on explaining why a tuple is a (non-)answer to a query under AR, IAR, or brave semantics.

The need to equip reasoning systems with explanation services is widely acknowledged by the DL community. Indeed, there have been numerous works on axiom pinpointing, in which the objective is to identify (minimal) subsets of a KB that entail a given TBox axiom (or ABox assertion) [ 18, 9, 21, 16, 22, 20, 14, 15 ]. With regards to conjunctive queries (CQs), a proof-theoretic approach to explaining positive answers to CQs over DL-LiteA KBs was introduced in [ 8 ], and, more recently, the problem of explaining negative query answers over DL-LiteA KBs has been studied in [11{13]. Explanation facilities are all the more essential when using inconsistency-tolerant semantics, as recently argued in [ 1, 2 ]. Indeed, the brave, AR, and IAR semantics allow query answers to be classi ed into three categories of increasing reliability, and a user may naturally wonder why a given tuple was assigned to, or excluded from, one of these categories. To help the user understand this classi cation, we introduce the notion of explanation for positive and negative query answers under brave, AR, and IAR semantics. Formally, the explanations we consider take either the form of a set of ABox assertions (viewed as a conjunction) or a set of sets of assertions (disjunction of conjunctions).

The simplest answers to explain are positive brave- and IAR-answers (i.e., answers that hold under brave, resp. IAR, semantics). For the former, we can use as explanations the query's causes, which are the minimal consistent sets of assertions that entail the answer together with the TBox, and for the latter, we consider the causes that do not participate in any contradictions. To explain why a tuple is an AR-answer, it is no longer su cient to give a single cause since di erent repairs may use di erent causes. We therefore de ne explanations as (minimal) disjunctions of causes that `cover' all repairs, i.e., minimal sets of causes such that every repair contains at least one of them. To explain negative AR-answers, the idea is to give a (minimal) subset of the ABox that is consistent with the TBox and contradicts every cause of the query, since any such subset can be extended to a repair that omits all causes. For negative IAR-answers, we need only ensure that every cause is contradicted by some consistent subset.

When there are a large number of explanations for a given result, it may be impractical to present them all to the user. In such cases, one may choose instead to rank the explanations according to some preference criteria, and to present one or a small number of most preferred explanations. In the present work, we use cardinality to rank explanations for brave- and IAR-answers and negative AR- and IAR-answers. For positive AR-answers, we consider two ways of ranking explanations: the number of disjuncts, since fewer disjuncts requires less casebased reasoning, and the total number of assertions, to favour disjunctions of causes that share assertions. A complementary approach is to concisely summarize the set of explanations in terms of the necessary assertions (that occur in every explanation) and the relevant assertions (occurring in some explanation). 2

Complexity Results and Connections to SAT

In addition to the problem of computing explanations, we consider four natural decision problems: decide whether a given assertion appears in some explanation (rel) or in every explanation (nec), decide whether a candidate is an explanation (rec), resp. a best explanation according a given criteria (best rec). For our study, we consider ontologies formulated in the lightweight logic DL-LiteR that underlies the OWL 2 QL pro le [ 19 ].

The results of our complexity analysis are displayed in Figure 1. For the explanation tasks that are shown to be intractable, we have exhibited tight connections with variants of propositional satis ability that enable us to exploit brave, IAR neg. IAR neg. AR rel in P 2p-co in P NP-co nec in P NP-co in P coNP-co rec in P BH2-co in P in P best recy in P 2p-coz coNP-co coNP-co y upper bounds hold for ranking criteria that can be decided in P z 2p-hard for smallest disjunction or fewest assertions

coNP-hard for cardinality-minimal explanations facilities of modern SAT solvers. We use the encoding ':q ^ 'cons introduced in [ 5 ] which is unsatis able i the corresponding answer is entailed under AR semantics. Intuitively, ':q gives the ways of contradicting every cause, and 'cons enforces consistency. We can show that the explanations for positive AR-answers correspond to the minimal unsatis able subsets of ':q w.r.t. 'cons, while the smallest explanations for negative AR-answers (resp. negative IAR-answers) correspond to the cardinality-minimal models of ':q ^ 'cons (resp. ':q). 3

System and Experiments

We extended the CQAPri system [ 5 ] to implement our framework, relying on the SAT4J SAT solver to compute minimal unsatis able subsets and cardinalityminimal models [ 3 ]. Our prototype runs in two modes: either it explains some selected query answers, or all the answers as they are being computed. These answers are divided into three classes: Possible (brave-answers not entailed under the AR semantics), Likely (AR-answers not entailed under IAR semantics), and Sure (IAR-answers). Concretely, explaining an answer a consists in providing, for the relevant semantics S, S0 according to the class of a: (i) all explanations of a being an S-answer, as well as necessary and relevant assertions, and (ii) one smallest explanation of a not being an S0-answer, with necessary and relevant assertions when S0 = IAR, and necessary assertions when S0 = AR together with necessary and relevant assertions for explaining a not being an IAR-answer. Positive explanations are ranked as explained in Section 1.

The experimental evaluation of our prototype system over the slightly modi ed CQAPri benchmark shows that explanations of query (non-)answers can be generated very quickly (typically less than 1ms), although we did nd some rare di cult cases for which computing a smallest explanation for a negative answer is long (more than 1h). Finally, we observed that the average number of explanations per answer is often reasonably low, although some answers have a large number of explanations (e.g., 654 for an IAR-answer, 243 for an AR-answer, and 693 for a brave-answer), showing the practical interest of presenting such explanations in a concise way.

Acknowledgements This work was supported contract ANR-12-JS02-007-01.

References

1. Arioua , A. , Tamani , N. , Croitoru , M. : On conceptual graphs and explanation of query answering under inconsistency . In: Proc. of ICCS ( 2014 )

2. Arioua , A. , Tamani , N. , Croitoru , M. , Buche , P. : Query failure explanation in inconsistent knowledge bases using argumentation . In: Proc. of COMMA ( 2014 )

3. Berre , D.L. , Parrain , A. : The sat4j library, release 2.2. JSAT 7 ( 2-3 ), 59 { 64 ( 2010 )

4. Bertossi , L.E. : Database Repairing and Consistent Query Answering . Synthesis Lectures on Data Management , Morgan & Claypool Publishers ( 2011 )

5. Bienvenu , M. , Bourgaux , C. , Goasdoue , F. : Querying inconsistent description logic knowledge bases under preferred repair semantics . In: Proc. of AAAI ( 2014 )

6. Bienvenu , M. , Bourgaux , C. , Goasdoue , F. : Explaining query answers under inconsistency-tolerant semantics over description logic knowledge bases ( 2015 ), Technical Report 1580 , LRI, Orsay, France. Available at https://www.lri.fr/ ~bibli/Rapports-internes/ 2015 /RR1580.pdf

7. Bienvenu , M. , Rosati , R. : Tractable approximations of consistent query answering for robust ontology-based data access . In: Proc. of IJCAI ( 2013 )

8. Borgida , A. , Calvanese , D. , Rodriguez-Muro , M.: Explanation in the DL-Lite family of description logics . In: Proc. of OTM ( 2008 )

9. Borgida , A. , Franconi , E. , Horrocks , I. : Explaining ALC subsumption . In: Proc. of ECAI ( 2000 )

10. Calvanese , D. , De Giacomo , G. , Lembo , D. , Lenzerini , M. , Rosati , R. : Tractable reasoning and e cient query answering in description logics: The DL-Lite family . J. Autom. Reasoning (JAR) 39(3) , 385 { 429 ( 2007 )

11. Calvanese , D. , Ortiz , M. , Simkus , M. , Stefanoni , G. : Reasoning about explanations for negative query answers in DL-Lite . J. Artif. Intell. Res. (JAIR) 48 , 635 { 669 ( 2013 )

12. Du , J. , Wang , K. , Shen , Y. : A tractable approach to abox abduction over description logic ontologies . In: Proc. of AAAI ( 2014 )

13. Du , J. , Wang , K. , Shen , Y. : Towards tractable and practical abox abduction over inconsistent description logic ontologies . In: Proc. of AAAI ( 2015 )

14. Horridge , M. , Bail , S. , Parsia , B. , Sattler , U. : The cognitive complexity of OWL justi cations . In: Proc. of ISWC ( 2011 )

15. Horridge , M. , Parsia , B. , Sattler , U. : Extracting justi cations from bioportal ontologies . In: Proc. of ISWC ( 2012 )

16. Kalyanpur , A. , Parsia , B. , Sirin , E. , Hendler , J.A. : Debugging unsatis able classes in OWL ontologies . J. Web Sem . 3 ( 4 ), 268 { 293 ( 2005 )

17. Lembo , D. , Lenzerini , M. , Rosati , R. , Ruzzi , M. , Savo , D.F. : Inconsistency-tolerant semantics for description logics . In: Proc. of RR ( 2010 )

18. McGuinness , D.L. , Borgida , A. : Explaining subsumption in description logics . In: Proc. of IJCAI ( 1995 )

19. Motik , B. , Cuenca Grau , B. , Horrocks , I. , Wu , Z. , Fokoue , A. , Lutz , C. : OWL 2 Web Ontology Language pro les . W3C Recommendation (11 December 2012 ), available at http://www.w3.org/TR/owl2-profiles/

20. Pen~aloza, R., Sertkaya , B. : Complexity of axiom pinpointing in the dl-lite family of description logics . In: Proc. of ECAI ( 2010 )

21. Schlobach , S. , Cornet , R.: Non-standard reasoning services for the debugging of description logic terminologies . In: Proc. of IJCAI ( 2003 )

22. Sebastiani , R. , Vescovi , M. : Axiom pinpointing in lightweight description logics via horn-sat encoding and con ict analysis . In: Proc. of CADE ( 2009 )