The price of query rewriting in ontology-based data access

DOI10.1016/j.artint.2014.04.004zbMath1390.68246OpenAlexW1981545838WikidataQ59259475 ScholiaQ59259475MaRDI QIDQ2453744

Thomas Schwentick, Roman Kontchakov, Stanislav Kikot, Georg Gottlob, Vladimir V. Podolskii, Michael Zakharyashchev

Publication date: 10 June 2014

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2014.04.004

zbMATH Keywords

Datalogconjunctive queryontologysuccinctnessBoolean circuitquery rewritingmonotone complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Knowledge representation (68T30)

Related Items (13)

Unnamed Item ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Circuit Complexity Meets Ontology-Based Data Access ⋮ Bounds in ontology-based data access via circuit complexity ⋮ Finite model reasoning over existential rules ⋮ Polynomial combined first-order rewritings for linear and guarded existential rules ⋮ Ontology-Mediated Query Answering with Data-Tractable Description Logics ⋮ Logical foundations of information disclosure in ontology-based data integration ⋮ Reasoning on anonymity in Datalog ⋮ Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data ⋮ Polynomial rewritings from expressive description logics with closed predicates to variants of Datalog ⋮ Foundations of ontology-based data access under bag semantics ⋮ Preference-based inconsistency-tolerant query answering under existential rules

Uses Software

• Ontop

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards more expressive ontology languages: the query answering problem
• Boolean function complexity. Advances and frontiers.
• On rules with existential variables: walking the decidability line
• The monotone circuit complexity of Boolean functions
• Conjunctive query containment revisited
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Parametrized complexity theory.
• Exponential Lower Bounds and Separation for Query Rewriting
• Homomorphism preservation theorems
• The DL-Lite Family and Relations
• Monotone circuits for matching require linear depth
• Logical Description of Monotone NP Problems
• On the succinctness of query rewriting over shallow ontologies
• Fast parallel matrix and GCD computations
• When is the evaluation of conjunctive queries tractable?
• Optimized Query Rewriting for OWL 2 QL
• Eliminating definitions and Skolem functions in first-order logic
• Computational Complexity
• Linking Data to Ontologies

This page was built for publication: The price of query rewriting in ontology-based data access