Exponential Lower Bounds and Separation for Query Rewriting
Exponential Lower Bounds and Separation for Query Rewriting
复制标题
查询重写的指数下界和分离
DOI：
10.1007/978-3-642-31585-5_26
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Zakharyaschev
中科院分区：
文献类型：
--
作者：
S. Kikot;R. Kontchakov;V. Podolskii;M. Zakharyaschev
我们建立了计算单调布尔函数的电路和公式的大小与OWL2QL本体上合取查询的一阶和非递归数据重写的大小之间的联系。我们使用已知的下界和电路复杂性的分离结果来证明不使用非签名常量的重写大小的类似结果。例如，我们证明了，在最坏的情况下，正的存在和非递归的Datalog重写比原始查询的长度是指数级的；非递归的Datalog重写通常比正的存在的重写以指数的方式更简洁；而一阶重写可以比正的存在的重写更简洁。
We establish connections between the size of circuits and formulas computing monotone Boolean functions and the size of first-order and nonrecursive Datalog rewritings for conjunctive queries over OWL 2 QL ontologies. We use known lower bounds and separation results from circuit complexity to prove similar results for the size of rewritings that do not use non-signature constants. For example, we show that, in the worst case, positive existential and nonrecursive Datalog rewritings are exponentially longer than the original queries; 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.
使用 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
虚拟视图对遏制的影响
影响因子：
2.5
作者：
Benedikt M
通讯作者：
Benedikt M