Compact Rewritings for Existential Rules

1 Introduction

Querying data while taking ontologies into account is a currently active research domain, often referred to as ontologybased data access (OBDA). Data is typically stored in a database and basic queries are conjunctive queries. Different means are available to represent ontologies. The mainstream approach uses description logics [Baader et al., 2007]. In that case, most studies for OBDA focuses on lightweight description logics, such as DL-Lite [Calvanese et al., 2007] or EL [Baader, 2003]. In this paper, we focus on existential rules [Baget et al., 2011], similar to Datalog± [Cal`ı et al., 2012]. On the one hand, they cover lightweight description logics (and in fact, Horn Description Logics); on the other hand, these rules allow for more flexibility, since both body and head need not to be tree-shaped (as in DLs) and predicates can be of any arity (whereas they are restricted to arity 1 or 2 in DLs).

∗This work was partially supported by ANR project PAGODA (ANR 12 JS02 007 01).

The fundamental decision problem 1 we consider is the following: given a set of facts F, a (Boolean) conjunctive query Q, and a set of existential rules R, is it true that F,R |= Q? Due to the presence of existential variables in the head of rules, this problem is undecidable. A variety of approaches for query answering have been investigated, based on two main mechanisms. First, some approaches include a step of materialization, that is, all or part of the data that can be inferred is added to the initial facts. These approaches include "pure" forward chaining (where we add all data that can be inferred) and combined approach [Kontchakov et al., 2011]. Combined approach (where a step of query rewriting is added) can in particular be applied to DL-Lite and EL ontologies, and is thus arguably useful for practical purposes. A similar approach can be applied to a class of existential rules generalizing guarded rules [Thomazo et al., 2012]. However, materialization-based approaches suffer from several drawbacks: they require read and write permits, the saturation step incurs a blow-up of data (and this is not acceptable when data is huge), and, to the best of our knowledge, no solution has been proposed when data is often changing, that is when facts are added or removed on a regular basis.

Other approaches are based on "pure" query rewriting: given Q and R, a new query Q′ is computed such that for all set of facts F, F,R |= Q if and only F |= Q′ . Only read permits are necessary, no blow-up of data occurs since it is not changed, and data updates do not impact the rewritings. Mostly two kinds of rewritings occurs in the literature: Datalog programs and union of conjunctive queries. Polynomial rewriting in Datalog programs have been proposed for some existential rules [Gottlob and Schwentick, 2012; Stefanoni et al., 2012; Rosati and Almatelli, 2010]. They however do not cover all classes of rules treated here, and their efficient evaluation remains an open problem.

More widely studied widely rewritings are using union of conjunctive queries (UCQs). The rationale is that most of the available data is stored in databases, and existing database systems are optimized to efficiently evaluate conjunctive queries. This strand of work, initiated in [Calvanese et al., 2007], has led to a number of prototypes, such as, among others, Iqaros [Venetis et al., 2012], Nyaya [Gottlob et al., 2011], QuOnto [Calvanese et al., 2007], Rapid [Chortaras et al., 2011], Requiem [P´erez-Urbina et al., 2009], or the algorithm presented in [K¨onig et al., 2012], relying on piece-based rewriting. More details about the characteristics of some of them and how they relate with this work will be presented in Section 6.

1 We consider only the decision problem for the sake of simplicity. We could consider non-boolean queries, as well as union of conjunctive queries instead of a single CQ.

However, as all these tools compute rewritings which are UCQs, they share the major drawback of these rewritings: even reasonable sets of existential rules can generate huge rewritings. We propose to produce rewritings that are neither a union of conjunctive queries nor a Datalog program, but a union of so-called semi-conjunctive queries (SCQ). We advocate that such queries can be both efficiently computed and evaluated. For that purpose, we adopt a two-step approach:

1. we design a novel algorithm that produces a union of semi-conjunctive queries (USCQ), for any set of existential rules and any query that admits a finite union of most general (CQ) rewritings. It computes short rewritings, and first experiments show that they are generated faster than their equivalent UCQ by state-of-the-art tools, even though these tools are dedicated to that particular case.
2. we compare the evaluation efficiency of the USCQ with the evaluation efficiency of the optimal rewriting in conjunctive queries. First experiments show that the viewbased evaluation of USCQ is more efficient than the evaluation of the corresponding UCQ.

We first recall some technical preliminaries, and in particular piece unifiers, that we generalize in this paper. Section 3 introduces semi-conjunctive queries. Section 4 introduces a generalization of piece unifiers for semi-conjunctive queries, as well as the COMPACT algorithm. We evaluate both the rewriting step and the evaluation step of COMPACT in Section 5. Last, we stress similarities and novelties with respect to existing algorithms in Section 6.

2 Preliminaries

We consider first-order logical (FOL) languages with constants but no other function symbols. A language L = (P, C) is composed of two disjoint sets: a set P of predicates and a set C of constants. An atom on L is of form p(t1, . . . , tk) where p is a predicate in P of arity k and ti are terms, i.e., variables or constants in C. A fact is an existentially closed conjunction of atoms 2 . A conjunctive query is an existentially quantified conjunction of atoms - it is Boolean if it is closed.

Definition 1 An existential rule (or simply rule) R = (B,H) on a language L is a closed formula of form ∀x1 . . . ∀xp(B → ∃z1∃zq H) where B and H are two (finite) conjunctions of atoms on L; {x1, . . . , xp} = var(B); and {z1, . . . , zq} = var(H) \ var(B). 3 B and H are respectively called the body and the head of R, also denoted by body(R) and head(R). The frontier of R (denoted by fr(R)) is the set of variables occurring in both B and H: fr(R) = var(B) ∩ var(H).

2 This generalizes the usual notion of fact.

3 Quantifiers are usually omitted, since there is no ambiguity.

W.l.o.g., we will consider that all existential rules have atomic head, i.e., the head of the rule is restricted to a single atom. Moreover, we will assume (w.l.o.g.) that rules and queries share no variables. 4 We will often consider logical formulas as sets: a conjunction or a disjunction of atoms will be seen as a set of atoms, and a conjunction of disjunctions will be seen as a set of disjunctions. It will be clear from the context which object is dealt with. Given two atom sets A and B, a homomorphism from A to B is a substitution h of vars(A) by terms(B) such that h(A) ⊆ B. Given two formulas ϕ and ψ, we say that ϕ is more general than ψ (denoted by ϕ ≥ ψ) if ψ |= ϕ. In the case of (existentially closed) conjunctions of atoms, A ≥ B if and only if there exists a homomorphism from A to B.

We recall below the definition of piece unifiers [K¨onig et al., 2012], which will be extended in this work. If rules were plain Datalog rules, this unification would be the classical one. However, in order to take existential variables of the head into account, we may unify several atoms at once. If Q is a set of atoms, for any set Q′ ⊆ Q, we define sep(Q′ ) = var(Q′ ) ∩ var( ¯Q′ ), where ¯Q′ = Q \ Q′ .

Definition 2 (Piece unifier) Let Q be a CQ and R be a rule. A piece unifier of Q with R is a pair µ = (Q′ , u) with Q′ ⊆ Q, Q′ ̸= ∅, and u is a substitution of fr(R) ∪ var(Q′ ) by terms(head(R)) ∪ C such that:

1. for all x ∈ fr(R), u(x) ∈ fr(R) ∪ C (for technical convenience, we allow u(x) = x);
2. for all x ∈ sep(Q′ ), u(x) ∈ fr(R) ∪ C;
3. u(Q′ ) ⊆ u(head(R)).

We define the notion of rewriting using piece unifiers. Given a query Q, Qk is an R-rewriting of Q if Qk can be obtained from Q by a sequence of rewritings.

Definition 3 (Rewriting) Given a CQ Q, a rule R and a piece unifier µ = (Q′ , u) of Q with R, the rewriting of Q according to µ, denoted β(Q, R, µ), is u(body(R) ∪ ¯Q′ ).

Example 1 Let Q = p(x) ∧ r(x, y) ∧ r(z, y) ∧ q(z), and R = h(x1) → r(x1, y1). There is only one unifier of R with Q, which is µ = ({r(x, y), r(z, y)}, {x → x1, y → y1, z → x1}), and β(Q, R, µ) = p(x1) ∧ h(x1) ∧ q(x1).

Definition 4 (R-rewriting of Q) Let Q be a CQ and R be a set of rules. 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, R, µ).

Theorem 1 (Soundness and completeness) (basically [Salvat and Mugnier, 1996]) Let F be a fact, R be a set of existential rules, and a (Boolean) CQ Q. Then F,R |= Q iff there is an R-rewriting Q′ of Q such that F |= Q′ .

In this paper, we will consider rewritings that are not necessarily CQs or UCQs. Given a class Φ of formulas, we define sound and complete Φ-rewritings.

4 One can always rename apart the variables in a rule and thus satisfy our assumption.

Definition 5 (Φ-rewriting soundness and completeness)

Let Q be a first-order formula, Φ be a class of first-order formulas and R be a set of existential rules.

• A sound Φ-rewriting of Q (w.r.t R) is a formula ϕ belonging to Φ such that for each fact F, F |= ϕ implies that F, R |= Q.
• A complete Φ-rewriting of Q (w.r.t R) is a formula ϕ belonging to Φ such that for each fact F, F,R |= Q implies that F |= ϕ.

An interesting class of rules when performing backward chaining is the class of finite unification sets, which are sets of rules for which any query admits a finite UCQ-rewriting.

Definition 6 (Finite unification set) Let R be a set of rules. R is a finite unification set (fus) if for any Q there exists a finite UCQ-rewriting of Q (w.r.t. R).

The fus property is unrecognizable. However, some recognizable subclasses are known: atomic-body rules [Cal`ı et al., 2008; Baget et al., 2009], (join)-sticky-rules [Cal`ı et al., 2010], aGRD [Baget et al., 2011].

3 Semi-conjunctive Queries

CQs are considered as the basic queries in databases, and UCQs can be dealt with by processing each CQ separately. Hence, most of the research effort in OBDA has focused on UCQs. The query rewriting approach usually focuses on creating UCQ-rewritings. One of the reasons is that UCQs are efficiently dealt with by existing DBMS. However, this last statement is questionable in this setting, since the size of UCQ-rewritings is generally large, in particular when ontologies contain large class/role hierarchies (which is often the case). We first introduce the notion of a semi-conjunctive query - which allows for a limited use of disjunction - and illustrate with Example 3 what it has to offer to OBDA.

Definition 7 (Semi-conjunctive query) A semi-conjunctive query (SCQ) is a closed logical formula of the following form:

where Di is a disjunction of atoms (for any i), and x is the set of variables that appear in the formula.

Definition 8 (Selection) Let S = ∧i Di be an SCQ. A CQ Q = ∧i di is a selection of S if, for each i, we have di ∈ Di.

Example 2 (Selection) Let S = (r1(x, y) ∨ r2(x, y)) ∧ (s1(y, z) ∨ s2(y, z)). S has four selections, which are r1(x, y) ∧ s1(y, z), r1(x, y) ∧ s2(y, z), r2(x, y) ∧ s1(y, z), r2(x, y) ∧ s2(y, z).

Example 3 By generalizing Example 2 with k disjunctions of q atoms, the smallest UCQ equivalent to a single USCQ would contain qk CQs.

Property 1 Let Q be a CQ, and S be an SCQ. S is a sound SCQ-rewriting of Q w.r.t. R if and only if every selection of S is a sound CQ-rewriting of Q w.r.t. R.

If S1 is more general than S2, one can discard S2 from a USCQ-rewriting. We thus define the notion of cover of a set S of SCQs, which contains only most general elements of S.

Definition 9 (Cover) Let S be a set of first-order queries. A cover of S is a set S c ⊆ S such that:

1. for any S ∈ S, there is S′ ∈ S c such that S ≤ S′ ,
2. elements of S c are pairwise incomparable w.r.t. ≤.

Of course, a cover of a sound and complete USCQrewriting is also sound and complete. In the case of UCQrewriting, being a sound and complete cover is a sufficient condition for being of minimal size [K¨onig et al., 2012]. However with SCQs, this condition does not ensure the minimality of the USCQ-rewriting, as shown by the Example 4.

Example 4 Let S1 be a set of SCQs containing:

• (r1(x, y) ∨ r2(x, y)) ∧ (s1(x, y) ∨ s2(x, y)),
• (r1(x, y) ∨ r3(x, y)) ∧ (s1(x, y) ∨ s2(x, y)),
• (r1(x, y) ∨ r2(x, y)) ∧ (s1(x, y) ∨ s3(x, y)),
• (r1(x, y) ∨ r3(x, y)) ∧ (s1(x, y) ∨ s3(x, y)).

All elements of S1 are incomparable by the "more general" relation, but S2 = {(r1(x, y) ∨ r2(x, y) ∨ r3(x, y)) ∧ (s1(x, y) ∨ s2(x, y) ∨ s3(x, y))} is equivalent to S1 and contains strictly less SCQs.

Property 2 Let S and S′ be two SCQs. S ≥ S′ iff for every selection Q′ of S′ , there exists a selection Q of S s.t. Q ≥ Q′ .

4 Query Rewriting Using SCQs

In this section, we present COMPACT, an algorithm that computes USCQ-rewritings. We define for that purpose piece unifiers for SCQs. This notion naturally generalizes the corresponding notion for CQs by operating a selection on SCQs. As for CQs, given an SCQ S and a set of disjunctions S′ ⊆ S, we define sep(S′ ) = var(S′ ) ∩ var( ¯ S′ ), where ¯ S′ = S \ S′ .

Definition 10 (Piece unifier) Let S be an SCQ and R be a rule. A piece unifier of S with R is a triple µ = (S′ ,Q′ , u) with S′ ⊆ S, S′ ̸= ∅, Q′ a selection of S′ , and u is a substitution of fr(R) ∪ vars(Q′ ) by terms(head(R)) ∪ C such that:

1. for all x ∈ fr(R), u(x) ∈ fr(R) ∪ C (for technical convenience, we allow u(x) = x);
2. for all x ∈ sep(S′ ), u(x) ∈ fr(R) ∪ C;
3. u(Q′ ) ⊆ u(head(R)).

A unifier of a rule with one body atom is local if S′ contains only one disjunction, and if u restricted to terms(S′ ) is injective and does not map a variable to a constant. A non-local unifier µ = (S′ ,Q′ , u) is prime if for any D ∈ S′ , there exists no uL, substitution of fr(R) ∪ vars(Q′D ) by terms(head(R)) ∪ C, such that µ = ({D},Q′D , uL) is a local unifier, where Q′D is the selection of {D} that selects the same elements as Q′ .

Example 5 Let R1 = p(x) → r(x, y), R2 = q(x′ ) ∧ h(x′ ) → s(x′ , y′ ), and S = r(x1, x2)∧t(x1, x3)∧r(x3, x4)∧ s(x1, x5) ∧ s(x3, x5). S is a CQ, thus an SCQ too.

• let µ1 = ({{r(x1, x2)}}, {r(x1, x2)}, {u1(x1) = x, u1(x2) = y}). µ1 is a local unifier of R1 with S.

• let µ2 = ({{s(x1, x5)}, {s(x3, x5)}}, {s(x1, x5), s(x3, x5)}, {u2(x1) = x′ , u2(x5) = y′ , u2(x3) = x′}) is a prime (non-local) unifier of R2 with S, because R2 has a non-atomic body
• let µ3 = ({{r(x1, x2)}, {r(x3, x4)}}, {r(x1, x2), r(x3, x4)}, {u3(x1) = x, u3(x2) = y, u3(x3) = x, u3(x4) = y}). µ3 is a non-local (two disjunctions unified at once), non-prime unifier (because µ1 is a local unifier) of R1 with S.
• let µ4 = ({{s(x1, x5)}}, {s(x1, x5)}, {u4(x1) = x′ , u4(x5) = y′}). µ4 is not a unifier of R2 with S, because x5 is mapped to an existential variable of R2, and there is a disjunction of S containing x5 but not belonging to the unified disjunctions.

To define the rewriting operations of our algorithm, we first need the definition of X-entailment.

Definition 11 (X-entailment) Let D be a set of atoms, and X a set of variables. Let a be an atom. a is X-entailed by D if there is a homomorphism π from a to D such that if x ∈ var(a) ∩ X, then π(x) = x.

Example 6 Let D = {r(x, y), p(x, u)}. p(x, v) is {x,y}- entailed by D, but r(y, x) is not.

We distinguish two kinds of rewriting operations. Local rewritings, which are performed when rewriting w.r.t. a local unifier, and non-local rewritings otherwise. Local rewritings are the novelty of our approach: they can introduce disjunctions. Non-local rewritings are a simple recast of usual rewritings in the framework of SCQs. Disjunctions that have a unified atom are removed, the substitution is applied to each atom of the body of the rule, creating a new disjunction for each of these atoms.

Definition 12 (Local rewriting) Let S = ∧ni=1 Di be an SCQ, R be an atomic body rule and µ = ({D1},Q′ , u) be a local piece unifier of R with S. The local rewriting of S with respect to µ (denoted by γL(S,R, µ)) is S′ = D′1 ∧ ∧ni=2 u(Di), where D′1 = u(D1) ∨ u(body(R)), if u(body(R)) is not sep({D1})-entailed by D1, and S otherwise.

Checking that u(body(R)) is not sep({D1})-relatively entailed by D1 ensures that the same unification will not add twice equivalent atoms. Thus, given an SCQ, we can saturate it by applying local rewritings until all of them have been applied. This process, called LU-Saturation, is presented in Algorithm 1.

Definition 13 (Non-local rewriting) Let S = ∧ni=1 Di be an SCQ, R be a rule (with body(R) = ∧bi=1 bi(R)) and µ = ({D1, . . . ,Dk},Q′ , u) be a non local unifier of R with S. The non-local rewriting of S with respect to µ (denoted by γNL(S, R, µ)) is S′ = ∧bj=1 D′j ∧ ∧ni=k+1 u(Di), where D′j = u(bi(R)).

Example 5 ((cont.) Local and non-local rewriting) The rewriting of S:

• w.r.t. to µ1 is (r(x1, x2)∨p(x1))∧t(x1, x3)∧r(x3, x4)∧ s(x1, x5) ∧ s(x3, x5).
• w.r.t. to µ2 is r(x, x2)∧t(x, x)∧r(x, x4)∧q(x)∧h(x).
• w.r.t. to µ3 is p(x)∧r(x, x)∧s(x, x5)∧s(x, x5), which is simplified to p(x) ∧ r(x, x) ∧ s(x, x5).

Let us now focus on properties of piece-based rewriting for SCQs. Property 3 ensures that soundness is preserved while performing a rewriting.

Property 3 Let S be a sound SCQ-rewriting of a CQ Q. If µ is a local (resp. non-local) unifier of R with S, then γL(S,R, µ) (resp. γNL(S,R, µ)) is a sound SCQ-rewriting of Q.

Performing an LU-saturation is relevant since applying a local unifier does not prevent any other unifier to be applied.

Property 4 Let S be an SCQ, R1 and R2 be two rules, µ1 be a local unifier of R1 with S and µ2 be a unifier (not necessarily local) of R2 with S. µ2 is a unifier of R2 with β(S, R1, µ1). Moreover the (possible) locality of µ2 is conserved.

We now present the key properties that will ensure the completeness of our algorithm.

Property 5 Let R be a set of rules, S be an SCQ, and Q a selection of S. Let Q′ be a one step R-rewriting of Q. Either Q′ is less general than a selection of the LU-saturation of S, or there exists a one step rewriting S′ of S s.t. Q′ is less general than a selection of S′ .

The following property ensures that computing the cover at each step does present completeness.

Property 6 Let S and S′ be two SCQs such that S ≥ S′ . For any selection Q′r of a one step-rewriting S′r of Sr, either there exists a selection Q of LU-saturation(S) such that Q ≥ Q′r , or there exists a selection Qr of a one step rewriting of LU-saturation(S) such that Qr ≥ Q′r .

COMPACT (Algorithm 2) performs a breadth-first exploration of the SCQ-rewritings of Q. For each SCQ S to be explored, S is first LU-saturated. Then, any prime unifier is used to generate new SCQs - which are in turn explored. To ensure that COMPACT halts, one should check that newly created SCQs are not less general than previously explored SCQs. This check is not trivial: in particular, we use the very specific structure of the rewriting generated by COMPACT in order to avoid to blow-up each SCQ, as would be suggested by Property 2.

Algorithm 1: LU-SATURATION

Data: A SCQ S, a set of existential rules R Result: S saturated with respect to local unifications So = null; Sn = S; while So ̸= Sn do So = Sn; for every rule R ∈ R do for every local unifier µ of R with Sn do Sn = γL(Sn, R, µ); return Sn

Algorithm 2: COMPACT

Data: A CQ S (thus as SCQ), a fus R Result: A sound and complete USCQ-rewriting of S w.r.t. R SF = {S}; SE = {S}; while SE ̸= ∅ do St = ∅; for every S′ ∈ SE do S′ = LU-SATURATION(S′ ); for every rule R ∈ R do for every prime unifier µ of R with S′ do St = St ∪ {γNL(S′ , R, µ)} St = cover(SF ∪ St); SE = St \ SF ; SF = St; return SF

Property 7 Algorithm 2 outputs a sound and complete rewriting of S w.r.t. R.

Sketch of proof: Property 3 ensures that all generated queries are sound. An induction on the length of the smallest derivation generating a CQ-rewriting of Q based on Property 5 and Property 6 shows that for any CQ-rewriting of Q, there exists an SCQ SQ generated by Algorithm 2 such that Q is less general than a selection of SQ. □

Example 5 ((Cont.)Execution of COMPACT on S, R) We start from S and LU-saturate it. We obtain S′ = LU-Saturate(S) = (r(x1, x2) ∨ p(x1)) ∧ t(x1, x3) ∧ (r(x3, x4) ∨ p(x3) ∧ s(x1, x5) ∧ s(x3, x5). The only prime unifier applicable to S′ unifies R2 with S′ , which is rewritten into S′′ = (r(x, x2)∨p(x))∧t(x, x)∧(r(x, x4)∨p(x))∧q(x). No new unifications are possible, and thus {S′ , S′′} is a sound and complete rewriting of S w.r.t. R.

The efficiency of the USCQ representation of sound and complete rewritings is striking when dealing with class or role hierarchies, which are covered by the following property.

Property 8 Let R be a set of rules with no constants, no existential in the head, and such that no variable appear twice in the same atom. Let Q be a conjunctive CQ. The sound and complete SCQ-rewriting of Q w.r.t. R is a single SCQ.

5 Experimental Evaluation

We now evaluate both steps of our query rewriting approach for OBDA. One the one hand, we want a rewriting algorithm that computes quickly sound and complete rewritings. On the other hand, we want these rewritings to be efficiently evaluable by current RDMS. For both steps, we use the ontologies introduced for benchmarking in [P´erez-Urbina et al., 2009], which have been also used in [Gottlob et al., 2011; Chortaras et al., 2011; Imprialou et al., 2012]. Moreover, since these ontologies are rather flat, we slightly modify the LUBM ontology 5 , creating LUBMn, by adding n subpredicates for each original predicate (e.g., Course has as sublcasses Course1,. . ., Coursen). This process is very similar to what has been done in [Rodriguez-Muro and Calvanese, 2012] and [Lutz et al., 2012]. As for the queries, we use two sets of queries for each ontology. First, the original handcrafted queries, which are only five. Then, we use the query generator Sygenia 6 [Imprialou et al., 2012] in order to have a larger number of queries. For space reasons, we only present the results on the LUBMn ontologies and its modified version, which are representative of other experiments.

5 http://swat.cse.lehigh.edu/projects/lubm/

Rewriting. To test the rewriting step of COMPACT, we compare the rewritings obtained by COMPACT and by Iqaros, which has been shown to be faster than other tools on the considered benchmarks [Imprialou et al., 2012]. For COMPACT, we present the number of output SCQs, the number of selections (i.e., the number of CQs that would be obtained by exploding each output SCQ), as well as the time needed to generate the USCQ. For Iqaros, we present the number of output CQs and the time required for computing them.

Querying. Since generating queries is only half of the story, we also test how efficiently the output queries can be evaluated against a database. The method is the following: given a CQ Q, let Q be the optimal UCQ-rewriting, and S be the USCQ output by COMPACT. We separately evaluate each CQ of Q by translating them into an SQL query, and compute the time required for evaluating all queries. We do the same thing for each SCQ of S, where the translation involves the creation of views. The data we evaluate the query on is generated from the LUBM generator, with 20 universities (for a total of 556k unary atoms, and 2,2M binary atoms). A timeout has been set: all queries of the benchmark should have been answered within 30 minutes. COMPACT is implemented in Java. All tests have been performed on a 2.4GHz processor, with 4GB of RAM. The RDMS used is Sqlite.

5.1 Rewriting Step

Rewriting results are presented in Tables 1 and 2. For most queries, the USCQ rewriting output by COMPACT contains only one SCQ. On the benchmarks, the time needed for computing USCQs is better than the time needed for computing UCQs. The difference increases dramatically as the size of the UCQ rewritings increases, as witnessed by handcrafted queries with the LUBMn ontologies.

5.2 Querying Step

Figures 1 and 2 present the time, in seconds, needed to evaluate the optimal UCQ rewriting (black bars), and USCQ rewriting (white bars), for Sygenia-generated queries and for handcrafted queries, respectively. The ontologies are LUBMn, for n from 0 to 8. Missing bars are timeouts.

USCQs are evaluated faster than their equivalent (optimal) UCQs. The difference grows as the size of the UCQ grows (with a fixed size of USCQ), which typically happens when class or role hierarchies are present.

6 http://code.google.com/p/sygenia/

6 RelatedWork

COMPACT has some similarities with two algorithms already published: Rapid and the piece-based rewriting algorithm. Incremental rewriting performed by Iqaros being further from our methods, we focus on these two.

First, the piece-based rewriting algorithm presented in [K¨onig et al., 2012]: the distinguishing feature of this algorithm is that it computes optimal CQ-rewritings for any finite unification set. This generality - any finite unification set - is due to the use of piece unifiers. COMPACT is based upon the same mechanisms, modulo some generalizations in order to take disjunction into account.

Rapid performs sound and complete rewritings for OWLQL ontologies. Rapid first performs a shrinking step, where all possible "structures" of CQ rewriting are generated at once. An important property of OWL-QL on which rapids is based on (in order to be time-efficient) is that such a shrinking step can be done only once. Then, every atom is separately rewritten using the ontology. Last, a distributivity step, including some compatibility checks, is performed. The separate rewriting for each atom can find a counter-part in COMPACT with the use of local unifiers, and creation of disjunctions. The distributivity step is not done - which allows for a dramatic time improvement when there are several large disjunctions in a single semi-conjunctive query.

7 Conclusion and FurtherWork

In this paper, we proposed a novel method to compute sound and complete rewritings of conjunctive queries with respect to finite unification sets of existential rules. Designing efficient tools for that task is important because it allows one to answer conjunctive queries against databases while taking ontologies into account without changing data. The distinguishing feature of our method is that it outputs a set of semi-conjunctive queries, which are a more general form of positive existential formulas than conjunctive queries. We advocated that such queries allow for a more compact representation of sound and complete rewritings that can be efficiently computed and evaluated. In particular, we presented a novel algorithm, COMPACT, that outperforms state-of-the-art algorithms on OWL-QL, while producing sound and complete rewritings for any finite unification set. First experiments showed that semi-conjunctive queries can be more efficiently evaluated than the equivalent union of conjunctive queries, especially when the size of the disjunctions involved is big enough - which happens even with queries and ontologies of moderate size.

Further work includes both practical and theoretical aspects. First, since existing benchmarks are limited, properly evaluating rewriting algorithms is hard. In particular, we evaluated COMPACT only on OWL-QL ontologies, whereas it is designed as a rewriting tool for any finite unification set. Then, an interesting improvement of COMPACT would be to take into account the possible completeness of a database with respect to some predicates. This method has been proven useful with some very light description logics [RodriguezMuro and Calvanese, 2012]. We believe such an approach could be successfully adapted to any finite unification set.