Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
复制标题
DOI：
10.1145/3034786.3056108
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
André Hernich;C. Lutz;Fabio Papacchini;F. Wolter
中科院分区：
文献类型：
--
作者：
André Hernich;C. Lutz;Fabio Papacchini;F. Wolter
我们研究的复杂性，本体介导的查询时，制定的一阶逻辑（GF）的守护片段的本体。我们的总体目标是分类的本体的查询评价w.r.t.的水平上的数据复杂性。如果所有（合取的并集）查询可以在PTime中被评估，则本体O被认为在PTime中。O和coNP-hard，如果至少一个查询是coNP-hard w.r.t. O.我们确定了几个大的和相关的GF片段，享受PTime和coNP之间的二分法，其中一些还承认一种形式的计数。事实上，BioPortal存储库中几乎所有的本体都属于这些片段，或者可以很容易地重写。然后，我们建立了一个变化的拉德纳定理的NP-中间问题的存在，并使用这个结果表明，对于其他片段，可证明没有这样的二分法。同样对于其他片段（如全GF），建立二分法意味着Feder-Vardi猜想约束满足问题的复杂性。我们还将这些结果与数据记录可重写性联系起来，并研究了给定本体是否享有PTime查询评估的可判定性，给出了积极和消极的结果。
We study the complexity of ontology-mediated querying when ontologies are formulated in the guarded fragment of first-order logic (GF). Our general aim is to classify the data complexity on the level of ontologies where query evaluation w.r.t. an ontology O is considered to be in PTime if all (unions of conjunctive) queries can be evaluated in PTime w.r.t. O and coNP-hard if at least one query is coNP-hard w.r.t. O. We identify several large and relevant fragments of GF that enjoy a dichotomy between PTime and coNP, some of them additionally admitting a form of counting. In fact, almost all ontologies in the BioPortal repository fall into these fragments or can easily be rewritten to do so. We then establish a variation of Ladner's Theorem on the existence of NP-intermediate problems and use this result to show that for other fragments, there is provably no such dichotomy. Again for other fragments (such as full GF), establishing a dichotomy implies the Feder-Vardi conjecture on the complexity of constraint satisfaction problems. We also link these results to Datalog-rewritability and study the decidability of whether a given ontology enjoys PTime query evaluation, presenting both positive and negative results.