In ontology-mediated query answering, access to incomplete data sources is mediated by a conceptual layer constituted by an ontology. To correctly compute answers to queries, it is necessary to perform complex reasoning over the constraints expressed by the ontology. In the literature, there exists a multitude of techniques incorporating the ontological knowledge into queries. However, few of these approaches were designed for comprehensibility of the query answers. In this article, we try to bridge these two qualities by adapting a proof framework originally applied to axiom entailment for conjunctive query answering. We investigate the data and combined complexity of determining the existence of a proof below a given quality threshold, which can be measured in different ways. By distinguishing various parameters such as the shape of a query, we obtain an overview of the complexity of this problem for the lightweight ontology languages DL-Lite_R and EL, and also have a brief look at temporal query answering.
翻译:在以本体学为介质的解答中,对不完全的数据源的存取由本体学构成的概念层进行调解。为了正确计算对询问的答案,有必要对本体学的限制因素进行复杂的推理。在文献中,存在着将本体学知识纳入查询的多种技术。然而,这些方法中很少设计为查询答案的可理解性。在文章中,我们试图通过调整最初适用于对质质解回答的必然要求的证据框架来弥补这两个特性。我们调查在某一质量阈值以下确定证据存在的数据和综合复杂性,这些数据和综合复杂性可以用不同方式衡量。通过区分查询形状等各种参数,我们获得了关于轻量学语言DL-Lite_R和EL问题的复杂性的概览。我们还简要查看了时间问答。