2012/02/19 by Stanislav Kikot, Roman Kontchakov, Kikot, Stanislav +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · doi:10.48550/arxiv.1202.4193
openalex publication_date 2012/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.