Chapter 11Regular Path Expressions

Regular path expressions (RPEs) describe constrained walks through a graph and form the declarative core of GQL’s path-matching capabilities. In this chapter, we fix a precise syntax for RPEs, use an auxiliary witness semantics that can record explicit multiset alternation, and connect this semantics to the family of selective shortest-path operators. Graph-pattern evaluation itself returns a set of reduced matches, as specified in Chapter 7.

11.1 Syntax and Denotation

Syntax. Fix a graph $G=⟨V,E,\dots <!--\; FUNCTION\; APPLICATION\; -->⟩$ and a finite alphabet ${\mathrm{\Sigma }}_L\subseteq 𝕃$ of edge-label names. RPEs are generated by:

where $\ell \in {\mathrm{\Sigma }}_L$, $m,n\in \mathbb{N}\cup \{\infty \}$ with $m\le n$, $[\nu ]$ is a node test to be satisfied at the current node, and $\{\eta \}$ and ${\{\eta \}}^{-1}$ are edge tests to be satisfied by the next directed edge consumed in forward and backward orientation, respectively (see below). Here $\nu :V\to \{\top <!--\; FUNCTION\; APPLICATION\; -->,\perp \}$ is a two-valued node predicate and $\eta :E\to \{\top <!--\; FUNCTION\; APPLICATION\; -->,\perp \}$ is a two-valued edge predicate.

Concrete syntax for path expressions. At the concrete-syntax level, regular path expressions appear inside $⟨$path pattern$⟩$ constructs and are written using infix alternation, concatenation by juxtaposition, and postfix quantifiers. Parenthesized subexpressions may carry an attached WHERE clause whose search condition is local to the component. The following simplified BNF captures the backbone of this concrete syntax. Here element-pattern is an abstract interface for a node or edge pattern; its role in path patterns is described in Section 7.2.

path-expr    ::= path-term
               | path-term "|" path-term ( "|" path-term )*
               | path-term "|+|" path-term ( "|+|" path-term )*
path-term    ::= path-factor+          /* concatenation */
path-factor  ::= path-primary [ quantifier ]
path-primary ::= element-pattern
               | "(" [ subpath-var "=" ] path-expr
                     [ where-clause ] ")"
quantifier   ::= "?"
               | "*"
               | "+"
               | "{" int "}"
               | "{" [ int ] "," [ int ] "}"
where-clause ::= "WHERE" search-condition
subpath-var  ::= identifier
element-pattern  ::= node-pattern | edge-pattern
node-pattern     ::= ...  /* node test and optional binding */
edge-pattern     ::= ...  /* edge step, tests, and optional binding */
search-condition ::= ...  /* boolean expressions */

Informally, path-expr corresponds to the abstract $r$-grammar above, with "|" realizing set alternation, the GQL multiset-alternation token "|+|" realizing ${\cup }_{\mathrm{ms}}$, juxtaposed path-factors realizing concatenation, and the quantifier forms mapping to $r^{\ast }$, $r^{m..n}$, and their common shorthands. A subpath variable is a graph-pattern variable used to distinguish reduced matches for multiset alternation; it is not bound to a value and cannot be referenced.

For example, the expression $\mathrm{OWNS}\cdot {\mathrm{CHECK}\text{\_}\mathrm{OUT}}^{-1}\cdot \mathrm{INCLUDES}$ accepts the library-instance path from the reader through the account and loan to either book.

For every quantified or questioned path primary, the simply contained primary shall have minimum path length greater than zero. In particular, ${𝜀}^{\ast }$ and any other repetition of a zero-edge primary belong to the auxiliary calculus but are not well-formed concrete GQL path patterns. This condition prevents a single zero-edge witness from acquiring infinitely many derivations through different repetition counts.

Important At the level of path witnesses alone (i.e., when one forgets how variables are exposed by element patterns), the postfix quantifier "?" behaves like the bounded repetition $\{0,1\}$: it admits either zero or one occurrence of the subexpression. However, when "?" is applied to a path-primary that contains element-patterns with bindings, GQL assigns it the status of a questioned path-pattern primary in the sense of Chapter 7. In particular, the propagation of variable exposure degrees for "?" is not in general identical to treating it as a mere abbreviation for $\{0,1\}$: singleton-variable exposure becomes conditional due to the zero-iteration branch, while group-variable exposure is preserved as specified in Table 7.1. Thus, in this book we treat "?" as syntactic sugar for $\{0,1\}$ only in the purely language-theoretic sense of accepted path witnesses, not as an identity of the variable-exposure meta-theory.

An element-pattern contributes a single step (possibly with tests on nodes and edges), while a parenthesized path-expr with an optional WHERE clause behaves as a grouped subpattern whose search condition is evaluated prior to any selective path-search prefix. A non-selective component may use a non-local reference of singleton degree; a selective path pattern may not reference a graph-pattern variable declared outside it.

Step predicates and step relations (for element patterns). To connect the abstract RPE syntax above with the concrete element-pattern constructs, we use a generalized notion of a step predicate.

Step predicates. A step predicate $\delta$ is a quadruple

where $\mathrm{orient}\in \{\to ,\leftarrow ,\leftrightarrow \}$ selects forward/backward/undirected traversal (query-time), distinct from the graph attribute $\mathrm{dir}(e)\in \{\to ,\leftrightarrow \}$ (data-time directedness); ${\Phi }_e$ is a Boolean predicate over $(e,{\lambda }_E(e),{\rho }_E(e))$; and ${\Phi }_{\mathrm{src}},{\Phi }_{\mathrm{dst}}$ are Boolean predicates over endpoint vertices (their labels/properties). Predicates evaluate in the three-valued logic of Section 8.3; $U$ counts as failure for step selection. Reading an absent property yields $\mathrm{null}$ when its declared property type is nullable; for a material property type it raises 22G03. A surrounding predicate may then evaluate to $U$ as a consequence of a null value.

Step relation. The graph-induced ternary relation $S_{\delta }\subseteq V\times E\times V$ is defined as

Intuition: forward and backward steps match directed edges in the indicated orientation, while the undirected step $\leftrightarrow$ matches an undirected edge in either traversal direction. Edge-pattern variants that admit more than one orientation use the union of the corresponding cases.

Example (one library step). For the library instance, let

Since $e_{\mathrm{inc},1}$ is directed from $l$ to $b_1$ and has this label,

Label and predicate atoms as special cases. The abstract atoms $\ell$, ${\ell }^{-1}$, and $\{\eta \}$ can be seen as notational shorthands for specific step predicates:

• $\{\eta \}$ corresponds to the forward step predicate ${\delta }_{\eta }=(\to ,{\Phi }_e,\top <!--\; FUNCTION\; APPLICATION\; -->,\top <!--\; FUNCTION\; APPLICATION\; -->)$ with ${\Phi }_e(e)=\top <!--\; FUNCTION\; APPLICATION\; -->$ iff $\eta (e)=\top <!--\; FUNCTION\; APPLICATION\; -->$.
• ${\{\eta \}}^{-1}$ corresponds to the backward step predicate ${\delta }_{{\eta }^{-1}}=(\leftarrow ,{\Phi }_e,\top <!--\; FUNCTION\; APPLICATION\; -->,\top <!--\; FUNCTION\; APPLICATION\; -->)$ with the same edge test.
• $\ell$ corresponds to the forward label-step predicate ${\delta }_{\ell }=(\to ,{\Phi }_e,\top <!--\; FUNCTION\; APPLICATION\; -->,\top <!--\; FUNCTION\; APPLICATION\; -->)$ with ${\Phi }_e(e)=\top <!--\; FUNCTION\; APPLICATION\; -->$ iff $\ell \in {\lambda }_E(e)$.
• ${\ell }^{-1}$ corresponds to the backward label-step predicate ${\delta }_{{\ell }^{-1}}=(\leftarrow ,{\Phi }_e,\top <!--\; FUNCTION\; APPLICATION\; -->,\top <!--\; FUNCTION\; APPLICATION\; -->)$ with the same label test.

We keep the explicit equations for these atoms below to make the endpoint orientation transparent; undirected steps are represented by the $\mathrm{orient}=\leftrightarrow$ case of $S_{\delta }$.

Ternary denotation with bag semantics. For the fixed graph $G$ and mode $\mathrm{mode}$, the denotation of $r$ is a (possibly infinite) bag of endpoint-labeled path witnesses:

Its support consists of triples $(u,w,v)$ such that $\mathrm{head}(w)=u$, $\mathrm{tail}(w)=v$, ${\mathrm{ok}}_{\mathrm{mode}}(w)=\top <!--\; FUNCTION\; APPLICATION\; -->$, and $w$ matches $r$ by the rules below.

Important (bag meaning). The multiplicity $\mathit{⟦r}{⟧}_G^{\mathrm{mode}}(u,w,v)$ counts the number of derivations (proof trees) of the judgment “$w$ matches $r$ from $u$ to $v$” induced by the inductive clauses (alternation may add multiplicities; concatenation multiplies and sums over intermediate endpoints; repetition sums over iteration depth). Consequently, the same triple $(u,w,v)$ may occur with multiplicity $>1$ when the expression admits multiple decompositions producing the same witness $w$ (e.g., due to explicit multiset duplication such as $r{\cup }_{\mathrm{ms}}r$, or due to different decompositions in iterated constructs). This derivation count is auxiliary bookkeeping. Ordinary alternation and the final graph-pattern result are set-valued; only distinctions introduced by explicit multiset alternation are intended to survive as distinct reduced matches.

Conformance note. GQL distinguishes the ordinary vertical-bar alternation, which has set semantics, from a multiset-sensitive alternation form. Accordingly, the unsubscripted abstract constructor $r_1\cup r_2$ denotes set alternation; ${\cup }_{\mathrm{ms}}$ is used only for the explicit multiset-alternation form.

For a bag $B$, define its setification by

If one needs set semantics (“distinct path witnesses”) for the overall result of an RPE, it can be obtained either by setification $\mathrm{setify}$ or, equivalently, by taking the support $\mathrm{supp}(\mathit{⟦r}{⟧}_G^{\mathrm{mode}})$ as a post-processing step.

Base cases. (All bags below assign multiplicity $1$ to each listed triple.)

Inductive cases. Here and in the sequel, ${\uplus <!--\; FUNCTION\; APPLICATION\; -->}_k{B}_k$ denotes the iterated bag union of bags $B_k$, obtained by pointwise addition of multiplicities.

We write bag-join on the middle endpoint with path concatenation as ${⋊⋉}_{\bowtie }$, where $\bowtie$ combines two compatible triples by concatenating their path witnesses:

Formally, for bags $B_1,B_2\in \mathcal{M}(V\times \mathrm{Path}(G)\times V)$, define

We also use the mode filter, which rejects witnesses not admissible under the chosen path mode:

Alternation. We distinguish explicitly:

Unless stated otherwise, we interpret the abstract constructor $(r_1\cup r_2)$ as ${\cup }_{\mathrm{set}}$, matching concrete "|". Only the distinct multiset-alternation token is interpreted as ${\cup }_{\mathrm{ms}}$.

Concatenation and repetition. Concatenation composes the witnesses produced by its two operands. A witness of $r_1$ ending at some node $x$ may be combined with a witness of $r_2$ starting at the same node $x$. The resulting witness is obtained by concatenating the two paths, while its multiplicity is the product of the multiplicities of the component witnesses. Contributions obtained through different intermediate nodes or different decompositions of the same path are then added by the bag join defined above.

Although each operand has already been evaluated under the selected path mode, their concatenation need not itself satisfy that mode. For example, two individually admissible path witnesses may, after concatenation, repeat an edge or a node forbidden by the selected mode. The mode filter is therefore applied again to the composed witnesses:

To define repetition, we first define the $k$-fold concatenation of an expression $r$. The zeroth power denotes the empty path at each node and is therefore identified with the semantics of $𝜀$:

For $k\ge 0$, the $(k+1)$-st power is obtained by concatenating one additional witness of $r$ with a witness of its $k$-th power. As in ordinary concatenation, the resulting path is filtered according to the selected path mode:

Consequently, $\mathit{⟦r}{⟧}_G^{\mathrm{mode},k}$ contains the path witnesses formed from exactly $k$ successive occurrences of $r$, with their bag multiplicities determined by all admissible decompositions into $k$ component witnesses.

For a well-formed concrete GQL quantified primary, every occurrence of $r$ consumes at least one edge. Hence a witness of length $L$ can arise only from repetition counts $k\le L$, and its multiplicity cannot become infinite by summing over repetition depths. Expressions that violate the positive minimum-path-length condition, such as ${𝜀}^{\ast }$, are excluded from the concrete language.

The Kleene-star expression collects the witnesses obtained for every finite number of repetitions:

Thus, the result includes the empty-path witnesses contributed by $k=0$, as well as witnesses formed by one or more occurrences of $r$. Because the outer operation is bag union, the multiplicity of a witness records the total number of derivations of that witness across all repetition counts and all admissible decompositions.

Finally, for bounds $m\in \mathbb{N}$ and $n\in \mathbb{N}\cup \{\infty \}$ with $m\le n$, bounded repetition retains only the powers whose repetition counts lie in the specified interval:

When $n=\infty$, the expression denotes lower-bounded repetition; when $m=n$, it denotes exactly $m$ repetitions. In particular, $r^{0..\infty }$ coincides with $r^{\ast }$.

Reversal of expressions. Define the reversal $r^{\top <!--\; FUNCTION\; APPLICATION\; -->}$ recursively by

This witnesses symmetry of undirected matching and is used in bidirectional expansions.

Guards over intermediates. Let $\psi$ be a Boolean predicate on paths, with type

It is built from node/edge predicates with quantifiers $\forall <!--\; FUNCTION\; APPLICATION\; -->,\exists <!--\; FUNCTION\; APPLICATION\; -->$ over position indices. For $B\in \mathcal{M}(V\times \mathrm{Path}(G)\times V)$, define

and define a guarded expression $r\&\psi$ by

Intent: $r\&\psi$ is a semantic shorthand for a parenthesized path pattern with an attached WHERE clause that uses only the component’s local variables.

11.2 Shortest-Path Semantics

Candidates and endpoint partitions. Fix a graph $G$ and a path mode $\mathrm{pm}$ such that

For a regular path expression $R$, let $\mathrm{Cand}(R,\mathrm{pm})$ be the set of candidate path matches admitted by the auxiliary denotation and the chosen path mode. More precisely, let $\mathrm{Der}(R,\mathrm{pm})$ be the set of successful derivation trees. For $d\in \mathrm{Der}(R,\mathrm{pm})$, write $(u_d,w_d,v_d)$ for its endpoint/path triple and ${\chi }_{\mathrm{sp}}(d)$ for its trace of subpath markers introduced by explicit multiset alternation. Define

For a candidate class $c={[d]}_{{\equiv }_{\mathrm{sp}}}$, define

This is well-defined because equivalent derivations have the same endpoint/path triple. Thus ordinary derivational duplicates are identified, while branch distinctions introduced by explicit multiset alternation remain distinct, as represented in the standard by subpath markers. For $u,v\in V$, write the endpoint partition

Below, ${\mathrm{\Pi }}_{u,v}$ abbreviates this partition for the fixed $R$ and $\mathrm{pm}$. Every path-search selector acts endpoint-locally on these sets and returns the set union of its per-partition results.

Example (one endpoint partition). For the library instance, take $R_{\mathrm{inc}}=\mathrm{INCLUDES}$ and $\mathrm{pm}=\mathrm{WALK}$, and let

If $c_{\mathrm{inc},1}$ is the candidate represented by the successful derivation whose endpoint/path triple is $(l,w_{\mathrm{inc},1},b_1)$, then

Length and groups. Let $\mathrm{len}(w)$ denote the number of edge-steps in $w$. For a fixed partition ${\mathrm{\Pi }}_{u,v}$, define its length-groups by

Groups are ordered by the key $k$ in increasing order. We write

when ${\mathrm{\Pi }}_{u,v}\ne \varnothing$.

Selective path-search operators. A path-search prefix in this abstraction is one of:

where $N\in {\mathbb{Z}}_{>0}$. Except for $\mathrm{ALL}\mathrm{PATHS}$, these are selective prefixes. Their denotation is a partition-wise selection operator ${\mathrm{SPSP}}_s(\cdot )$ over $\mathrm{Cand}(R,\mathrm{pm})$, defined as follows.

All paths (non-selective).

Any $N$ paths per endpoints. For each $(u,v)$, if $\left|{\mathrm{\Pi }}_{u,v}\right|\le N$, keep ${\mathrm{\Pi }}_{u,v}$; otherwise choose an implementation-dependent subset ${\mathrm{pick}}_N({\mathrm{\Pi }}_{u,v})\subseteq {\mathrm{\Pi }}_{u,v}$ of cardinality $N$.

Counted shortest $N$ paths per endpoints. Within each ${\mathrm{\Pi }}_{u,v}$, order candidates by nondecreasing path length; ties may be resolved in an implementation-dependent manner. Return up to $N$ candidates from the front of this order.

where ${\mathrm{takeShortest}}_N({\mathrm{\Pi }}_{u,v})\subseteq {\mathrm{\Pi }}_{u,v}$ and $|{\mathrm{takeShortest}}_N({\mathrm{\Pi }}_{u,v})|=\min <!--\; FUNCTION\; APPLICATION\; -->\{N,|{\mathrm{\Pi }}_{u,v}|\}$.

Counted shortest $N$ groups per endpoints. Within each ${\mathrm{\Pi }}_{u,v}$, take the groups ${\mathcal{G}}_{u,v}(k)$ in increasing $k$. Return the set union of the first $N$ nonempty groups (or all of them if fewer exist):

Named shorthands and defaults. The following equivalences and defaults hold:

Well-formedness and finiteness. If a selective prefix declares $N\le 0$ it is an error. Every quantified or questioned path-pattern primary has positive minimum path length. For each unbounded quantifier, a restrictive mode $\mathrm{TRAIL}$, $\mathrm{ACYCLIC}$, or $\mathrm{SIMPLE}$, a selective prefix, or the graph pattern’s DIFFERENT EDGES match mode is required. A restrictive mode or DIFFERENT EDGES makes the admissible match set finite; a selective prefix may start from an infinite candidate set but returns a finite selected set.