The complexity of ontology-based data access with OWL2QL and bounded treewidth queries
The DL workshop is the major annual event of the description logic research community. It is the forum at which those interested in description logics, both from academia and industry, meet to discuss ideas, share information and compare experiences.
The International Workshop on Description Logics is the main annual event of the Description Logic research community. It is the forum at which those interested in description logics, from both academia and industry, meet to discuss ideas, share information, and compare experiences. The workshop explicitly welcomes submissions from researchers that are new to the area and provides quality feedback via peer-reviewing, while at the same time being of an inclusive nature with a very high acceptance rate. There are only informal (electronic) proceedings and inclusion of a paper there is not supposed to preclude its publication at conferences. Further information can be found on the DL Web pages at http://dl.kr.org/.
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.