Query Rewriting for Existential Rules with Compiled Preorder

1 Introduction

We address the issue of Ontology-Based Query Answering (OBQA), which seeks to exploit knowledge expressed in ontologies when querying data. We consider the novel framework of existential rules, also called Datalog± [Baget et al., 2011; Cal`ı et al., 2012; Kr¨otzsch and Rudolph, 2011]. Existential rules are an exstension of function-free positive conjunctive rules that allows for existentially quantified variables in rule heads. These rules are able to assert the existence of unknown entities, a fundamental feature in an open-domain perspective, where it cannot be assumed that the description of data is complete. Interestingly, existential rules generalize Horn description logics (DLs), in particular lightweight DLs used in the context of OBQA, such as DL-Lite [Calvanese et al., 2005] and EL [Baader, 2003], which form the core of so-called tractable profiles of the Semantic Web ontological language OWL 2. They overcome some limitations of these DLs by allowing for non-tree structures as well as unbounded predicate arity. We consider here the basic database queries, i.e., conjunctive queries (CQs).

There are two main approaches to query answering in presence of existential rules and Horn DLs. The first approach is related to forward chaining: it triggers the rules to build a finite representation of inferred data such that the answers can be computed by evaluating the query against this representation, e.g., [Cal`ı et al., 2008; Thomazo et al., 2012]. The second approach, initiated by DL-Lite [Calvanese et al., 2005], is related to backward chaining: it rewrites the query using the rules such that the answers can be computed by evaluating the rewritten query against the data, e.g., [Baget et al., 2009; Gottlob et al., 2011] on existential rules. Some techniques combine both approaches [Kontchakov et al., 2011; Thomazo and Rudolph, 2014]. Each technique is applicable to a specific existential rule fragment.

In this paper, we focus on the query rewriting approach, which has the advantage of being independent from the data. This technique typically outputs a union of conjunctive queries (UCQ), with the aim of benefiting from optimized relational database management systems (RDBMS). However, despite the good theoretical data complexity, first experiments exhibited a serious problem related to the size of the rewritten query, e.g., [Rosati and Almatelli, 2010]. Indeed, the output query can be exponentially larger than the initial query, even with very simple ontologies, and even if the output is extended to arbitrary first-order queries [Kikot et al., 2011; 2012]. This led to a significant amount of work on rewriting into more compact queries, which may remain firstorder queries (hence expressible in SQL) or go beyond them (like Datalog programs, e.g., [Gottlob and Schwentick, 2012; Stefanoni et al., 2012]). Nowadays, mature systems have emerged for OWL 2 QL [Rodriguez-Muro et al., 2013; Civili et al., 2013], as well as prototypes for the EL family and more expressive DLs, e.g., [Eiter et al., 2012]. Existential rules are more complex to process. Entailment with general existential rules is even undecidable (e.g., [Beeri and Vardi, 1981]). However, expressive subclasses ensuring the existence of a UCQ rewriting are known, such as linear rules, which generalize most DL-Lite dialects, the sticky family, classes satisfying conditions expressed on a graph of rule dependencies, and weakly recursive rules [Cal`ı et al., 2009; 2012; Baget et al., 2011; Civili and Rosati, 2012].

A well-known source of combinatorial explosion are some very simple rules that typically express taxonomies or relation signatures. These rules are at the core of any ontology. We propose a new technique to tame this source of complexity. It relies on compiling these rules into a preorder on atoms and embedding this preorder into the rewriting process. Intituitively, each atom "represents" all its "specializations". Hence, the query rewriting process avoids exploring many CQs and outputs a small UCQ. This UCQ can be seen as a "pivotal" representation, in the sense that it can be evaluated by different kinds of systems: it can be passed to a Datalog engine or unfolded into a positive existential query (a UCQ or a more compact form of query) to be processed by an RDBMS; it can also be directly processed if data is stored in main memory and the appropriate homomorphism operation is implemented.

First, we prove that the new rewriting operator is sound and complete, and provide an algorithm that, given any CQ and any set of existential rules, effectively outputs a minimal, sound and complete UCQ-rewriting, if one exists (which may not be the case due to the indecidability of the problem). Since the computation of the preorder is independent from any query, we can divide this algorithm into a compilation step performed offline, and a query rewriting step, which takes the preorder as input. Second, we report experiments, which show that this optimization leads to substantial gains, in terms of size of the output and query rewriting runtime, and is able to scale on very large ontologies. In the case when the desired output is a "regular" UCQ, it remains faster for our rewriting tool to compute a pivotal UCQ and to unfold it, than to directly compute a regular UCQ. Moreover, our prototype behaves well compared to other UCQ-rewriting tools tailored for DL-Lite ontologies, even if it does not exploit the specificities of these languages.

2 Preliminaries

An atom is of the form p(t1, . . . , tk) where p is a predicate with arity k, and the ti are terms, i.e., variables or constants (we do not consider other function symbols). Given an atom or a set of atoms A, vars(A), consts(A) and terms(A) denote its set of variables, of constants and of terms, respectively. In the following examples, all the terms are variables (denoted by x, y, z, etc.) unless otherwise specified. |= denotes the classical logical consequence. Given sets of atoms A and B, a homomorphism h from A to B is a substitution of vars(A) by terms(B) such that h(A) ⊆ B. It is convenient to extend the domain of a substitution h to a set of terms, such that h(t) = t for all unchanged terms (in particular constants). If there is a homomorphism h from A to B, we say that A maps to B (by h); then, A is said to be more general than B, and B more specific than A.

A fact is the existential closure of a conjunction of atoms (this generalization of the classical notion of a fact allows to take existential variables into account). A conjunctive query is an existentially quantified conjunction of atoms. W.l.o.g. we consider only Boolean conjunctive queries (i.e., closed formulas) in this paper and denote them by CQs. In the following, we will see facts and CQs as sets of atoms. The answer to a CQ Q in a fact F is yes if F |= Q; it is well-known that F |= Q iff Q maps to F .

Definition 1 (Existential rule) An existential rule (or simply rule hereafter) is a formula R = ∀x∀y(B[x, y] → (∃z H[y, z])) where B = body(R) and H = head(R) are conjunctions of atoms, resp. called the body and the head of R. The frontier of R is the set of variables vars(B) ∩ vars(H) = y. The existential variables in R is the set of variables vars(H) \ vars(B) = z.

In the following, we will omit quantifiers in rules as there is no ambiguity. E.g. p(x, y) → p(y, z) denotes the formula ∀x∀y(p(x, y) → ∃zp(y, z)).

A knowledge base (KB) K = (F,R) is composed of a finite set of facts (which can be seen as a single fact) F and a finite set of existential rules R. The CQ entailment problem is the following: given a KB K = (F,R) and a CQ Q, does F,R |= Q hold? This problem is known to be undecidable in the general case [Beeri and Vardi, 1981]. It can be solved by computing a sound and complete rewritten query Q from Q and R, provided that such a finite Q exists, then asking if F |= Q. Here, the target query Q is a union of CQs (UCQ), that we see as a set of CQs, called a rewriting set of Q.

Definition 2 [Sound and Complete (rewriting) set of CQs] Let R be a set of existential rules, Q be a CQ, and Q be a set of CQs. Q is said to be sound w.r.t. Q and R if for any fact F, for all Qi ∈ Q, if Qi maps to F then R, F |= Q. Reciprocally, Q is said to be complete w.r.t. Q and R if for any fact F, if R, F |= Q then there is Qi ∈ Q such that Qi maps to F.

A set of rules R for which any query Q has a finite sound and complete set of rewritings (in other words, Q is rewritable into a UCQ), is called a finite unification set (fus) [Baget et al., 2009]. Note that restricting a complete rewriting set Q to its most general elements preserves its completeness. A cover of Q is an inclusion-minimal subset Q′ of Q such that each element Q of Q is more specific than an element Q′ of Q′ (i.e., in database terms: Q is contained in Q′ ). If a set has a finite cover, then all its covers have the same size, hence all minimal, sound and complete rewriting sets have the same cardinality [K¨onig et al., 2012]. Hereafter, we, respectively, denote by R, R and Q the considered set of rules, a rule of R, and the initial query. We assume that rules have disjoint sets of variables, as well as Q and R.

The rewriting operation involves unifying part of Q and part of head(R). Existential variables in rule heads induce a possibly complex structure, therefore unification has to consider subsets of atoms at once (called "pieces") instead of single atoms, hence the name piece-unifier. Indeed, if a variable x from Q is unified with an existential variable from head(R), then all atoms in which x occurs must be part of the unification, otherwise the obtained rewriting is unsound. Given Q′ ⊆ Q, we call separating variables of Q′ , the variables occurring in both Q′ and (Q \ Q′ ); the other variables from Q′ are called non-separating. Let Q′ be the unified part of Q: only non-separating variables from Q′ can be unified with an existential variable of the rule.

Definition 3 (Piece-Unifier [K¨onig et al., 2012]) A pieceunifier of Q with R is a triple µ = (Q′ ,H′ , u), where Q′ ̸= ∅, Q′ ⊆ Q, H′ ⊆ head(R) and u is a substitution of T = terms(Q′ ) ∪ terms(H′ ) by T , such that:

1. u(H′ ) = u(Q′ );
2. for all existential variable x ∈ vars(H′ ) and t ∈ T, with t ̸= x, if u(x) = u(t), then t is a non-separating variable fromQ′ .

Example 1 (Piece-unification) Let R = twin(x, y) → motherOf(z, x) ∧ motherOf(z, y), where z is an existential variable, expressing that twins have a common mother. Let Qno = {motherOf(v,w), painter(v)}, asking if there is a mother who is a painter. The only candidate atom in Qno is motherOf(v,w): then, v would be unified with z, hence painter(v) should be unified as well, which is impossible. Let Qyes = {motherOf (v, w), motherOf (v, t), f emale(w), male(t)} asking if there is a mother of a female and a male. A piece-unifier of Qyes with R is µ = (Q′ = {motherOf(v,w),motherOf(v, t)},H′ = {motherOf(z, x),motherOf(z, y)}, u = {z ↦→ v, x ↦→ w, y ↦→ t}) (in the general case Q′ and H′ may be nonisomorphic). The one-step rewriting of Qyes according to µ is {twin(w, t),female(w),male(t)}, as formally defined below.

Definition 4 (One-step Rewriting, R-rewriting, β∗ ) Given a piece-unifier µ = (Q′ ,H′ , u) of Q with R, the one-step rewriting of Q according to µ, denoted by β(Q,R, µ), is the CQ u(body(R)) ∪ u(Q \ Q′ ). An R-rewriting of Q is a CQ Qk obtained by a finite sequence (Q0 = Q),Q1, . . . ,Qk such that for all 0 ≤ i < k, there is Ri ∈ R and a piece-unifier µ of Qi with Ri such that Qi+1 = β(Qi, Ri, µ). We denote by β∗ (Q, R) the set of all R-rewritings of Q.

It is known that β∗ (Q,R) is a sound and complete set (within the meaning of Def. 2) [Baget et al., 2011].

3 Embedding a Preorder on Atoms

We first explain the ideas underlying the rewriting technique before providing formal definitions. An essential component of any ontology is a hierarchy of concepts and, to a lesser extent, a hierarchy of relations (binary relations are also called roles or properties). In a logical framework, concepts and relations are represented by predicates. Simple rules of the form p(x1, . . . , xk) → q(x1, . . . , xk), where k = 1 for a concept, express that p is more specific than q (notation p ≤ q). See e.g., the logical translation of atomic inclusions in DL, and the subClassOf and subPropertyOf assertions in RDFS / OWL. These rules, called hierarchical hereafter, are an obvious cause of combinatorial explosion in query rewriting, as illustrated by the next example.

Example 2 Let R1 . . .Rn be rules of the form Ri : bi(x) → bi-1(x). Let Q = {b0(x1), . . . , b0(xk)}. Each atom b0(xj) in Q is rewritten into b1(xj), which in turn is rewritten into b2(xj), and so on. Thus, there are (n + 1)k rewritings of Q.

Hierarchical rules can be compiled into a (partial) preorder (i.e., a reflexive and transitive relation) on predicates, say

≤. Then, the homomorphism notion can be extended to take this preorder into account. Let us call ≤-homomorphism h from a set of atoms A1 to a set of atoms A2 a substitution of terms(A1) by terms(A2) such that for all q(e1, . . . , ek) ∈ A1, there is p(h(e1), . . . , h(ek)) ∈ A2 with p ≤ q. It is easily checked that, given a set of hierarchical rules Rc, it holds that Rc, F |= Q if and only if there is a ≤-homomorphism from Q to F. Now, let R = Rc ∪Re be a set of existential rules, where Rc is composed of the hierarchical rules. Given the preorder ≤ associated with Rc, we would like to have F,R |= Q if and only if there is an Re-rewriting of Q that maps to F by a ≤-homomorphism. In Ex. 2, we would have bj ≤ bi for any i ≤ j; then, since all rules are hierarchical, we would get a single rewriting, i.e., Q itself, instead of exponentially many. However, to achieve completeness, we cannot simply rewrite Q with Re and forget about Rc, we have to embed the preorder into the rewriting process. This idea can be further extended to compile all rules with an atomic body, as long as they do not introduce existential variables. This allows to compile other common axioms, as illustrated by Ex. 3. However, since the atoms in a rule may have predicates of different arity and arguments in different positions, we cannot rely on a simple preorder on predicates anymore. We have to embed a preorder on atoms.

Example 3 Let Rex be the following set of rules:

• R1 = r(x, y) → t(x, y) (r is a specialization of t)
• R2 = s(x, y) → t(y, x)
• R′2 = t(x, y) → s(y, x) (s and t are inverse relations)
• R3 = t(x, y) → q(x) (q is the domain of t)
• R4 = t(x, y) → q(y) (q is the range of t)
• R5 = p(x, y, z) → r(x, z) (r is a projection of p)
• R6 = p(x, x, z) → s(x, x) (introduction of a "self loop")

A rule is said to be compilable if it has a single body atom, no existential variable and no constant. 1 W.l.o.g. we also assume that a compilable rule has a single head.

Definition 5 (Inferred Rule, Saturation) Let R1 and R2 be compilable rules such that head(R1) and body(R2) are unifiable by a (classical) most general unifier u. The rule inferred from (R1, R2) is R1 · R2 = u(body(R1)) → u(head(R2)). Given a set Rc of compilable rules, the saturation of Rc, denoted by R∗c , is the closure of Rc by the · operation.

Example 4 The rules inferred from Rex (Ex. 3) are the following; we recall that rules have disjoint sets of variables, even if we use the same variables for simplicity:

• R1 · R′2 = r(x, y) → s(y, x); R1 · R3 = r(x, y) → q(x)
• R1 · R4 = r(x, y) → q(y); R2 · R′2 = s(x, y) → s(x, y)
• R2 · R3 = s(x, y) → q(y); R2 · R4 = s(x, y) → q(x)
• R′2 ·R2 = t(x, y) → t(x, y); R5 ·R1 = p(x, y, z) → t(x, z)
• R6 · R2 = p(x, x, z) → t(x, x)
• R5 · R1 · R′2 = p(x, y, z) → s(z, x)
• R5 · R1 · R3 = p(x, y, z) → q(x)
• R5 · R1 · R4 = p(x, y, z) → q(z)
• R6 · R2 · R3 = R6 · R2 · R4 = p(x, x, z) → q(x)

The size of R∗c is polynomial in the size of Rc when the predicate arity is bounded (more specifically, when the number of occurrences of a variable in a predicate is bounded):

1 The condition on constants is to simplify definitions.

Proposition 1 |R∗c | is bounded by |Rc|2 ×Bk, where k is the maximum predicate arity and Bk is the k-th Bell number.

Proof: The number of possible specializations of an atom with arity k is bounded by the number of partitions of {1, . . . , k}, known as the k-th Bell number Bk. Thus, the number of distinct rules (up to variable renaming) that can be obtained is bounded by |Rc|2 ×Bk. Note that Bk < 2k2 . □

The saturation of Rc can easily be made minimal by removing tautological rules (necessarily of the form H → H) and redundant rules, i.e., rules entailed by other rules. Given non-tautological compilable rules Ri and Rj , Rj |= Ri iff Ri subsumes Rj , as defined below.

Definition 6 (Rule Subsumption) Let Ri and Rj be compilable rules. We say that Ri subsumes Rj if there is a homomorphism h from body(Ri) to body(Rj) such that h(head(Ri)) = head(Rj ).

Example 3 (cont'd) R2 · R′2 and R′2 · R2 are tautological rules. R6 · R2 · R3 = p(x, x, z) → q(x) is subsumed by R5 · R1 · R3 = p(x, y, z) → q(x).

We first define a preorder ≼ on atoms (and sets of atoms) that will be used to avoid query rewriting with Rc.

Definition 7 (≼) Let a and b be atoms. We note a ≼ b if (i) a = b or (ii) there is a rule R ∈ R∗c that subsumes the rule (a → b) (equivalently: the application of R to a yields exactly b). Let A and B be sets of atoms. We note A ≼ B if there is a surjective mapping f from B to A such that for all b ∈ B, f(b) ≼ b.

In the above definition, note that a ≼ b implies terms(b) ⊆ terms(a), and the same holds for A and B; moreover, if a ≼ b and a ̸= b, then the one-step rewriting of b with R may be strictly more general than a, as shown in Ex. 5.

Example 5 Let R = r(x, y) → q(x), a = r(c1, c2) and b = q(c1). The application of R to a yields b, hence a ≼ b. The one-step rewriting of b with R is not a but r(c1, y).

More generally, considering sets of atoms:

Property 1 Let A and B be sets of atoms. It holds that A ≼ B iff there is an Rc-rewriting B′ of B that maps to A by a substitution s of vars(B′ ) \ vars(B) by terms(A) such that s(B′ ) = A.

Example 6 Let R∗ex from Ex. 3 and 4. Let A = {p(u, u, c1), r(c2, c1)} and B = {s(u, u), s(c1, u), t(c2, c1), q(c2)}, where c1 and c2 are constants. One has A ≼ B since p(u, u, c1) → s(u, u) is subsumed by R6, p(u, u, c1) → s(c1, u) is subsumed by R5 · R1 · R′2 , r(c2, c1) → t(c2, c1) is subsumed by R1 and r(c2, c1) → q(c2) is subsumed by R1 · R3. According to Prop. 1, one can also check that B′ = {p(u, u, z), p(u, y′ , c1), r(c2, c1), r(c2, y)} is an Rexrewriting of B (by successively using rules R6,R5,R1, R′2 , R1, R1, R3) and that B′ maps to A.

Thanks to the preorder ≼, we are now able to embed compiled rules in piece-unifiers.

Definition 8 (≼-Piece-Unifier, ≼-rewriting, β≼) Given a preorder ≼ on atoms, a ≼-piece-unifier of Q with R is a triple µ = (Q′ ,H′ , u) defined similarly to a piece-unifier (Def. 3), with Condition 1 replaced by u(H′ ) ≼ u(Q′ ). The one-step ≼-rewriting of Q according µ, denoted by β≼, is the CQ u(body(R)) ∪ u(Q \ Q′ ).

Example 7 Consider the rules from Ex. 3, the rule R = b(x) → t(x, y) (where y is existential) and the query Q1 = {t(u, v), q(v)}. There is no piece-unifier of Q1 with R but there is a ≼-piece-unifier µ = (Q1, head(R), {x ↦→ u, y ↦→ v}), since R4 subsumes t(u, v) → q(v). We obtain β≼(Q1,R, µ) = {b(u)}. Consider now Q2 = {q(w), s(z,w), c(w)}. With the ≼-piece-unifier µ′ = ({q(w), s(z, w)}, head(R), {x ↦→ w, y ↦→ z}), using R3 and R′2 , we obtain β≼(Q2, R, µ′ ) = {b(w), c(w)}.

Logical entailment between queries and facts can be computed by a homomorphism check, which we now extend to embed ≼.

Definition 9 (≼-homomorphism) Let A and B be sets of atoms. A ≼-homomorphism from B to A is a substitution h from vars(B) to terms(A) such that for all b ∈ B, there is a ∈ A with a ≼ h(b).

Example 8 Consider Q1 and Q2 from Ex. 7. The substitution h = {(u, w), (v, z)} is a ≼-homomorphism from Q1 to Q2. Indeed, t(u, v) and q(v) are both mapped to s(z,w), by using R2 and R2 · R4 respectively.

Property 2 Let A and B be sets of atoms, and Rc be a set of compilable rules with associated preorder ≼. There is a ≼-homomorphism from B to A iff Φ(A), Rc |= Φ(B), where Φ assigns an existentially closed formula to a set of atoms.

The next theorem states that the new rewriting operator β≼, associated with ≼-homomorphism, is logically sound and complete.

Theorem 1 (Soundness and Completeness of β≼) Let K = (F,R) be a KB, where R is partitioned into Re and Rc, a set of compilable rules with associated preorder ≼. Let Q be a CQ. Then F,R |= Q iff there is Q′ ∈ β∗≼(Q,Re) with a ≼-homomorphism fromQ′ to F.

Proof:(Sketch) We rely on the soundness and completeness of classical piece-based rewriting and prove that: (1) if Q′ ∈ β∗≼(Q,Re) then Q′ ∈ β∗ (Q,R) and (2) if Q′ ∈ β∗ (Q,R) then there is Q′′ ∈ β∗≼(Q,Re) such that Q′ ≼ Q′′ . □

4 ACorrect ≼-Rewriting Algorithm

The compilation step consists in partitioning R into Rc and Re, and compiling Rc into the preorder ≼. Then, the rewriting step (Algorithm 1) follows the general schema of [K¨onig et al., 2012]. Given Re, ≼ and Q, the algorithm starts from the rewriting set QF = {Q} and proceeds in a breadth-first manner. At each step, queries from QF that have been generated at the preceding step (i.e., set QE) are explored. "Exploring" a query consists of computing the set of one-step rewritings of this query with all rules in Re (set Qt). At the end of the step, only a cover of QF ∪ Qt is kept (in case of equivalent queries, priority is given to QF for termination reasons).

Algorithm 1: ≼c-REWRITING ALGORITHM

Data: A set of existential rules Re, a preorder on atoms ≼ and a conjunctive query Q Result: A cover of the sound Re-≼-rewritings of Q QF ← {Q}; // resulting set QE ← {Q}; // queries to explore while QE ̸= ∅ do Qt ← ∅; // queries generated at this rewriting step for Qi ∈ QE do for R ∈ Re do for µ ≼-piece-unifier of Qi with R do Qt ← Qt ∪ {β≼(Qi, R, µ)}; Qc ←ComputeCover(QF ∪Qt); // update cover QE ← Qc \ QF ; // select unexplored queries QF ← Qc ; return QF

Pairwise comparing all queries at each step may seem expensive since the comparison relies on a ≼-homomorphism check. The point is to ensure the termination of the algorithm whenever a finite rewriting set exists: since a set of rewritings may be infinite and still have a finite cover, a cover has to be maintained at each step (or computed after a finite number of steps). Note, however, that for linear and sticky rules, this problem does not occur, and the cover could be computed only once at the end of the algorithm.

Theorem 1 is not sufficient to ensure the completeness of the produced set. Indeed, one has to ensure that by pruning more specific queries at each step, the algorithm does not "miss" rewritings. A sufficient property is the so-called prunability of the rewriting operator [K¨onig et al., 2013]. Intuitively, this property ensures that for any Q2 more specific than Q1, the following holds: each one-step rewriting of Q2 is either more specific than Q1 itself, or than a onestep-rewriting of Q1; hence no rewriting is missed if Q2 is removed from the rewriting set without being explored. This property can be formally expressed as follows for β≼:

Property 3 (Prunability) Let Q1 and Q2 be CQs, R be a rule, and ≼ be a preorder on atoms. If Q2 is more specific than Q1, i.e., Q1 maps to Q2 by a ≼-homomorphism, then for all ≼-piece-unifier µ2 of Q2 with R, either β≼(Q2, R, µ2) is more specific than Q1, or there is a ≼-piece-unifier µ1 of Q1 with R such that β≼(Q2,R, µ2) is more specific than β≼(Q1, R, µ1).

With the previous property and Theorem 1, we can prove the correctness of the algorithm:

Theorem 2 Algorithm 1 outputs a (minimal) sound and complete finite rewriting set (with respect to ≼-homomorphism), if such exists, and it does not terminate otherwise.

Algorithm 1 stops exactly when a UCQ-rewriting exists for the input set of rules and query (a sufficient condition being that the set of rules is fus).

5 Query Evaluation

The rewriting set Q produced by Algorithm 1 can be seen as a "pivotal" representation, in the sense that it can be transformed into different kinds of queries, depending on the type of data storage and the applicative context. Obviously, Q can be directly evaluated with an adequate implementation of ≼-homomorphism in the case the data can be loaded in main memory. Otherwise, the set Q ∪ Rc can be straightforwardly translated into a Datalog query. A mixed approach can be adopted with Rc being used to saturate the data, and Q being evaluated over the saturated data. One may even assume that all information that could be inferred by compilable rules is already present in the data, and delegate the encoding of this information to the database manager. This notion is called H-completeness in [Rodriguez-Muro et al., 2013] in the specific context of DL ABoxes. In particular, if Rc is composed solely of hierarchical rules and the data are stored in a RDBMS, semantic index techniques allow to avoid the effective computation of saturation [Rodriguez-Muro and Calvanese, 2012].

When partial saturation of the data is not feasible, Q may also be unfolded into a set of CQs (i.e., a UCQ) Q′ : Q′ is obtained from Q by adding, for each Q ∈ Q, all Q′ such that Q′ ≼ Q (then eliminating redundant queries). Our experiments (see the last section) show that it is more efficient to unfold Q than to directly compute Q′ . More compact forms of positive existential queries can be computed, for instance unions of semi-conjunctive queries (SCQs), which are conjunctions of disjunctions [Thomazo, 2013]: each CQ Q ∈ Q is transformed into an SCQ by replacing each atom a ∈ Q by the disjunction of all atoms a′ such that a′ ≼ a.

6 RelatedWork

Since the seminal paper on DL-Lite [Calvanese et al., 2005], a significant amount of work has been carried out on query rewriting algorithms, mainly for DL-Lite, but also for other Horn-DLs. The work closest to ours is certainly the treewitness (tw) rewriting algorithm for DL-Lite [Kikot et al., 2012] because of the similarities between tw-rewritings and pieces. Another similarity is that tw-rewriting can make the assumption that the database is already saturated with inferrable knowledge that does not involve existential variables (H-completeness assumption). In the context of DL-Lite, this kind of knowledge corresponds exactly to compilable rules (up to the usual DL restrictions: predicate arity bounded by two, no multiple occurrences of variables in atoms). Hence, one could see our technique as an extension of twrewriting with the H-completeness assumption to existential rule KBs. However, the underlying techniques are quite different. Moreover, tw-rewriting heavily exploits the specificities of DL-Lite. First, "DL-Lite rules" without existential variables are necessarily compilable rules. Second, the "anonymous part" of the possibly infinite canonical model of a DL-Lite knowledge base is a set of trees (instead of a hypergraph with any structure for existential rules). This allows for a smart technique that rewrites the query in a single pass (instead of possibly exponentially many passes with fus rules).

Regarding general existential rules, two rewriting methods were proposed [Baget et al., 2009; Gottlob et al., 2011] and respectively implemented in Alaska/PURE [K¨onig et al., 2012] and Nyaya [Virgilio et al., 2012].

7 Experiments

Our algorithm 2 was implemented in Java, as an extension of the query rewriting prototype PURE. All tests were performed on a DELL machine with a processor at 3.60 GHz and 16 GB of RAM. As benchmarks dedicated to existential rules are not available yet, and in order to compare with other tools producing UCQs, which are mostly restricted to DL-Lite, we considered rule bases obtained by translation of DL-LiteR ontologies: first, the widely used benchmark introduced in [P´erez-Urbina et al., 2009] (i.e., ADOLENA (A), STOCKEXCHANGE (S), UNIVERSITY (U) and VICODI (V)); second, very large ontologies built from OpenGalen2 (G) and OBOProtein (O), and used in [Trivela et al., 2013], which respectively contain more than 53k and 34k rules, with 54% and 64% of compilable rules. Each ontology is provided with 5 handcrafted queries. Timeout was set to 10 minutes. Due to space limitation, we list only parts of the experiments.

We first evaluated the impact of rule compilation on the rewriting process, w.r.t. rewriting sizes and runtime respectively. We denote by PUREC the extension of PURE and call pivotal UCQ its output. Table 1 shows the size of the UCQ (we recall that it is the same for all systems outputing a minimal, sound and complete UCQ), the size of the pivotal UCQ produced by PUREC, and the number of generated queries during the rewriting process for PURE and PUREC. Missing values are due to timeouts. We find a huge gap between the sizes of the output; the pivotal UCQ is often restricted to a single CQ even when the UCQ has thousands of CQs (which also explains the gap between the numbers of generated queries). Unsurprisingly, the results on the runtimes lead to similar observations (Table 2, Columns 1 and 2). We see that PUREC remains faster than PURE when we include the time required to unfold the pivotal UCQ into a UCQ (Table 2, Column 3), except for Q2 on O, which comes from the fact that the pivotal UCQ is almost as large as the UCQ. Note that we implemented a brute-force unfolding method, which removes redundant CQs only at the end by a pairwise comparison of queries. Almost all the unfolding time is actually spent in checking redundancies. Nervertheless, the size of the UCQ obtained for some queries (up to more than 30000 CQs on O) clearly advocates for more compact forms of output.

We also compared to other query rewriting tools, namely: PURE and Nyaya, which are the only tools processing existential rules, as well as some well-known DL tools: Requiem [P´erez-Urbina et al., 2009] (optimized "full modality"), Iqaros [Imprialou et al., 2012], Rapid [Chortaras et al., 2011] and tw-rewriting (part of the Ontop OBDA system [Rodriguez-Muro et al., 2013]). We emphasize again that these DL tools exploit the specificities of DL-Lite, specially the most recent ones, Rapid and tw-rewriting, whereas the algorithms of Nyaya and PURE are designed for general existential rules. Despite this fact, PUREC (without or with unfolding) scales well on DL-Lite large ontologies (except for extreme cases which are difficult for all tools, see Ontology O). Globally, PUREC behaves similarly to twrewriting and Rapid. If we restrict the comparaison to classical UCQ output, the fastest tools are undeniably tw-rewriting and Rapid, followed by PUREC with unfolding. The difficulties of Nyaya on A can be explained by the fact that A contains some rules with two atoms in the head, whereas Nyaya only processes rules with a single head; hence, it had to take as input the ontology obtained by decomposing these rules into single-head rules, which introduces new predicates, whereas PURE processes rules with any head size. Nyaya could not process the very large ontologies G and O, which also needed to be decomposed.

2 Available at https://github.com/graphik-team/graal

Table 2: Impact of rule compilation on rewriting time

We checked that all systems return exactly the same size of UCQ, hence the choice of a given query rewriting tool between those outputing a UCQ is irrelevant for the query evaluation step. We carried out additional experiments to compare the evaluation of the pivotal UCQ over the data saturated by the compilable rules and the evaluation of the corresponding classical UCQ over the initial data (data generated with the modified LUBM generator [Lutz et al., 2013] and stored in a MySQL database). As expected, in a number of cases the system did not accept the classical UCQ because of its size, and in the other cases the pivotal UCQ was evaluated much more efficiently than the classical UCQ.

Further work includes extending query rewriting techniques outside the fus fragment, by exploiting datalog rewritability or combining with other paradigms for rules.

Acknowledgments. This work was partially funded by the ANR project PAGODA (ANR-12-JS02-007-01).