Exponential lower bounds and separation for query rewriting

DOI10.1007/978-3-642-31585-5_26MaRDI QIDQ3167017zbMATH OpenOpenAlexFDO

Authors Roman Kontchakov, Stanislav Kikot, Vladimir V. Podolskii, Michael Zakharyaschev

Publication date 1 November 2012

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4193, https://eprints.bbk.ac.uk/id/eprint/6632/1/ICALP-final.pdf

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30) Logic programming (68N17) Database theory (68P15) Grammars and rewriting systems (68Q42)

Abstract: We establish connections between the size of circuits and formulas computing monotone Boolean functions and the size of first-order and nonrecursive Datalog rewritings for conjunctive queries over OWL 2 QL ontologies. We use known lower bounds and separation results from circuit complexity to prove similar results for the size of rewritings that do not use non-signature constants. For example, we show that, in the worst case, positive existential and nonrecursive Datalog rewritings are exponentially longer than the original queries; 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.

Recommendations

• The price of query rewriting in ontology-based data access
• On the succinctness of query rewriting over shallow ontologies
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• Tree-like queries in OWL 2 QL: succinctness and complexity results
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics

Cited in

(9)

• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• On the succinctness of query rewriting over shallow ontologies
• Tree-like queries in OWL 2 QL: succinctness and complexity results
• Scalable reasoning by abstraction beyond DL-Lite
• Circuit complexity meets ontology-based data access
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• The price of query rewriting in ontology-based data access
• Bounds in ontology-based data access via circuit complexity

This page was built for publication: Exponential lower bounds and separation for query rewriting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167017)