The core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its phys- ical incorporation into the database itself. The de-facto method of computing it, is through the recursive application of inference rules. Due to it being a costly operation, it is a must for datalog engines to provide incremental materialization, that is, to adjust the computation to new data, instead of restarting from scratch. One of the major caveats, is that deleting data is notoriously more involved than adding, since one has to take into account all possible data that has been entailed from what is being deleted. Differential Dataflow is a computational model that provides efficient incremen- tal maintenance, notoriously with equal performance between ad- ditions and deletions, and work distribution, of iterative dataflows. In this paper we investigate the performance of materialization with three reference datalog implementations, out of which one is built on top of a lightweight relational engine, and the two others are differential-dataflow and non-differential versions of the same rewrite algorithm, with the same optimizations. KEYWORDS datalog, incremental view maintenance, differential dataflow 1 INTRODUCTION Datalog[ 9], the canonical language for reasoning over relational databases, ground fact stores, is a declarative language used to eval- uate sets of possibly-recursive restricted horn clauses, programs, while remaining not Turing complete. Evaluating a program entails computing implicit consequences over a fact store, yielding new facts. Materialization, or the physical storage of a program’s conse- quences, eliminates the need for reasoning during query answering. Maintaining this computation is essential for modern Datalog use- cases, as it relates to the broader problem of incremental view maintenance. While the semi-naive evaluation method[ 9] efficiently handles additions, deletions are often less efficient, as retracting a fact may naively imply deleting all data derived from it. The delete- rederive[ 18] method addresses this issue by computing the ma- terialization adjustment through the generation of new Datalog programs, first calculating all possible deletions, and then deter- mining alternative derivations. The difference between these sets represents the actual facts to be deleted. Using two distinct algorithms for additions and deletions results in different performance characteristics, potentially causing severe biases. For example, when a large portion of ground facts are deleted, such as more than ten percent, a not very realistic value, delete- rederive could be significantly more expensive than recomputing from scratch, since computing all overdeletions, and alternativederivations, might take longer than re-materialization in itself, for as there can be cases where a small portion of ground facts have a high impact on the number of inferred facts. A promising way to tackle incremental maintenance in a more uniform manner is to use differential dataflow, a programming model that efficiently processes and maintains large-scale possi- bly recursive dataflow computations. Central to it is the notion of fine-grained tracking, with partially-ordered timestamps, and pro- cessing differences between collections of data, rather than entire collections themselves. This approach facilitates efficient updates in response to changes in the underlying data[1]. In the context of datalog, differential dataflow (DD) presents an opportunity to address the performance challenges arising from handling additions and deletions. Contrary to traditional methods, such as semi-naive evaluation for additions and delete-rederive for deletions, differential dataflow provides a unified and efficient approach to incremental view maintenance. The utilization of partially ordered timestamps and arrangements allows DD to precisely identify affected parts of the computation and to recompute only the necessary components. This leads to a more efficient handling of incremental updates in Datalog evalua- tion, as the system can focus on affected sub-computations rather than re-evaluating the entire program. Furthermore, there also is first-class support for both automatic parallelism and distributed computing, contributing to enhanced performance and scalability. DDLog[ 26] has been the only attempt at building a datalog engine that utilized DD. Similarly to the high-profile reasoner Souffle[ 27], it is a compiler, in which a datalog program becomes an executable low-level language program, C++ in Souffle’s case, and Rust for DDLog. The rationale for the language choice, is that DD’s canonical implementation lives as a heavily optimized map- reduce-like framework written in Rust. Notably, given that DDLog is a compiler, it is not suited for situations where either the program is expected to be dynamic, with rules being added or removed, or where new programs ought to be evaluated during run time, therefore restricting its use case to the specific scenarios where such drawbacks are acceptable. There has been no study evaluating the isolated benefit of DD to datalog evaluation. Therefore the suitability of DD in this context remains unclear, emphasizing the importance of further research on its potential benefits and limitations in incremental view main- tenance. Contributions. In this work, we directly address the posited research question by developing a datalog interpreter utilizing DD. We then compare our implementation with other prototypical dat- alog interpreters, created from scratch, that share as many com- ponents as it is reasonable, in order to isolate the effect of DD in both runtime performance and memory efficiency. This allows us Matthew Stephenson to more accurately empirically assess how does DD in itself fare against more traditional approaches. Unlike DDLog, which compiles a datalog program into its evalu- ation as a fixed DD program, our approach involves writing a single DD program capable of evaluating any datalog program. This elim- inates the need for compilation and provides the additional benefit of incremental maintenance for both rule removals and additions. Structure of the paper. •Background. A brief recapitulation of the general back- ground, with datalog, its evaluation methods, and the delete- rederive method being formally introduced. •Differential Evaluation. DD, and the translation of data- log evaluation to a dataflow is showcased and explained. •System. The developed interpreters are described, along- side with all optimizations and benchmark-relevant infor- mation. •Evaluation. An empirical evaluation of all reasoners, over multiple different programs and datasets is undertaken. 2 RELATED WORKS DD Applications and Related Projects. There are two relevant DD projects that are worth mentioning. One of them is Graspan, a parallel graph processing system that uses DD for efficient in- cremental computation of static program analyses over large code- bases. Graspan models the program analysis problem as a reachability problem on a graph, where nodes represent program elements and edges represent the relationships between these elements. It lever- ages DD to incrementally update the analysis results in response to changes in the input graph, which can be due to code modifications or updates to the analysis rules. Graspan has demonstrated its abil- ity to scale to large codebases and provide low-latency updates for various static analyses, including points-to analysis, control-flow analysis, and data-flow analysis. Another project of interest is DBSP[ 8], a recent development, that started from the need for a more concise theoretical definition of DD. All of DBSP operators are based on DD’s, however, its com- putational model is less powerful as it does not allow updates to past values in a stream, and it is also assumed that inputs arrive in time order. DBSP can express both incremental and non-incremental computations, with the former not being possible in DD. Datalog engines. There are two kinds of datalog engines. The first encompasses those that compile a datalog program to usu- ally a systems-level programming language, and the second are interpreters, able to evaluate any datalog program. Soufflé is a prominent example of a datalog compiler that trans- lates datalog programs into high-performance C++ code. It incor- porates several optimization techniques, such as parallel execution with highly specialized data structures[ 21], and nearly optimal join ordering[ 3]. Notably, its development has been an unparalleled source of articles on the engineering of reasoners. DDLog As previously mentioned, compiles datalog to DD, achiev- ing efficient differential data updates for datalog programs. It demon- strates the applicability of DD in the context of declarative logic programming and incremental view maintenance.The majority of reasoners recently developed have been mostly interpreters, further split into distributed or shared memory sys- tems. Out of the shared memory ones, the most notable are RDFox[ 23], a highly specialized and performant reasoner that is tailored to the semantic web needs, RecStep[ 31], that builds on top of a highly efficient relational engine, and DCDatalog[ 30], that builds upon the query optimizer DeALS[ 29] and extends a work that establishes how some linear datalog programs could be evaluated in a lock-free manner, to general positive programs. One of the most high-profile datalog papers of interest has been BigDatalog[ 28], that originally used the query optimizer DeALs, and was built on top of the very popular Spark[ 4] distribution frame- work. Soon after, a prototypical implementation[ 20] over Flink[ 24], a distribution framework that supports streaming, Cog, followed. Flink, unlike Spark, supports iteration, so implementing reasoning did not need to extend the core of the underlying framework. The most successful attempt at creating a distributed implemention has been Nexus[ 19], that is also built on Flink, and makes use of its most advanced feature, incremental stream processing. 3 BACKGROUND Datalog [9] is a declarative programming language. A program 𝑃is a set of rules 𝑟, with each𝑟being a restriction of tuple-generating dependencies: 𝐻(𝑥1,...,𝑥𝑗)←𝑘Û 𝑖=1𝐵𝑖(𝑥1,...,𝑥𝑗) with𝑘,𝑗as finite integers, 𝑥as terms, and each 𝐵𝑖and𝐻as predi- cates. A term can belong either to the set of variables, or constants. The set of all 𝐵𝑖is called the body , and𝐻thehead . A rule𝑟is said to be datalog, if no predicate is negated, and all variables in the head appear somewhere in the body, thereby not there being the possibility for existential variables to exist, conversely, a datalog program is one in which all rules are datalog. Example 3.1. Datalog Program 𝑃={𝑇𝐶(?𝑥,?𝑦)←𝐸𝑑𝑔𝑒(?𝑥,?𝑦) 𝑇𝐶(?𝑥,?𝑧)←𝑇𝐶(?𝑥,?𝑦),𝑇𝐶(?𝑦,?𝑧)} Example 3.1 shows a simple valid recursive program. The first rule denotes that for all x and y, if x is in a Edge relation with y, then it follows that x is in a TC relation with y , and the second for all x, y, z, if x is in a TC relation with y, and y is in a TC relation with z, then it follows that x is in a TC relation with z . Programs denote implications over a store of ground facts. This store is called the extensional database, 𝐸𝐷𝐵 , and the result of evaluating a program over some 𝐸𝐷𝐵 is the𝐼𝐷𝐵, the intensional database. Let𝐷𝐵=𝐸𝐷𝐵∪𝐼𝐷𝐵, and for there to be a program 𝑃. We define theimmediate consequence of𝑃over𝐷𝐵as all facts that are either in𝐷𝐵, or stem from the result of applying the rules in 𝑃to𝐷𝐵. The immediate consequence operator I𝐶(𝐷𝐵)is the union of 𝐷𝐵and its immediate consequence. The 𝐼𝐷𝐵, at the moment of the application ofI𝐶(𝐷𝐵), is the difference of the union of all previous 𝐷𝐵with the𝐸𝐷𝐵 , therefore consisting only of the inferred facts. A Differential Datalog Interpreter It is trivial to see that 𝐼𝐶(𝐷𝐵)is monotone, and given that both the𝐸𝐷𝐵 and𝑃are finite sets, and that 𝐼𝐷𝐵=∅at the start, at some point𝐼𝐶(𝐷𝐵)=𝐷𝐵, since there won’t be new facts to be inferred. This point is the least fixed point of𝐼𝑐(𝐷𝐵)[9]. Computing the least fixed point as described, recursively applying the immediate consequence operator, is called naive evaluation, which is not often used in practice, since in every iteration not only does it infer new facts, but also recomputes all previously inferred ones. 3.1 Semi-Naive Evaluation The semi-naive evaluation algorithm [ 9] is a widely-used technique for improving naive evaluation, that directly addresses, but does not solve entirely, its major inefficiency, redundant recomputations of previously inferred facts. Given a Datalog program 𝑃and an𝐸𝐷𝐵 , the algorithm iteratively computes the 𝐼𝐷𝐵 in the same manner as naive evaluation, with the addition of maintaining a set of new delta facts Δthat are generated in each iteration. Given a program 𝑃with rules𝑟0,...,𝑟𝑛, with bodies 𝑏(𝑟)={𝑏0,...,𝑏𝑘} and heads𝐻(𝑟), the delta program will generate one new Δrule for each𝐼𝐷𝐵 relation𝑏𝑗in each rule body 𝑏(𝑟𝑖), in order to represent that only facts that have been recently inferred are to be taken into account for subsequent iterations. Example 3.2. Semi-naive Evaluation Delta Program 𝑟0=𝑇𝐶(?𝑥,?𝑦)←𝐸𝑑𝑔𝑒(?𝑥,?𝑦) Δ𝑟1=𝑇𝐶(?𝑥,?𝑧)←Δ𝑇𝐶(?𝑥,?𝑦),𝑇𝐶(?𝑦,?𝑧) Δ𝑟2=𝑇𝐶(?𝑥,?𝑧)←𝑇𝐶(?𝑥,?𝑦),Δ𝑇𝐶(?𝑦,?𝑧) With example 3.1 as the baseline, 3.2 is its resulting delta program. While semi-naive evaluation indeed reduces the number of inferred redundant facts, it is particularly efficient for a certain class of simple Datalog programs that are common in practice, namely linear programs, which are those in which each rule has at most one IDB relation in its body, therefore generating only one delta rule per rule, instead of multiple, as in the example. In spite of being asymptotically better than naive evaluation, there are substantial implementation challenges that need to be addressed in order to ensure that the overhead is not larger than possible performance gains, since it requires multiple indexes, each delta relation, and efficient set operations to keep track of the most recently inferred facts. This is of utmost importance when using semi-naive evaluation as a method to incrementally handle additions to the 𝐸𝐷𝐵 . It often occurs that a materialization needs to be adjusted, either to additions or retractions of ground facts. Both semi-naive and naive evaluation are iterative, thus additions can be dealt with by simply having their computations restarted, with the former having the entire𝐼𝐷𝐵 as the initial set of delta facts, instead of the empty set. The major goal of continuing the computation is such that it will be more efficient than restarting the materialization altogether. 3.2 Delete-Rederive While both aforementioned evaluation methods provide mecha- nisms to incrementally adjust materialization to new ground facts,neither support retraction of ground facts, a problem that is sig- nificantly more involved, since a single fact might have multiple possible derivations. The most used method is a bottom-up algorithm[ 18] that relies on evaluating two new programs, one that computes all possi- ble deletions that could stem from the deletion of the facts being retracted, and then another that attempts to find alternative deriva- tions to the overdeleted ones. Given a program 𝑃with rules𝑟0,...,𝑟𝑛, with bodies 𝑏(𝑟)={𝑏0,...,𝑏𝑘} and headsℎ(𝑟), the overdeletion program will generate one new −rule for each 𝑏𝑗in each rule body 𝑏(𝑟𝑖), in order to represent that if such fact were to be deleted, then ℎ(𝑟𝑖)would not hold true. Example 3.3. DRED Overdeletion Program −𝑟0=−𝑇𝐶(?𝑥,?𝑦)←−𝐸𝑑𝑔𝑒(?𝑥,?𝑦) −𝑟1=−𝑇𝐶(?𝑥,?𝑧)←−𝐸𝑑𝑔𝑒(?𝑥,?𝑦),𝑇𝐶(?𝑦,?𝑧) −𝑟2=−𝑇𝐶(?𝑥,?𝑧)←𝐸𝑑𝑔𝑒(?𝑥,?𝑦),−𝑇𝐶(?𝑦,?𝑧) On example 3.3 negative predicates represent overdeletion tar- gets for example 3.1. For instance, if Edge(2, 3) is being deleted, then TC(2, 3) will be deleted, and any other inferred fact that depends on it. Given that it is a regular datalog program, it can be efficiently evaluated with semi-naive evaluation, or any other evaluation algorithm. The next step is to compute the alternative derivations of the deleted facts, since some overdeleted facts might still hold true. The alternative derivation program will generate one new +rule for each𝑟𝑖in𝑃, with one extra−head predicate per body, representing an overdeleted fact. The +program requires the overdeleted facts to already not be present. Example 3.4. DRED Alternative Derivation Program 𝑟0=+𝑇𝐶(?𝑥,?𝑦)←−𝑇𝐶(?𝑥,?𝑦),𝐸𝑑𝑔𝑒(?𝑥,?𝑦) 𝑟1=+𝑇𝐶(?𝑥,?𝑧)←−𝑇𝐶(?𝑥,?𝑧),𝐸𝑑𝑔𝑒(?𝑥,?𝑦),𝑇𝐶(?𝑦,?𝑧) The output relations from example 3.4 represent the data that has to be put back into the materialization for example 3.1. The rationale for alternative derivations is that, for 𝑟1, for instance, if the edge TC(3, 4) was overdeleted, because of there being Edge(1, 2) andTC(2, 3) , ifEdge(3, 4) was not deleted, by rule 𝑟0, then there is an alternative derivation for TC(3, 4) . As it can be seen, computing the maintenance of the materializa- tion implies evaluating a program bigger than the materialization itself, however, due to the fact that it is evaluated with semi-naive evaluation, the asymptotic complexity remains the same. Nonethe- less, in practice, deletion is often much slower than addition, as it can be trivially seen by the worst-possible scenario, in which all facts are deleted, whereby while materialization would be free, DRED would inquire an expensive fact-by-fact deletion operation. 3.3 Substitution-based evaluation The most impactful aspect of all of the introduced evaluation mech- anisms is the implementation of 𝐼𝑐itself. The two most high-profile Matthew Stephenson methods to do so are either purely evaluating the rules, or rewrit- ing them in some other imperative formalism, such as relational algebra, and executing it. The substitution-based[ 9] method is the simplest example of the former. A substitution 𝜎is a homomorphism [𝑥1→𝑦1,...,𝑥𝑖→𝑦𝑖], such that𝑥𝑖is a variable, and 𝑦𝑖is a constant. Given a not-ground fact, such as 𝑇𝐶(?𝑥,4),applying the substitution[?𝑥→1]to it will yield the ground fact 𝑇𝐶(1,4). Let𝑟be a Datalog rule of the form ℎ←𝑏1,𝑏2,...,𝑏𝑚, whereℎ is the head atom and 𝑏𝑖are the body atoms. Let 𝐸𝐷𝐵 be the set of ground facts for the input relations. The substitution-based method computes the immediate conse- quence of the rule 𝑟as follows: Define the initial set of substitutions as Σ0={𝜎0}, where𝜎0 is an empty substitution. For each body atom 𝑏𝑚, find the set of ground facts 𝐹𝑗⊆𝐹that match𝑏𝑚. Algorithm 1 is the formal spec- Algorithm 1: Substitution-based Immediate Consequence Input : Σ0, set of ground facts 𝐹, head atom ℎ, body atom list𝐵 Output: Immediate Consequence 𝐼 1foreach𝑖=1,2,...,𝑚 do 2 foreach fact𝑓∈𝐹and each partial substitution 𝜎𝑖−1∈Σ𝑖−1do 3 Generate an extension 𝜎′ 𝑖−1of𝜎𝑖−1with the constant-to-variable homomorphisms from 𝑓that are consistent with the current body atom 𝑏𝑚; 4 if𝜎′ 𝑖−1is a valid substitution then 5 Σ𝑖=Σ𝑖−1∪𝜎′ 𝑖−1; 6 end 7 end 8 foreach final substitution 𝜎𝑚∈Σ𝑚do 9𝐼=𝐼∪𝜎𝑚𝐻 10 end 11end ification of the substitution-based method. There is a noteworthy performance issue that arises due to the interaction between it and DRED. During the alternate derivation phase, the new program has one more body atom. This can be prohibitively more expensive to evaluate than the original program, since one extra body atom implies one extra iteration, which could generate a polynomial number of substitutions, due to the cartesian product nature of each step. 3.4 Relational algebra rewriting method The de-facto datalog evaluation method, that virtually all recent reasoners[ 19,20,27,28,30,31] abide by, is to rewrite datalog rules into relational algebra, a well-known technique, to efficiently com- pute their evaluation, due to the extensive industrial and academic research poured into developing data processing frameworks that handle very large amounts of data, and the techniques that have arisen from those. Relational Algebra[ 11] explicitly denotes operations over sets of tuples with fixed arity, relations. It is the most popular databaseformalism that there is, with virtually every single major database system adhering to the relational model[ 10,12?] and using SQL as a declarative syntax. DD either implements, or makes it trivial to do so, all relevant-to- datalog relational algebra operators, therefore providing convenient tools to manually specify the evaluation of a datalog program as a dataflow. It nonetheless does not directly make writing the inter- preter more convenient, only a compiler. 4 DIFFERENTIAL EVALUATION Differential Dataflow is a computational framework that gener- alizes incremental processing to times that are possibly partially ordered, and specifically operates over generalized multisets. Let𝐶be a multiset, referred to as a collection, with 𝐶𝑡being its value at a partially ordered time 𝑡, and𝐶𝑡(𝑏)being the monoid representing the multiplicity of some record 𝑏∈𝐶𝑡. We establish that the difference of some collection 𝐶at time𝑡, named𝛿𝐶𝑡, is defined as: 𝛿𝐶𝑡=𝐶𝑡−𝐶𝑡−1 It also therefore holds that the value of 𝐶𝑡can be reconstructed by the following equivalence: 𝐶𝑡=∑︁ 𝑖≤𝑡𝛿𝐶𝑖 We utilize plain multiset semantics with signed integers as multi- plicity. Let𝐴and𝐵be collections, and OPbe some operator that maps a collection to some other collection, or itself. Assuming 𝐵to be the output ofOPapplied over 𝐴, computations in DD follow the following: 𝐵𝑡=OP(𝐴𝑡)=OP(∑︁ 𝑖≤𝑡𝛿𝐴𝑖)=∑︁ 𝑖≤𝑡OP(𝛿𝐴𝑖) withOPbeing proportional to 𝛿𝐴𝑡, and not𝐴𝑡. Stateful Operators, such as the relational join, require more involved differentiation steps. A core premise of the canonical DD implementation, is in clev- erly, and efficiently, maintaining 𝛿𝐵and𝛿𝐴, specifically in the context of iterative dataflows, due to 𝑡being partially ordered. Let’s assume that a datalog program is being evaluated, and five fact updates, labeled as 𝛼𝑡arrive. In regular semi-naive evaluation, even though rule application might happen in parallel, 𝛼𝑡+1will only be evaluated after 𝛼𝑡’s evaluation has finished, and the data used to compute each will always consist of all extensional and intensional(previously inferred) facts. In contrast, program evaluation could be written as a DD dataflow with a (partially ordered) product order timestamp ⟨𝑡,𝑎⟩with𝑡be- ing the time of arrival of the update, and 𝑎keeping track of iteration. Product order is defined as: ⟨𝑡𝑖,𝑎𝑗⟩≤⟨𝑐𝑘,𝑑𝑙⟩ ⇐⇒𝑡𝑖≤𝑐𝑘∧𝑎𝑗≤𝑑𝑙 If we treat 𝛼0,𝛼1,𝛼2,𝛼3,𝛼4as differences with the following respective timestamps: ⟨0,0⟩,⟨0,1⟩,⟨0,2⟩,⟨1,1⟩,⟨2,1⟩ it is noticeable, from table 1, that neither 𝛼2is visible from 𝛼3, nor that𝛼3is visible from 𝛼2. This, in turn, has an important conse- quence in differential dataflow, that the computation of both 𝛼3 A Differential Datalog Interpreter Table 1: Product Order Truth Table ≤⟨0,0⟩⟨0,1⟩⟨0,2⟩⟨1,1⟩⟨2,1⟩ ⟨0,0⟩ 1 1 1 1 1 ⟨0,1⟩ 0 1 1 1 1 ⟨0,2⟩ 0 0 1 0 0 ⟨1,1⟩ 0 0 0 1 1 ⟨2,1⟩ 0 0 0 0 1 and𝛼2happened independent of each other, meaning both may be computed in parallel: 𝛼2=𝛿𝐴0,2=𝐴0,2−(𝛿𝐴0,0+𝛿𝐴0,1) 𝛼3=𝛿𝐴1,1=𝐴1,1−(𝛿𝐴0,0+𝛿𝐴0,1+𝛿𝐴1,0) Within the context of datalog, the aforementioned evaluation se- mantics provide a full alternative to the way incremental datalog evaluation is currently done, most specifically, the practical advan- tage of differential dataflow, is that instead of using semi-naive evaluation and DRED, one can just describe the evaluation process as a dataflow, and have both additions and retractions handled in the same way, with efficient parallelism and symmetric handling of updates. 4.1 Differential Substitution-based Method We now present a translation of algorithm 1 to DD, by emulating sequentially iterating over each rule’s body with relational joins, notably, all relational algebra operators are available through a map- reduce-like API. Figure 1 depicts the substitution-based method Input Iteration OutputΣ0 Facts Rules flat_map1map2 Subs. Var Facts. Var join_map3 join_map4 join_map5 Facts Figure 1: Substitution method dataflow as a dataflow. Superscripts denote points of the dataflow that re- quire further explanation. Furthermore, for clarity, we establish the shape of the data, and the meaning of the Varsuffix, that both facts and substitutions eventually take up. a Variable is used to express recursive or iterative computations. It allows one to define iterative operations and data dependencies in the dataflow graph, enablingthe system to track and propagate changes across iterations effi- ciently, with product timestamps. Each node either represents an operation, such as join_map , that joins indexed collections and then applies a mapping function to the join output, or flat_map , that given a function that outputs an iterable, applies it over a col- lection, and flattens each element’s output to be part of a single collection. We also note that this is a summarized description, where certain trivial, or too-implementation-specific parts have been omitted. Σ0 is the stream of empty substitutions indexed per rule identifier, which is pre-populated with one empty substitution per rule. We assume that rules have an unique identifier. Facts is the relation- indexed stream of facts, and rules is the stream of rules, with two indexes, created with the operations with superscripts 1and 2. (1)The first rule index indexes rules first by their identifier, and then by each of its body atoms, enumerating them sequentially, imposing an order of evaluation as the original algorithm. (2)The second rule index indexes by identifier and body size, being necessary to ensure that only the substitutions which have been exhaustively expanded ought to be considered for application to the rule head. (3)In the first join, the function that is applied, is one that applies substitutions to the input atoms, therefore either creating new atoms, with less variables as terms, or the very same ones. This is equivalent to the necessary setup for step 1 of Algorithm 1 to occur, making use of index 1. (4)The next join creates new substitutions, based on the newly minted atoms. All current substitutions are attempted to be expanded further, with the successful ones being emitted from the join. (5)This is the last step of the algorithm, where all final sub- stitutions are applied to the head of each rule, index 2, to then create new ground facts. With the dataflow being specified, over the next section we elab- orate on the commonalities and differences with the other imple- mentations. 5 SYSTEM In this section we provide a technical overview of the implemented reasoners, and what is shared between them, alongside a novel indexing technique for the substitution-based method, that at the cost of increased memory usage, can significantly decrease the number of times the operation that occurs the most frequently, substitution extension, occurs. The reasoner that uses the substitution-based method without DD is named Chibi, differential is the one that does. Both of these reasoners share the implementation of the three core elements: unification, substitution application, and in asserting that a fact is ground. All of the aforementioned operations are trivial, and each do not require more than ten or so lines of code. Unification is a computationally cheap operation, given an atom, and a ground fact, the output is a new substitution that maps the variables of the right to the constants of the left one. All others are self descriptive, with substitution application merely substituting an atom’s variables for Matthew Stephenson the mapped variables in a substitution. Checking if a fact is ground is done by ensuring that no terms are variables. Chibi, Differential and Relational all share the same memory layout for the core elements of datalog and storage. In Rust terms, it is to be assumed that all referred data structures are standard library implementations unless stated otherwise. Furthermore, a step of rule application is always done in parallel. •Constant: an enumeration of boolean, 64-bit integer or string, respectively named typed values •Variable: an 8 bit integer, hence imposing a bound on the number of variables that a rule can have •Term: an enumeration of constant and variable •Atom: A struct with a vector of terms, and a symbol, that can be either a 64-bit integer or a string •Rule: A struct with an atom representing the head, and a vector of atoms as the body •Storage: A Hash map of hash sets, with keys represent- ing relation names, or id, and their respective hash sets containing vectors of typed terms, ground facts Relational reasoner has one extra data structure, a btree index, that is used for sort-merge joins. Relational relies on naively translating datalog rules into relational algebra, without any further optimiza- tions whatsoever, aside from inserting all data that is to be joined in its index, right before actually doing it. All relational operations and their evaluator were implemented from scratch. The point of this reasoner is to evaluate how performant the popular relational alge- bra evaluation can be in isolation, compared to the often forgotten substitution-based method. Rule application until the least fixpoint is reached is done with semi-naive evaluation[ 2], with a program transformation. DRED is implemented as described in [ 18], in two steps, with both the overdeletion and alternative derivation program being executed with semi-naive evaluation too. Both Chibi and Relational use the same function for this, with differential evidently not using semi- naive evaluation nor DRED, given that it has its own iteration mechanism, heavily inspired by semi-naive evaluation, which al- ready handles retractions. 5.1 Demand-driven Multiple-column-based Indexing There is a possibly very large performance cost of the substitution- method, that can be exemplified in the specific scenario of DRED, that could render it unable to be used in practice. As it was intro- duced, substitutions are both incrementally expanded, and built anew, by iterating over every single body atom. In the second step of DRED, an alternate derivation program is created. This program has one extra body atom, representing overdeletions of the head’s relation. This implies that this step could be prohibitively more expensive to evaluate than even evaluating the program, due to the cartesian nature of the unification step, that implies iterating over the knowledge base once, for every atom. This inefficiency can be demonstrated with the following example, in which the rule could be seen as the alternate derivation step of some rule:𝑅(?𝑥,?𝑧)<−𝑇(?𝑥,?𝑦),𝑇(?𝑦,?𝑧), with−𝑅representing the overdeletion estimation from the previous step.Let𝑃={+𝑅(?𝑥,?𝑧) ← −𝑅(?𝑥,?𝑧),𝑇(?𝑥,?𝑦),𝑇(?𝑦,?𝑧)}, and 𝐸𝐷𝐵 ={𝑇(𝑎,𝑏),𝑇(𝑏,𝑐),𝑇(𝑐,𝑑),−𝑅(𝑎,𝑐),−𝑅(𝑏,𝑑)}Algorithm 1 will have three iterations: (1) (a) Current body atom: −𝑅(?𝑥,?𝑧),Σ0:[{}] (b)Fresh atoms - Applying all 𝜎:Σ0to−𝑅(?𝑥,?𝑧)yields −𝑅(?𝑥,?𝑧) (c) Substitution extension: (i)unification: -R(?x, ?z) ∪-R(a, c) ={?𝑥→𝑎,?𝑧→ 𝑐} (ii)unification: -R(?x, ?z) ∪-R(b, d) ={?𝑥→𝑏,?𝑧→ 𝑑} (2) (a) Current body atom: 𝑇(?𝑥,?𝑦),Σ1:[{?𝑥→𝑎,?𝑧→ 𝑐},{?𝑥→𝑏,?𝑧→𝑑}] (b)Fresh atoms - Applying all 𝜎:Σ1to𝑇(?𝑥,?𝑦)yields 𝑇(𝑎,?𝑧),𝑇(𝑏,?𝑧) (c) Substitution extension: (i)unification: T(a, ?y) ∪T(a, b) ={?𝑥→𝑎,?𝑦→ 𝑏,?𝑧→𝑐} (ii) unification: T(a, ?y) ∪T(b, c) = none (iii) unification: T(a, ?y) ∪T(c, d) = none (iv) unification: T(b, ?y) ∪T(a, b) = none (v)unification: T(b, ?y) ∪T(b, c) ={?𝑥→𝑏,?𝑦→ 𝑐,?𝑧→𝑑} (vi) unification: T(b, ?y) ∪T(c, d) = none (3) (a) Current body atom: 𝑇(?𝑦,?𝑧),Σ2:[{?𝑥→𝑎,?𝑦→ 𝑏,?𝑧→𝑐},{?𝑥→𝑏,?𝑦→𝑐,?𝑧→𝑑}] (b)Fresh atoms - Applying all 𝜎:Σ2to𝑇(?𝑦,?𝑧)yields 𝑇(𝑏,𝑐),𝑇(𝑐,𝑑) (c) Substitution extension: (i) unification: T(b, c) ∪T(a, b) = none (ii)unification: T(b, c) ∪T(b, c) ={?𝑥→𝑎,?𝑦→ 𝑏,?𝑧→𝑐} (iii) unification: T(c, d) ∪T(c, d) = none (iv) unification: T(c, d) ∪T(a, b) = none (v) unification: T(c, d) ∪T(b, c) = none (vi) unification: T(c, d) ∪T(c, d) ={?𝑥→𝑏,?𝑦→ 𝑐,?𝑧→𝑑} With the final substitutions being: [{?𝑥→𝑎,?𝑦→𝑏,?𝑧→ 𝑐},{?𝑥→𝑏,?𝑦→𝑐,?𝑧→𝑑}], therefore inferring two atoms: +𝑅(𝑎,𝑐)and+𝑅(𝑏,𝑑). The major source of inefficiency are calls to unification attempt, that yield no new substitution. The number of unification attempts could grow quadratically with each next body atom. The solution to this issue is straightforward; to avoid the cartesian product. We devise a novel indexing technique specifically tailored to be portable to DD. Returning to the example, it is trivial to see that wasteful unifica- tion attempts can be prevented by joining on bindings; If 𝑇(𝑎,?𝑦) is the left-hand side of unification, and 𝑇(𝑎,𝑏),𝑇(𝑏,𝑐)are the can- didates, no candidate that does not already match all constants in 𝑇(𝑎,?𝑦)would produce a substitution extension. We name our approach Demand-driven Multiple-column-based Indexing, because indexes are built on-demand to address the need of indices for joining substitutions, that can be over multiple con- stants, therefore spanning over multiple columns, in each iteration. For each rule we determine the column combinations that will be used in such a join, and maintain one globally shared index for A Differential Datalog Interpreter each unique column combination. First, we demonstrate the tech- nique over the same example, and then provide a new version of Algorithm 1. (1) (a) Current body atom: −𝑅(?𝑥,?𝑧),Σ0:[{}] (b)Fresh atoms - Applying all 𝜎:Σ0to−𝑅(?𝑥,?𝑧)yields −𝑅(?𝑥,?𝑧) (c)Index 1 - Index all fresh atoms with the positions of their constant terms as keys: {[]:[[?𝑥,?𝑧]]} (d)Index 2 - Index−𝑅based on all distinct values of the column keys of index 1 : {[] :[[𝑎,𝑐]:[[]],[𝑏,𝑑]: [[]]]} (e) Index 4 - Join Index 1 with Index 2: (i)([?𝑥,?𝑧],[[𝑎,𝑐]:[[]]]) (ii)([?𝑥,?𝑧],[[𝑏,𝑑]:[[]]]) (f) Attempt to unify: (i)unification: -R(?x, ?z) U -R(a, c) = {?𝑥→𝑎,?𝑧→ 𝑐} (ii)unification: -R(?x, ?z) U -R(b, d) = {?𝑥→𝑏,?𝑧→ 𝑑} (2) (a) Current body atom: 𝑇(?𝑥,?𝑦),Σ1:[{?𝑥→𝑎,?𝑧→ 𝑐},{?𝑥→𝑏,?𝑧→𝑑}] (b)Fresh atoms - Applying all 𝜎:Σ1to𝑇(?𝑥,?𝑦)yields 𝑇(𝑎,?𝑦),𝑇(𝑏,?𝑦) (c)Index 1 - Index all fresh atoms with the positions of their constant terms as keys: {[0]:[[𝑎,?𝑦],[𝑏,?𝑦]]} (d)Index 2 - Index 𝑇based on all distinct values of the col- umn keys of index 1 {[0]:{[𝑎]:[[𝑏]],[𝑏]:[[𝑐]],[𝑐]: [[𝑑]]}} (e) Index 4 - Join Index 1 with Index 2: (i)([𝑎,?𝑦],[[𝑎]:[[𝑏]]]]) (ii)([𝑏,?𝑦],[[𝑏]:[[𝑐]]]]) (f) Attempt to unify: (i)unification: T(a, ?y) U T(a, b) = {?𝑥→𝑎,?𝑦→ 𝑏,?𝑧→𝑐} (ii)unification: T(b, ?y) U T(b, c) = {?𝑥→𝑏,?𝑦→ 𝑐,?𝑧→𝑑} (3) (a) Current body atom: 𝑇(?𝑦,?𝑧),Σ2:[{?𝑥→𝑎,?𝑦→ 𝑏,?𝑧→𝑐},{?𝑥→𝑏,?𝑦→𝑐,?𝑧→𝑑}] (b)Fresh atoms - Applying all 𝜎:Σ2to𝑇(?𝑦,?𝑧)yields 𝑇(𝑏,𝑐),𝑇(𝑐,𝑑) (c)Index 1 - Index all fresh atoms with the positions of their constant terms as keys: {[0,1]:[[𝑏,𝑐],[𝑐,𝑑]]} (d)Index 2 - Index 𝑇based on all distinct values of the column keys of index 1 : {[0,1]:{[𝑎,𝑏]:[[]],[𝑏,𝑐]: [[]],[𝑐,𝑑]:[[]]}} (e) Index 4 - Join Index 1 with Index 2: (i)([𝑏,𝑐],[[𝑏,𝑐]:[[]]]) (ii)([𝑐,𝑑],[[𝑐,𝑑]:[[]]]) (f) Attempt to unify: (i)unification: T(b, c) U T(b, c) = {?𝑥→𝑎,?𝑦→ 𝑏,?𝑧→𝑐} (ii)unification: T(c, d) U T(c, d) = {?𝑥→𝑏,?𝑦→ 𝑐,?𝑧→𝑑} From this new example, it can be seen that the indexing scheme is relatively simple, relying on creating new indices that wouldallow unification to never wastefully occur. We now structure it as Algorithm ??. Let𝑃:𝑎→[N]be a function mapping an atom to an array of integers representing the positions of constants within the atom’s terms, and𝑅:([N],𝑎)→𝐶another function, that maps an array of integers and an atom, to a subset of the atom’s terms 𝑐denoted by𝐶. The algorithm relies on two main indexes: (1)𝐼1:𝑃(𝑎)→ 1𝐹, where 1𝐹is the subset of 𝐹such that all 𝑎 have the same 𝑃(𝑎)value. (2)𝐼2:𝑃(𝑎)→𝐼3, where𝐼3:𝑅(𝐹)→ 1𝐹is a nested index, and 1𝐹is the subset of 𝐹such that all 𝑎have the same 𝑅(𝑃(𝑎),𝑎). Algorithm 2: Substitution-based Immediate Consequence with Demand-driven Multiple-column-based Indexing Input : Σ0, set of ground facts 𝐹, head atom 𝐻, body atom list𝐵 Output: Immediate Consequence 𝐼 1foreach𝑖=1,2,...,𝑚 do 2 Apply Σ𝑖−1to the current body atom to obtain fresh atoms 𝔄; 3 Create the first index 𝐼1:𝑃(𝑎)→ 1𝔄; 4 Create the second index 𝐼2:𝑃(𝑎)→𝐼3; 5 Create the last index by joining Index 1 and Index 2: 𝐼4(𝑎)=(𝐼1(𝑎),𝐼2(𝑎))for each𝑎∈𝔄; 6 for(𝑆1,𝑆2)∈𝐼4do 7 Unify each element in 𝑆1with each element in 𝑆2; 8 Generate an extension 𝜎′ 𝑖−1of𝜎𝑖−1with the constant-to-variable homomorphisms from 𝑓that are consistent with the current body atom 𝑏𝑚; 9 if𝜎′ 𝑖−1is a valid substitution then 10 Σ𝑖=Σ𝑖−1∪𝜎′ 𝑖−1; 11 end 12 end 13 foreach final substitution 𝜎𝑚∈Σ𝑚do 14𝐼=𝐼∪𝜎𝑚𝐻 15 end 16end 17?? All indexing steps are 𝑂(|𝐹|)in time and data complexity, save for index two, that has worst-case data complexity of 𝑂(|𝐹|·2|𝑎|), with 2|𝑎|representing the powerset of the number of terms in some atom𝑎, and𝐹such that it has only atoms 𝑎. The product with the powerset arises due to how indexing occurs by mapping all unique combinations of constant terms of fresh atoms, which in the worst- case could be exponential to the arity. Figure 2 displays the DD version of Algorithm ??, that mostly remains exactly the same, save for new operations happening during the phase before iteration. We now clarify the points of interest in the new dataflow. There were no differences in the steps inside iteration, aside from joins happening through the vector of constant positions and relation symbols, instead of only relation symbols. Matthew Stephenson Input Iteration OutputΣ0 Facts Rules join_map3flat_map2map1 flat_map4 join_map5 Subs. Var Facts. Var6 join_map join_map join_map Facts Figure 2: Substitution method with indexing dataflow (1)The first mapoperator remains the same, indexing rules by their identifier and body size, used to ensure that only fully expanded substitutions will be applied to rule heads. The same as superscript 2in 1. (2)The unique column combinations of the input ruleset are computed by this operator. (3)This step joins the rule identifiers with the unique column combinations. This is only used at the very last join during iteration, to ensure that the output fact is indexed by the correct column combination. (4) Equivalent to superscript 1in 1. (5)With superscript 2, the input fact stream can be immediately indexed by the necessary constant position combinations. This is done by a join on relation symbol, that will index each fact by all column combinations. (6)Facts. var, unlike in Algorithm 1’s dataflow, which was only indexed by relation, is now indexed by each unique column combination. This dataflow is possibly much more efficient. An arrangement in DD is a pre-computed, indexed representation of a collection that allows for efficient querying and manipulation of the data. These arrangements play a crucial role in the performance of joins. By carefully choosing which arrangements to create and maintain, it is possible to keep joins efficient, without unnecessarily wasting memory. Most specifically, arrangements dictate the level of join efficiency. The fact that the join operator indexes the data by a more fine- grained key than relation symbol, such as relation symbol and positions occupied by constant values, allows is to be much more restrictive than cartesian product.Table 2: Dataset Overview Dataset Area of Interest Programs LUBM semantic web RhoDFS, RhoDFS-s, OWL2RL RMAT1K synthetic tc RAND1K synthetic tc 6 EVALUATION Three thorough experiments were conducted in order to showcase relative performance, scalability, and memory usage, of all reason- ers, with the intent being twofold: to evaluate the performance characteristics of DD, in isolation of virtually all other elements, and to establish as to whether general algorithmic improvements, such as the demand-driven indexing scheme, are portable to DD. Setup. The experiments were run on a google-cloud-provisioned x86 machine of type e2-standard-16, with 16 intel skylake cores and 64 gigabytes of RAM. Each benchmark measurement was taken 70 times, with the 20 measurements of most variance removed, and averaged out. All datasets, datalog programs and reasoner implementations are available online[25]. Datasets. On table 2 all datasets and program names, or acronyms, are shown. There are two areas of interest. The semantic web has very specific use-cases for datalog, and are the leading source of research in extending the datalog mathematical formalism, and in providing improvements to decades-old algorithms, such as DRED, with the backward-forward algorithm[ 22]. Seeking ways to intro- duce tuple-generating dependencies to programs, with evaluation remaining tractable, has been one of the most active research direc- tions, with highly-influential papers establishing new families of datalog languages[ 14] and thoroughly exploring their complexity classes alongside even further extensions[ 6,13,15]. These advance- ments have been somewhat tested in practice, albeit with no full reference implementation having been specified. The most compre- hensive, and recent, is closed-source[ 7]. The leading datalog engine in general, is also closed-source[ 23], and is tailored specifically to the semantic web. The second area of interest is of purely mathematical synthetic graph benchmarks, that allow for generating infinitely-scalable specific graph structures. all datasets however, including LUBM[ 17], are synthetic, with the difference being that there are multiple specific programs for RhoDFS. •LUBM is a classic inference benchmark dataset for both RhoDFS and OWL2RL rulesets. The data is divided in two parts, the TBox, terminological box, that holds an ontol- ogy able to describe universities, and the ABox, assertional box, that asserts facts about universities using the termi- nology in the TBox. The RhoDFS ruleset, depicted on A.1, is relatively simple, but complex, there being only a sin- gle relation that is mutually recursive in every single rule. RhoDFS-s A.2 is an improved version of RhoDFS, that cre- ates new relations for every single constant combination in the original program, avoiding every body atom imply- ing a full dataset, mimicking the relational selection. The last ruleset, OWL2RL, has over 100 rules and is by far the most complex, representing the lower bound of OWL2RL A Differential Datalog Interpreter implications, specific of the LUBM Tbox. More information on converting description logic entailments to datalog can be found on[16]. •RMAT1k . is a graph generated by the rmat profile of the GT[5] graph generator, used to benchmark various other reasoners[ 31][28]. The dataset is a graph with ten times the number of edges as vertices, that follows an inverse power-law distribution. •RAND1k is also a graph generated with the rand profile of GT. The dataset is comprised of a graph that has one thousand edges, with each having 0.01 probability of being connected to every other. In spite of having a small num- ber of nodes, it is incredibly dense, with the output of the transitive closure program having almost a hundred times more edges than the initial graph. 6.1 Runtime comparison Table 3 pictures the main benchmark, in which three measurements, Mat, +, and -, for every batch size, are recorded. All measurements are in seconds . If the batch size is 75%, then Mat is the amount of time taken to materialize 75% of the data, using regular semi-naive evaluation, + is how much incremental materialization, of 25% of the data, the remaining amount, also using semi-naive evaluation, took, and lastly, - is how much time DRED has taken to delete the 25% that has been added. This provides a comprehensive and thorough overview of the performance of DRED and semi-naive evaluation, compared to differential dataflow, which offers an alternative to both. Notably, the selection of facts in + and - can dramatically influ- ence the performance of both DRED and DD. However, conducting extensive performance estimations by running the algorithms on numerous random subsets of the data is impractical due to the extensive duration required to run the entire benchmark, coupled with the factorial number of possible permutations. Thus, we chose to just select random subsets of the data that contained 50%, 25%, 10%, 1%, and 0.1% of its original size, as update sizes. We discuss the table over each dataset and its respective pro- grams. First, for LUBM under the rdfs program, all differential reasoners exhibit a clear trend of decreasing update computation times, as the batch size increases, with diff𝐼performing much bet- ter in general, up until updates get very small, possibly indicating that at this level, indexing starts to have too big of an overhead. In the case of all other reasoners, the trend is very different, with all update times, curiously save for chibi, which is orders of magnitude slower than all other reasoners, not decreasing. This is unsurpris- ing, due to the very strong degree of recursiveness of the program, therefore showcasing that neither DRED nor semi-naive evaluation provide significant speedups over rematerialization, with the best result being for chibi𝐼, in which updates and deletions, in spite of being constant, are up to 40% faster. All reasoners perform significantly better on rdfs-s, indicating the importance of the program. Chibi’s pathological performance issue is entirely gone with the new program, and its performance discrepancy with chibi𝐼is almost eliminated, save for deletions, which remain several times slower than rematerialization.In the most complex program, owl2rl, both chibi and diff are not able to finish materialization, with the former having had taken more than 1000 seconds, and the latter exceeding 64 gigabytes of RAM. Differential performs in the same manner as the previous programs, with decreasing update times, and symmetry between additions and deletions. Both chibi𝐼and rel exhibit decreasing dele- tion reasoning times in aggressive cliffs, with little decrease for additions. The transitive closure program is simple, and linear, therefore being embarassingly simple to incrementalize. For the RAND-1k dataset, differential reasoners once again perform in the same man- ner, with incremental behavior scaling linearly with the size of the data. The same behavior is shown for all other reasoners, with a caveat, that DRED only starts to be competitive once the update size is less than 10% of the original data. For RMAT-1k, reasoning times are much longer, showcasing a significantly more complex dataset, with all non-differential reasoners struggling to provide proportional update times save for update sizes of less than 1%. In sum, diff and diff𝐼performed predictably irrespective of the dataset and program being run, always being faster, and having proportionally decreasing reasoning times for updates, while at the same time being symmetric. All other reasoners did not show the expected incremental behavior, neither for semi-naive evaluation nor DRED unless the update size was small, which is not necessarily a hindrance in practice, since rarely if ever a system will receive an update that is bigger than 10% of the original size of the data. 6.2 Peak memory usage comparison. The results of the previous subsection cannot be seen in an en- tirely positive light without there being consideration for memory usage. DD relies on multiple in-memory indexes to keep track of all changes, and as it was seen, it entirely failed a benchmark due to running out of memory, thus, in this section we analyze the results of measuring peak memory usage over the previous exper- iments. Table 4 presents the peak memory usage for each of the methods and programs across different datasets. Memory usage is presented in megabytes. LUBM1 occupies 20 megabytes of disk space, RAND-1k and RMAT-1k, respectively, 100 kilobytes. For LUBM1, with the ’rdfs’ and ’rdfs-s’ programs, all reasoners performed comparably with each other, with respect to memory usage, however, as seen on the previous table, there are major differ- ences in runtime performance between them, with the most extreme example being for chibi and diff𝐼, in which the former is over 1000x times slower, while using almost 50% more memory. Interestingly, diff performed significantly better for the owl2rl program, consum- ing 100 times less memory than chibi and rel. It is likely that this is due to the aforementioned aggressive compaction mechanism by the in-memory LSM trees. Notably, the indexed version of diff, diff𝐼, ran out of memory (OOM) for this program, indicating possible limitations of the indexing method for handling complex queries in large datasets, which conversely is not true in the case of chibi𝐼, therefore being an issue with the DD implementation in itself. In both the RAND-1k and RMAT-1k datasets, all differential reasoners consume at least twice as much memory as all other reasoners, while performing similarly for initial materialization runtime. This posits an interesting counterpoint to the dominance Matthew Stephenson Table 3: Runtime Experimental Results Dataset Program Batch diff diff𝐼chibi chibi𝐼rel Mat + - Mat + - Mat + - Mat + - Mat + - LUBM1 rdfs50% 1.47 1.43 1.40 0.47 0.48 0.49 124 530 584 0.84 1.13 1.62 0.71 1.02 1.58 75% 2.15 0.74 0.73 0.67 0.29 0.25 276 559 369 1.10 1.01 1.38 1.01 0.97 1.42 90% 2.58 0.33 0.34 0.84 0.14 0.13 397 573 168 1.40 1.02 1.22 1.26 1.03 1.42 99% 2.91 0.05 0.05 0.95 0.05 0.03 486 584 23 1.54 1.00 0.97 1.41 0.97 1.23 99.9% 2.94 0.03 0.01 0.97 0.03 0.02 487 586 5.5 1.60 1.00 1.23 1.38 0.94 1.45 100% 2.89 0 0 0.99 0 0 487 0 0 1.34 0 0 1.20 0 0 rdfs-s50% 0.84 1.11 0.92 0.27 0.29 0.35 0.72 1.2 126 0.65 1.11 1.67 0.63 1.25 1.72 75% 1.31 0.46 0.49 0.35 0.17 0.16 1.11 1.04 103 1.11 1.21 1.3 0.94 1.03 1.41 90% 1.67 0.24 0.23 0.40 0.09 0.09 1.3 1.10 54 1.12 1.08 1.2 1.26 1.16 1.32 99% 1.72 0.05 0.05 0.44 0.05 0.02 1.5 1.1 9.5 1.48 1.09 1.1 1.28 1.20 1.58 99.9% 1.65 0.03 0.02 0.45 0.03 0.02 1.5 1.0 2.9 1.39 1.10 1.0 1.46 1.32 1.52 100% 1.77 0 0 0.45 0 0 1.2 0 0 1.38 0 0 1.12 0 0 owl2rl50% 3.16 8.48 9.19 OOM OOM OOM OOT OOT OOT 31.1 85.7 55.9 32.0 88.1 16.3 75% 6.59 4.91 5.00 OOM OOM OOM OOT OOT OOT 66.8 71.7 36.4 85.1 81.3 16.1 90% 9.50 2.42 2.29 OOM OOM OOM OOT OOT OOT 114 63.5 15.1 130 70 16.3 99% 11.2 0.04 0.03 OOM OOM OOM OOT OOT OOT 114 60.2 2.52 156 34 0.60 99.9% 11.3 0.03 0.02 OOM OOM OOM OOT OOT OOT 117 73.3 1.3 161 34 0.61 100% 11.2 0 0 OOM 0 0 OOT 0 0 138 0 0 162 0 0 RAND-1k tc50% 0.06 1.07 1.02 0.03 0.08 0.10 0.03 0.48 1.08 0.01 0.13 0.17 0.01 0.13 0.13 75% 0.23 0.94 0.91 0.05 0.07 0.07 0.14 0.42 2.25 0.02 0.12 0.23 0.02 0.13 0.16 90% 0.64 0.56 0.56 0.07 0.06 0.05 0.45 0.48 5.96 0.08 0.15 0.70 0.07 0.15 0.26 99% 1.05 0.17 0.17 0.08 0.03 0.03 0.77 0.52 0.72 0.12 0.16 0.15 0.11 0.16 0.16 99.9% 1.13 0.03 0.03 0.09 0.01 0.01 0.85 0.43 0.11 0.16 0.07 0.06 0.14 0.05 0.05 100% 1.15 0 0 0.10 0 0 0.86 0 0 0.16 0 0 0.14 0 0 RMAT-1k tc50% 1.30 13.0 11.2 0.63 2.51 3.83 0.99 5.01 7.70 0.12 1.40 2.03 0.20 1.36 1.72 75% 5.29 9.22 8.59 1.51 2.13 2.57 3.71 4.52 8.84 0.57 1.67 2.06 0.61 1.54 1.84 90% 8.88 4.09 3.91 2.11 1.08 0.95 6.17 5.25 9.48 0.89 1.72 2.11 0.89 1.67 2.01 99% 12.0 0.76 0.59 2.40 0.06 0.06 8.32 5.51 10.2 1.12 1.68 2.68 1.20 1.55 2.28 99.9% 12.7 0.04 0.04 2.36 0.01 0.01 8.79 4.63 0.55 1.25 0.90 0.69 1.31 0.58 0.78 100% 12.8 0 0 2.31 0 0 8.78 0 0 1.26 0 0 1.30 0 0 Table 4: Memory usage experimental results Dataset Program diff diff𝐼chibi chibi𝐼rel LUBM1rdfs 488 466 631 941 722 rdfs-s 495 383 573 665 579 owl2rl 446 OOM 42190 29269 25450 RAND-1k tc 90 85 41 47 31 RMAT-1k tc 434 521 265 285 258 in both memory usage and runtime shown with more complex pro- grams. The reason for this discrepancy, is that the TC program has a very large number of iterations, therefore causing a significantly greater flux in the dataflow, and since each iteration implies a new difference being stored, memory usage can grow at a fast pace. While there are major differences in runtime among all reasoners, with some being orders of magnitude faster, the same cannot be said about memory usage, which save for a very large program, there are no clear winners, implying that the memory requirements forDD in itself are not greater than regular reasoners, save for highly- iterative dataflows, and remains proportional to the computation. The starkest example of this is for the owl2rl program, which in spite of containing over a hundred rules, does not output much more data than rdfs/rdfs-s. 7 CONCLUSION In this article we introduced a novel datalog reasoner, with two different algorithms, whose core value proposition is in it using the promising, but relatively obscure, DD model of computation, and evaluated it against two other reference implementations that shared as many components as reasonable. We also described an indexing method that significantly sped up a often overlooked method of implementing reasoning, the substitution method, that was shown to have solved many pathological performance issues in benchmarks, at very little cost of extra memory. In all experiments, all DD based reasoners implemented bested their non differential counterparts, showing unparalleled scalability over increasing up- date sizes, alongside virtually no performance differences between additions and retraction, while remaining competitive in memory A Differential Datalog Interpreter usage. There are multiple ways in which the work could be ex- panded in the future, such as in porting it over to support negation and more expressive variants of datalog, and most importantly, making it distributed, which DD provides out of the box.