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

ontological query answeringquery optimizationquery rewritingtuple-generating dependencies

Mathematics Subject Classification ID

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

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

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)