Chapter 10Path Semantics

This chapter formalizes paths as first-class values in the GQL data model and explains how different path modes constrain the shape of walks through a graph. It describes the interaction between path modes, selective search prefixes, and accessors, and clarifies how path values are constructed, combined, and projected back into binding tables.

10.1 Modes: Walk, Trail, Simple, Acyclic

Paths in a graph. Given a graph

G = ⟨ V, E, λ_{V}, ρ_{V}, λ_{E}, ρ_{E}, src, dst, dir ⟩,

a path in $G$ is a finite alternating sequence

w = ⟨ v_{0}, e_{1}, v_{1}, \dots, e_{n}, v_{n} ⟩ \in Path (G) (n \geq 0)

such that for every $i \in {1, \dots, n}$ , the edge $e_{i}$ connects $v_{i - 1}$ and $v_{i}$ . More explicitly, if $e_{i}$ is directed, either $(src (e_{i}), dst (e_{i})) = (v_{i - 1}, v_{i})$ or $(src (e_{i}), dst (e_{i})) = (v_{i}, v_{i - 1})$ ; its orientation in the path is respectively left-to-right or right-to-left. If $e_{i}$ is undirected, its endpoints are $v_{i - 1}$ and $v_{i}$ , without a directed orientation. Which of these possibilities satisfies a particular edge pattern is determined by that pattern’s directionality constraint. We write $head (w) = v_{0}$ , $tail (w) = v_{n}$ , $| w | = n$ (number of edges), $Edges (w) = ⟨ e_{1}, \dots, e_{n} ⟩$ as a list, and $Nodes (w) = ⟨ v_{0}, \dots, v_{n} ⟩$ as a list.

Walk, trail, simple, acyclic.

$w$ is a walk always.
$w$ is a trail iff all $e_{i}$ are pairwise distinct.
$w$ is simple iff the node sequence has no repetitions except possibly that the first and last node may coincide; i.e., $v_{i} \neq v_{j}$ for all $0 \leq i < j \leq n$ with the single allowed case $i = 0, j = n$ (so $v_{0} = v_{n}$ is permitted).
$w$ is acyclic iff the node sequence has no repetitions at all (in particular $v_{0} \neq v_{n}$ unless $n = 0$ ).

For $M \in {WALK, TRAIL, SIMPLE, ACYCLIC}$ , define the mode predicate ${ok}_{M} : Path (G) \to {⊤, ⊥}$ by ${ok}_{M} (w) = ⊤$ iff $w$ obeys the restriction of $M$ . Default: unless explicitly qualified otherwise, the path mode is $WALK$ .

For example, the library-instance path $⟨ r, e_{owns}, a, e_{check}, l, e_{inc, 1}, b_{1} ⟩$ , where $e_{check}$ is the CHECK_OUT edge directed from $l$ to $a$ , is traversed from the reader through the account and loan to the first book. This path has no repeated node or edge. It is therefore a walk, trail, simple path, and acyclic path.

Concatenation of walks. For two paths

\begin{aligned} w & = ⟨ v_{0}, e_{1}, \dots, e_{n}, v_{n} ⟩ and \\ w^{'} & = ⟨ v_{0}^{'}, e_{1}^{'}, \dots, e_{m}^{'}, v_{m}^{'} ⟩ \end{aligned}

with $v_{n} = v_{0}^{'}$ , their walk concatenation is the path

w \cdot w^{'} = ⟨ v_{0}, e_{1}, \dots, e_{n}, \underset{glued}{v_{n} = v_{0}^{'} ︸}, e_{1}^{'}, \dots, e_{m}^{'}, v_{m}^{'} ⟩ .

This is a purely combinatorial operation on the walk domain and will be used when defining the semantics of regular path expressions.

10.2 Finiteness and Selection

Notation. For a set $X$ , let $P (X)$ denote its power set and $P_{fin} (X)$ its finite subsets.

For a path mode $M \in {WALK, TRAIL, SIMPLE, ACYCLIC}$ and a regular path expression $R$ , we use the preview notation

P_{M}^{R} (u, v) \in P (Path (G))

for the path projection, at endpoints $(u, v)$ , of the RPE witness denotation defined in Section 11.1. Thus its members are exactly the paths that satisfy $R$ under direction tests and the mode predicate $M$ . Selective path search prefixes ( $shortest$ , $all shortest$ , $any$ , etc.) are maps

Sel : P (Path (G)) \to P_{fin} (Path (G))

applied independently per $(u, v)$ -partition. The well-formedness rules require every unbounded quantifier to be bounded in effect by a restrictive path mode, a selective path-search prefix, or the DIFFERENT EDGES match mode; accordingly, graph-pattern evaluation returns a finite set of reduced matches.

10.3 Path Accessors and Results

Accessors on path values. Let $p \in PathVal \cup {null}$ . We write $PEL (p)$ for the path element list and $len (p)$ for the path length. Formally,

PEL (p) : = ELEMENTS (p) and len (p) : = PATH_LENGTH (p) .

Both accessors are null-propagating: if $p = null$ then $PEL (p) = null$ and $len (p) = null$ .

For a material path value $p = PATH [⟨ n_{0}, e_{1}, n_{1}, \dots, e_{k}, n_{k} ⟩]$ , the element list is exactly that alternating list and the length is the number of edges:

PEL (p) = ⟨ n_{0}, e_{1}, n_{1}, \dots, e_{k}, n_{k} ⟩ and len (p) = k .

Malformed representations (non-alternating lists or lists not starting/ending in a node reference) are outside the well-formed path domain; if encountered at runtime, they raise a malformed path data exception (rather than yielding $null$ ).

From $PEL (p)$ we derive the node and edge projections as lists:

\begin{aligned} nodes (p) & : = ⟨ x \in PEL (p) ∣ x is a node reference ⟩, \\ edges (p) & : = ⟨ x \in PEL (p) ∣ x is an edge reference ⟩ . \end{aligned}

When $p$ is material, the following cardinality equalities hold (including the case $len (p) = 0$ ):

\begin{aligned} # nodes (p) & = len (p) + 1, \\ # edges (p) & = len (p), \\ # PEL (p) & = 2 \cdot len (p) + 1 . \end{aligned}

We abbreviate the endpoints by

\begin{aligned} head (p) : = the first element of nodes (p), \\ tail (p) : = the last element of nodes (p), \end{aligned}

with the understanding that if $p = null$ (or $len (p) = null$ ) then $head (p) = tail (p) = null$ .

Path value construction and concatenation. For node/edge references $n_{i}, e_{i}$ forming a path element list $⟨ n_{0}, e_{1}, n_{1}, \dots, e_{k}, n_{k} ⟩$ ,

PATH [⟨ n_{0}, e_{1}, n_{1}, \dots, e_{k}, n_{k} ⟩]

denotes the corresponding (material) path value.

List helpers. For any finite list $L = ⟨ x_{1}, \dots, x_{m} ⟩$ with $m \geq 1$ , let

dropLast (L) : = ⟨ x_{1}, \dots, x_{m - 1} ⟩ and dropFirst (L) : = ⟨ x_{2}, \dots, x_{m} ⟩,

and let $L + + L^{'}$ denote list concatenation.

Given path values $p$ and $q$ , their value-level concatenation $p \circ q$ is defined when the last and first elements, respectively, are node reference values whose referent is the same node, and yields the path value obtained by gluing these endpoints so that the shared node occurs once. Otherwise, a malformed path exception is raised.

Formally, if either operand is $null$ , then $p \circ q = null$ . Otherwise assume

PEL (p) = ⟨ n_{0}, e_{1}, n_{1}, \dots, e_{k}, n_{k} ⟩ and PEL (q) = ⟨ n_{0}^{'}, e_{1}^{'}, n_{1}^{'}, \dots, e_{ℓ}^{'}, n_{ℓ}^{'} ⟩,

with $k, ℓ \geq 0$ . If $n_{k}$ and $n_{0}^{'}$ are not node reference values whose referent is the same node, a malformed-path exception is raised. If their referent is the same node but

card (dropLast (PEL (p))) + card (PEL (q))

exceeds the implementation-defined maximum path-element-list cardinality (IL015), data exception 22G10 is raised. Otherwise:

PEL (p \circ q) : = dropLast (PEL (p)) + + PEL (q) .

Equivalently (expanding the list and showing the glued node once):

PEL (p \circ q) = ⟨ n_{0}, e_{1}, n_{1}, \dots, e_{k}, \underset{same referent as n_{k}}{n_{0}^{'} ︸}, e_{1}^{'}, n_{1}^{'}, \dots, e_{ℓ}^{'}, n_{ℓ}^{'} ⟩ .

In particular, whenever both $p$ and $q$ are material and $p \circ q$ is defined,

len (p \circ q) = len (p) + len (q) .

When both $p$ and $q$ are material and correspond to walks $w, w^{'}$ , the operation $p \circ q$ mirrors the walk concatenation $w \cdot w^{'}$ defined above.

Result projection (from matches to values). Let a graph pattern be evaluated to a finite set of reduced matches (multi-path bindings). Projection of binding variables into a working record proceeds per variable $X$ as follows:

If $X$ is a node variable of singleton degree and is bound to a node $v$ , the projected field value is the node reference value for $v$ . If $X$ is conditional singleton and unbound, the value is $null$ . If $X$ has group degree, the projected value is the list of node reference values in the left-to-right binding order (duplicates retained).
If $X$ is an edge variable, the cases are analogous with edge reference values.
If $X$ is a path variable declared by some path pattern of the graph pattern, the projected field value is the path value $p$ whose $PEL (p)$ is the left-to-right list of graph element references in the extracted path of that binding. If the surrounding statement semantics preserves rows in which that declaring component contributes no match (e.g., OPTIONAL MATCH), then the path variable is projected as $null$ for those rows, analogously to other newly introduced binding variables.

A reference to a path variable always has singleton reference degree. Within reduced matches produced by its declaring path pattern component it is unconditionally bound; however, statement-level optionalization may yield $null$ in the output binding table for unmatched input rows.

Result typing. Let $type (X)$ denote the declared value type of the projected field for variable $X$ in the current query: Element variables. Let $X$ be an element variable. At singleton degree, $type (X)$ is an implementation-determined supertype. It contains the corresponding node/edge reference value type. At conditional singleton degree, the type additionally contains $null$ . At group degree, $type (X)$ is a group list value type of node (resp. edge) reference values.

Path variables. If $X$ is a path variable and is unconditionally exposed in the output, then $type (X)$ is the (material) path value type. If $X$ may be $null$ due to statement-level optionalization, then $type (X)$ additionally contains $null$ (i.e., it is an $Opt (Path)$ -like type in the sense of Chapter 6).

Interaction with selection and modes. For each selective path pattern, selection is applied to the candidate path bindings after evaluating any contained WHERE conditions and enforcing restrictive path modes (e.g., TRAIL, SIMPLE, ACYCLIC). Variants such as ANY SHORTEST, ALL SHORTEST, SHORTEST N PATHS, and SHORTEST N GROUPS operate on the candidates as specified and yield a finite set of retained bindings; projection then proceeds as above.

Chapter 10 — Takeaways.

Purpose: Defined paths as first-class values and fixed how path modes constrained admissible traversals.
Introduced: Path modes such as walk, trail, acyclic, and simple; admissibility conditions for each mode; path accessors that exposed length and component sequences.
Key distinctions: Allowing repetition of edges or nodes versus forbidding it under stricter modes; binding endpoints only versus binding the entire path object.
Consequences: Determined exactly what a path match could return and what the user could inspect; constrained evaluation to avoid ill-defined or explosive results where required; enabled downstream clauses to treat paths as structured values.
Bridge: Set the stage for regular path expressions as the declarative mechanism that generated these path values.