REsolution-based QUery rewrIting for Expressive Models

REQUIEM (REsolution-based QUery rewrIting for Expressive Models) is a prototypical implementation of a query rewriting algorithm recently developed by Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks at the Department of Computer Science, University of Oxford (see publications).

Given an ELHI TBox and a conjunctive query, REQUIEM computes a datalog query that is a rewriting of the query w.r.t. the TBox. REQUIEM produces worst-case optimal rewritings: if the TBox is in ELHI, ELH or EL, then the rewriting is a datalog query; if the TBox is in DLlite+, then the rewriting consists of a union of conjunctive queries and a linear datalog program; and if the TBox is in DLliteR, then the rewriting is a union of conjunctive queries. Existing (deductive) database technology can be used to evaluate the rewriting over any ABox.

REQUIEM can be run in three modalities: the Naive modality, which corresponds to the original algorithm; the Full modality, which applies forward/query subsumption and dependency graph pruning, and the Greedy modality, which applies the optimizations of the Full modality plus greedy unfolding (only useful for EL ontologies) (see Using REQUIEM).