The price of query rewriting in ontology-based data access

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

AIJ-final.pdf - Accepted Version

Download (235kB) | Preview
Official URL:

Abstract / Description

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.

Item Type: Article
Uncontrolled Keywords: ontology, datalog, conjunctive query, query rewriting, succinctness, Boolean circuit, monotone complexity
Subjects: 000 Computer science, information & general works
Department: School of Computing and Digital Media
Depositing User: Stanislav Kikot
Date Deposited: 15 May 2020 11:32
Last Modified: 15 May 2020 11:32


Downloads per month over past year

Downloads each year

Actions (login required)

View Item View Item