QDEF and Its Approximations in OBDM
This work addresses query definability challenges in OBDM, offering approximations and complexity insights, but it appears incremental as it builds on existing OBDM frameworks without introducing a new paradigm.
The paper tackles the problem of query definability in Ontology-based Data Management (OBDM) by proposing approximations for perfect characterizations in terms of recall and precision, and conducts a complexity analysis of verification, existence, and computation problems.
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).