Query Rewriting Under Ontology Change. (22nd January 2016)

• Record Type: Journal Article
• Authors: Tsalapati, Eleni; Stoilos, Giorgos; Chortaras, Alexandros; Stamou, Giorgos; Koletsos, George
• Is Part Of: Computer journal. Volume 60:Number 3(2017)
• Page Start: 389
• Page End: 409
• Publication Date: 2016-01-22
• Subjects: ontologies -- query rewriting -- ontology evolution -- ontology contraction -- ontology revision; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxv120
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: 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.