Optimizing Query Answering under Ontological Constraints

Abstract

Ontological queries are evaluated against a database combined with ontological constraints. Answering such queries is a challenging new problem for database research. For many ontological modelling languages, query answering can be solved via query rewriting: given a conjunctive query and an ontology, the query can be transformed into a first-order query, called the perfect rewriting, that takes into account the semantic consequences of the ontology. Then, for every extensional database D, the answer to the query is obtained by evaluating the rewritten query against D. In this paper we present a new algorithm that computes the perfect rewriting of a conjunctive query w.r.t. a linear Datalog+/- ontology. Also, we provide an experimental comparison of our algorithm with existing rewriting techniques.