Rewriting Minimizations for Efficient Query Answering over Ontologies
Tassos Venetis, Giorgos Stoilos, Vasilis Vassalos · International Journal of Artificial Intelligence Tools · 2017
Computing a (Union of Conjunctive Queries — UCQ) rewriting ℛ for an input query and ontology and evaluating it over the given dataset is a prominent approach to query answering over ontologies. However, ℛ can be large and complex in structure hence additional techniques, like query subsumption and data constraints, need to be employed in order to minimize ℛ and lead to an efficient evaluation. Although sound in theory, how to efficiently and effectively implement many of these techniques in practice could be challenging. For example, many systems do not implement query subsumption. In the current paper we present several practical techniques for UCQ rewriting minimization. First, we present an optimized algorithm for eliminating redundant (w.r.t. subsumption) queries as well as a novel framework for rewriting minimization using data constraints. Second, we show how these techniques can also be used to speed up the computation of ℛ in first place. Third, we integrated all our techniques in our query rewriting system IQAROS and conducted an extensive experimental evaluation using many artificial as well as challenging real-world ontologies obtaining encouraging results as, in the vast majority of cases, our system is more efficient compared to the two most popular state-of-the-art systems.