Compressed Graph Representations for Evaluating Regular Path Queries

Gonzalo Navarro and Josefa Robert

Regular Path Queries (RPQs) are at the core of graph database query languages like SPARQL. They consist, essentially, of regular expressions that must match the sequence of edge labels of paths in the database graph. A way to answer them is to traverse the graph and the automaton of the RPQ in synchronization, reporting the graph nodes where the automaton reaches final states. We implement this approach on top of a compact graph representation that is particularly well suited for this task. The result is an index using considerably less space and/or query time than all existing approaches.