Eleni Tsalapati, National Technical University of Athens
Mon 23 Mar 2015, 14:00 - 15:00
Informatics Forum (IF-4.31/4.33)

If you have a question about this talk, please contact: Suzanne Perry (sperry)

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 O, is transformed into a new datalog query that captures all answers of Q over O and any dataset D.

This process can be time consuming as it is of high computational complexity. 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. This can be particularly problematic in many real world applications that involve frequent and relatively small modifications on quite large ontologies.

In this talk we will initially present in brief two resolution-based query-rewriting systems: Requiem and Rapid. Requiem is a fairly straightforward implementation of resolution with very little optimisations and is the core of the commercial system Blackout. Rapid is one of the fastest state-of-the-art rewriting systems. Next, we will present the problem of computing a rewriting for a CQ over an ontology that has been modified. Our approach is based on the reuse of the information obtained by the extraction of some previous rewriting with the goal of performing the least possible computations. We will present detailed algorithms for both ontology revision and ontology contraction and finally, we will present an experimental evaluation using the systems Requiem and Rapid.