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

Preview

Text AIJ-final.pdf - Accepted Version Download (235kB) | Preview

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
URI:	https://repository.londonmet.ac.uk/id/eprint/5789

Downloads

Actions (login required)

View Item