# QDEF and Its Approximations in OBDM

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 40 references that are in the map.
- First posted on arXiv 23 Aug 2021.

## Builds on (most cited first, 4 of 4)

- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [The complexity of reverse engineering problems for conjunctive queries](https://mlsanity.com/paper/1606.01206/) (2016)
- [Query Expressibility and Verification in Ontology-Based Data Access](https://mlsanity.com/paper/2011.09176/) (2020)
- [Preliminary results on Ontology-based Open Data Publishing](https://mlsanity.com/paper/1705.10480/) (2017)

## Abstract (arXiv)

Given an input dataset (i.e., a set of tuples), query definability in Ontology-based Data Management (OBDM) amounts to find a query over the ontology whose certain answers coincide with the tuples in the given dataset. We refer to such a query as a characterization of the dataset with respect to the OBDM system. Our first contribution is to propose approximations of perfect characterizations in terms of recall (complete characterizations) and precision (sound characterizations). A second contribution is to present a thorough complexity analysis of three computational problems, namely verification (check whether a given query is a perfect, or an approximated characterization of a given dataset), existence (check whether a perfect, or a best approximated characterization of a given dataset exists), and computation (compute a perfect, or best approximated characterization of a given dataset).