Compact Path Representations for Graph Database Pattern Matching

Compact Path Representations for Graph Database Pattern Matching

연구 분야: Databases

학회: 2024 IEEE 40th International Conference on Data Engineering Workshops (ICDEW)

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.