The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries
复制标题
使用 OWL 2 QL 和有界树宽查询进行基于本体的数据访问的复杂性
DOI：
10.1145/3034786.3034791
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Bienvenu M
中科院分区：
文献类型：
--
作者：
Bienvenu M
我们关心的是在基于本体的数据访问中回答 OWL 2 QL 本体介导的查询 (OMQ) 与评估其底层树形和更一般的有界树宽联合查询 (CQ) 相比的开销。我们表明，具有有限深度本体的 OMQ 具有非递归数据记录（NDL）重写，可以在 LOGCFL 中构建和评估组合复杂性，甚至在 NL 中，如果它们的 CQ 是具有有限数量叶子的树形。因此，从复杂性理论的角度来看，此类 OMQ 不会产生任何开销。对于具有任意本体和有界叶树形 CQ 的 OMQ，在 LOGCFL 中构建和评估 NDL 重写。与之前提出的 NDL 重写相比，我们通过实验证明了我们重写的可行性和可扩展性。另一方面，我们证明，如果将本体深度或 CQ 中的叶子数量视为参数，则用树形 CQ 回答 OMQ 不是固定参数可处理的，并且用固定本体（无限深度）回答 OMQ 对于树形 CQ 是 NP 完全的，对于有界叶 CQ 是 LOGCFL 完全的。
Our concern is the overhead of answering OWL 2 QL ontology-mediated queries (OMQs) in ontology-based data access compared to evaluating their underlying tree-shaped and, more generally, bounded treewidth conjunctive queries (CQs). We show that OMQs with bounded depth ontologies have nonrecursive datalog (NDL) rewritings that can be constructed and evaluated in LOGCFL for combined complexity, and even in NL if their CQs are tree-shaped with a bounded number of leaves. Thus, such OMQs incur no overhead in complexity-theoretic terms. For OMQs with arbitrary ontologies and bounded-leaf tree-shaped CQs, NDL-rewritings are constructed and evaluated in LOGCFL. We experimentally demonstrate feasibility and scalability of our rewritings compared to previously proposed NDL-rewritings. On the negative side, we prove that answering OMQs with tree-shaped CQs is not fixed-parameter tractable if the ontology depth or the number of leaves in the CQs is regarded as the parameter, and that answering OMQs with a fixed ontology (of infinite depth) is NP-complete for tree-shaped CQs and LOGCFL-complete for bounded-leaf CQs.
登录
查看更多内容
DOI：
--
发表时间：
2014
期刊：
TODS
影响因子：
--
作者：
G. Gottlob;G. Orsi;Andreas Pieris
通讯作者：
Andreas Pieris
影响因子：
14.4
作者：
Gottlob, Georg;Kikot, Stanislav;Zakharyaschev, Michael
通讯作者：
Zakharyaschev, Michael
重写最小化以实现高效的基于本体的查询应答
DOI：
10.1109/ictai.2016.0168
发表时间：
2016
期刊：
2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI)
影响因子：
--
作者：
Tassos Venetis;G. Stoilos;V. Vassalos
通讯作者：
V. Vassalos
kyrie2：ELHIO 中扩展约束下的查询重写
DOI：
10.1007/978-3-319-11964-9_36
发表时间：
2014
期刊：
2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI)
影响因子：
--
作者：
José Mora;R. Rosati;Óscar Corcho
通讯作者：
Óscar Corcho
Chase 的所有实例终止是不可判定的
影响因子：
--
作者：
Tomasz Gogacz;J. Marcinkowski
通讯作者：
J. Marcinkowski