Enhancing Datalog Reasoning with Hypertree Decompositions

1 Introduction

Datalog [Abiteboul et al., 1995] is a widely used rule language that can express recursive dependencies, such as graph reachability and transitive closure. Reasoning in Datalog has found applications in different areas and supports a wide range of tasks including consistency checking [Luteberget et al., 2016] and data analysis [Alvaro et al., 2010]. Datalog is also able to capture OWL 2 RL ontologies [Motik et al., 2009] extended with SWRL rules [Horrocks et al., 2004] and can thus support query answering over ontologyenriched data; it has been implemented in a growing number of open-source and commercial systems, such as VLog [Carral et al., 2019], LogicBlox [Aref et al., 2015], Vadalog [Bellomarini et al., 2018], RDFox [Nenov et al., 2015], Oracle's database [Wu et al., 2008], and GraphDB. 1

1 https://graphdb.ontotext.com/

In a typical application, Datalog is used to declaratively represent domain knowledge as 'if-then' rules. Given a set of explicit facts and a set of rules, Datalog systems are required to answer queries over all the facts entailed by the given rules and facts. To facilitate query answering, the entailed facts are often precomputed in a preprocessing step; we use materialisation to refer to both this process and the resulting set of facts. Queries can then be evaluated directly over the materialisation without considering the rules. The materialisation can be efficiently computed using the semina¨ıve algorithm [Abiteboul et al., 1995], which ensures that each inference is performed only once. Incremental maintenance algorithms can then be used to avoid the cost of recomputing the materialisation when explicitly given facts are added/deleted; these include general algorithms such as the counting algorithm [Gupta et al., 1993], the Delete/Rederive (DRed) algorithm [Staudt and Jarke, 1995], and the Backward/Forward (B/F) algorithm [Motik et al., 2015], as well as special purpose algorithms designed for rules with particular shapes [Subercaze et al., 2016]. It has recently been shown that general and special purpose algorithms can be combined in a modular framework that supports both materialisation and incremental maintenance [Hu et al., 2022].

Existing (incremental) materialisation algorithms implicitly assume that the evaluation of rule bodies is based on traditional join plans which can be suboptimal in many cases [Ngo et al., 2014; Gottlob et al., 2016], especially in the case of cyclic rules. This can lead to a blow-up in the number of intermediate results and a corresponding degradation in performance (as we demonstrate in Section 5). This phenomenon can be observed in real-life applications, for example where rules are used to model complex systems, which may include the evaluation of numerical expressions. 2 The resulting rules are often cyclic and have large numbers of body atoms.

Similar problems also exist in query answering. One promising solution is based on hypertree decomposition [Gottlob et al., 2016]. Hypertree decomposition is able to decompose cyclic queries, and Yannakakis's algorithm [Yannakakis, 1981] can then be used to achieve efficient evaluation over the decomposition [Gottlob et al., 2016]. This method has been well-investigated with its effectiveness shown in many empirical experiments for query evaluation [Tu and R´e, 2015; Aberger et al., 2016].

2 https://2021-eu.semantics.cc/graph-based-reasoning-scalingenergy-audits-many-customers

It is unclear, however, whether the hypertree decomposition approach can benefit rule evaluation in Datalog reasoning. Unlike query answering, which requires only a single evaluation via decomposition, rules in a Datalog program are applied multiple times until no new data can be derived. In this setting, it is important to avoid repetitive derivations, but this is not easy to achieve when hypertree decomposition is used for rule evaluation. Moreover, incremental materialisation usually depends on efficiently tracking fact derivations, and it is unclear how to achieve this when such derivations depend on hypertree decomposition. Finally, hypertree decomposition introduces some additional overhead, and this may degrade performance on simple rules.

In this paper, we introduce a Datalog reasoning algorithm that exploits hypertree decomposition to provide efficient (incremental) reasoning of recursive programs. Moreover, we show how this algorithm can be combined with the semina¨ıve algorithm in a modular framework so as to avoid unnecessary additional overhead on simple rules. Our empirical evaluation shows that this combined approach significantly outperforms the standard approach, sometimes by orders of magnitude, and it is never significantly slower. Our test system and data are available online. 3 Proofs and additional evaluation results are included in a technical report [Zhang et al., 2023].

2 Preliminaries

2.1 Datalog

A term is a variable or a constant. An atom is an expression of the form P(t1, ..., tk) where P is a predicate with arity k, k ≥ 0, and each ti, 1 ≤ i ≤ k, is a term. A fact is a variablefree atom, and a dataset is a finite set of facts. A rule is an expression of the following form:

where n ≥ 0 and Bi, 0 ≤ i ≤ n, and H are atoms. For r a rule, h(r) = H is its head, and b(r) = {B0, . . . ,Bn} is the set of body atoms. For S an atom or a set of atoms, var(S) is the set of variables appearing in S. For a rule r to be safe, each variable occurring in its head must also occur in at least one of its body atoms, i.e., var(h(r)) ⊆ var(b(r)). A program is a finite set of safe rules.

A substitution σ is a mapping of finitely many variables to constants. For α a term, an atom, a rule, or a set of them, ασ is the result of replacing each occurrence of a variable x in α with σ(x) if σ(x) is defined in σ. For a rule r and a substitution σ, if σ maps all the variables occurring in r to constants, then rσ is an instance of r.

For a rule r and a dataset I, r[I] is the set of facts obtained by applying r to I:

Moreover, for a program Π and a dataset I, Π[I] is the set obtained by applying every rule r in Π to I:

3 https://xinyuezhang.xyz/HDReasoning/

Algorithm 1 MAT(Π, E)

• 1: I ← ∅
• 2: ∆←E
• 3: while ∆ ̸= ∅ do
• 4: I := I ∪∆
• 5: ∆ := Π[I ···∆] \ I

For E a dataset, let I0 = E, and we define the materialisation I∞ of Π w.r.t. E as:

2.2 Semina¨ıve Algorithm

We will briefly introduce the semina¨ıve algorithm to facilitate our discussion in later sections. As we shall see, our algorithms exploit similar techniques to avoid repetition in reasoning.

The semina¨ıve algorithm [Abiteboul et al., 1995] realises non-repetitive reasoning by identifying newly derived facts in each round of rule application. Given a program Π and a set of facts E, the algorithm computes the materialisation I of Π w.r.t. E. As shown in Algorithm 1, ∆ is initialised as E. In each round of rule applications, the algorithm will first update I by adding to it the newly derived facts from the previous round and then computing a fresh set of derived facts using the operator Π defined as below:

in which σ in expression (5) is a substitution mapping variables in r to constants, and ∆ ⊆ I. The definition of Π[I ··· ∆] ensures that the algorithm will only consider rule instances that have not been considered before. In practice, r[I ··· ∆] can be efficiently implemented by evaluating the rule body n + 1 times [Motik et al., 2019]. Specifically, for the ith evaluation, 0 ≤ i ≤ n, the body is evaluated by:

in which the superscript identifies the set of facts where each atom is matched.

2.3 DRed Algorithm

The original DRed algorithm is presented by Gupta et al. [1993], but it does not support non-repetitive reasoning. In this paper, we consider a non-repetitive and generalised version of the DRed algorithm presented by Hu et al. [2022]. This version of the DRed algorithm allows modular reasoning, i.e., reasoning over different parts of the program can be implemented using customised algorithms, which is more suitable for our discussions below.

The DRed algorithm is shown in Algorithm 2 where input arguments Π and E represent the program and the original set of explicitly given facts, I is the materialisation of Π w.r.t. E, and E+ and E- are the sets of facts that are to be added to and deleted fromE, respectively. As shown in lines 2-4, the main idea behind DRed is to first overdelete all possible derivations that depend on E-; and then the algorithm tries to rederive facts that have alternative proofs using the remaining facts; lastly, to add to the materialisation, the algorithm computes the consequences of E+ as well as the rederived facts.

Specifically, overdeletion involves recursively finding all the consequences derived by Π and E-, directly or indirectly, as shown in lines 7-14. The function Delr called in line 13 is intended to compute the facts that are directly affected by the deletion of ∆-. More precisely, Delr (I,∆-) should compute r[I ···∆-] ∩ (I\∆-). Note that in line 13 the first argument of the call is I\D, so it should compute r[I ′ ···∆-] ∩ (I ′ \∆-) with I ′ = I\D; the same clarification applies to Redr and Addr , so we will not reiterate.

The rederivation step recovers the facts that are overdeleted but are one-step provable from the remaining facts. Formally, function Redr (I,∆) should compute r[I] ∩∆. Finally, during addition, the added set NA is initialised in line 21, and then from line 22 to 28 the rules are iteratively applied, similarly as in the semina¨ıve algorithm. In this case, function Addr (I,∆+) is required to compute r[I ···∆+]\I.

The correctness of Algorithm 2 is guaranteed by Theorem 1, which straightforwardly follows from the correctness of the modular update algorithm by Hu et al. [2022].

Theorem 1. Algorithm 2 correctly updates the materialisation I∞ of Π w.r.t. E to I ′∞ of Π w.r.t. E′ where E′ = (E\E-) ∪E+, provided that Delr (I,∆-), Redr (I,∆), and Addr (I,∆+) compute r[I ···∆-] ∩ (I\∆-), r[I] ∩∆, and r[I ···∆+]\I, respectively.

Please note that the DRed algorithm could be used for the initial materialisation as well. To achieve this, we can set E, I and E- as empty sets, and pass the set of explicitly given facts as E+ to the algorithm.

2.4 Hypertree Decomposition

Following the definition of hypertree decomposition for conjunctive queries [Gottlob et al., 2002], we define it for Datalog rules in a similar way.

For a Datalog rule r, a hypertree decomposition is a hypertree HD = ⟨T, χ, λ⟩ in which T = ⟨N, E⟩ is a rooted tree, and χ associates each vertex p ∈ N with a set of variables in r whereas λ associates p with a set of atoms in b(r). This hypertree satisfies all the following conditions:

1. for each body atom Bi ∈ b(r), there exists p ∈ N such that var(Bi) ⊆ χ(p);
2. for each variable v ∈ var(r), the set {p ∈ N | v ∈ χ(p)} induces a connected subtree of T .
3. for each vertex p ∈ N, χ(p) ⊆ var(λ(p)).
4. for each vertex p ∈ N, var(λ(p)) ∩ χ(Tp) ⊆ χ(p) in which Tp is the subtree of T rooted at p.

The width of the hypertree decomposition is defined as maxp∈N|λ(p)|. The hypertree-width hw(r) of r is the minimum width over all possible hypertree decompositions of r. In this paper, we refer to r as a complex rule, or interchangeably, a cyclic rule, if and only if its hypertree width hw(r) is greater than 1.

Algorithm 2 DRed(Π, E, I , E+, E-)

1: D := A := ∅, E- := (E- ∩ E)\E+, E+ := E+\E 2: OVERDELETE 3: REDERIVE 4: ADD 5: E := (E\E-) ∪E+, I := (I\D) ∪A 6: procedure OVERDELETE 7: ND := E8: loop 9: ∆- := ND\D 10: if ∆- = ∅ then break 11: ND := ∅ 12: for r ∈ Π do 13: ND := ND ∪ Delr (I\D, ∆-) 14: D := D ∪ ∆- 15: procedure REDERIVE 16: ∆ := ∅ 17: for r ∈ Π do 18: ∆ := ∆ ∪ Redr (I\D, D) 19: ∆ :=∆∪ ((E\E-) ∩D) 20: procedure ADD 21: NA := (∆∪E+)\(I\D) 22: loop 23: ∆+ := NA\((I\D) ∪ A) 24: if ∆+ = ∅ then break 25: A := A ∪ ∆+ 26: NA := ∅ 27: for r ∈ Π do 28: NA := NA ∪ Addr ((I\D) ∪ A, ∆+)

Next, we will introduce how query evaluation works using a decomposition as join plan. Query evaluation via hypertree decomposition is a well-investigated problem in the database literature [Gottlob et al., 2016; Flum et al., 2002], and such a process typically consists of in-node evaluation and cross-node evaluation. During in-node evaluation, each node p in the decomposition joins the body atoms that are assigned to it (i.e., λ(p)) and stores the join results for later use. Then, cross-node evaluation applies the Yannakakis algorithm to the above join results using T as the join tree. The standard Yannakakis algorithm in turn has two steps. The full reducer stage applies a sequence of bottom-up left semijoins through the tree, followed by a sequence of top-down left semi-joins using the same fixed root of the tree [Bernstein and Chiu, 1981]. This removes dangling data that will not be needed in the second stage and decreases the join result size for each node. The cross-node join stage joins the nodes bottom-up, and it projects to the output variables, i.e., var(h(r)), to obtain the final answers.

Overall, the (combined) complexity of query evaluation via a decomposition tree is known to be O(v · (mk +s) · log(m+ s)) [Gottlob et al., 2016] where v is the number of variables in the query, m is the cardinality of the largest relation in data, k is the hypertree width of r, and s is the output size.

3 Motivation

In this section, we use an example to explain how hypertree decompositions could benefit rule evaluation and provide some intuitions as to how they can be exploited in the evaluation of recursive Datalog rules. To this end, consider the following rule r, in which PC, CW and CA represent PossibleCollaborator, Coworker, and Coauthor, respectively:

Moreover, consider the dataset E as specified below, where n and k are constants. Refer to Figure 1 for a (partial) illustration of the dataset and the joins.

Each relation above contains O(n · k) facts, and the materialisation will additionally derive n · k +k facts, i.e., {PC(ai, dj) | 0 ≤ i ≤ n, 1 ≤ j ≤ k}.

Now consider the first round of rule evaluation, and assume that the rule body of r, which corresponds to a conjunctive query, is evaluated left-to-right. Then, matching the first three atoms involves considering O(n · k2 ) different substitutions for variables x, y, z1, and z2; only O(n·k) of them will match the last atom and eventually lead to successful derivations. In fact, one can verify that no matter how we reorder the body atoms of r, it will result in similar behaviour.

Using hypertree decompositions could help process the query more efficiently. Consider decomposition T of the above query consisting of two nodes p1 and p2, where p1 is the parent node of p2. Furthermore, function χ is defined as: χ(p1) = {x, z1, y}, χ(p2) = {x, z2, y}, and function λ is defined as: λ(p1) = {CW(x, z1), PC(z1, y)}, λ(p2) = {CA(x, z2), PC(z2, y)}. Recall the steps of decompositionbased query evaluation we introduced in Section 2. During the in-node evaluation stage, each node in the decomposition will consider O(n · k) substitutions; the full reducer will consider O(n · k) substitutions and find out that nothing needs to be reduced; lastly, the cross-node evaluation joining p1 and p2 also considers O(n · k) substitutions. Compared with the left-to-right evaluation of the query, the overall cost of this approach is O(n · k), as opposed to O(n · k2 ). For every ai (0 ≤ i < n), the first round of rule application will introduce additional PC relations between ai and d1 to dk (n·k in total).

Notice that rule r is recursive, so the facts produced by the first round of rule evaluation could potentially lead to further derivations of the same rule. This is indeed the case in our example: the first round derives all PC(ai, dj) facts with 0 ≤ i < n and 1 ≤ j ≤ k; combined with {CW(an, a2), CA(an, a3)} this will additionally derive PC(an, dj) with 1 ≤ j ≤ k. If we used the hypertree decomposition-based technique discussed above, then a na¨ıve implementation would just add all the facts derived in the first round to the corresponding nodes and run the decompositionbased query evaluation again. However, this is unlikely to be very efficient as it would have to repeat all the work performed in the first round of rule evaluation. Ideally, we would like to make the decomposition-based query evaluation algorithm 'incremental', in the sense that the algorithmminimises the amount of repeated work between different rounds of rule evaluation. As we shall see in Section 4, this requires nontrivial adaptation of in-node evaluation, as well as the two stages of the Yannakakis algorithm. Handling incremental deletion presents another challenge, which we address following the well-known DRed algorithm.

4 Algorithms

We now introduce our reasoning algorithms based on hypertree decomposition. We use DRed as the backbone of our algorithm, but instead of standard reasoning algorithms with plan-based rule evaluation, we will use our hypertree decomposition-based functions Delr , Addr , and Redr as discussed below. For each rule r in Π, we assume its hypertree decomposition ⟨T r , χr , λr ⟩ with T r = ⟨N r , Er ⟩ has already been computed, and tr is the root of the decomposition tree T r . Our reasoning algorithms are independent of decomposition methods.

4.1 Notation

First, analogously to expression (5), for each node p ∈ N r we define operator Πp[I,∆], in which I and ∆ are sets of facts with ∆ ⊆ I .

Intuitively, this operator is intended to compute for a node p all the instantiations influenced by the incremental update ∆. Additionally, for each node p ∈ N r , we will make use of the following sets in the presentation of our algorithms. These sets are initialised as empty the first time DRed is executed.

1. instIp contains the join result of in-node evaluation for p under the current materialisation I, and it is represented as tuples for variables χr (p). Since cross-node evaluation builds upon such join results, to facilitate incremental evaluation and to avoid computing instIp every time from scratch, instIp has to be correctly maintained between different executions of DRed.
2. instI ···∆+ p represents the set of instantiations that should be added to instIp given a set of newly added facts ∆+. This set can be obtained using the operator Πp.

Algorithm 3 Addr [I , ∆+]

• 1: /* in-node evaluation */
• 2: for p ∈ N r do:
• 3: instI ···∆+ p := Πp[I,∆+] \ instIp
• 4: /* cross-node evaluation */
• 5: ∆A := CrossNodeEvaluationr (L+)
• 6: /* updating instantiations for each node */
• 7: for p ∈ N r do
• 8: instIp := instIp ∪ instI ···∆+ p
• 9: instI ···∆+ p := ∅
• 10: return ∆A\I
• instI ···∆- p represents the set of instantiations that no longer hold after removing ∆- from I; these instantiations should then be deleted from instIp . Similarly as above, this set can be computed using Πp.
• instac p represents the currently active instantiations that will participate in the cross-node evaluation.
• instre p represents the instantiations that will need to be checked during the rederivation phase.

4.2 Addition

As discussed in Section 3, the decomposition-based query evaluation should be made incremental. To this end, Algorithm 3, which is responsible for addition, needs to distinguish between old instantiations and the new ones added due to changes in the explicitly given data. This is achieved by executing the in-node evaluation for each node p ∈ N r in line 3 using the Πp operator. Then, the cross-node evaluation (line 5) is performed in a way similar to the evaluation of r[I ···∆] outlined in Section 2, treating each node in T r as a body atom. Specifically, as shown in algorithm 4, we will evaluate the tree |N r | times. Assume that there is a fixed order among all the tree nodes for r, and let pi, 1 ≤ i ≤ |N r |, denote the ith node in this ordering. Then, in the ith iteration of the loop of lines 2-8, node pi is chosen in line 2, and the label of each node will be determined by the labelling function L+ as specified below. In particular, node pi will be labelled ∆+; nodes preceding and succeeding pi will be labelled I and I ∪∆+, respectively.

Based on the labels assigned in line 4, we will set pac j , the active instantiations that will participate in the subsequent evaluation, as follows. Note that the last two cases will be used later for deletion.

After fixing the active instantiations, algorithm 4 proceeds with an adapted version of the Yannakakis algorithm: lines 67 complete the full reducer stage whereas line 8 performs the cross-node join. By performing left semi-joins between nodes, the full reducer stage aims at deactivating instantiations that do not join and keep only the relevant ones. The standard full reducer does not consider incremental updates so adaptations are required. In particular, our incremental version of the full reducer traverses the tree three times. The first traversal in line 6 consists of a sequence of top-down left semi-joins with pi (the node labelled with ∆+) as the root. As ∆+ is typically smaller than the materialisation I, starting from pi could potentially reduce the numbers of active instantiations for the other nodes to a large extent. The second and the third traversal (line 7) involves applying the standard bottom-up and top-down left semi-join sequences, respectively, using the root of the decomposition tree tr as the root for the evaluation. Then, the cross-node join in line 8 evaluates the decomposition tree T r bottom-up: for each node p ∈ N r , it joins active instantiations in p with those in its children, and then projects the result to variables χr (p) ∪ var(h(r)). The join result obtained at the root tr is projected to the output variables var(h(r)) to compute the derived facts, which are then returned to the Addr function.

Lastly, lines 7-9 of algorithm 3 update the instantiations instIp for each node p and empty instI ···∆+ p for later use.

By applying the principles of semina¨ıve evaluation to both the in-node evaluation and the cross-node evaluation, Addr avoids repeatedly reasoning over the same facts or instantiations. Lemma 1 states that the algorithm is correct.

To further elucidate the algorithmic process, we will build upon the examples presented in Section 3 to demonstrate our algorithm's recursive application in a step-by-step manner.

Example 1. Following the initial round of rule application as detailed in Section 3, the instantiations in instI ···∆+ p1 and instI ···∆+ p2 are derived in line 3 of algorithm 3 and then merged into instIp1 and instIp2 in line 8, respectively, before being cleared in line 9. Therefore, we have instIp1 = {(ai, bi·k+j, dj) | 0 ≤ i < n, 1 ≤ j ≤ k}, and instIp2 = {(ai, ci·k+j, dj) | 0 ≤ i < n, 1 ≤ j ≤ k}. Additionally, the cross-node evaluation in line 5 derives facts

Algorithm 4 CrossNodeEvaluationr (L)

• 1: ∆ := ∅ 2: for pi ∈ N r do /* the ∆ node */ 3: for pj ∈ N r do 4: label pj with the output of L(pi, pj) 5: set instac pj according to the label 6: TopDownLSJ(pi) 7: BottomUpLSJ(tr ); TopDownLSJ(tr ) 8: ∆ :=∆∪ πvar(h(r))(CrossNodeJoin(tr )) 9: return ∆

{PC(ai, dj) | 0 ≤ i < n, 1 ≤ j ≤ k}, which are all returned in line 10 of the algorithm.

In the second round of application, the facts derived in the first round, i.e., PC(ai, dj) with 0 ≤ i < n and 1 ≤ j ≤ k, are passed to the Addr function as ∆+. Then, line 3 identifies for p1 the new instantiations involving facts in ∆+; specifically, {(an, a2, dj) | 1 ≤ j ≤ k} are assigned to instI ···∆+ p1 . Similarly, we have instI ···∆+ p2 = {(an, a3, dj) | 1 ≤ j ≤ k}. For an illustration of the related joins, please refer to figure 2 (1). Then, during the cross-node evaluation, lines 2-5 ensure that when node p1 is labeled with ∆+, node p2 is labeled with I, and so instI ···∆+ p1 is joined with instIp2 , deriving no new fact. In contrast, when node p2 is labeled with ∆+, node p1 is labeled with I ∪ ∆+, and so instI ···∆+ p2 is joined with instIp1 ∪ instI ···∆+ p1 , deriving PC(an, dj) with 1 ≤ j ≤ k. As one can readily see, the second round of rule application does not repeat work already carried out in the first round.

The above example demonstrates the process of initial materialisation. Now consider adding {CW(an, a4), CA(an, a5)} to the explicitly given data, i.e., by setting E+ to the above set of facts in the DRed algorithm. In this case, ∆+ in Addr will consist of CW(an, a4) and CA(an, a5). Then, in line 3 of algorithm 3, we clearly have Πp1 [I,∆+] = {(an, a4, dj) | 1 ≤ j ≤ k}, as illustrated by figure 2 (2).

However, instI ···∆+ p1 will be empty since the identified instantiations already exist in instIp1 ; the same applies to p2. As a result, no new fact is derived. This shows the benefit of keeping instantiations for the nodes of the decomposition between different runs of the DRed algorithm.

4.3 Deletion

The Delr algorithm shown in algorithm 5 is analogous to Addr , and it identifies consequences of r that are affected by the deletion of ∆-. The algorithm first computes the overdeletion instI ···∆- p using the operator Πp in lines 2-3. In addition, the instantiations that have been overdeleted are also added to instre p so that they can be checked and potentially recovered during rederivation.

The cross-node evaluation in line 6 is similar to that of

Algorithm 5 Delr [I , ∆-]

• 1: /* in-node: overdelete */ 2: for p ∈ N r do: 3: instI ···∆- p := Πp[I, ∆-] ∩ instIp 4: instre p := instre p ∪ instI ···∆- p 5: /* cross-node: overdelete */ 6: ∆D := CrossNodeEvaluationr (L-) 7: /* updating instantiations for each node */ 8: for p ∈ N r do 9: instIp := instIp \instI ···∆- p 10: instI ···∆- p := ∅ 11: return ∆D ∩ (I\∆-)

Addr , except that a different labelling function L- is used:

Note that the initialisation of instac pj follows equation (9). Finally, for each node p, the set of instantiations instIp is updated in line 9 to reflect the change, and instI ···∆- p is emptied in line 10 for later use. Similarly as in Addr , our Delr function exploits the idea of semina¨ıve evaluation to avoid repeated reasoning. Lemma 2 states that the algorithm is correct.

The following example illustrates overdeletion using our customised algorithms.

Example 2. Assume that E- is set as {CA(an, a3)} in algorithm 2. During the overdeletion phase, E- is passed to Delr as ∆-. After the execution of line 3 in algorithm 5, we have instI ···∆- p2 = {(an, a3, dj) | 1 ≤ j ≤ k} and instI ···∆- p1 = ∅, as can be seen from figure 2 (3). Then, the cross-node evaluation will derive PC(an, dj), 1 ≤ j ≤ k. These facts are temporarily overdeleted, and the rederivation stage will check whether they have alternative derivations from the remaining facts.

4.4 Rederivation

The rederivation step described in algorithm 6 aims at recovering facts that are overdeleted but are one-step rederivable from the remaining facts using rule r. In the presentation of the algorithm we take advantage of an oracle function O which serves the purpose of encapsulation. The oracle function can be implemented arbitrarily, as long as it satisfies the following requirement: given a fact/tuple f, the oracle function returns true if f has a one-step derivation from the remaining facts/tuples, and it returns false otherwise.

In practice, there are several ways to implement such an oracle function. A straightforward way is through query evaluation. For example, to check whether a tuple f ∈ instre p is one-step rederivable, one can construct a query using atoms in λ(p), instantiate the query with the corresponding constants in f, and then evaluate the partially instantiated query over

Algorithm 6 Redr [I , ∆]

• 1: for p ∈ N r do

2:

instI ···∆+

p

:= {f ∈ instre

p | O[f] = true}

• 3: ∆R := CrossNodeEvaluationr (L+) ∩∆
• 4: for p ∈ N r do
• 5: instIp := instIp ∪ instI ···∆+ p

6:

instre

p

p := instI ···∆+

:= ∅

• 7: return ∆R ∪ {f ∈ ∆ | O[f] = true}

the remaining facts. A more advanced approach is through tracking derivation counts [Hu et al., 2018]: each tuple is associated with a number that indicates how many times it is derived; during reasoning, this count is incremented if a new derivation is identified, and it is decremented if a derivation no longer holds. Then, the oracle function can be realised with a simple check on the derivation count of the relevant tuple. We have adopted the second approach in this paper.

Algorithm 6 proceeds as follows. First, lines 1-2 perform rederivation for in-node evaluation using the oracle. Recall that rule evaluation is decomposed into in-node evaluation and cross-node evaluation stages, so changes in the join results stored in the tree nodes have to be propagated through the decomposition tree, and this is achieved through line 3. Then, lines 4-6 update the join results and clear temporal variables. Finally, line 7 performs rederivation for cross-node evaluation and returns all the rederived facts. Lemma 3 states that the algorithm is correct. Together with Theorem 1 and Lemmas 1 and 2, this ensures the correctness of our approach.

Below we continue with our running example and focus on the rederivation stage.

Example 3. After the overdeletion in Example 2, we have instre p2 = {(an, a3, dj) | 1 ≤ j ≤ k}. These instantiations will not be recovered in line 2 of algorithm 6 since the oracle O will find out that they have no alternative derivation from the remaining data. In contrast, the overdeleted facts PC(an, dj) with 1 ≤ j ≤ k are recovered in line 7. This is so since each PC(an, dj) can be rederived using instantiation (an, a2, dj) from instIp1 and instantiation (an, a5, dj) from instIp2 . These rederived triples are passed on to Addr as ∆+, but no new fact will be derived. Overall, the removal of {CA(an, a3)} do not affect the materialisation.

5 Implementation and Evaluation

To evaluate our algorithms we have developed a proof-ofconcept implementation and conducted several experiments.

5.1 Implementation

The algorithms presented in Section 4 are independent of the choice of decompositions; however, different hypertree decompositions will lead to very different performance even if they share the same hypertree width. This is because the decomposition method only considers structural information of the queries and ignores quantitative information of the data. To address this problem, Scarcello et al. [2007] introduced an algorithm that chooses the optimal decomposition w.r.t. a given cost model. We adopt this algorithm with a cost model consisting of two parts: (1) an estimate of the cost of intranode evaluation, i.e., the joins among λ(p); and (2) an estimate of the cost of inter-node evaluation, i.e., the joins between nodes. In our implementation, for (1), we use the standard textbook cardinality estimator described in Chapter 16.4 of the book [Garcia-Molina, 2008] to estimate the cardinality of ▷◁ Bi∈λ(p) Bi for a node p; for (2), we use 2 ∗ (| ˆ pi| + | ˆ pj|) to estimate the cost of performing semi-joins between nodes pi and pj , where | ˆ pi| and | ˆ pj| represent the estimated node size.

Moreover, the extra step of full reducer we introduced in algorithm 4 (line 6) is more suitable for small updates, in which the node with the smallest size helps reduce other large nodes. If the size of all the nodes is comparable, then this step would be unnecessary. Therefore, in practice, we only perform this optimisation if the number of active instantiations in the ∆ node (i.e., pi) is more than three times smaller than the maximum number of active instantiations in each node.

5.2 Benchmarks

We tested our system using the well-known LUBM and YAGO benchmarks [Guo et al., 2005; Suchanek et al., 2008], and a synthetic Exp (expressions) benchmark which we created to capture complex rule patterns that commonly occur in practice. LUBM models a university domain, and it includes a data generator that can create datasets of varying sizes; we used the LUBM-500 dataset which includes data for 500 universities. Since the ontology of LUBM is not in OWL 2 RL, we use the LUBM L variant created by Zhou et al. [2013]. The LUBM L rules are very simple, so we added 16 rules that capture more complex but semantically reasonable relations in the domain; some of these rules are rewritten from the cyclic queries used by Stefanoni et al. [2018]; we call the resulting rule set LUBM L+C. One example rule is SA(?p1, ?p2) ← HA(?o.?p1), AD(?p1, ?ad), HA(?o, ?p2), AD(?p2, ?ad), in which HA and AD represent predicates hasAlumnus and hasAdvisor respectively, while SA in the head represents a new predicate haveSameAdvisor that links pairs of students ?p1 and ?p2 (not necessarily distinct) who are from the same university ?o and share the same advisor ?ad.

YAGO is a real-world RDF dataset with general knowledge about movies, people, organisations, cities, and countries. We rewrote 23 cyclic queries with different topologies (i.e., cycle, clique, petal, flower) used by Park et al. [2020] into 19 non-recursive rules and 4 recursive rules. These rules are helpful to evaluate the performance of our algorithm on topologies that are frequently observed in real-world graph queries [Bonifati et al., 2017].

As mentioned in Section 1, realistic applications often involve complex rules. One example is the use of rules to evaluate numerical expressions, and our Exp benchmark has been created to simulate such cases. Specifically, Exp applies Datalog rules to evaluate expression trees of various depths. It contains three recursive rules capturing the arithmetical operations addition, subtraction and multiplication; each of these rules is cyclic and contains 9 body atoms. A generator is used to create data for a given number of expressions, sets of values and maximum depth. In our evaluation we generated 300 expressions, each with 300 values and a maximum depth of 5. Details of the three benchmarks are given in Table 1, where |E| is the number of given facts, |I| is the number of facts in the materialisation, and |Π|, |Πs|, |Πc| are the numbers of rules, simple rules, and complex rules, respectively.

5.3 Compared Approaches

We considered three different approaches. The standard approach uses the semina¨ıve algorithm for materialisation and an optimised variant of DRed for incremental maintenance. The HD approach uses our hypertree decomposition based algorithms. The combined approach applies HD algorithms to complex rules and standard algorithms to the remaining rules. To ensure fairness, all three approaches are implemented on top of the same code base obtained from the authors of the modular reasoning framework [Hu et al., 2022]. The framework allows us to partition a program into modules and apply custom algorithms to each module as required.

5.4 Test Setups

All of our experiments are conducted on a Dell PowerEdge R730 server with 512GB RAM and 2 Intel Xeon E5-2640 2.60GHz processors, running Fedora 33, kernel version 5.10.8. We evaluate the running time of materialisation (the initial materialisation with all the explicitly given facts inserted as E+ in Algorithm 2), small deletions (randomly selecting 1,000 facts from the dataset as E- in Algorithm 2), large deletions (randomly selecting 25% of the dataset as E-), and small additions (adding 1,000 facts as E+ into the dataset). Materialisation can be regarded as a large addition.

5.5 Analysis

The experimental results are shown in Table 2 in which L and L+C are short for LUBM L and LUBM L+C respectively. The computation of decompositions takes place during initial materialisation only and the time taken is included in the materialisation time reported in Table 2; it takes less than 0.05 seconds in all cases. As can be seen, the combined approach outperforms the other approaches in most cases, sometimes by a large factor, and it is slower than the standard approach only for some of the small update tasks on LUBM L and L+C where processing time is generally small. In contrast, the standard approach performs poorly when complex rules are included (i.e., L+C, YAGO, and Exp), while the HD approach performs poorly on the simple rules in LUBM L. In particular, our combined approach is 75-139x faster than the standard approach for all the tasks on Exp; on YAGO, it is 100-793x faster. Moreover, for the materialisation and large deletion tasks on LUBM L+C, the combined approach is about 53x and 77x faster than the standard approach, respectively. Furthermore, for the small deletion and addition tasks on LUBM L+C and all the tasks on LUBM L, our combined method achieves a comparable result with the standard approach. The combined approach performs similarly to the standard approach on LUBM L, as the HD module is never invoked (there are no cyclic rules), and it performs similarly to the HD approach on Exp and YAGO, as the HD module is always invoked (all rules are cyclic). Our evaluation illustrates the benefit of the hypertree decomposition-based algorithms when processing complex rules, and it shows that by combining HD algorithms with standard reasoning algorithms in a modular framework we can enjoy this benefit without degrading performance in cases where some or all of the rules are relatively simple.

Finally, the HD algorithms have to maintain auxiliary data structures for rule evaluation, which incurs some space overhead when the HD module is invoked. Specifically, our combined method consumes up to 2.3 times the memory consumed by the standard algorithm; the detailed memory consumption for each setting can be found in the technical report [Zhang et al., 2023].

6 RelatedWork

6.1 HD in Query Answering

The HD methods have been used in database systems to optimise the performance of query answering. For RDF workload, Aberger et al. [2016] evaluated empirically the use of HD combined with worst-case optimal join algorithms, showing up to 6x performance advantage on bottleneck cyclic RDF queries. Also, in the EmptyHeaded [Aberger et al., 2017] relational engine, a query compiler has been implemented to choose the order of attributes in multiway joins based on a decomposition. This line of work focuses on optimising the evaluation of a single query, while our work focuses on evaluating recursive Datalog rules. For a more comprehensive review of HD techniques for query answering, please refer to [Gottlob et al., 2016].

6.2 HD in Answer Set Programming

Jakl et al. [2009] applied HD techniques to the evaluation of propositional answer set programs. Assuming that the treewidth of a program is fixed as a constant, they devise fixed-parameter tractable algorithms for key ASP problems including consistency checking, counting the number of answer sets of a program, and enumerating such answers. In contrast to our work, their research focuses on propositional answer set programs.

For ASP in the non-ground setting, a program is usually grounded first, and then a solver deals with the ground instances. The usage of (hyper)tree decomposition has been investigated to decrease the size of generated ground rules in the grounding phase [Bichler et al., 2020; Calimeri et al., 2019]. Bichler et al. [2020] used hypertree decomposition as a guide to rewrite a larger rule into several smaller rules, thus reducing the number of considered groundings; Calimeri et al. [2019] studied several heuristics that could predict in advance whether a decomposition is beneficial. In contrast, our work focuses on the (incremental) evaluation directly over the decomposition since the decomposition solely cannot avoid the potential blowup during the evaluation of the smaller rules.

7 Perspectives

In this paper, we introduced a hypertree decomposition-based reasoning algorithm, which supports rule evaluation, incremental reasoning, and recursive reasoning. We implemented our algorithm in a modular framework such that the overhead caused by using decomposition is incurred only for complex rules, and demonstrate empirically that this approach is effective on simple, complex and mixed rule sets.

Despite the promising results, we see many opportunities for further improving the performance of the presented algorithms. Firstly, our decomposition remains unchanged once it is fixed. However, as the input data and the materialisation change over time, the initial decomposition may no longer be optimal for rule evaluation. It would be beneficial if the maintenance could be done with the underlying decomposition changing. However, this would be challenging since the data structure in each decomposition node is maintained based on the previous decomposition, and changing the decomposition would require transferring information from the old node to the new one.

Secondly, although the memory usage has been optimised to some extent, intermediate results still take up a significant amount of space. This problem could be mitigated by incrementally computing the final join result without explicitly storing the intermediate results, or by storing only "useful" intermediate results.

Finally, it would be interesting to adapt our work to Datalog extensions, such as Datalog± [Cal`ı et al., 2011] and DatalogMTL [Walega et al., 2019]. This would require introducing mechanisms to process the relevant additional features, such as the existential quantifier in Datalog± and the use of intervals in DatalogMTL.

Acknowledgements

This work was supported by the following EPSRC projects: OASIS (EP/S032347/1), UK FIRES (EP/S019111/1), and ConCur (EP/V050869/1), as well as by SIRIUS Center for Scalable Data Access, Samsung Research UK, and NSFC grant No. 62206169.