On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases
On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases
复制标题
浅层追踪在 OWL 2 QL 本体上进行查询重写的简洁性
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Zakharyaschev
中科院分区：
文献类型：
--
作者：
S. Kikot;R. Kontchakov;V. Podolskii;M. Zakharyaschev
利用超图程序计算布尔函数，研究了深度为1和2的owl2本体上连接查询的一阶重写的大小。得到了肯定和否定的结果。深度为1的本体上的合取查询具有多项式大小的非递归数据重写；树形查询具有多项式正存在重写；然而，在最坏的情况下，正存在重写只能是超多项式大小。深度为2的本体上的查询的正存在和非递归数据重写在最坏的情况下会遭受指数爆炸，而一阶重写是超多项式，除非$ ext{NP} subseteq ext{P}/ ext{poly}$。我们还分析了任意本体上树形查询的重写，并观察到此类查询的查询蕴涵问题是固定参数可处理的。
We investigate the size of first-order rewritings of conjunctive queries over OWL 2 QL ontologies of depth 1 and 2 by means of hypergraph programs computing Boolean functions. Both positive and negative results are obtained. Conjunctive queries over ontologies of depth 1 have polynomial-size nonrecursive datalog rewritings; tree-shaped queries have polynomial positive existential rewritings; however, in the worst case, positive existential rewritings can only be of superpolynomial size. Positive existential and nonrecursive datalog rewritings of queries over ontologies of depth 2 suffer an exponential blowup in the worst case, while first-order rewritings are superpolynomial unless $ ext{NP} subseteq ext{P}/ ext{poly}$. We also analyse rewritings of tree-shaped queries over arbitrary ontologies and observe that the query entailment problem for such queries is fixed-parameter tractable.
使用 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