AAAI Publications, Sixteenth International Conference on Principles of Knowledge Representation and Reasoning

Font Size: 
Query Expressibility and Verification in Ontology-Based Data Access
Carsten Lutz, Johannes Marti, Leif Sabellek

Last modified: 2018-09-24


In ontology-based data access, multiple data sources are integrated using an ontology and mappings. In practice, this is often achieved by a bootstrapping process, that is, the ontology and mappings are first designed to support only the most important queries over the sources and then gradually extended to enable additional queries. In this paper, we study two reasoning problems that support such an approach. The expressibility problem asks whether a given source query qs is expressible as a target query (that is, over the ontology's vocabulary) and the verification problem asks, additionally given a candidate target query qt, whether qt expresses qs. We consider (U)CQs as source and target queries and GAV mappings, showing that both problems are Πp2-complete in DL-Lite, coNExpTime-complete between EL and ELHI when source queries are rooted, and 2ExpTime-complete for unrestricted source queries.


description logic; ontology-based data access; query expressibility

Full Text: PDF