Can I read Exponential Lower Bounds and Separation for Query Rewriting on EtoBox?

Exponential Lower Bounds and Separation for Query Rewriting by Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Zakharyaschev, Michael is a scholarly article available to read on EtoBox.

What is Exponential Lower Bounds and Separation for Query Rewriting about?

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.

Author

Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Zakharyaschev, Michael

Published

2012

Language

EN