# Query Expressibility and Verification in Ontology-Based Data Access

arXiv: https://arxiv.org/abs/2011.09176 · HTML: https://mlsanity.com/paper/2011.09176/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2020.

## Built on by (most cited first, 2 of 2)

- [QDEF and Its Approximations in OBDM](https://mlsanity.com/paper/2108.10021/) (2021)
- [Abstractions of Queries in Ontology-Based Data Access](https://mlsanity.com/paper/2606.24618/) (2026)

## Abstract (arXiv)

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 Pip2-complete in DL-Lite, coNExpTime-complete between EL and ELHI when source queries are rooted, and 2ExpTime-complete for unrestricted source queries.