Query Rewriting Under Ontology Change
Eleni Tsalapati, Giorgos Stoilos, Alexandros Chortaras, Giorgos B. Stamou, George Koletsos · The Computer Journal · 2016
Query rewriting is an important technique for answering queries over data described using ontologies. In query rewriting the input, a conjunctive query (CQ) |$q$| and an ontology |$\mathcal {O}$|, is transformed into a new datalog query that captures all answers of |$q$| over |$\mathcal {O}$| and any dataset |$D$|. This process can be time-consuming as it is of high computational complexity. In many real-world applications, this can be particularly problematic as they involve frequent and relatively small modifications on quite large ontologies. Hence, a drawback of most of modern query rewriting systems is that every time the initial ontology is modified, e.g. when new axioms are added or existing ones removed, they compute a new rewriting from scratch. In this paper, we study the problem of computing a rewriting for a CQ over an ontology that has been modified. We do this by reusing the information obtained by the extraction of some previous rewriting with the goal of performing the least possible computations. We study the problem theoretically, present detailed algorithms for both ontology revision and ontology contraction and finally, present an extensive experimental evaluation using the well-known query rewriting systems Requiem and Rapid.