Explanation in the DL-Lite Family of Description Logics

Alexander Borgida, Diego Calvanese, and Mariano Rodriguez-Muro

Proc. of the 7th Int. Conf. on Ontologies, DataBases, and Applications of Semantics (ODBASE 2008). Volume 5332 of Lecture Notes in Computer Science. 2008.

In ontology-based data access (OBDA), access to (multiple) incomplete data sources is mediated by a conceptual layer constituted by an ontology. In such a setting, to correctly compute answers to queries, it is necessary to perform complex reasoning over the constraints expressed by the ontology. We consider the case of ontologies expressed in DL-Lite, a family of DLs that, in the context of OBDA, provide an optimal tradeoff between expressive power and computational complexity of reasoning: on the one hand, DL-Lite captures the essential features of conceptual modeling notations such as Entity-Relationship diagrams and UML class diagrams; on the other hand, reasoning over a DL-Lite ontology is polynomial, and query answering is LOGSPACE in the size of the data, and can be carried out by resorting to a relational query engine. However, query answering with reasoning comes at a price: the justification of the presence of tuples in answers is no longer trivial, and requires explanation. In this paper, we characterize reasoning in DL-Lite, through deduction rules for building proofs, and we provide several novel contributions: (i) For standard ontology level reasoning, explanation is relatively simple, and our contribution comes mainly from a novel focus on brevity of proofs. (ii) Motivated by the use of DL-Lite for OBDA, we analyze and provide explanation for reasoning in finite models. (iii) We provide a facility for the explanation of an answer to a conjunctive query over a DL-Lite ontology. This algorithm is able to exploit the relational query engine to extract from the data the information necessary for finding the explanation more efficiently, and thus scales to large data sets. The presented approach has been implemented in a prototype for constructing explanations.

   title = "Explanation in the DL-Lite  Family of Description Logics",
   year = "2008",
   author = "Alexander Borgida and Diego Calvanese and Mariano
   booktitle = "Proc. of the 7th Int. Conf. on Ontologies, DataBases, and
Applications of Semantics (ODBASE 2008)",
   pages = "1440--1457",
   volume = "5332",
   publisher = "Springer",
   series = "Lecture Notes in Computer Science",
   doi = "10.1007/978-3-540-88873-4_35",
pdf url