  Modern graph database query languages such as GQL, SQL/PGQ, and their
academic predecessor G-Core promote paths to first-class citizens in the sense
that paths that match regular path queries can be returned to the user. This
brings a number of challenges in terms of efficiency, caused by the fact that
graphs can have a huge amount of paths between a given node pair.
  We introduce the concept of path multiset representations (PMRs), which can
represent multisets of paths in an exponentially succinct manner. After
exploring fundamental problems such as minimization and equivalence testing of
PMRs, we explore how their use can lead to significant time and space savings
when executing query plans. We show that, from a computational complexity point
of view, PMRs seem especially well-suited for representing results of regular
path queries and extensions thereof involving counting, random sampling,
unions, and joins.
