Existential rules is an expressive ontology formalism for ontologymediated query answering and as a trade-o , query answering is of high complexity, while several tractable fragments have been identi ed. Existing systems are based on rst-order rewriting methods and the resulting queries can be too large for DBMS to handle. It is shown that datalog rewriting can result in more compact queries but the previous study is mostly theoretical. A practical datalog rewriting algorithm is still missing. In this paper, we ll the gap by proposing a practical datalog rewriting algorithm for conjunctive query answering over existential rules, and establish its correctness over well known fragments of existential rules. Experiments on our prototype system showed superior or comparable performance over state-of-the-art systems on both the compactness of rewritings and the e ciency of query answering.
Existential rules (a.k.a. Datalog and tuple generating dependencies) [2, 6] 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 E L [5], which underlay the OWL 2 Pro les. This makes existential rules an appealing formalism for ontology-mediated query answering. While the query answering problem is undecidable over the full formalism, several interesting fragments have been proposed [4, 6, 17] that support tractable query answering.
A major approach for query answering over ontologies expressed in description logics or existential rules is query rewriting. Given an ontology and a query q, a rewriting method transforms them into another query q , which is sometimes in a di erent 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 ontology-mediated 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 [18, 7, 25, 23], particularly for DL-Lite and E L [15, 20, 22, 12], it is challenging to extend them to more general existential rules, as existential rules allow predicates of arbitrary arities (instead of only unary and binary predicates) and variable permutations in the rules.
Existing systems for query answering over existential rules are typically based on rst-order rewritings [8, 13, 14], i.e., q is a rst-order query. A limitation of such an approach is that it can only handle ontologies and queries that are rst-order rewritable. Well-accepted rst-order rewritable classes are the linear and sticky existential rules [6]. Yet many practical ontologies do not necessarily fall into these classes, such as some ontologies formulated in E L. Even for ontologies and queries that are rst-order rewritable, the results of rewriting can su er from a signi cant blow-up and become di cult for DBMSs to handle [19].
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 (nonrecursive) datalog rewritings is much more feasible for DBMSs than equivalent rstorder rewritings [12]. All ontologies and queries that are rst-order rewritable are trivially datalog rewritable, and more datalog rewritable classes are known, such as the guarded existential rules [9]. However, existing research on datalog rewriting of existential rules are mostly theoretical [10, 3] (refer to [1] for a detailed discussion). While several algorithms and systems have been developed for datalog rewriting for various description logics [7, 12], to the best of our knowledge, a practical system is still missing for datalog rewriting over more general existential rules.
In this paper, we ll the gap by presenting both a practical algorithm and a prototype system for datalog rewriting and query answering over existential rules. Our algorithm is based on the notion of unfolding [24] and the observation that unfolding can generate a datalog rewriting whenever it exists. Yet instead of naive unfolding, to achieve compactness of rewriting, we separate the results of unfolding into short rules by introducing fresh predicates and reusing such predicates when possible. Such a separation technique not only reduces the length of generated rules but also facilitates structure sharing (via the reuse of predicates). While such a rewriting process may not terminate, we move on to identify classes of ontologies where the rewriting process terminates and produce correct datalog rewritings, including both a novel class and several existing well-accepted classes. After that, we introduce a practical algorithm for computing the datalog rewriting through constructing rewriting graphs, which again facilitates structure sharing and can be seen as a decomposed representation of rewritings. Finally, we implemented our algorithm as a prototype system and evaluate it against the state-of-the-art systems for both existential rules and description logics on commonly used benchmark ontologies and queries. 2
Let Nc, Nn, and Nv be disjoint, countably in nite sets of constants, (labelled) nulls, and variables respectively. A term is either a constant, null, or variable. We assume standard rst-order logic notions, such as predicates, (ground) atoms, formulas, entailment (j=) and equivalence ( ). An instance is a (possibly in nite) set of atoms that contains only constants and nulls. A dataset is a nite ground instance. For a formula or an instance ', var(') denotes the variables in '.
An existential rule (or a rule) r is a formula of the form 8x:8y:[9z:'(x; z) (x; y)] where x, y and z are pairwise disjoint vectors of variables, and '(x; z) and (x; y) are conjunctions of atoms with variables from respectively x [ z and x [ y. We assume rules do not contain constants. Variables in x are called frontier variables, denoted fr(r). and those in z are called existential variables, denoted ext(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 (existentially quanti ed conjunctions of) sets of atoms. For brevity, universal quanti ers in a rule are often omitted, and we sometimes express rule r as head(r) body(r). A datalog rule r is an existential rule whose head consists of a single atom and ext(r) is empty.
A conjunctive query (CQ) q is a rst-order formula of the form 9y:'(x; y), where x and y are tuples of variables and is a conjunction of atoms containing only constants and variables from x [ y. Sometimes it is convenient to treat it as a datalog rule Q(x) '(x; y) where Q is a fresh predicate with arity jxj. If x is empty then q is a Boolean CQ (BCQ). Answering CQs can be reduced to that of BCQs and hence w.l.o.g. we consider only BCQs in this paper. For convenience, we assume a xed renaming between variables and labelled nulls, which allows us to identify a BCQ with the set of its atoms where all the variables are renamed as nulls, and vice versa. A union of BCQs (UCQ) is a disjunction of BCQs, which is seen as a nite set of nite instances.
An ontology-mediated query (OMQ) is a pair Q = ( ; q) with a nite set of rules and q a BCQ. The answer of Q over a dataset D is true if [ D j= q, and false otherwise. A datalog rewriting of an OMQ ( ; q) is a of the form ( ; Q) where is a datalog program and Q is a nullary predicate, such that for any dataset D, [ D j= q i [ D j= Q. We call it a strong datalog rewriting if additionally [ fqg j= . Q is the query predicate of q and sometimes denoted as Qq. When consists of only non-recursive datalog rule with Q in their heads, the rewriting is a UCQ rewriting.
The UCQ rewriting of OMQs can be obtained through the notion of piece uni cation for a given BCQ q and a rule r [16]. First, for a subset q0 of q, a variable occurring both in q0 and in q n q0 is a separating variable for q0 in q. A piece uni er of q and r is a triple = (B; H; ), where ; B q, H head(r), and is a most general uni er between B and H such that the following condition is satis ed for each z 2 ext(r): If a term t (t 6= z) in B [ H is uni ed with z, i.e., z = t , then t is not a separating variable for B in q.
For a set X of variables and a substitution , jX denotes the restricted substitution to domain X. Another substitution 0 is a safe extension of jX on a set of variables Y , if 0 coincides with jX and for each y 2 Y , y 0 is a fresh variable. 3
In this section, we will introduce a compact datalog rewriting approach, based on the notion of unfolding for existential rules [24]. A rule r can be unfolded by a rule r0 if there exists a piece uni er = (B; H; ) of body(r) and r0, and the result of unfolding r by r0 with is the following rule denoted unf (r; r0): where 0 is a safe extension of jvar(H) on var(r0) n var(H), 00 is a safe extension of jfr(r) on ext(r), and z consists of all the variables in the head but not in the body. The result of exhaustive unfolding for is denoted unfold( ).
Note that if a strong datalog rewriting exists for an OMQ, then there exists a subset of its unfolding that consists of datalog rules and is such a datalog rewriting.
nite subset unfold( [ fqg) such that ( ; Qq) is such a datalog rewriting.
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 breaking up long datalog rules into smaller ones. It is known that every OMQ ( ; q) can be transformed into an OMQ ( 0; q) whose rule heads have single atoms in a way that preserves query answering [8]. For convenience, in what follows, we assume consists of rules of single-atom heads. As a rst step, we present an alternative operator, which we simply call rewriting, between two existential rules. De nition 1. For two rules r; r0 and a piece uni er = (B; H; ) of body(r) and r0, the result of rewriting r by r0 with , denoted rew (r; r0), consists of the following rules
P(xr0 )
R(v) for each
2 head(r) 00 [ head(r0) 0;
where 0; 00 are as in Equation (
Note that rule (
We can use rew (r; r0) to replace unf (r; r0) in the unfolding of rules and it is not hard to see that the resulting set of rules are equivalent w.r.t. query answering. Indeed, if we allow fresh predicates P and R to be further unfolded, then the rewriting process generates strictly more rules than unfold( ). However, it is clear that allowing the unfolding of fresh predicates forfeits their purpose, as they were introduced to break up long rules and their unfolding simply reverses it. Hence, it is natural to disallow unfolding of such fresh predicates.
Furthermore, it also does not make sense to introduce a di erent fresh predicate each time when the \same" piece uni er, i.e., up to variable renaming, is applied. This is achieved through a label function ( ) that maps each fresh predicate to a set of atoms. Formally, for predicates P and R in De nition 1, (P) = H = head(r0) 0 and (R) = (head(r)) 00 [ (head(r0)) 0, where (A(x)) = A(x) if A is a (non-fresh) predicate occurring in the initial rules and otherwise (A(x)) = (A).
Finally, special handling for rewriting a query q by another rule r0 is needed.
In particular, the handling of head atoms is simpler, such that rew (q; r0) replaces
rules (
Q
Q
(body(q) n B) [ fP(xr0 ) g;
(body(q) n B) [ body(r0) 0:
(
We are ready to de ne the rewriting of a set of existential rules .
De nition 2. The rewriting of a set of existential rules , denoted rewrite( ) is
the (possibly in nite) set of rules obtained by exhaustively applying rewriting between
each pair of rules r; r0 as in De nition 1 under the following conditions and by deleting
temporary and non-datalog rules at the end:
{ H does not contain any fresh predicate;
{ If r is a query (i.e., has Q in the head), its rewriting follows (
variant of rewrite( ) where temporary rules in R are not generated (resp., only rules in R are generated) during rewriting.
Example 1. Consider 1 = fr1 : B(y) A(x; y); r2 : 9y:A(x; y) B(x)g and q = Q A(x; y) ^ A(y; z). The (one step) rewriting of r1 by r2 results the following rules: r3 : P1(x) r6 : B(y)
B(x); r4 : 9y:R1(x; y)
P1(x); R1(x; y); r7 : 9y:[A(x; y) ^ B(y)]
P1(x); r5 : A(x; y)
R1(x; y); where (P1) = fA(x; y)g and (R1) = fA(x; y); B(y)g.
Rewriting q by r2, by r1, and then by r2 leads to (not a complete list of) rules: r8 : Q r10 : P2(y) r13 : Q
P1(x);
A(z; y); A(x; y) ^ P1(y); r9 : Q
A(x; y) ^ B(y); r11 : Q r14 : Q
A(x; y) ^ P2(y); r12 : Q
A(x; y) ^ A(z; y);
B(x): Note that P1 is reused; also, rules r13 and r14 cannot be obtained without keeping temporary rules r9 and r12 during the rewriting.
Now we establish the soundness and completeness of our datalog rewriting.
Proposition 1. For an OMQ Q = ( ; q), let = rewrite(
rewritej(
[ fqg) (resp., = nite then ( ; Qq) is a Proof (Sketch). We want to show for each dataset D, [D j= q i [D j= Qq. First, we only need to establish \if" direction for = rewrite( [fqg), which can be checked inductively through the unfolding of rules in . In particular, consider the unfolding of (reused) fresh predicates in two rules r1 and r2 of the form Q B1 [ fA(x)g and A(x) B2, where A is a fresh predicate and B1; B2 do not contain fresh predicates. Suppose (A) = H(y; z) with some substitution such that y = x, then by the de nition of rewriting and unfolding, there are rules (up to variable renaming) Q B1 [ H0 with H0 H and H B2 from unfold( [ fqg). Note that the predicate reuse condition in De nition 2 ensures that H0 is a piece for uni cation. Thus, the result of unfolding r1 by r2 is in unfold( [ fqg). This can be extended to the cases where B1; B2 contain fresh predicates.
Also, we only need to show the \only if" direction for = rewritej(
The process of rewriting introduced in the previous section does not necessarily terminate; for example, it does not terminate on 2 = f9z:A(z; x) A(x; y)g. It is not hard to see that the termination issue is caused by the generation of temporary rules. If we disallow the generation of temporary rules, the rewriting always terminates.
nates and the result is nite.
, the computation of rewritej(
In what follows, we discuss several classes of rules on which ( nite) datalog rewritings can be obtained by restricting the generation temporary rules. We start by de ning a novel class called separable rule sets, which is through adapting a marking procedure from [17].
We use zr to denote an existential variable z in rule r. For a set of rules , an atom and a variable x occurring at position i in , we mark the position with a minimum set of variables M (i; ) satisfying the following conditions: (i) if head(r) = for some r 2 with x 2 ext(r) then M (i; ) = fxrg; (ii) if head(r) = for some r 2 with x 2 fr(r) then M (i; ) is the intersection of all M (j; ) s.t. 2 body(r) and x occurs at position j in atom ; (iii) if 2 body(r) then M (i; ) is the union of M (i; head(r0)) for all r0 2 s.t. r can be unfolded by r0 with uni ed with head(r0).
a variable x shared by two body atoms such that the intersection of all M (i; ), for each atom 2 body(r) and each position i that x occurs in , is non-empty. It is not hard to see that 2 is separable.
The class of shy rule sets is proposed in [17]. Intuitively, a set of rules is shy if no existential variable occurs in a position of a relation where a join variable occurs in a rule body, neither can two variables occurring in such (existential-variable) positions of the body also occur in the same head atom.
This can be seen from that any rule set violating separability also violates Condition 1 of shyness [17]. However, the converse of the proposition is not necessarily true and 2 [ fB(x; y) A(x; u) ^ A(y; v)g is such a case.
fqg) is a datalog rewriting of ( ; q).
[ fqg is separable, rewrite(
The class of sticky rule sets is introduced in [6], which are shown to be rst-order rewritable. The key idea is that fresh variable generated during backward chaining cannot occur in two separate atoms [21]. The two classes of sticky and separable rules are incomparable; for instance, 3 = fA(x; y) A(x; z) ^ A(z; y)g is separable but not sticky, and 1 [ fC(x; y; z) A(x; y) ^ A(y; z)g (where 1 is from Example 1) is sticky but not separable.
a datalog rewriting of ( ; q).
is sticky, rewrite(
Finally, we are also interested in the class of acyclic rule sets, for which various notions of acyclicity have been proposed [11], which guarantees the termination of forward chaining (i.e., on certain chase procedures).
datalog rewriting of ( ; q).
is acyclic, rewritej(
In this section, we introduce a practical algorithm for computing datalog rewritings
of the form rewritej(
For a set of rules whose maximum number of body atoms is m, we de ne a
rewriting graph to be a direct graph (N; E) whose nodes in N are of the form (R; I),
where R and I each consists of at most m atoms, and whose edges in E are labelled
with piece uni ers. Each node n = (R; I) is associated with two fresh predicates Pn
and Rn, and we reuse fresh predicates as in Section 3 through a label function ( ).
For each node n = (R; I), let un = fr(R I) and vn = var(R). Intuitively, an edge
from node n = (R; I) to node n0 = (R0; I0) labelled with = (B; H; ) represents a
set of rules (i.e., rules (
I0;
9z:Rn0 (vn0 )
(I n B) [ fPn0 (un0 )g;
Rn0 (vn0 ) for each
2 R0;
corresponding to (
Now, we present the algorithm for computing rewriting graphs. Note that similar
as the rule elimination in De nition 2, for a new node n = (R; I), if there is an existing
node n0 = (R0; I0) and a homomorphism from I0 to I such that a safe extension 0
of exists with R R0 0, then n should be eliminated. In Algorithm 1, actions with
a are subject to the reuse of fresh predicates and node elimination. Also, 0 and 00
denote safe extensions of as in Equation (
In Algorithm 1, we rst initialise the nodes to be the pairs of heads and bodies
of existing rules (line 2) and use a queue to store the nodes representing rules
to be rewritten (line 4 onwards). Since a piece uni er cannot contain a fresh
predicate (by De nition 2 and guaranteed in line 7), only original rules or rules of the
forms (
We establish the correctness of Algorithm 1 as follows. Algorithm 1: Compute Rewriting Graphs input : A set of existential rules output: A rewriting graph (N; E) 1 begin 2 initialise N := f(head(r); body(r)) j r 2 g and E := ;; 3 assign fresh predicates Pn; Rn to each n = (R; I) 2 N with (Pn) = (Rn) = R; 4 let be a queue and initially := N ; 5 while 6= ; do 6 take n = (R; I) popped from ; 7 foreach n0 = (R0; I0) 2 N and 2 R0 containing no fresh predicate do 8 consider rule r := I0; 9 foreach piece uni er = (B; H; ) of I and r do 10 if n 2 N then 11 take n00 := (R00; I0 0) where R00 = R 00 [ f 0g if R is a singleton; otherwise R00 = fPn(un) 00; 0g; 12 assign a fresh predicate Rn00 and let (Rn00 ) := (Pn) 00 [ f 0g; 13 14 15
6
We have implemented a prototype system Drewer (Datalog REWriting for Existential Rules), where the piece uni cation implementation is adapted from the rst-order rewriting system Graal [13], and used RDFox1 as the datalog engine. We conducted two set of experiments to evaluate the performance of our system. All experiments were performed on a desktop machine with a processor at 3.30 GHz and 8GB of RAM. 1 https://www.cs.ox.ac.uk/isg/tools/RDFox/
In the rst set of experiments, we compared our system with state-of-the-art query rewriting systems regarding the compactness and e ciency of query rewriting. In particular, Graal is a rst-order rewriting system for existential rules, Iqaros [23] is a rst-order rewriting system for OWL 2 DL featured in its rewriting minimisation, and Rapid [22] is a datalog rewriting system for DL-Lite and EL based on optimised resolution. For benchmark ontologies and queries, we selected 3 commonly used ontologies [13], which are DL-Lite versions of Adolena (A), OpenGALEN2 (G), and StockExchange (S). Each of the ontologies comes with 5 conjunctive 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.
Ontology
Query
UCQ
Rewriting Size
Drewer Graal
Rewriting Time Drewer Graal Rapid Iqaros A G S
Both Rapid and Iqaros output minimal rewritings of the same sizes recorded under \UCQ". To achieve e ciency as well as compactness in rewriting, Graal makes use of the so called rule compilation, which leads to its small rewriting output. Yet, the results of rewriting produced by Graal are not standard UCQs, which have to be evaluated through a special homomorphism mechanism, and thus cannot be directly handled by DBMSs for datalog engines. We can see that the bene t of datalog rewriting w.r.t. sizes compared to UCQ rewritings becomes obvious when large UCQ rewritings are generated ( 50), with two exceptions q2 and q4 on G. This is because the ontology has a large number of simple axioms. For rewriting times, the performance of our system is comparable to Graal and Rapid, with an exception on G due to the reason discussed before.
In the second set of experiments, we compared our system with existing end-toend in-memory (as our system is in-memory) query answering systems regarding time e ciency. We use RDF4j as the data store of Graal. Another system we compared is Pagoda [25], which is not a standard rewriting system, but a hybrid system combining a datalog engine and an OWL 2 reasoner. To compare with Graal and Iqaros, we used the DL-Lite versions of two widely used ontologies, LUBM and Reactome [25]. As Reactome comes with over 100 queries, we randomly selected 5 queries. Table 2 records the times (in seconds) on pre-processing (Pre) and query evaluation (Eval).
Ontology Query
Drewer Pre Eval
Graal Pre
Eval
Pagoda Pre Eval
Iqaros Pre Eval
LUBM Reactome
Our system showed superior performance in most cases compared to Graal, which is possibly due to the special homomorphism mechanism implemented in it. both of which took signi cantly more time in pre-processing. Considering only the query evaluation times, Drewer is comparable to Pagoda, whereas Pagoda took more preprocessing time for the materialization of upper-bound and lower-bound datalog programs. Iqaros shows best performance among all the systems, while the performance of Drewer is comparable on Reactome. Note that Iqaros is specialised for rst-order rewritable OWL 2 DL ontologies, whereas Drewer is for more general existential rules. 7
In this paper, we have presented a novel approach to datalog rewriting for existential rules and introduced a new datalog rewritable class, the separable rule sets, which generalises the class of shy rule sets. Furthermore, we presented a practical algorithm for computing datalog rewritings and established its correctness. Finally, we implemented and evaluated our prototype system Drewer, which is to the best of our knowledge, the rst datalog rewriting system for existential rules. Our system demonstrated superior or comparable performance compared to state-of-the-art rewriting and query answering systems.
For future work, we are working on identifying a more general class of datalog rewritable existential rules, optimising our rewriting algorithm and implementation, and conducting further evaluation on more complex ontologies and queries.