Query Expressibility and Verification in Ontology-Based Data Access
share
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.
READ FULL TEXT