Navigational query languages for graph databases allow to recursively traverse
the edges of a graph while checking for the existence of a path that satisfies
certain regular conditions. The basic building block of such languages is the
class of regular path queries (RPQs), which are expressions that compute the
pairs of nodes that are linked by a path whose label satisfies a regular
expression. RPQs are often extended with features that turn them more flexible
for practical applications, e.g., with the ability to traverse edges in the
backward direction (RPQs with inverses) or to express arbitrary patterns over
the data (conjunctive RPQs).