A tetrachotomy of ontology-mediated queries with a covering axiom
A tetrachotomy of ontology-mediated queries with a covering axiom
复制标题
具有覆盖公理的本体介导查询的四分法
DOI：
10.1016/j.artint.2022.103738
复制
发表时间：
2022
影响因子：
14.4
通讯作者：
Gerasimova O
中科院分区：
文献类型：
--
作者：
Gerasimova O
我们关注的是有效确定回答由描述逻辑本体介导的查询的数据复杂性并构建对标准数据库查询的最佳重写的问题。起源于基于本体的数据访问和数据记录优化，这个问题通常在计算上非常复杂，没有明确的语法特征可用。在本文中，旨在了解这一困难的根本根源，我们将问题剥离到最简单的部分，并重点关注由一个简单的覆盖公理介导的布尔连接查询，该公理指出一个类被其他两个类的并集覆盖。我们表明，一方面，这些基本的本体介导的查询，称为析取糖浆（或d-糖浆），捕获了一般情况的许多特征和困难。例如，对于组合复杂性，回答 d-sirups 是 Π 2 p-complete，并且对于数据复杂性可以是 Image 1 或 L-、NL-、P-或 coNP-complete（识别 d-sirups 的 FO-可重写性问题是 2 ExpTime-hard）；一些 d-sirup 仅具有指数大小的分辨率证明，一些仅具有双指数大小的正存在 FO 重写和单指数大小的非递归数据记录重写。另一方面，我们证明了 d-sirups 的 FO 和（对称/线性）数据记录可重写性的一些部分充分必要条件。我们的主要技术成果是一个完整且透明的句法 Image 1/NL/P/coNP 四分法，具有不相交的覆盖类和路径形布尔连接查询。为了获得这种四分法，我们开发了新技术来建立回答非 Horn 本体介导的查询的 P 和 coNP 硬度，并表明它们可以在 NL 中得到回答。
Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description logic ontologies and constructing their optimal rewritings to standard database queries. Originated in ontology-based data access and datalog optimisation, this problem is known to be computationally very complex in general, with no explicit syntactic characterisations available. In this article, aiming to understand the fundamental roots of this difficulty, we strip the problem to the bare bones and focus on Boolean conjunctive queries mediated by a simple covering axiom stating that one class is covered by the union of two other classes. We show that, on the one hand, these rudimentary ontology-mediated queries, called disjunctive sirups (or d-sirups), capture many features and difficulties of the general case. For example, answering d-sirups is Π 2 p-complete for combined complexity and can be in Image 1 or L-, NL-, P-, or coNP-complete for data complexity (with the problem of recognising FO-rewritability of d-sirups being 2 ExpTime-hard); some d-sirups only have exponential-size resolution proofs, some only double-exponential-size positive existential FO-rewritings and single-exponential-size nonrecursive datalog rewritings. On the other hand, we prove a few partial sufficient and necessary conditions of FO-and (symmetric/linear-) datalog rewritability of d-sirups. Our main technical result is a complete and transparent syntactic Image 1/NL/P/coNP tetrachotomy of d-sirups with disjoint covering classes and a path-shaped Boolean conjunctive query. To obtain this tetrachotomy, we develop new techniques for establishing P-and coNP-hardness of answering non-Horn ontology-mediated queries as well as showing that they can be answered in NL.
登录
查看更多内容
DOI：
--
发表时间：
2014
期刊：
TODS
影响因子：
--
作者：
G. Gottlob;G. Orsi;Andreas Pieris
通讯作者：
Andreas Pieris
关于图的简洁表示的注解
DOI：
10.1016/s0019-9958(86)80009-2
发表时间：
1986
期刊：
Inf. Control.
影响因子：
--
作者：
C. Papadimitriou;M. Yannakakis
通讯作者：
M. Yannakakis
受保护逻辑的有界性的复杂性
DOI：
--
发表时间：
2015
期刊：
2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Michael Benedikt;B. T. Cate;Thomas Colcombet;M. V. Boom
通讯作者：
M. V. Boom
DOI：
10.1145/1379759.1379763
发表时间：
2008
期刊：
J. ACM
影响因子：
--
作者：
Benjamin Rossman
通讯作者：
Benjamin Rossman
实施易处理性测试
影响因子：
1.6
作者：
R. Gault;P. Jeavons
通讯作者：
P. Jeavons