\input zb-basic
\input zb-ioport
\iteman{io-port 06101151}
\itemau{Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir; Zakharyaschev, Michael}
\itemti{Exponential lower bounds and separation for query rewriting.}
\itemso{Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9--13, 2012. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-31584-8/pbk). Lecture Notes in Computer Science 7392, 263-274 (2012).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-31585-5\_26}
\end