The Price of Query Rewriting in Ontology-Based Data Access

Artificial Intelligence. 2014. Vol. 213. P. 42–59.

Gottlob G., Kikot S., Kontchakov R., Подольский В. В., Schwentick T., Zakharyaschev M.

We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontologybased data access with ontology languages such as OWL2QL, linear Datalog and sticky Datalog. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case of datalog rewritings), suer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP in P/poly. We also prove that 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. On the other hand, we construct polynomial-size positive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants.

Ключевые слова: ontology, datalog, conjunctive query, query rewriting, succinctness, Boolean circuit, monotone complexity