Existential rules is an expressive ontology formalism for ontologymediated query answering and as a trade-off, query answering is of high complexity, while several tractable fragments have been identified. Existing systems are based on first-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 fill 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 efficiency 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 EL [5], which underlay the OWL 2 Profiles. 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 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 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 EL [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 first-order rewritings [8,13,14], 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 [6]. 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 [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 firstorder rewritings [12]. 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 [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 fill 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.
Let N c , N n , and N v be disjoint, countably infinite sets of constants, (labelled) nulls, and variables respectively. A term is either a constant, null, or variable. We assume standard first-order logic notions, such as predicates, (ground) atoms, formulas, entailment (|=) and equivalence (≡). An instance is a (possibly infinite) set of atoms that contains only constants and nulls. A dataset is a finite 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
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 quantified conjunctions of) sets of atoms. For brevity, universal quantifiers 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 first-order formula of the form ∃y.ϕ(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 |x|. 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 fixed 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 finite set of finite instances.
An ontology-mediated query (OMQ) is a pair Q = (Σ, q) with Σ a finite set of rules and q a BCQ. The answer of Q over a dataset D is true if Σ ∪ D |= 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 |= q iff Π ∪ D |= Q. We call it a strong datalog rewriting if additionally Σ ∪ {q} |= Π. Q is the query predicate of q and sometimes denoted as Q q . 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 unification for a given BCQ q and a rule r [16]. First, for a subset q of q, a variable occurring both in q and in q \ q is a separating variable for q in q. A piece unifier of q and r is a triple µ = (B, H, τ ), where ∅ ⊂ B ⊆ q, H ⊆ head(r), and τ is a most general unifier between B and H such that the following condition is satisfied for each z ∈ ext(r): If a term t (t = z) in B ∪ H is unified 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 σ, σ| X denotes the restricted substitution to domain X. Another substitution σ is a safe extension of σ| X on a set of variables Y , if σ coincides with σ| X and for each y ∈ Y , yσ is a fresh variable.
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 r if there exists a piece unifier µ = (B, H, τ ) of body(r) and r , and the result of unfolding r by r with µ is the following rule denoted unf µ (r, r ):
where τ is a safe extension of τ | var(H) on var(r ) \ var(H), τ is a safe extension of τ | fr(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.
Lemma 1. For an OMQ (Σ, q), a strong datalog rewriting exists iff there exists a finite subset Π ⊆ unfold(Σ ∪ {q}) such that (Π, Q q ) 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 (Σ , 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 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, H, τ ) of body(r) and r , the result of rewriting r by r with µ, denoted rew µ (r, r ), consists of the following rules
∃z.
[head(r)τ ∪ head(r
where τ , τ are as in Equation ( 1), v is a tuple of variables in head(r)τ ∪ head(r )τ , z consists of all the variables in the head but not in the body, and P and R are fresh predicates with arities |x r | and |v|.
Note that rule (5) can be captured by rules ( 3) and ( 4), yet it is included for the correctness of rewriting in some cases. We mark rule (5) as temporary which will be deleted after the rewriting is completed, and we will discuss in next section when the generation of such temporary rules are not necessary. Also, for rules of the form (3) that are not datalog rules, we also mark them for deletion. We can use rew µ (r, r ) to replace unf µ (r, r ) 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 different fresh predicate each time when the "same" piece unifier, 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 Definition 1, λ(P) = Hτ = head(r )τ and λ(R) = γ(head(r))τ ∪ γ(head(r ))τ , 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 r is needed. In particular, the handling of head atoms is simpler, such that rew µ (q, r ) replaces rules (3)-( 5) with the following rules
Again, rule (7) can be captured by rules ( 2) and ( 6), yet it is included for the correctness of rewriting in some cases. It is also temporary rules to be deleted after the rewriting is completed. We are ready to define the rewriting of a set of existential rules Σ.
Definition 2. The rewriting of a set of existential rules Σ, denoted rewrite(Σ) is the (possibly infinite) set of rules obtained by exhaustively applying rewriting between each pair of rules r, r as in Definition 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 ( 2), ( 6) and ( 7); -For each introduced fresh predicate A ∈ {P, R} in an atom of the form A(x), if there is an atom A (x ) with A another fresh predicate of the same type introduced in previous rewriting steps such that there is a most general unifier σ between λ(A) and λ(A ) with xσ = x σ, then reuse A to replace A. -Eliminate rule r if there is another rule r and a homomorphism σ from body(r )
to body(r) such that a safe extension σ of σ exists with head(r )σ = head(r).
We use rewrite| R (Σ) (resp., rewrite R (Σ)) with R ⊆ {(2), . . . , (7)} to denote the variant of rewrite(Σ) where temporary rules in R are not generated (resp., only rules in R are generated) during rewriting.
Example 1. Consider Σ 1 = {r 1 : B(y) ← A(x, y), r 2 : ∃y.A(x, y) ← B(x)} and q = Q ← A(x, y) ∧ A(y, z). The (one step) rewriting of r 1 by r 2 results the following rules: Rewriting q by r 2 , by r 1 , and then by r 2 leads to (not a complete list of) rules:
Note that P 1 is reused; also, rules r 13 and r 14 cannot be obtained without keeping temporary rules r 9 and r 12 during the rewriting. Now we establish the soundness and completeness of our datalog rewriting.
Proof (Sketch). We want to show for each dataset D, Σ ∪D |= q iff Π ∪D |= Q q . First, we only need to establish "if" direction for Π = rewrite(Σ ∪{q}), which can be checked inductively through the unfolding of rules in Π. In particular, consider the unfolding of (reused) fresh predicates in two rules r 1 and r 2 of the form
where A is a fresh predicate and B 1 , B 2 do not contain fresh predicates. Suppose λ(A) = H(y, z) with some substitution σ such that yσ = x, then by the definition of rewriting and unfolding, there are rules (up to variable renaming) Q ← B 1 ∪ H σ with H ⊆ H and Hσ ← B 2 from unfold(Σ ∪ {q}). Note that the predicate reuse condition in Definition 2 ensures that H σ is a piece for unification. Thus, the result of unfolding r 1 by r 2 is in unfold(Σ ∪ {q}). This can be extended to the cases where B 1 , B 2 contain fresh predicates. Also, we only need to show the "only if" direction for Π = rewrite| (5) (Σ ∪ {q}) and Π = rewrite| (7) (Σ ∪ {q}), and we only need to show for each rule r ∈ unfold(Σ ∪ {q}) with head Q, r also occurs in unfold(Π) (up to variable renaming). We only demonstrate the proof for Π = rewrite| (7) (Σ ∪ {q}). We show this by an induction on forward chaining, i.e., consider an unfolding chain: (i) r 1 , . . . , r n ∈ Σ ∪ {q}, (ii) for i ≥ 2, r i,...,1 is the result of unfolding r i by r i−1,...,1 , and (iii) r n = q. For the first two rules r 1 , r 2 in the chain, r 2,1 is of the form (1), and it has corresponding results of rewriting, rules ( 5) and ( 2), denoted r for further unfolding and the body of r 2,1 can be reconstructed through (unfolding) r 2,1 . For each rule r i (i ≥ 2), there is a rule r (5) i,...,1 in the process of rewriting that rewrites it to r (5) i,...,1 and r (2) i,...,1 , such that the head of r i,...,1 is preserved in r (5) i,...,1 for further unfolding and the body of r i,...,1 can be reconstructed through (unfolding) r
The process of rewriting introduced in the previous section does not necessarily terminate; for example, it does not terminate on Σ 2 = {∃z.A(z, x) ← A(x, y)}. 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.
Lemma 2. For a set of rules Σ, the computation of rewrite| (5), (7) (Σ) always terminates and the result is finite.
This can be seen as follows. Suppose the maximum number of atoms in the initial rule bodies is m. For each rule of the forms (2)-( 4) and (6), it has a single atom head and its body has at most m atoms. Also, for each fresh predicate P, λ(P) consists of a single head atom of an initial rule (up to variable renaming). Similarly, for each fresh predicate R, λ(R) consists of at most m head atoms of initial rules, as each rewriting step may add one atom to the head and rule (3) can be rewritten at most m times (noting that unfolding of fresh predicates is disallowed).
In what follows, we discuss several classes of rules on which (finite) datalog rewritings can be obtained by restricting the generation temporary rules. We start by defining a novel class called separable rule sets, which is through adapting a marking procedure from [17].
We use z r 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 ∈ Σ with x ∈ ext(r) then M (i, α) = {x r }; (ii) if head(r) = α for some r ∈ Σ with x ∈ fr(r) then M (i, α) is the intersection of all M (j, β) s.t. β ∈ body(r) and x occurs at position j in atom β; (iii) if α ∈ body(r) then M (i, α) is the union of M (i, head(r )) for all r ∈ Σ s.t. r can be unfolded by r with α unified with head(r ). Definition 3. A set of rules Σ is separable if for each rule r ∈ Σ, there do not exists a variable x shared by two body atoms such that the intersection of all M (i, α), for each atom α ∈ 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.
Proposition 2. Each rule set that is shy is also separable.
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
Intuitively, the proof is based on the fact that the unfolding of rules in Σ ∪ {q} only involves a single atom in the body each time, and thus the result of unfolding can be reconstructed from the result of rewriting even if the bodies are separated.
The class of sticky rule sets is introduced in [6], which are shown to be first-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 = {A(x, y) ← A(x, z) ∧ A(z, y)} is separable but not sticky, and Σ 1 ∪ {C(x, y, z) ← A(x, y) ∧ A(y, z)} (where Σ 1 is from Example 1) is sticky but not separable. Proposition 4. For a OMQ (Σ, q) such that Σ is sticky, rewrite (2),( 6), (7) (Σ ∪ {q}) is a datalog rewriting of (Σ, q). Indeed, the proposition holds for all finite unification sets [2], as the backward chaining always terminates on such rule sets and hence rewrite (2),( 6), (7) (Σ ∪ {q}) (in particular, rules of the form ( 7)) is finite. Moreover, if we disallow the reuse of fresh predicates, the resulting datalog rewriting is a non-recursive one.
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).
Proposition 5. For a OMQ (Σ, q) such that Σ is acyclic, rewrite| (7) (Σ ∪ {q}) is a datalog rewriting of (Σ, q). It can be seen from that the acyclicity conditions guarantee the Skolem chase terminates on critical instances [11], which avoids the generation of infinitely many Skolemised terms. In our case, it avoids the generation of infinitely many existential variables in the heads of rules (5), whereas the sizes of their bodies are always bounded. Hence, the number of such rules is finite, and rewrite| (7) (Σ ∪ {q}) is finite.
In this section, we introduce a practical algorithm for computing datalog rewritings of the form rewrite| (5) (Σ), which can be configured to compute rewrite| (5), (7) (Σ) and rewrite (2),( 6),(7) (Σ). It can also be easily adapted to compute rewrite| (7) (Σ). Inspired by [12], we compute a decomposed representation of the heads and bodies of the resulting rules from unfolding, such that (i) the representation is compact due to structure sharing, (ii) the datalog rewriting rewrite| (5) (Σ) can be conveniently extracted from such a representation, and (iii) the complete rules from unfolding (e.g., rule (7)) can be reconstructed via backtracking.
For a set of rules Σ whose maximum number of body atoms is m, we define 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 unifiers. Each node n = (R, I) is associated with two fresh predicates P n and R n , and we reuse fresh predicates as in Section 3 through a label function λ(•). For each node n = (R, I), let u n = fr(R ← I) and v n = var(R). Intuitively, an edge from node n = (R, I) to node n = (R , I ) labelled with µ = (B, H, τ ) represents a set of rules (i.e., rules (2)-( 4) and ( 6)) obtained during rewriting as follows:
where z consists of all the variables in the head but not in the body. For a rewriting graph G, dlg(G) is the set of datalog rules obtained as above from the edges of G. Now, we present the algorithm for computing rewriting graphs. Note that similar as the rule elimination in Definition 2, for a new node n = (R, I), if there is an existing node n = (R , I ) and a homomorphism σ from I to I such that a safe extension σ of σ exists with R ⊆ R σ , then n should be eliminated. In Algorithm 1, actions with a * are subject to the reuse of fresh predicates and node elimination. Also, τ and τ denote safe extensions of τ as in Equation (1).
In Algorithm 1, we first 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 unifier cannot contain a fresh predicate (by Definition 2 and guaranteed in line 7), only original rules or rules of the forms (2), (3), ( 6) and (7) need to be rewritten, and only original rules or rules of the form (4) with head α can rewrite such rules. Lines 9-21 are the rewriting process, with lines 10-12 corresponding to the rewriting of an original rule or a rule (2), and lines 13-15 corresponding to that of rules ( 3) and (6). The rewriting produces 2 new node (subject to predicate reuse and node elimination): node n represents the generated rules (2)-( 4) and ( 6), and is added to N . It is added to the queue for the further rewriting of rule (2); node n † is not added to N but is added to the queue for the further rewriting of rules ( 3) and (6). Note that temporary rules of the form (7) need to be generated to ensure the correctness. The generation of their representations is achieved through backtracking (lines 22-27). It is not hard to verify that rule (7) corresponds to ∃z.R n (v n ) ← S.
We establish the correctness of Algorithm 1 as follows.
We have implemented a prototype system Drewer (Datalog REWriting for Existential Rules), where the piece unification implementation is adapted from the first-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.
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, Iqaros [23] is a first-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. Both Rapid and Iqaros output minimal rewritings of the same sizes recorded under "UCQ". To achieve efficiency 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 benefit of datalog rewriting w.r.t. sizes compared to UCQ rewritings becomes obvious when large UCQ rewritings are generated (≥50), with two exceptions q 2 and q 4 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 efficiency. 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). 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 significantly 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 first-order rewritable OWL 2 DL ontologies, whereas Drewer is for more general existential rules.
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 first 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.