Exponential lower bounds and separation for query rewriting

DOI10.1007/978-3-642-31585-5_26zbMATH Open1367.68089arXiv1202.4193OpenAlexW2137498727MaRDI QIDQ3167017FDOQ3167017

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)

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.

Full work available at URL: https://arxiv.org/abs/1202.4193

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

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)

Cited In (9)

• The price of query rewriting in ontology-based data access
• Circuit complexity meets ontology-based data access
• Scalable reasoning by abstraction beyond DL-Lite
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Ontology-Mediated Query Answering with Data-Tractable 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
• 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)