XPath for DL−Lite ontologies
Egor V. Kostylev · 2014
Abstract. Applications of description logics (DLs) such as OWL 2 and ontology-based data access (OBDA) require understanding of how to pose database queries over DL knowledge bases. While there have been many studies regarding tradi-tional relational query formalisms such as conjunctive queries and their exten-sions, little attention has been paid to graph database queries, despite the fact that graph databases share the structure of interpretations with DLs; that is they de-scribe essentially the same objects. In particular, not much is known about the interplay between DLs and XPath. The last is a powerful formalism for querying semistructured data: it is in the core of most practical query languages for XML trees, and it is also gaining popularity in theory and practice of graph databases. In this paper we make a step towards coupling knowledge bases and graph data-bases by studying how to answer powerful XPath-style queries over DL-Lite. We start with adapting the definition of XPath to the DL context, and then proceed to study the complexity of evaluating XPath queries over knowledge bases. Results show that, while query answering is undecidable for the full XPath, by carefully tuning the amount of negation allowed in the queries we can arrive to XPath frag-ments that have a potential to be used in practical applications. 1