QDEF and Its Approximations in OBDM
  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).
