Sun 23 Jun 2019 12:00 - 12:20 at 106C - Graphs and Streams

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.

Sun 23 Jun
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

11:20 - 12:20: DBPL 2019 - Graphs and Streams at 106C
dbpl-2019-papers11:20 - 11:40
Mohammad Amin FarvardinPSL, Université Paris-Dauphine, LAMSADE, Dario Colazzo, Khalid BelhajjamePSL, Université Paris-Dauphine, LAMSADE, Carlo Sartiani
dbpl-2019-papers11:40 - 12:00
Lars KrollKTH Royal Institute of Technology, Sweden, Klas SegeljaktKTH, Paris CarboneKTH, Sweden, Christian SchulteKTH Royal Institute of Technology, Sweden, Seif Haridi
Pre-print Media Attached
dbpl-2019-papers12:00 - 12:20
Ruby TahboubPurdue University, Xilun WuPurdue University, Gregory Essertel, Tiark RompfPurdue University