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).
翻译:根据输入数据集(即一套图例),基于本体数据管理(OBDM)中的查询可定义性等于找到对本体学的查询,其某些答案与给定数据集中的图例相吻合。我们把这种查询称为对OBDM系统数据集的定性。我们的第一个贡献是提出在召回(完整特征)和精确度(正确特征)方面完美定性的近似值。第二个贡献是对三个计算问题进行彻底的复杂分析,即核查(检查某一查询是否完美,或某一数据集的大致特征)、存在(检查某一数据集是否存在完美或最接近的特征)和计算(对某一数据集进行完美或最接近的特征定性)。