Query Answering for Existential Rules via Efficient Datalog Rewriting

1 Introduction

Existential rules (a.k.a. Datalog± and tuple generating dependencies) [Baget et al., 2011; Cal`ı et al., 2012b] is a family of expressive ontology languages. It attracted intensive interest lately due to its expressive power covering datalog and many Horn description logics, including the core dialects of DL-Lite and EL [Cal`ı et al., 2012a], which underlay the OWL 2 Profiles. This makes existential rules an appealing formalism for ontology-mediated query answering [Bienvenu et al., 2014]. While query answering is undecidable over the full formalism, several interesting fragments have been proposed [Baget et al., 2011; Cal`ı et al., 2012b; Cal`ı et al., 2013; Leone et al., 2019] that support tractable query answering.

There are two major approaches for query answering over ontologies expressed in existential rules or Horn description logics, the chase-based approach and the query rewriting approach. The chase-based approach relies on the termination of the chase procedure (a.k.a. forward chaining), and it is shown that computing a full chase can be rather inefficient when query answers depend only on a small portion of it [Benedikt et al., 2018]. On the other hand, the query rewriting approach does not require expanding the data. Given an ontology Σ and a query q, a rewriting method transforms them into another query qΣ, which is sometimes in a different query formalism, such that answering qΣ can be handled by conventional database management systems (DBMSs) and at the same time preserves the answers to the original ontology-mediated query. The rewriting approach is particularly promising as it allows ontologymediated query answering to be implemented on top of existing highly-optimised database query engines. While many algorithms and systems have been developed for various description logics [P´erez-Urbina et al., 2010; Eiter et al., 2012; Zhou et al., 2015; Venetis et al., 2016], particularly for DLLite and EL [Kontchakov et al., 2010; Stefanoni et al., 2013; Trivela et al., 2015; Hansen et al., 2015; Bienvenu et al., 2017], it is challenging to extend them to more general existential rules, which allow predicates of arbitrary arities (instead of only unary and binary predicates) and variable permutations in the rules.

∗Corresponding Author

Existing query rewriting systems for existential rules are typically based on first-order rewritings [Gottlob et al., 2014a; K¨onig et al., 2015a; K¨onig et al., 2015b], i.e., qΣ is a first-order query. A limitation of such an approach is that it can only handle ontologies and queries that are first-order rewritable. Well-accepted first-order rewritable classes are the linear and sticky existential rules [Cal`ı et al., 2012b]. Yet many practical ontologies do not necessarily fall into these classes, such as some ontologies formulated in EL. Even for ontologies and queries that are first-order rewritable, the results of rewriting can suffer from a significant blow up and become difficult for DBMSs to handle [Rosati and Almatelli, 2010; Bienvenu et al., 2017].

On the other hand, taking datalog as the target query language can lead to much more compact rewritings and it is shown for description logics that executing (non-recursive) datalog rewritings is much more feasible for DBMSs than equivalent first-order rewritings [Hansen et al., 2015]. All ontologies and queries that are first-order rewritable are trivially datalog rewritable, and more datalog rewritable classes are known, such as the guarded existential rules [Gottlob et al., 2014b]. However, existing research on datalog rewriting of existential rules are mostly theoretical [Gottlob and Schwentick, 2012; Bienvenu et al., 2014] (refer to [Ahmetaj et al., 2018] for a detailed discussion). While several algorithms and systems have been developed for datalog rewriting for various description logics [Eiter et al., 2012; Trivela et al., 2015; Hansen et al., 2015], very few systems have been developed for datalog rewriting over more general existential rules. A notable exception is ChaseGoal [Benedikt et al., 2018], which however, relies on the termination of the chase procedure.

In this paper, we fill the gap by presenting both a practical approach and a prototype system for datalog rewriting and query answering over a wide range of ontologies expressed in existential rules. Our algorithm is based on the notion of unfolding [Wang et al., 2018] and to achieve compactness of rewriting, we separate the results of unfolding into short rules by introducing the so-called separating predicates and reusing such predicates when possible. While such a rewriting process may not terminate, we move on to identify classes of ontologies where the rewriting process terminates, introducing a class by combining existing well-accepted classes. And we introduce an efficient algorithm for computing the datalog rewritings. Finally, we implemented a prototype system, Drewer, and experiments show that it is able to handle a wide range of benchmarks in the literature. Moreover, Drewer shows superior or comparable performance over state-of-theart systems on both the compactness of rewriting and the efficiency of query answering.

2 Preliminaries

We assume standard first-order logic notions, such as predicates, atoms, facts (i.e., ground atoms), formulas, entailment (|=) and equivalence (≡). For a set of formulas Φ, [Φ] denotes the set of predicates in Φ. For convenience, we sometimes identify a finite set of atoms with the conjunction of its atoms where all the variables are existentially quantified, and vice versa. A dataset is a finite set of facts (i.e., ground atoms).

For a set of atoms A, var(A) denotes the set of variables in A. By assuming a fixed order on all the variables, for a set of variables V , we may refer to the vector of V ; also, for denotational simplicity, we may use a vector to represent the set of its elements. A substitution σ is a functional mapping between two sets of terms such that tσ = t if t is a constant or is not in the domain of σ; and it naturally extends to (sets of) atoms and formulas. A unifier between two sets of atoms A and A′ is a substitution τ such that Aτ = A′ τ; and τ is a most general unifier (MGU) if for each unifier τ ′ between A and A′ , there exists a substitution σ such that τ ′ = τσ.

An existential rule (or a rule) r is a formula of the form

where ⃗x, ⃗y and ⃗z are pairwise disjoint vectors of variables, and ϕ(⃗x, ⃗z) and ψ(⃗x, ⃗y) are conjunctions of atoms containing only variables from respectively ⃗x∪⃗z and ⃗x∪⃗y. Variables in ⃗x are frontier variables and those in ⃗z are existential variables, and we use ⃗xr and ⃗zr to emphasis they are for rule r. Formula ϕ is the head of the rule r, denoted head(r), and formula ψ is the body of r, denoted body(r) (again, they can be seen as sets of atoms). For brevity, universal quantifiers in a rule are often omitted, and we assume each rule employs a distinct set of variables. A rule r is implied by another rule r′ if r′ |= r. Two sets of rules Σ1 and Σ2 are equivalent on a set of predicates P, denoted Σ1 ≡P Σ2, if for each pair of dataset D and fact α over P, Σ1 ∪ D |= α iff Σ2 ∪ D |= α. It is known that a set of existential rules Σ can be transformed into a set of rules Σ′ whose heads are singletons in a way that preserves query answering [Gottlob et al., 2014a]. In what follows, we assume Σ consists of such rules and use head(r) to denote the single atom in the rule head.

A datalog rule r is an existential rule with a single head atom and ⃗zr is empty. A fact-preserving datalog rewriting (FPDR) of a set of existential rules Σ is a datalog program Π that preserves fact derivation, that is, Π ≡[Σ] Σ; and it is a strong FPDR if additionally, Σ |= Π.

A conjunctive query (CQ) q(⃗x) can be conveniently represented as a datalog rule Q(⃗x) ← ϕ(⃗x, ⃗y) where Q is a predicate with arity |⃗x|. When ⃗x is empty the query is Boolean, called BCQ and denoted q. A UCQ is a set of CQs with the same head. An ontology-mediated query (OMQ) is of the form Q = Σ ∪ {q(⃗x)} with Σ a finite set of existential rules and q(⃗x) a CQ. A tuple ⃗a with the same arity as ⃗x is an answer to Q over a dataset D if Q ∪ D |= Q(⃗a).

Datalog rewriting for an OMQ is relaxed to preserve only the query answers; in particular, a query-preserving datalog rewriting (QPDR) of an OMQ Q = Σ ∪ {q(⃗x)} is a datalog program ΠQ such that ΠQ ≡{Q} Σ. Clearly, an FPDR of a OMQ is also a QPDR, but the converse does not necessarily hold. When ΠQ is a UCQ, it is a UCQ rewriting. Answering CQs can be reduced to that of BCQs and hence w.l.o.g. we consider only BCQs in this paper.

Existing works on UCQ rewriting of OMQs are (essentially) based on the notion of piece unification for two sets of atoms B,H w.r.t. a set of variables V from H [Baget et al., 2011; Lecl`ere et al., 2016]. A piece unifier of B and H w.r.t. V is a tuple µ = (B′ ,H′ , τ), where ∅ ⊂ B′ ⊆ B, H′ ⊆ H, and τ is a MGU between B′ and H′ such that for each v ∈ V , v can only be unified with variables u (i.e., vτ = uτ) occurring in B′ 1 . For a CQ q to be rewritten by a rule r, one would take B = body(q), H = {head(r)}, and V consisting all the existential variables in r; thus, we can omit V and talk about the piece unification of body(q) and head(r), and because H is a singleton, the notion can be simplified as µ = (B′ , τ).

3 Compact Datalog Rewriting

In this section, we introduce a compact datalog rewriting approach, based on the notion of unfolding for existential rules [Wang et al., 2018]. A rule r can be unfolded by a rule r′ if there exists a piece unifier µ = (B, τ) of body(r) and head(r′ ), and the result is unf µ (r, r′ ):

1 It excludes the cases where v is unified with a constant, with a variable in H other than v, or with a variable in B shared between atoms inside and outside B′ .

where ⃗z consists of all the variables in the head but not in the body, and τ ′ is a safe extension of τ by substituting variables ⃗zr ∪ ⃗yr′ with fresh variables.

Example 1. Let Σex1 = {r1 : ∃y.A(x, y) ← B(x, z), r2 : ∃z.B(y, z) ← A(x, y)} and qex = Q ← A(u, v) ∧ A(v, w). Then, qex can be unfolded by r1 with a piece unifier µ = ({A(v,w)}, {x ↦→ v, y ↦→ w}), and unf µ (qex, r1) = ∃w.[Q ∧ A(v, w)] ← A(u, v) ∧ B(v, z). On the other hand, µ = ({A(u, v)}, {x ↦→ u, y ↦→ v}) is not a piece unifier, as it does not correctly unify the existential variable y.

Note that the result of unfolding can be simplified when the unified rule heads of r and r′ do not share existential variables, i.e., var(head(r)τ ′ ) ∩ var(head(r′ )τ) ∩ ⃗z = ∅. In this case, the two heads can be separated and result in

where ⃗ z1 consists of all the variables in the head but not in the body. Note that ∃⃗ z2.head(r′ )τ ← ∧(body(r) \ B)τ ∧ ∧ body(r′ )τ ′ is implied by r′ and thus is redundant.

For a rule set Σ, unfold(Σ) is the smallest rule set containing Σ such that unf µ (r, r′ ) ∈ unfold(Σ) for each r, r′ ∈ unfold(Σ) and each µ (disregarding variable renaming).

Towards a datalog rewriting method, we observe that when a strong datalog rewriting exists for a rule set, it can be obtained via unfolding.

Proposition 1. For a set of rules Σ, a strong FPDR of Σ exists iff a finite subset of unfold(Σ) is an FPDR of Σ.

Clearly, a naive method to compute a datalog rewriting using the above unfolding is impractical, as the datalog rules obtained from unfolding can be very large (indeed, are often of unbounded sizes). In what follows, we introduce a practical approach for datalog rewriting by splitting long datalog rules generated via unfolding into compact ones. As a first step, we present an alternative operator, which we simply call rewriting, between two existential rules.

Definition 1. For two rules r, r′ and a piece unifier µ = (B, τ) of body(r) and head(r′ ), the result of rewriting r by r′ with µ, denoted rewµ (r, r′ ), consists of rule (*) and the following two rules

where ⃗x = ⃗xrτ ∪ var(body(r) \ B)τ ∩ ⃗xr′τ, P is a fresh predicate with arity |⃗x|, called a separating predicate, and ⃗ z1, τ and τ ′ are as in (*).

Intuitively, we split the body of (*) by introducing P to obtain compact rules. Note that rule (*) can be obtained by unfolding (2) by (1), yet it is generated for the correctness of rewriting as we show later. We call rules of the form (*) auxiliary rules; they will be deleted after the whole rewriting process is completed.

Example 2. For Σex1 and qex in Example 1, rewµ (qex, r1) consists of the following rules:

Replacing unf µ (r, r′ ) with rewµ (r, r′ ) for unfolding leads to a set of rules that are equivalent to unfold(Σ) w.r.t. fact derivation (over original predicates) and query answering. Yet allowing the unfolding of separating predicates (i.e., including them in piece unifiers) clearly forfeits their purpose, as they were introduced to split long rules and their unfolding simply reverses the split. Hence, the unfolding of separating predicates must not be allowed.

Furthermore, it is possible to reuse separating predicates. This is achieved through a labelling function λ(·) such that λ(P) = head(r′ )τ. Intuitively, the label records how P is introduced (e.g., the head atom involved in the piece unification). When introducing a new separating predicate P′ with the same arity and if λ(P) is equivalent to λ(P′ ) up to variable renaming, we reuse P to replace P′ .

We are ready to define our datalog rewriting.

Definition 2. The rewrite chaining on a rule set Σ is a sequence of rule sets Σirew (i ≥ 0), where Σ0rew = Σ, and Σi+1 rew = Σirew ∪ { rewµ (r, r′ ) | r ∈ Σirew , r′ ∈ Σ} for i ≥ 0 satisfying the following two conditions: (i) separating predicates are reused whenever possible, and (ii) any rule that is implied by another rule is eliminated.

The rewriting of Σ, rewrite(Σ), is obtained from Σ∞rew by deleting all auxiliary and non-datalog rules.

Example 3. For Σex1 and qex in Examples 1 and 2, the rewriting of qex by r1 and r2 include additionally the following (non-exhaustive list of) rules:

Note that rules r9 and r10 cannot be obtained without keeping auxiliary rules r5 and r8 during the rewriting.

We establish the correctness of our rewriting approach. We use rewrite q () to denote the variant of rewrite() where only rules with query or separating predicates in their heads are rewritten (i.e., in Definition 1, head(r) = Q or head(r) = P′ (⃗x) for some separating predicate P′ ).

Proposition 2. For a rule set Σ, a BCQ q, and the OMQ Q = Σ ∪ {q}, rewrite(Σ) (or rewrite q (Q)) is an FPDR (resp., QPDR) of Σ (resp., Q) whenever rewrite(Σ) (resp., rewrite q (Q)) is equivalent to a finite set of rules.

4 Datalog Rewritable Classes

The rewriting method in the previous section does not necessarily terminate; for example, it does not terminate on Σex2 = {C(x, y) ← C(x, z) ∧ C(z, y)}. Yet it terminates on the class of finite unification sets (fus) [Baget et al., 2011], for which several concrete classes have been identified, such as the linear (lin), sticky (stky) [Cal`ı et al., 2012b], and acyclic graph of rule dependency (agrd) [Baget et al., 2011].

Proposition 3. For a set of rules Σ in fus, rewrite(Σ) is finite; and for any BCQ q, rewrite(Σ ∪ {q}) is finite.

However, Σex2 is not fus. It is not hard to see that the termination issue is caused by the generation of infinitely many auxiliary rules. We use rewritea() to denote the variant of rewrite() where auxiliary rules (of the form (*)) are not generated during rewriting.

Lemma 1. For a set of rules Σ, rewritea(Σ) is finite.

A rule set Σ is separable if rewritea(Σ) ≡[Σ] Σ. Intuitively, the condition requires the rule bodies (in particular, the bodies of auxiliary rules) can be separated during rewriting. The class of separable rule sets is denoted sep. Clearly, a separable rule set always admits a (finite) datalog rewriting, yet the definition does not suggest how to effectively identify such a rule set. Thus, we first show that the existing shy class [Leone et al., 2019] is a subclass of sep and then extend it to cover more practical rule sets.

A position is of the form A[i] with A being an n-ary predicate and 1 ≤ i ≤ n, and a variable v occurs at position A[i] if there is an atomA(t1, . . . , tn) with ti = v. For a set of rules Σ and an existential variable z in Σ, a position A[i] is invaded by z if there is a rule r ∈ Σ such that head(r) = A(t1, . . . , tn) and either ti = z or ti is a frontier variable that occurs in body(r) only at positions that are invaded by z. Recall that we assume each rule has a distinct set of variables. Then, a variable x in Σ is attacked by z if x only occurs in positions invaded by z. Two atoms in the same rule body are chained if (1) they share a variable that is attacked, or (2) they each contains a frontier variable and these two variables are both attacked by the same variable. Finally, Σ is shy if it does not contain two chained atoms, and we denote the class of shy rule sets as shy. It can be seen that Σex2 is shy, and every shy rule set is also separable.

Theorem 1. shy ⊂ sep.

An example of separable but not shy rule set is Σex3 = {r1 = A(x, y) ← B(x), r2 = C(x, y, z) ← A(x, y) ∧ A(x, z), r3 = D(x) ← C(x, y, z)}. It is not shy because frontier variables y and z in r2 are both attacked by the existential variable y in r1, which makes the two body atoms in r2 chained. Yet it is separable, as any datalog rule in rewrite(Σ) over [Σ], e.g., D(x) ← B(x), is derivable from rewritea(Σ).

The class of separable rule sets can be expanded to cover more datalog rewritable cases. Note that OMQ Σex1 ∪ {qex} from Example 1 is not separable, yet a datalog rewriting does exist. We call a rule set Σ weakly-separable if it can be transformed into a finite set of rules Σ′ such that rewritea(Σ′ ) ≡[Σ] Σ, and the extended class is denoted as wsep. From the definition, a weakly-separable rule set always admits a (finite) datalog rewriting. Indeed, the wsep class consists of all datalog rewritable rule sets Σ, as one can take the FPDR of Σ as Σ′ , which is finite and separable (as it contains no existential variable). Next, we want to extend the shy class (i) to allow blocks of, instead of individual, body atoms to be separable, and (ii) to combine it with concrete subclasses of fus.

A block B ⊆ body(r) for some rule r is a smallest nonempty set such that if α ∈ B then for each atom β chained to α, β ∈ B. We say a block B depends on a rule r if head(r) share the same predicate with an atom in B. For a set of rules Σ, the dependent rule set of a block B, dep(B), is the smallest set of rules r ∈ Σ such that B depends on r or some rule in dep(B) contains a block that depends on r.

Definition 3. Let fus-shy consist of rule sets Σ satisfying for each block B in Σ with |B| ≥ 2, dep(B) ∈ lin ∪ stky ∪ agrd.

The OMQ Σex1 ∪ Σex2 ∪ {qex} belongs to fus-shy, as the only block with size greater than 1 is B = {A(u, v), A(v, w)} in qex and dep(B) = Σex1 which is fus; yet it is neither shy nor fus. We can show that each rule set that belongs to fus-shy is weakly separable, and thus is datalog rewritable. Intuitively, we can transform the rule set by fully unfolding the blocks B of sizes greater than 1 by dep(B), resulting in an equivalent and separable rule set.

Theorem 2. lin ∪ stky ∪ agrd ∪ shy ⊂ fus-shy ⊂ wsep.

Moreover, a rule set in fus-shy coupled with any BCQ is also datalog rewritable.

Proposition 4. For a rule set Σ that belongs to fus-shy and any BCQ q, the OMQ Σ ∪ {q} belongs to wsep.

5 An Efficient Rewriting Algorithm

In this section, we introduce an efficient method for computing datalog rewritings of the form rewritea(Σ) whenever they exist, and discuss how it can be adapted to compute rewrite(Σ). Inspired by [Hansen et al., 2015], we compute a decomposed representation of the heads and bodies of the resulting rules generated during the rewriting, such that the representation is compact due to structure sharing and the datalog rewriting can be conveniently extracted from such a representation. For the ease of presentation, we first present a variant of the representation and then further simplify it.

For a set of rules Σ, its rewriting forest FΣ has nodes of the form (P(⃗x), H, B1, B2), where P is a fresh predicate not occurring in Σ, ⃗x is a vector of variables, H is an atom, and B1,B2 are sets of atoms; and edges are labelled with piece unifiers. The roots of FΣ correspond to the rules in Σ, i.e., are of the form (⊤, head(r), ∅, body(r)) for all rules r ∈ Σ, where ⊤ represents true. Intuitively, each node ((P(⃗x),H,B1,B2) represents two rules as follows:

where ⃗z consists of all the variables in the head but not in the body. Rules (1*) and (2*) correspond to the rules (1) and (2) generated during rewriting. Hence, P can be reused in the same way as separating predicates through the labelling function λ(·). Moreover, a node n is blocked by another node n′ if its corresponds rules are both implied by those of n′ .

Formally, FΣ has the smallest number of nodes and edges satisfying the following conditions: For each node n = (P(⃗x),H,B1,B2) and each root node n′ = (⊤,H′ , ∅,B′2 ), let ⃗x′ = var(H′ ) ∩ var(B′2 ); and

1. for each piece unifier µ = (B, τ) of B2 and H′ , n has a child n′′ = (P′′ (⃗x′′ ), H′′ , B′′ 1 , B′′ 2 ) whenever n′′ is not blocked s.t.
2. ⃗x′′ = var(H)τ∪var(B2\B)τ∩⃗x′ τ, λ(P′′ ) =H′ τ,
3. H′′ = Hτ ′ , where τ ′ is as in (*), B′′ 1 = B′2 τ ′ and B′′ 2 = (B2 \ B)τ ∪ {P′′ (⃗x′′ )};
4. if n is not a root, for each piece unifier µ of B1 and H′ , n has a child n′′ whenever n′′ is not blocked s.t.
5. ⃗x′′ = ⃗xτ ∪ var(B1 \ B)τ ∩ ⃗x′ τ ,

• H′′ = P(⃗x)τ ′ and B′′ 2 = (B1 \ B)τ ∪ {P′′ (⃗x′′ )},
• B′′ 1 and λ(P′′ ) are as in Condition 1;

Our algorithm starts with the nodes corresponding to the rules in Σ and expands the rewriting forest based on the above conditions. The expansion terminates due to the blocking condition, and the number of nodes are bounded based on the same argument as for Lemma 1. Let datalog(FΣ) be the set of datalog rules obtained as above from the nodes of FΣ.

Theorem 3. For a set of rules Σ, FΣ is always finite and datalog(FΣ) ≡[Σ] rewritea(Σ).

To further simplify the representation, note that H and B2 in each non-root node can be computed on the fly. In particular, for the computation of H′′ and B′′ 2 under Conditions 2, it only needs the current node n′′ and its parent node n; whereas under Condition 1, B′′ 2 refers to B2 in the parent node n, which can be computed through back-tracking till a root.

To adapt rewriting forests for the computation of rewrite(Σ), we can expand each node with a fourth component B3, which is a set of atoms. Intuitively, it is used to capture rules ∃⃗z.H ← ∧ B3, that corresponds to the rules of the form (*) generated during the rewriting. In particular, B′′ 3 = (B2 \ B)τ ∪ B′2 τ ′ in Conditions 1, and B′′ 3 = (B1\B)τ ∪B′2 τ ′ in Condition 2. Furthermore, there is a third condition: if n is not a root, for each piece unifier µ of B3 and H′ , n has a child n′′ whenever n′′ is not blocked such that ⃗x′′ = var(H)τ ∪var(B3 \B)τ ∩⃗x′ τ , B′′ 3 = (B3\B)τ∪B′2 τ ′ , and everything else is defined as in Condition 1. Again, B3 in each node can be computed on the fly via back-tracking. The difference fromB1 and B2 is that the sizes of B3 are not necessarily bounded, unless rewrite(Σ) is finite.

6 Experiment

We have implemented a prototype system, Drewer (Datalog REWriting for Existential Rules), with our piece unification module adapted from the first-order rewriting system Graal 2 [K¨onig et al., 2015a], and we deployed VLog 3 as our datalog engine. All experiments were performed on a laptop with a processor at 2.2 GHz and 8GB of RAM. The system and experiment benchmarks can be found at https://www.ict.griffith.edu.au/aist/Drewer.

We evaluated ontologies including the DL-Lite versions of LUBM, OpenGALEN2, OBOprotein and RS. RS is from [Bienvenu et al., 2017] with a simple ontology but specially crafted long queries (with up to 15 atoms), which is a known challenge to existing rewriting-based systems. Reactome and Uniprot are in OWL2, and we used the existential rule fragments of them which are more expressive than DL-Lite. The ontologies were converted into existential rules using a transformation tool provided by Graal. DEEP200/300, STB-128, and ONT-256 are from ChaseBench [Benedikt et al., 2017], a benchmark for chase-based reasoning systems. They contain existential rules with predicates of arities more than two. All the tested ontologies are found to be in fus-shy and thus can be handled by Drewer, whereas none of the compared rewriting system could successfully handle all of them.

2 http://graphik-team.github.io/graal/

3 https://github.com/knowsys/vlog4j

We conducted two sets of experiments to evaluate the performance of our system. In the first set of experiments, we compared our system with state-of-the-art query rewriting systems regarding the compactness and efficiency of query rewriting. In particular, Graal is a first-order rewriting system for existential rules, Rapid [Trivela et al., 2015] and Iqaros [Venetis et al., 2016] are datalog and UCQ rewriting systems for description logic ontologies. We used original queries that come with the datasets and evaluated 5 queries per ontology, except for RS which has only 3 long queries.

Table 1 records the sizes and times for query rewriting, where sizes are measured by the numbers of atoms and the times are in milliseconds. We set a 5 minutes time limit per query, and TO denotes a timeout whereas a "-" means the system could not handle the OMQ (or reported errors).

It can be seen from Table 1, the sizes of datalog rewritings are often comparable to or much smaller than those of UCQ rewritings. Note that to achieve efficiency as well as compactness in rewriting, Graal makes use of the so-called compiled pre-orders of the form A ⪯ B for predicates A, B, which can be seen as datalog rules B(⃗x) ← A(⃗x). Hence, the UCQ rewritings produced by Graal need to be coupled with the compiled pre-orders for query answering. For a fair comparison, we report the rewriting sizes for Graal in the form of x + y, where x is the size of the UCQ rewriting and y is that of the datalog rules corresponding to the compiled preorders. Since not all pre-orders are used for specific queries, we tracked for each query those pre-orders actually used for query answering (following Graal's native query answering process) and y is the number of only those used pre-orders.

Regarding the time efficiency of rewriting, Drewer is again superior or comparable to other systems in almost all cases. In particular, all other systems reached a timeout on q5 for OBOprotein, whereas Drewer took only less than a second to complete the rewriting. And all other systems except for Graal failed to complete their rewriting on the 3 queries for RS, due to the large sizes of UCQ rewritings.

To evaluate the overall performance of Drewer in query answering, we conducted a second set of experiments comparing it with other in-memory (as Drewer is in-memory) query answering systems. To separate the contribution of our rewriting method from that of an efficient datalog engine, besides Graal and Iqaros, we also compare Drewer with stateof-the-art chased-based systems VLog [Carral et al., 2019] and DLV∃ [Leone et al., 2019]. All ontologies except for Uniprot are weak acyclic [Grau et al., 2013], so the chasebased systems can be used for query answering. To compare with Graal on the quality of different rewritings, we used a datalog translation for both of its UCQ rewritings and the used pre-orders, and deployed the same datalog engine VLog.

Table 2 presents the average times (in milliseconds) for answering the 5 queries over each ontology, where we ran each query separately (which may involve running the chase procedure separately for each query). If a system reached a timeout on a particular query, we counted 5 minutes. Hence, a TO means a failure for all the 5 queries. We separate the query answering times (QA, including possibly rewriting, chase computation, and query evaluation) out of the total times, except for DLV∃ where it was difficult to make such a separation.

Overall, our (datalog) rewritings demonstrate significantly better efficiency in query answering compared to UCQ rewritings (by Graal and Iqaros); while Drewer could successfully handle all queries, Graal reached a timeout on 4 queries for Reactome and 2 queries for DEEP200 and DEEP300. In the comparison with chase-based systems, our system demonstrates superior time efficiency (sometimes by magnitudes) than VLog on all tested cases, which shows our performance gain is significantly contributed by the rewriting. Drewer also outperforms or is comparable to DLV∃ , which compute the parsimonious chase rather than the full chase, on most of the cases. A chase-based system still has the advantage of being able to answering multiple queries over a single computation of the chase.Yet when the chase is difficult or impossible to compute, e.g., on Uniprot, our rewriting can be a determining factor between success and failure.

7 Conclusion

In this paper, we have presented a novel approach to datalog rewriting for existential rules and introduced a new concrete datalog rewritable class by combining several existing classes. We also implemented and evaluated our prototype system, Drewer, which is capable to handle a wide range of practical ontologies with superior or comparable performance compared to state-of-the-art rewriting and query answering systems. For future work, we are working on identifying more general classes of datalog rewritable existential rules, and optimising our rewriting algorithm and implementation.

Acknowledgements

This work was partially supported by NSFC under grant 61976153.