We show that evaluating positive Datalog programs in a bottom-up manner can be modelled as a "circuit" of facts and rules where both can be freely added and retracted during runtime. This is realised by writing a definitional interpreter as a higher order program that defines bottom-up evaluation in terms of Database Stream Processing Theory (DBSP) operators that have incremental semantics. Our approach is compared against Souflé, and DDLog. Up to almost 10 times faster performance is exhibited when handling incremental updates compared to DDLog, and 2 times when compared to Souflé.
We posit that a simple and potentially eficient way to tackle the materialization of dynamic programs
is to define Datalog interpretation with an expressive language that has transparent incremental
semantics, such as the recent DBSP[
The value that these two bring is in allowing one to define non-incremental recursive programs
that inherit their incremental semantics by exclusively using expressive declarative operators. We
further argue that there is significant practical value in doing so, as both languages have very eficient
interpreters[
Contributions. Our contribution is in attempting to provide a practical and unified solution to
handling incremental evaluation of programs where rules and facts change during runtime. This is
realized over three tangible outputs:
• A novel formulation of incremental interpretation as a higher-order streaming computation. We
formulate incremental evaluation as a DBSP circuit and then empirically evaluate whether the
interpreter indeed inherited the incremental semantics of the host language by comparing it
both with the DDLog[
We consider Datalog engines to be relevant to this work if they are both bottom-up and their core purpose is either incremental materialisation, or in having had been notable ancestors of those. Souflé being a well known engine is relevant because it is useful to gauge the overhead of supporting incremental updates in the evaluation section. A incremental reasoner will not provide value if it cannot compute updates faster than some other non-incremental reasoner can compute from scratch.
Reasoner
Souflé[
Kind Both Compiler Compiler Compiler Compiler Compiler Interpreter
Fact Add No No No Yes Yes Yes Yes
Fact Del No No No No Yes Yes Yes
Rule Add No No No No No No Yes
Rule Remove No No No No No No Yes
With Table 1 we situate the reasoning system described in this paper, the Dynamic Datalog Reasoner (DYRE), among other relevant reasoners.
BigDatalog is an extension of the Apache Spark[
Cog is BigDatalog’s successor project. It swaps Apache Spark for Apache Flink[
Both of these engines, while notable, do not support maintaining the materialization. Nexus is Cog’s incremental follow-up, and it fully supports eficiently adjusting the computation to new data that is being streamed, including when the program contains recursive aggregates. It uses a provenance technique inspired by the counting method to keep track of all derivation paths. This is similar to how DBSP maintains computations.
The first Datalog engine that supports both incremental addition and deletion at scale is DDlog. The
DD stands for Diferential Dataflow[
The key component of both program provenance and incremental materialization is time. While in DD the time component can be an arbitrary lattice, DBSP restricts it to either being a total or product order, for use cases that require nested timestamps such as iteration. In our experiments we found that we did not need time to be a lattice other than product order.
DDLog compiles an expressive dialect of Datalog to non-incremental recursive relational algebra
formulated with DD. In the seminal DBSP article[
Every reasoner referred to in the table compiles a static Datalog program to either some dialect of SQL or to a intermediate representation that models relational algebra. While this approach has proven itself to be successful, all of the underlying frameworks, sans DBSP and Diferential Dataflow, were not developed with eficiently supporting iterative workloads in mind, as it is typical of Datalog.
Moreover, the compilation step is a significant bottleneck that all of these reasoners sufer from. For instance, DDLog takes minutes to compile a trivial transitive closure program. This makes it unusable for scenarios that require incrementally adding or removing rules, as that is impossible altogether.
This is not the case for the system proposed in this paper, where Datalog reasoning in itself is
implemented as a circuit with both rules and facts being dynamic.
3. Revisiting datalog as a rewriting system
We model Datalog evaluation as a rewriting system in a similar vein to the expositions found in
[
Syntax. A program is a finite set of horn clauses syntactically represented as implications, with definite clauses referred to as rules, and those with no positive literal as ground atoms. Equation 1 discerns predicates , terms , rules , atoms , ground atoms , programs Π, and finite fact stores . Bold symbols represent ordered lists of symbols, that if keyed represent sets. Constants are quoted names, and variables are unquoted. The left-hand side of a rule is called head, and the right-hand body.
Evaluation. A substitution is a function that maps a single variable to a constant. A rewrite Σ is a set of substitutions such that no ∈ Σ share a variable. We write dom(Σ) as the set of variables among all ∈ Σ and Σ[] as the constant that the some variable maps to. ::= Const | Var
::= ( ) ::= (Const) ::= ←
Π ::= { } ::= {g} (1) Example 3.1 (Rewriting) Applying the rewrite Σ : { ↦→ "a", ↦→ "b", ↦→ "c"} to (, ) grounds it to ("a", "c") If there is at least one rewrite that has one substitution for each variable term in some atom , applying it to will ground it.
Definition 3.1 The rewrite set monoid is a triple ⟨Σ , ⊕ , Σ0⟩ where: • Σ is a set of rewrites Σ • The binary operation Σ ⊕ Σ = Σ for any Σ, Σ ∈ Σ , with dom(Σ) = dom(Σ) ∪ dom(Σ) and each ∈ dom(Σ) maps to Σ[] if ∈ dom(Σ) or Σ[] otherwise • The identity element is Σ0, the empty rewrite
Grounding the head of a rule is done by iteratively building at least one Σ that satisfies the constraints of the body. Let x be the list of terms of some atom with predicate . We use the syntax . to refer to the set of ground atoms in with ’s predicate.
Definition 3.2 The rewrite product Σ ⊗ = Σ ′ of a rewrite set Σ and some atom , with the number of variable terms in being , is the set of rewrites such that for each Σ ∈ Σ , up to one new rewrite Σ′ = Σ ⊕ Σ is created for each ∈ . , with potentially up to new .
Given: = (, ) . = {("a", "b"), ("b", "c"), ("c", "d")} Σ = {{ ↦→ "a"}, { ↦→ "b"}} Then: Σ ⊕ = {{ ↦→ "a", ↦→ "b"}, { ↦→ "b", ↦→ "c"}}
There are two steps to the product. The first is unification , where each ∈ . is unified against all Σ ∈ Σ applied to . is said to unify with if there is no constant term in that occupies a position in where there is some other term ′ such that ̸= ′.
The second is extension. For all ⟨Σ, , ⟩ triples where ∈ . unifies with some Σ applied to some , there is one new rewrite Σ where each variable maps to some constant in such that ∈/ Σ, ∈ , and occupies the same position as . The output of the product is Σ ⊕ Σ for each triple.
Let Σ 0 be the empty rewrite set. It contains the empty rewrite Σ0. The immediate consequence (, ) of some rule with a ground atom set is computed by applying each rewrite from the final rewrite product Σ 0 ⊗ 0 ⊗ ... ⊗ to , with being the head, and all other atoms members of the body.
The immediate consequence (Π, ) of the program Π with ∈ Π is then ⋃︀=0 ( , ). Program
evaluation is then defined as the least fixed point (LFP) of the immediate consequence of the program.
4. Datalog interpretation as a DBSP circuit
While we do not assume the reader to be familiar with DBSP as we introduce its core tenets alongside
our contributions, we expect for there to be some familiarity with incremental view maintenance[
The central element of DBSP is the Stream. Streams are maps N ↦→ with the domain representing
time, and the codomain a value from an Abelian group . The restriction imposed on makes it
unsuitable for Datalog evaluation as presented, as set union, what ensures that at some point the fixed
point is reached, does not form an Abelian group. We address this by modelling and Π as Z-sets[
Definition 4.1 Z-sets are maps with each domain element having an associated integer count . For any two Z-sets Z and Z′ of the same underlying set , the following hold: • Z′′ = Z + Z′ where ∈ dom(Z′′ ) if Z [] + Z′ [] ̸= 0 and Z′′ [] = Z [] + Z′ [] • Z′ = − Z where ∀ ∈ dom(Z ), Z′ [] = − Z [] • If ∀ ∈ dom(Z ), Z [] = 1, then Z is bijective to some set.
We name Z-sets where all values in their codomain are either 1 or -1 as ΔZ and those that are bijective to sets as , and make use of the two auxiliary functions toset : Z ↦→ , and todif : Z ↦→ ΔZ that ensure this conversion.
Functions are maps 0 × ... × ↦→ where and are Abelian groups. An operator is also a map 0 × ... × ↦→ where each and are streams. Lift-ing some function : ↦→ yields an operator ↑ : ↦→ where ∀, [] = ([]). We use ↑ to denote lifted operators.
An operator is said to be causal if its output at time only ever relies on all inputs with time ′ such
that ′ ≤ , with it being strict if ′ < . All lifted operators are causal, but not necessarily strict. All
strict operators are guaranteed[
The two primitive building blocks of circuits are lifting and delaying. The delay operator −1 : ↦→ ′ produces a stream ′ such that ′[0] is the Abelian identity element, and ′[] = [ − 1] otherwise. As per [9, Lemma 2.11], feeding the output of some causal operator : × ↦→ back to itself with −1 yields a strict operator.
Given: = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 2}, 2 ↦→ { ("c", "d") ↦→ 1}] ′ = [0 ↦→ { ("a", "b") ↦→ − 1}, 1 ↦→ { ("b", "c") ↦→ 2}, 2 ↦→ { ("c", "d") ↦→ − 1}] ′′ = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 2}] Then: ↑toset( ) = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 1}, 2 ↦→ { ("c", "d") ↦→ 1}] ↑todif (′ ) = [0 ↦→ { ("a", "b") ↦→ − 1}, 1 ↦→ { ("b", "c") ↦→ 1}, 2 ↦→ { ("c", "d") ↦→ − 1}] − 1(′′ ) = [0 ↦→ {}, 1 ↦→ { ("a", "b") ↦→ 1}, 2 ↦→ { ("b", "c") ↦→ 2}] 4.1. naïve dynamic interpretation ΔΠ Let ℐ : ↦→ ′ be the stream integration operator: ∀, ′[] = ∑︀ =− 1 [], and (↑distinct)Δ : Z ↦→ Δ′Z the stateful Z-set distinct operator: ∀, ′ [] = todif ( [] − − 1(ℐ( ))[]).
With Π as a stream of bijective program Z-sets and of ground atoms, we define the lifted immediate consequence stream operator ↑ : Π × ↦→ Z′ as ∀, Z′ [] = (Π [], []).
Figure 1 showcases the circuit of naïve dynamic Datalog interpretation. The value of ′ [] for any will be the addition of ∑︀
=0 [] to the sum of all inferred distinct ground facts by then.
The fixed point of the circuit, after either a new fact or program Z-set is received, will happen at some timestamp where the − 1 operator returns the identity of , since then no new distinct atoms can be emitted.
The value of ′ [] will be the full materialization. As the input and the final integration are bijective to sets, the materialization will too be bijective, therefore emitting sets and matching regular Datalog semantics.
Example 4.2 (Integration and non-incremental dynamic interpretation)
Δ = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 1}, 2 ↦→ { ("c", "d") ↦→ 1}]
ΔΠ [0] = {(, ) ← (, ) ↦→ 1}
ΔΠ [
(, ) ↦→ − 1}]
ℐ( )[0] = { ("a", "b") ↦→ 1}
ℐ( )[
To derive incremental evaluation it is necessary to reason about the linearity of functions. A function : ↦→ is linear if for any , ∈ , ( + ) = () + (). This extends to functions with more than one argument e.g : × ↦→ is bilinear if it is linear in each of its arguments.
While operators obtained by lifting linear functions are linear, is not bilinear hence the general formula for their incrementalization[9, Theorem 1.4] when applied to it yields: ∀, (↑ )Δ[] = (ΔΠ [], Δ [])+ (− 1(ℐ(ΔΠ ))[], Δ [])+ (ΔΠ [], − 1(ℐ(Δ ))[])
Will not satisfy the invariant ∀, ↑ (ℐ(ΔΠ ), ℐ(Δ ))[] = ℐ((↑ )Δ(ΔΠ , Δ ))[] therefore being unsound.
Example 4.3 (Non-linearity of ↑ ) Given: Δ = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 1}}] ΔΠ = [0 ↦→ {(, ) ← (, ) ↦→ 1}, 1 ↦→ {(, ) ← ↑ (ΔΠ , Δ )[0] = {("a", "b") ↦→ 1} (, ), (, ) ↦→ 1}]
We aim to achieve incremental evaluation by creating a circuit that implements the previously introduced rewriting system exclusively with linear and bilinear operators.
In order to iteratively compute rewrite products, there have to be notions of direction and end, as rewrites need to be both propagated forward to meet other atoms and ultimately signalled to be ready for grounding, to generate new facts.
Definition 4.2 The expected provenance : × ↦→ N of the j-th atom with respect to some rule is ∑︀
=0 ℋ(), where ℋ() is some function that returns an integer such that if two , atoms have the same predicate and terms, then ℋ() = ℋ() Definition 4.3 The direction Z-set Z of some rule with atoms and weight is {⟨ (, − 0), (, )⟩ ↦→ | ∀ < ∧ ≥ 1} + {⟨0, (, 0)⟩ ↦→ }. The function dir : ↦→ Z computes the direction set for some rule .
Definition 4.4 The grounding signal of some rule with atoms is ⟨ (, ), .ℎ ⟩ with being the last atom, and .ℎ the rule head. The function sig : ↦→ computes the grounding signal for some rule Definition 4.5 The grounding kit K of some program Π and its rules with respective weights is a tuple ⟨Z, Z ⟩ where: • Z is ∑︀
=0 dir( ) • Z is {sig( ) ↦→ | ∀ < } The function kit : Π ↦→ K computes the grounding kit for some program Π, with dir : Π ↦→ Z and sig : Π ↦→ returning, respectively, Z and Z of some program’s K.
Given: = (, ) ← ′ = (, ) ← Π = { ↦→ 1, ′ ↦→ 1} Then: (, ) (, ), (, ) (, (, )) = ℋ( (, )) ( ′, (, )) = ℋ( (, )) ( ′, (, )) = ℋ( (, )) + ℋ((, )) dir(Π) = {ℋ( (, )) ↦→ 2, ( ′, (, )) ↦→ 1} sig(Π) = {⟨ℋ( (, )), (, )⟩ ↦→ 1, ⟨ ( ′, (, )), (, )⟩ ↦→ 1} kit(Π) = ⟨dir(Π), sig(Π)⟩ ΔΣ Δ ↑sig ↑dir ↑ 0 ↑ 0 ↑↑+ ↑↑+
We leverage the grounding kit to guide interpretation and implement the rewrite product as three incremental joins.
gatekeep
Example 4.5 (Nested streams and stream introduction and elimination) Δ = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 1}}] Then: 0(Δ [0]) = [0 ↦→ { ("a", "b") ↦→ 1}] ↑ 0(Δ ) = [0 ↦→ [0 ↦→ { ("a", "b") ↦→ 1}], 1 ↦→ [0 ↦→ { ("b", "c") ↦→ 1}]] ∫ (Δ ) = { ("a", "b") ↦→ 1, ("b", "c") ↦→ 1} ↑ ∫ (↑ 0(Δ )) = [0 ↦→ { ("a", "b") ↦→ 1}, 1 ↦→ { ("b", "c") ↦→ 1}}] ∫ (↑ 0(Δ )) = [0 ↦→ { ("a", "b") ↦→ 1, ("b", "c") ↦→ 1}]
We refer to as the outer timestamp of some stream of streams and ′ as the inner one. can be interpreted as the time of arrival of some update, and ′ as the fixed point iteration. As the materialization nonetheless expects the immediate consequence to be a single Z-set, the ↑ ∫︀ operator is used to "flatten" it into one Z-set.
gatekeep, product and ground are the three nested stream operators that implement the rewrite
product. All of them have the following form:
op : Z × ′Z ↦→ ′′Z , ∀, ′′Z [] = ↑↑ ((↑(↑ ⋊⋉)Δ)Δ(Z , ′Zℬ ))[]
Where is the Z-set projection with scalar function , and ⋊⋉ the Z-set join with boolean join
comparison scalar function . As is linear, by definition it already is incremental. For some stream
, the time complexity of ↑↑ ( ) at some , ′ is ( ((( )[])[′]))[
The relational ⋊⋉ operator is bilinear, with the time complexity of its incremental form (↑(↑ ⋊⋉)Δ)Δ with respect to its inputs at some , ′ being (‖↑ℐ(Z )[][′]‖ × ‖ℐ (Z )[][′]‖).
Example 4.6 (A parallel with semi-naïve evaluation of static programs) With ′ denoting the ifxed point iteration number, at each new data arrival a ↑ℐ operator applied to the left side of the incremental join would emit a stream where the value at ′ is ∑︀=′0((Z )[])[]. For the right side on the other hand, it would be ∑︀=0((Z )[])[′] instead as ℐ is not lifted. A parallel can be made with the regular non-incremental semi-naïve evaluation of a static program, where the left side takes as input the most recently inferred facts and the right side all. gatekeep : Z⟨N,Σ⟩ × ′Z ↦→ ′′Z⟨,Σ,N⟩ , ∀, ′′Z⟨,Σ,N⟩ [] = ↑↑ ((↑(↑ ⋊⋉)Δ)Δ(Z⟨N,Σ⟩ , ′Z ))[] Each iteration is initiated through operator gatekeep. Its inputs are a delayed stream of streams of Z-sets that contain tuples where the first element is the Z-set of expected provenances of some atom alongside a rewrite set Σ and a stream of directions.
The output is the Join of the delayed provenance-indexed rewrites with directions. The join predicate is the equality between the provenance of the left side with the "previous" provenance of matching directions.
The projection function outputs tuples that in push Σ as candidate rewrites for the next iteration. This is achieved by emitting tuples where candidate rewrites have their "next" provenance alongside some atom such that (, ) = and is any rule. This operator is proportional to the product of the previous iteration rewrites and all directions.
product : Z⟨,Σ,N⟩ × ′Z ↦→ ′′Z⟨N,Σ⟩ , ∀, ′′Z⟨N,Σ⟩ [] = ↑↑ ((↑(↑ ⋊⋉)Δ)Δ(Z⟨,Σ,N⟩ , ′Z ))[] (2) Operator product implements the core of the rewrite product, with its inputs being the output of gatekeep and the delayed stream of ground atoms. Let : ⟨, Σ, N⟩ be the left side and the right, is true if Σ applied to unifies with returning Σ . The projection then simply yields Σ ⊕ Σ and N. This operator is then proportional to the product of the rewrites propagated during this iteration with all ground atoms.
ground : Z⟨N,Σ⟩ × ′Z ↦→ ′′Z , ∀, ′′Z [] = ↑↑ ((↑(↑ ⋊⋉)Δ)Δ(Z⟨N,Σ⟩ , ′Z ))[] (3) The last operation is grounding itself, where the possibly-final rewrites stemming from product are joined with grounding signals. The output of this operator will be all rewrites that have been propagated beyond the last body atom, hence being applicable to the head of their respective rules to generate new ground atoms. is true if the provenance of the left side matches some found in a grounding signal. is the application of the rewrite to the head atom contained in the signal tuple. 4.3. A simple indexing scheme to improve performance While the proposed circuit has been demonstrated to be incremental in both programs and ground atoms, operator product is ineficient because in each iteration it needlessly attempts to unify every single rewrite with all facts that share the same predicate. This implies that both the best and worst case complexities of its join with respect to ground atoms are the same.
To make our circuit practical, we devise a way to make its join key more fine-grained by also taking
into account constant term combinations. We implemented a simplified version of the ground atom
indexing method that Soufle has pioneered[
Example 4.7 (The naïve join order of some rule) Given = (, ) ← (, ), (, ) with = 1, then jorder( ) = {⟨, ()⟩ ↦→ 1, ⟨, 0⟩ ↦→ 1}. The first tuple indicates that for the predicate there should be no index. The second on the other hand makes it explicit that ground atoms in ought to be indexed on their zeroth term.
Definition 4.7 The extended grounding kit Q of some program Π and its rules is a triple ⟨Z, Z , Z ⟩ where: Z and Z are the same as in K, and Z is ∑︀ =0 jorder( ). The function ekit : Π ↦→ Q computes the extended grounding kit for some program Π, and jorder : Π ↦→ Z returns some Π’s join order Z-set.
As Figure 3 shows, it is only necessary to make a few changes to the circuit depicted on Figure 2 to extend it with this incremental indexing mechanism.
First, one new operator must be applied to ΔZΠ , ↑jorder, and product’s predicate needs to be shifted to join over predicates and constant terms i.e indexed facts. This is enabled by adding a new operator after the distinct operator that follows the sum of recently arrived ground atoms and ground. index : Z × ′Z ↦→ ′′Z⟨,⟩ , ∀, ′′Z⟨,⟩ [] = ↑↑ ((↑(↑ ⋊⋉)Δ)Δ(Z , ′Z ))[] (4) The index operator receives as input ground atoms and join orders. The join key function is true if some atom’s predicate matches some order’s predicate. Given some matching order and atom , will output a tuple ⟨′, ⟩ containing partial atom ′ according to and .
This will ensure that while the right side is still proportional to all ground terms of some predicate , if there is only one match according to the order , then the best-case complexity decreases to being a scan over only that single match. Over the next section we demonstrate how this leads to enormous performance gains, at a seemingly minimal increase in memory usage.
There are three parts to this section. The first one pertains to comparing the materialisation performance of the circuit with indexing, versus without. To give a point of reference, Souflé was put through the same benchmark in interpreted mode.
The second part aims to compare DYRE’s incremental behavior with the reasoner that is the closest to it, DDLog. This is the most important empirical result of the paper, as this would indicate that the incremental semantics were indeed inherited, with the additional benefit of the program being dynamic.
As incremental systems must keep track of more data than non-incremental ones, the last part is dedicated to providing an overview of the peak memory usage witnessed across all benchmarks.
Datasets. We choose to strictly use three well-known synthetic datasets for performance evaluation.
The first dataset is LUBM[
(, "rdfs:domain", ), (, , ) (, , ) ← (, "rdf:type", ) ←
(, "rdfs:subPropertyOf", ), (, , ) (, "rdfs:subClassOf", ) ←
(, "rdfs:subClassOf", ), (, "rdf:type", ) (, "rdf:type", ) ← (, "rdfs:subPropertyOf", ) ←
(, "rdfs:subClassOf", ), (, "rdfs:subClassOf", ) (, "rdfs:range", ), (, , )
(, "rdfs:subPropertyOf", ), (, "rdfs:subPropertyOf", ) The core of RDFS entailment can be modelled as the program of approximately 6 mutually recursive rules contained in equation 5. ...
Faculty() ← ...
Employee() ← ...(95 more rules) degreeFrom(, ) ←
hasAlumnus(, )
The OWL2RL entailment program, in equation 6, is done by converting the description logic entailments
of LUBM’s ontology to Datalog according to [
The second and third datasets are graphs generated with the GT[
All benchmarks used the same AWS-provisioned M1 Mac Pro machine. No other processes were running during the evaluation. Each measurement was either taken fifty times, or up to until there wasn’t noticeable variance. Runtime performance was recorded with each reasoner’s own profiler, while peak memory usage was tracked with GNU Time.
The first benchmark set is shown on Figure 4. The X axis shows the percentage of the total data that is being materialized according to the respective program and dataset, indicated by the title of the facet of each subgraph. The Y axis shows the time in milliseconds taken to materialise the program. DYRE refers to DYRE with indexing, and its counterpart is referred to without the superscript. (5) (6) (7)
In two out of the four graphs, Souflé is faster than both versions of DYRE. In TC:Dense, Souflé is three times faster than DYRE with indexing, and twenty times otherwise. The same ratio holds true in the sparse graph. As both of these scenarios require imply fixpoint iterations, they ofer a good proxy to evaluate the impact of DBSP’s provenance, which is considerable in both variants. As the indexing scheme restricts the rewrite product to only occur between fresh atoms that share constants with facts, it decreases the amount of data that is retained.
LUBM:OWL2RL and LUBM:RDFS do not require multiple iterations to converge, with the latter only needing a handful. In both of these situations, DYRE with indexing is at least twice as fast as Souflé in every single measurement. Given these results, we posit that our simple indexing scheme brings overwhelmingly better performance, to the point that it rivals a state of the art reasoner that is not incremental.
With DYRE showing adequate single-batch performance when compared with the well-known reasoner Souflé, we turn to comparing it with DDLog, a Souflé-inpsired incremental reasoner that compiles non-incremental Datalog programs to diferential dataflow programs that are incremental. On the benchmark shown on Figure 5, the X axis contains three sequential steps: The first step 1 - mat indicates the initial materialisation, with the following ones representing incremental updates, with 2 - update being a incremental addition, followed by a incremental deletion 3 - remove.
The amount of data that is added is in the reasoner name. DDLog:99 means that the initial materialisation consisted of 99% of all available data, with the incremental addition containing the remaining 1%, and the deletion removing the same amount. DDLog:50 on the other hand, had a initial materialisation size of 50%, with subsequent updates each adding and retracting the remaining 50%.
We note that a update batch size that is equivalent to the initial materialisation is not realistic, as are all depicted measurements where the batch size is 50%. It being 1% however, is akin to highly dynamic scenarios. The expected behavior of a incremental system is to take less time to adjust to an update than to restart the computation from scratch.
For the programs that are run on LUBM, both DYRE and DDLog exhibit incremental behavior. It takes roughly as much time for both to initialise the materialisation, than to update it with both additions and deletions. When the batch size is 50% the line is flat, as each update takes roughly the same time, as expected.
When the update is much smaller than the initial materialisation, as is the case when the batch size is 1%, there should be a dramatic elbow from step 1 - mat to 2 - update. This is witnessed in both graphs, for both reasoners. DYRE however is over ten times faster than DDLog to initially materialise the data in RDFS, and twice to process updates. In OWL2RL it is respectively is four times and two times faster.
While DYRE is significantly faster, DDLog’s ratio of initial materialisation over update processing is better. For RDFS DDLog took 780 ms on average to materialise 99% of the data, and then only 10 ms for each update. DYRE on the other hand took 83 ms and 7ms. This implies that DYRE has an almost ten times bigger overhead to process updates.
The performance of DDLog in the benchmarks with the transitive closure program is close to DYRE. For the dense graph, DYRE did not manage to attain incremental behavior, as in the case where the batch size is 1%, updates took the same time as materialisation. DDLog however did not. In the sparse graph, DYRE performed better than DDLog but not by much, with both the initial materialisation and the updates being only 30% faster. DDLog struggled with the large batch size, where it took almost four times as long to update than the initial materialisation.
To provide further insight into the cost of supporting incremental reasoning, Figure 6 shows the peak memory usage that was recorded from each reasoner across all experiments. Souflé used at least one order of magnitude less memory than every single reasoner. In the most extreme case, transitive closure over the Sparse graph, DYRE used 100 times more memory than Souflé. In all scenarios DDLog consistently consumed four times less memory than DYRE.
The last notable observation is that the indexing scheme implied only a small increase in memory usage, in spite of leading to a constant ten times higher performance.
In this paper we put forward a novel take on the incremental interpretation of dynamic Datalog programs by entirely delegating that problem to DBSP. DBSP is a formal language for incremental iterative streaming computation that allows for highly expressive query languages to be expressed in.
DBSP’s primary benefit however isn’t in providing a suitable theoretical playground, but in also having a very eficient interpreter written in Rust. While Datalog has been recently seen almost exclusively as a problem of eficiently compiling horn clauses into relational algebra, we revisit its framing as a term rewriting system and directly model it as a incremental DBSP circuit that is then extended with a simple indexing scheme.
We evaluated our reasoner DYRE, Dynamic Datalog Reasoner, against two state of the art reasoners, Souflé, that is not incremental, and DDLog. We attained competitive benchmark results, surpassing the former running in interpreted mode in materialization runtime in two occasions, and the latter in most benchmarks, at the cost of four times higher memory consumption. Furthermore, our proposed incremental indexing scheme was shown to be the key element that made its performance competitive.
While DYRE is an interpreter, DDLog is a compiler. The total number of lines of code of DYRE’s DBSP circuit sits at 120. Each DDLog diferential dataflow program had hundreds, up to thousands for OWL2RL, of lines of code and took minutes to compile.
We then conclude that DBSP is an interesting venue for describing and writing incremental and non-incremental term writing systems whose primary goal is in attaining high performance. We see multiple ways of extending this work, such as by extending the interpreter to support stratified negation or other Datalog flavors, and in improving the indexing scheme by replicating Souflé’s.