The ongoing demand for graph query processing has prompted supporting graph workloads inside relational engines, after all, graphs are relations. Although supporting graph processing on the top of standard relational data management systems (RDBMS) may appear reasonable, it does not perform well, in practice, since graph workloads are naturally iterative and rely extensively on efficient traversal of adjacency structures that are not typically implemented in RDBMS. On the other side, extending RDBMS with specialized adjacency structures is undoubtedly hard due to the complexity of RDBMS architecture. Along the previous lines, combining existing graph processing techniques with runtime compilation and native code generation is a promising avenue to eliminate the complexities that prevent integrating specialized graph structures with relational engines though architecting a graph query compiler is a formidable task on its own.

In this paper, we demonstrate how the idea of the first Futamura projection, which links interpreted query engines and compilers through specialization, can be applied to compile graph workloads in an efficient way that simplifies the construction of relational engines that also support graph workloads. We extend the LB2 main-memory query compiler with graph adjacency structures and operators. We implement a subset of the Datalog logical query language evaluation to enable processing graph and recursive queries efficiently. The graph extension matches, and sometimes outperforms, best-of-breed low-level graph engines.