GoKawiilOptimizing Datalog for the GPU Yihao Sun, Ahmedur Rahman Shovon, Thomas Gilray, Sidharth Kumar, and Kristopher Micinski ASPLOS'25
Datalog Primer
Datalog source code comprises a set of relations, and a set of rules.
A relation can be explicitly defined with a set of tuples. A running example in the paper is to define a graph with a relation named edge :
Edge(0, 1) Edge(1, 3) Edge(0, 2)
A relation can also be implicitly defined with a set of rules. The paper uses the Same Generation (SG) relation as an example:
1: SG(x, y) <- Edge(p, x), Edge(p, y), x != y 2: SG(x, y) <- Edge(a, x), SG(a, b), Edge(b, y), x != y
Rule 1 states that two vertices ( x and y ) are part of the same generation if they both share a common ancestor ( p ), and they are not actually the same vertex ( x != y ).
Rule 2 states that two vertices ( x and y ) are part of the same generation if they have ancestors ( a and b ) from the same generation.
“Running a Datalog program” entails evaluating all rules until a fixed point is reached (no more tuples are added).
... continue reading