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
|
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
Downloads per month over past year
Downloads each year
Actions (login required)
![]() |
View Item |