Query Expressibility and Verification in Ontology-Based Data Access
This work addresses incremental ontology design for data integration, providing theoretical foundations for practitioners in semantic web and database communities.
The paper tackles the expressibility and verification problems in ontology-based data access, showing that these problems have varying computational complexities, such as Π^p_2-completeness in DL-Lite and 2ExpTime-completeness for unrestricted source queries.
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 $q_s$ is expressible as a target query (that is, over the ontology's vocabulary) and the verification problem asks, additionally given a candidate target query $q_t$, whether $q_t$ expresses $q_s$. We consider (U)CQs as source and target queries and GAV mappings, showing that both problems are $Π^p_2$-complete in DL-Lite, coNExpTime-complete between EL and ELHI when source queries are rooted, and 2ExpTime-complete for unrestricted source queries.