The price of query rewriting in ontology-based data access
The price of query rewriting in ontology-based data access
复制标题
DOI：
10.1016/j.artint.2014.04.004
复制
发表时间：
2014-08-01
影响因子：
14.4
通讯作者：
Zakharyaschev, Michael
中科院分区：
文献类型：
--
作者：
Gottlob, Georg;Kikot, Stanislav;Zakharyaschev, Michael
我们给出了一个解决方案的简洁性问题的一阶重写的合取查询的大小在基于本体的数据访问与本体语言，如OWL 2 QL，线性数据库（+/-）和粘性数据库。我们表明，积极的存在和非递归的数据重写，不使用额外的非逻辑符号（除了内涵谓词的情况下的数据重写），遭受指数爆破在最坏的情况下，而一阶重写可以增长超多项式，除非NP子集的P/poly。我们还证明了非递归数据重写一般指数更简洁的积极存在重写，而一阶重写可以超多项式更简洁的积极存在重写。另一方面，我们构造多项式大小的正存在和非递归的数据重写的假设下，任何数据实例包含两个固定的常数。(C)2014爱思唯尔有限公司版权所有。
We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontology-based data access with ontology languages such as OWL 2 QL, linear Datalog(+/-) and sticky Datalog. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case of datalog rewritings), suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP subset of P/poly. We also prove that nonrecursive datalog rewritings are in general exponentially more succinct than positive existential rewritings, while first-order rewritings can be superpolynomially more succinct than positive existential rewritings. On the other hand, we construct polynomial-size positive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants. (C) 2014 Elsevier B.V. All rights reserved.