Lists
Lists
Gottlob, Georg, Kikot, Stanislav, Kontchakov, Roman, Podolskii, Vladimir, Schwentick, Thomas and Zakharyaschev, Michael (2014) The price of query rewriting in ontology-based data access. Artificial Intelligence, 213. pp. 42-59. ISSN 0004-3702
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 asOWL 2 QL, linear Datalog±and sticky Datalog±. We show thatpositive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for inten-sional predicates in the case of datalog rewritings), suffer an exponential blowup in the worst case, while first-orderrewritings can grow superpolynomially unless NP⊆P/poly. We also prove that nonrecursive datalog rewritings arein general exponentially more succinct than positive existential rewritings, while first-order rewritings can be super-polynomially more succinct than positive existential rewritings. On the other hand, we construct polynomial-sizepositive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants.
 |
View Item |