On the succinctness of query rewriting over shallow ontologies
On the succinctness of query rewriting over shallow ontologies
复制标题
浅层本体查询重写的简洁性
DOI：
10.1145/2603088.2603131
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Kikot S
中科院分区：
文献类型：
--
作者：
Kikot S
本文研究了深度为1和2的OWL 2 QLontologies上通过超图程序计算布尔函数的合取查询重写的简洁性问题。得到了肯定和否定的结果。我们发现，在深度为1的本体，合取查询具有多项式大小的非递归数据重写;树形查询具有多项式正存在重写;然而，在最坏的情况下，正存在重写可以是超多项式。在深度为2的本体上，合取查询的正存在和非递归数据重写可能会遭受指数爆炸，而一阶重写可能是超多项式的，除非NP ≠ P/poly。我们还分析重写任意本体的树形查询，并注意到这种查询的查询蕴涵是固定参数易处理的。
We investigate the succinctness problem for conjunctive query rewritings overOWL 2QLontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. We show that, over ontologies of depth 1, conjunctive queries have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, in the worst case, positive existential rewritings can be superpolynomial. Over ontologies of depth 2, positive existential and nonrecursive datalog rewritings of conjunctive queries can suffer an exponential blowup, while first-order rewritings can be superpolynomial unless NP ⊆ P/poly. We also analyse rewritings of tree-shaped queries over arbitrary ontologies and note that query entailment for such queries is fixed-parameter tractable.
登录
查看更多内容
影响因子：
14.4
作者：
Gottlob, Georg;Kikot, Stanislav;Zakharyaschev, Michael
通讯作者：
Zakharyaschev, Michael
浅层追踪在 OWL 2 QL 本体上进行查询重写的简洁性
DOI：
--
发表时间：
2014
期刊：
arXiv.org
影响因子：
--
作者：
S. Kikot;R. Kontchakov;V. Podolskii;M. Zakharyaschev
通讯作者：
M. Zakharyaschev
DOI：
10.1007/978-3-642-31585-5_26
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
S. Kikot;R. Kontchakov;V. Podolskii;M. Zakharyaschev
通讯作者：
M. Zakharyaschev
DL-Lite 中扩展约束下的查询重写
DOI：
10.1007/978-3-642-30284-8_31
发表时间：
2012
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
R. Rosati
通讯作者：
R. Rosati
使用 OWL 2 QL 进行联合查询应答
DOI：
--
发表时间：
2012
期刊：
Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2012, Rome, Italy, June 10-14, 2012
影响因子：
--
作者：
Kikot S
通讯作者：
Kikot S