Compact Path Representations for Graph Database Pattern Matching

Modern graph database query languages such as GQL, SQL/PGQ, and Cypher allow regular path queries to return entire paths, as opposed to only their endpoints. This is challenging for query evaluation, since a graph can have an exponential number of paths between a given node pair. This means that intermediate query evaluation results can be huge. We recently introduced the concept of path multiset representations (PMRs) 1, which can represent multisets of paths exponentially succinctly and therefore bring significant advantages for representing intermediate results. As shown in our experiments, they can speed up regular path query evaluation with several orders of magnitude.