Datalog is a powerful yet elegant language that allows expressing recursive computation. Although Datalog evaluation has been extensively studied in the literature, so far, only loose upper bounds are known on how fast a Datalog program can be evaluated. In this work, we ask the following question: given a Datalog program, what is the tightest possible runtime? To this end, our main contribution is a structure-aware query evaluation technique that computes a Datalog program by first rewriting it to generate the smallest possible grounding. Using this technique we can obtain state-of-the-art theoretical runtime results. We also give some preliminary evidence that the rewriting method can lead to practical runtime improvements.
Datalog is a recursive query language that has gained prominence due to its expressivity and rich
applications across multiple domains, including graph processing [
Much prior work has sought to characterize the complexity of Datalog evaluation. The general
data complexity of Datalog is P-complete [
Endeavors to pinpoint the exact data complexity for Datalog fragments have focused on the class of
Conjunctive Queries (CQs) [
Our Contribution In [24], we address the following question: given a Datalog program , what is the tightest possible runtime as a function of the input size and the size of the active domain ?
To answer this question, we propose a general framework for evaluating based on rule rewriting. The key idea is based on the fundamental result that a grounded Datalog program (i.e., one where every rule has constants) can be evaluated in time linear w.r.t. its size. Hence, the goal of the framework is to transform into an equivalent grounded program that is as small as possible. Though constructing grounded programs naïvely is rather straightforward, we show that groundings of smaller size are attainable via rewriting using tree decomposition techniques. We apply our framework to prove state-of-the-art and new results for practical Datalog fragments (e.g. linear Datalog).
This paper summarizes the key results from [24] and seeks to experimentally evaluate the idea of rewriting a Datalog program to obtain the smallest possible grounding. We show that the rewriting can often lead to significant speed-ups in evaluation.
Datalog consists of a set of rules over a set of extensional and intensional relations (simply referred to as EDB and IDB respectively, henceforth). EDBs correspond to relations in a given database, each comprising a set of EDB tuples, whereas IDBs are derived by the rules. The head of each rule is an IDB, and the body of the rule consists of zero or more EDBs and IDBs as a Conjunctive Query defining how the head IDB is derived. We illustrate with the example of transitive closure on a binary EDB R denoting edges in a directed graph, a single IDB T, and two rules:
T(, ) ← T(, ) ←
R(, ).
R(, ), T(, ).
For every Datalog program, we will assume that there is a unique IDB that we identify as the target (or output) of the program. We use arity( ) to denote the maximum number of variables contained in any IDB of a program . We say that a Datalog program is monadic if every IDB is unary; a Datalog program is linear if the body of every rule contains at most one IDB. A chain Datalog program is a program where every rule has the following form:
T(1, +1) ←
T1(1, 2), T2(2, 3), . . . , T(, +1).
A chain Datalog program corresponds to a Context-Free Grammar (CFG).
We use to denote the sum of sizes of the input EDB relations to a Datalog program. We use to denote the size of the active domain of EDB relations (i.e., the number of distinct constants that occur in the input). We assume data complexity, i.e. the program size (the total number of predicates and the variables) is a constant. We use the standard word-RAM model with (log )-bit words and unit-cost operations for all complexity results.
In this section, we sketch the main results from [24] on structure-aware Datalog rewriting. The readers may refer to [24] for the formal algorithm and analysis. Our first result considers Datalog programs that are rulewise-acyclic. A rule is said to be acyclic if the body of the rule, viewed as a Conjunctive Query, admits a join tree. We say that a program is rulewise-acyclic if it has only acyclic rules. Theorem 3.1 ([24]). Let be a rulewise-acyclic Datalog program with input size , active domain size , and arity . Then, we can evaluate in time (− 1 · ( + )).
We give below an example of how our algorithm for the theorem works, using even-hop backward reachability in directed graphs: sink(). edge(, ), edge(, ), evenPath().
Both rules here are acyclic, and the arity is = 2. Observe that producing directly all groundings of the second rule would generate a grounded program of size ( · ). Our algorithm first rewrites the second rule following the structure of its join tree: oddPath() ←
Now grounding the resulting rules will produce a grounded program of only size (), which implies an evaluation algorithm with runtime (). In fact, a direct corollary of Theorem 3.1 is that for monadic acyclic Datalog we have a linear runtime of (), which is essentially optimal.
Theorem 3.1 can be generalized from acyclic rules to rules bounded by submodular width. Theorem 3.2 ([24]). Let be a Datalog program where arity( ) ≤ , subw is the maximum submodular width across all rules of , and suppose the input size is , and the active domain size is . Then, we can evaluate in time ̃︀(− 1 · (subw + · subw)), where ̃︀ hides a polylogarithmic factor.
As an example, consider the following Datalog program, which computes a diamond-pattern reachability starting from some node set source():
T() ← T() ← source().
T(), edge(, ), edge(, ), edge(, ), edge(, ).
For this program, the submodular width of the second rule is 3/2. Further, its arity is = 1. Thus, we can evaluate the above program in time ̃︀(3/2).
As a corollary of Theorem 3.2, monadic Datalog (i.e. when = 1) can be evaluated in time ̃︀(subw).
This is also the best-known runtime for Boolean Conjunctive Queries [
When the rules in the Datalog program are linear, we can obtain even stronger runtime results. Theorem 3.3 ([24]). Let be a linear and rulewise-acyclic Datalog program with input size , active domain size , and arity ≤ 2. Then, we can evaluate in time ( · ).
Theorem 3.4 ([24]). Let be a linear Datalog program with input size , active domain size , arity ≤ , and submodular width subw. Then, we can evaluate in time (− 1 · subw− 1 · ( + )).
In this section, we demonstrate that our rewriting technique can result in significant runtime speed-ups in practice. We ran all our experiments on a bare-metal single-node virtual machine on Cloudlab [25] that has two Intel E5-2683 v3 14-core CPUs and 256GB main memory.
We test our structure-aware rewritings via three programs on Soufflé. Soufflé [
edge(, ), sg(, ), edge(, ). sg(, ) ← sg(, ) ← fatherOf(, ) ← fatherOf(, ), edge(, ). edge(, ), edge(, ), ̸= .
edge(, ), sg(, ). (2) (3) (4) (5) Dataset G5k G10k wiki-Vote ego-Twitter web-Stanford soc-Livejournal 2 even-hop backward reachability and its rewriting (both outlined in Section 3), and 3 diamondpattern reachability (3) (it is not rulewise-acyclic) and its rulewise-acyclic rewriting as follows: T() ← source().
Z(, ) ← T(), edge(, ), edge(, ).
W(, ) ← T(), edge(, ), edge(, ).
T() ← Z(, ), W(, ). (6)
We use graph datasets (wiki-Vote, ego-Twitter, web-Stanford and soc-Livejournal) from the Stanford Large Network Dataset Collection [28] as program inputs. The G5k and G10k datasets are random graphs of 5 and 10 nodes sampled from the Erdős-Rényi model [29], where each edge exists with probability 0.001. All datasets are listed in Table 1. Whenever necessary, we randomly sample 100 nodes from the graph and designate them as the source nodes source() or the sink nodes sink().
Table 2 summarizes the runtime results on Soufflé. We find a consistent 2.5 up to ~20x speed-up on the first two programs. In the last row, one regression (~ 5x slowdown) is observed on web-Stanford because the final result set is small but the introduced Z(, ), W(, ) IDBs are very large and hence expensive to materialize in the rewritten Soufflé program (6).
We propose a structure-aware rewriting technique that allows us to obtain and even refine the bestknown theoretical runtime results. The theoretical results are based on our recent PODS 2024 publication [24]. In addition, our rewriting exhibits significant speed-ups on Soufflé across multiple recursive graph workloads. Future directions include an in-depth understanding of the tightness of our results and a more comprehensive investigation of the practicality of our technique in modern Datalog engines like Soufflé. 48–53
LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 19:1–19:20. [24] H. Zhao, S. Deep, P. Koutris, S. Roy, V. Tannen, Evaluating datalog over semirings: A groundingbased approach, Proc. ACM Manag. Data 2 (2024) 90. [25] Cloudlab, https://www.cloudlab.us/, 2018. [26] F. Bancilhon, D. Maier, Y. Sagiv, J. D. Ullman, Magic sets and other strange ways to implement logic programs, in: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, 1985, pp. 1–15. [27] Z. Fan, S. Mallireddy, P. Koutris, Towards better understanding of the performance and design of datalog systems., Datalog 2 (2022) 166–180. [28] J. Leskovec, A. Krevl, SNAP Datasets: Stanford large network dataset collection, http://snap.
stanford.edu/data, 2014. [29] D. A. Bader, K. Madduri, Gtgraph: A synthetic graph generator suite (2006).