Query Rewriting and Optimization for Ontological Databases

DOI10.1145/2638546MaRDI QIDQ5012503zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Giorgio Orsi, Andreas Pieris

Publication date 25 November 2021

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

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

zbMATH Keywords

query optimizationquery rewritingontological query answeringtuple-generating dependencies

Mathematics Subject Classification ID

Knowledge representation (68T30) Database theory (68P15)

Abstract: Ontological queries are evaluated against a knowledge base consisting of an extensional database and an ontology (i.e., a set of logical assertions and constraints which derive new intensional knowledge from the extensional database), rather than directly on the extensional database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper, we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent first-order query against the underlying extensional database. We present a novel query rewriting algorithm for rather general types of ontological constraints which is well-suited for practical implementations. In particular, we show how a conjunctive query against a knowledge base, expressed using linear and sticky existential rules, that is, members of the recently introduced Datalog+/- family of ontology languages, can be compiled into a union of conjunctive queries (UCQ) against the underlying database. Ontological query optimization, in this context, attempts to improve this rewriting process so to produce possibly small and cost-effective UCQ rewritings for an input query.

Recommendations

• Optimized query rewriting for OWL 2 QL
• The price of query rewriting in ontology-based data access
• On the succinctness of query rewriting over shallow ontologies
• Exact query reformulation with first-order ontologies and databases
• Exact query reformulation over databases with first-order and description logics ontologies

Cited in

(20)

• Ontological query answering under many-valued group preferences in Datalog\(+/-\)
• Optimized query rewriting for OWL 2 QL
• A Single Approach to Decide Chase Termination on Linear Existential Rules
• Compact query rewritings for ontology-based query answering
• Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
• Top-\(k\) retrieval for ontology mediated access to relational databases
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• Optimizing SPARQL query answering over OWL ontologies
• The pragmatic proof: hypermedia API composition and execution
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Exact query reformulation with first-order ontologies and databases
• Effective query answering with ontologies and DBoxes
• Reasoning on anonymity in Datalog
• Ontology-revision operators based on reinterpretation
• Polynomial combined first-order rewritings for linear and guarded existential rules
• On the interaction of existential rules and equality constraints in ontology querying
• Query answering over inconsistent knowledge bases: a probabilistic approach
• Inconsistency-tolerant query answering for existential rules
• Exact query reformulation over databases with first-order and description logics ontologies
• Finite model reasoning over existential rules

This page was built for publication: Query Rewriting and Optimization for Ontological Databases

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