Compact Rewritings for Existential Rules∗

Querying large databases while taking ontolo-gies into account is currently a very active do-main research. In this paper, we consider ontolo-gies described by existential rules (also known as Datalog+/-), a framework that generalizes lightweight description logics. A common ap-proach is to rewrite a conjunctive query w.r.t an on-tology into a union of conjunctive queries (UCQ) which can be directly evaluated against a database. However, the practicability of this approach is questionable due to 1) the weak expressivity of classes for which efficient rewriters have been im-plemented 2) the large size of optimal rewritings using UCQ. We propose to use semi-conjunctive queries (SCQ), which are a restricted form of positive existential formulas, and compute sound and complete rewritings, which are union of SCQ (USCQ). A novel algorithm for query rewriting, COMPACT, is presented. It computes sound and complete rewritings for large classes of ontologies. First experiments show that USCQ are both effi-ciently computable and more efficiently evaluable than their equivalent UCQ.