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 Q and ontology O O are transformed into a (datalog) program R R that captures the answers of Q Q over O O and every database D 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 R i for each refined query Qi Q i from scratch, discarding any information possibly computed previously. In this paper we study the problem of computing a rewriting for a query Q? Q ? which is a refinement of a query Q Q by exploiting as much as possible information possibly computed previously for Q Q . We investigate whether such information is usable when computing a rewriting for Q? Q ? and present detailed algorithms. Finally, we have implemented all proposed algorithms and conducted an extensive experimental evaluation.
query rewriting query refinement ontologies description logics dl-lite el