Efficient Compilation of Regular Path Queries

Frank Tetzel, Wolfgang Lehner, Romans Kasperovics

Ad hoc code generation is a state-of-the-art processing paradigm for database execution engines. It minimizes resource consumption by generating specialized code, tailored and streamlined for the single query at hand. In this work, we apply ad hoc code generation to regular path queries (RPQs), an advanced query type in declarative graph query languages. We investigate code generation from multiple angles. We propose COAT, an embedded domain specific language (EDSL) in C++ to improve accessibility of code generation by simplifying the interaction with compiler APIs. Furthermore, we analyze and compare two back ends for COAT providing the just-in-time (JIT) compilation functionality: LLVM, a compiler framework popularly used in databases for code generation, and AsmJit, a JIT assembler with very low compilation latency. We evaluate various compilation techniques for RPQs on different synthetic graph workloads.

Datenbank-Spektrum 2020, DOI: [10.1007/s13222-020-00353-9], [BibTeX]

Graph Traversals for Regular Path Queries

Frank Tetzel, Romans Kasperovics, Wolfgang Lehner

Regular Path Queries (RPQs) are at the core of many recent declarative graph pattern matching languages. They leverage the compactness and expressiveness of regular expressions for matching recursive path structures. Unfortunately, most prior works on RPQs only consider breadth-first search as traversal strategy, neglecting other possible graph traversals like depth-first search or a combination of both. Within this paper, we conduct an analysis of graph traversals for RPQs by introducing a generalized graph traversal framework subsuming breadth-first search and depth-first search as extreme cases and thus opening up a new design space for graph traversal algorithms. We outline the underlying principles as well as provide comprehensive experimental evaluation using implementations which yield beneficial results regarding evaluation time and peak memory consumption.

GRADES-NDA 2019, DOI: [10.1145/3327964.3328494], [BibTeX]

Analysis of Data Structures involved in RPQ Evaluation

Frank Tetzel, Hannes Voigt, Marcus Paradies, Romans Kasperovics, Wolfgang Lehner

A fundamental ingredient of declarative graph query languages are regular path queries (RPQs). They provide an expressive yet compact way to match long and complex paths in a data graph by utilizing regular expressions. In this paper, we systematically explore and analyze the design space for the data structures involved in automaton-based RPQ evaluation. We consider three fundamental data structures used during RPQ processing: adjacency lists for quick neighborhood exploration, visited data structure for cycle detection, and the representation of intermediate results. We conduct an extensive experimental evaluation on realistic graph data sets and systematically investigate various alternative data structure representations and implementation variants. We show that carefully crafted data structures which exploit the access pattern of RPQs lead to reduced peak memory consumption and evaluation time.

DATA 2018, DOI: [10.5220/0006860303340343], [BibTeX]

An Analysis of the Feasibility of Graph Compression Techniques for Indexing Regular Path Queries

Frank Tetzel, Hannes Voigt, Marcus Paradies, Wolfgang Lehner

Regular path queries (RPQs) are a fundamental part of recent graph query languages like SPARQL and PGQL. They allow the definition of recursive path structures through regular expressions in a declarative pattern matching environment. We study the use of the K2-tree graph compression technique to materialize RPQ results with low memory consumption for indexing. Compact index representations enable the efficient storage of multiple indexes for varying RPQs.

GRADES 2017, DOI: [10.1145/3078447.3078458], [BibTeX]

Don't Walk Twice: Path Sharing for Regular Path Queries on Large Graphs

Frank Tetzel

SIGMOD SRC 2017, DOI: [10.1145/3055167.3055173], [BibTeX]