Query rewriting under query refinements

Ontologies expressed in description logics or extensions of datalog are gradually used for describing the domain of many research and industrial strength applications. They provide a formal semantically rich and data-independent layer over which user queries can be posed. A prominent technique for query answering in ontology-based applications is query rewriting, where the given user query Q and ontology O are transformed into a (datalog) program R that captures the answers of Q over O and every database D. In realistic scenarios it is quite often the case that users refine their original query by adding or removing constraints until they produce a final one. In such scenarios, however, all existing systems would compute a new rewriting Ri for each refined query Qi from scratch, discarding any information possibly computed previously. In this paper we study the problem of computing a rewriting for a query Q′ which is a “refinement” of a query Q by exploiting as much as possible information possibly computed previously for Q. We investigate whether such information is usable when computing a rewriting for Q′ and present detailed algorithms. Finally, we have implemented all proposed algorithms and conducted an extensive experimental evaluation.