Chapter 07Patterns and Matching

This chapter formalizes the graph-pattern layer of GQL, which provides the primary mechanisms for selecting, relating, and constraining graph elements. We present the syntax of path and graph patterns, the scoping and safety conditions for variables, and the matching semantics that turn patterns into binding tables over a given graph.

7.1 Graph Patterns

A graph pattern is the central declarative object used by GQL to describe which parts of a property graph are to be selected, related, and exposed as bindings. Intuitively, a graph pattern specifies a finite syntactic description of a possibly large set of graph configurations: nodes, edges, paths between nodes, labels, properties, directions, and additional predicates that must be satisfied by the matched graph elements.

In this chapter, we treat a graph pattern as a structured expression whose primary components are path patterns. A path pattern describes an admissible path-shaped configuration in the graph, while a graph pattern combines one or more such path patterns and constrains their joint matches. Thus, graph patterns form the bridge between the graph-theoretic layer of the data model and the binding-table layer used by the query algebra. Concrete rigid and conjunctive graph patterns are used in Section 4.4.

Path and multi-path bindings. A path binding is a sequence whose entries associate variables or internal pattern markers from one path pattern with graph elements. A multi-path binding for a graph pattern is a tuple containing one path binding produced by each of its path-pattern components.

Abstract form. Let $PPat$ denote the set of well-formed path patterns. We write $GPat$ for the set of well-formed graph patterns. Abstractly, a graph pattern $\Gamma \in GPat$ has the form

where:

• $mm$ is an optional match mode, controlling whether repeated element bindings or repeated edge bindings are admitted;

• $P_1,\dots <!--FUNCTION\; APPLICATION-->,P_n\in PPat$ are the path-pattern components of the graph pattern;

• $kc$ is an optional keep clause, used to determine which path bindings are retained when path selection is applied at the graph-pattern level;

• $\phi$ is an optional graph-pattern search condition, corresponding to a WHERE clause.

The following simplified BNF captures the syntactic spine used in this chapter:

graph-pattern     ::= [ match-mode ] path-pattern-list
                      [ keep-clause ]
                      [ graph-pattern-where-clause ]

match-mode        ::= "REPEATABLE" element-bindings-or-elements
                    | "DIFFERENT" edge-bindings-or-edges

path-pattern-list ::= path-pattern { "," path-pattern }

keep-clause       ::= "KEEP" path-prefix

graph-pattern-where-clause
                  ::= "WHERE" search-condition

The full grammar contains additional syntactic refinements, but this abstraction is sufficient for the semantic development below: a graph pattern is a list of path patterns equipped with optional global controls over repetition, path selection, and filtering.

If a KEEP clause is present, its path-pattern prefix is distributed to every path pattern by the syntactic transformation specified for a graph pattern; those path patterns may not already contain a path-search prefix. The KEEP clause is then removed. If no match mode is written, the match mode is implementation-defined. REPEATABLE ELEMENTS imposes no cross-pattern repetition filter, whereas DIFFERENT EDGES retains only multi-path bindings in which no graph edge is bound at two different positions.

Path-pattern components. Each path pattern $P_i$ is evaluated against the current property graph and produces candidate path bindings. These bindings assign graph elements to the variables declared inside the corresponding path pattern. When a graph pattern contains several path patterns, the individual candidate bindings are combined by compatibility on shared variables. Shared variables therefore play the role of joins between path-pattern components.

For example, in a pattern consisting of two path patterns

the variable $b$ is shared. A graph-pattern match must therefore choose bindings for both path patterns such that the end node of the first component and the start node of the second component are the same graph element. In this sense, graph patterns generalize ordinary edge-pattern matching to joined path-shaped constraints.

Graph-pattern variables. Variables declared in graph patterns are called graph-pattern variables. They include element variables, which range over nodes or edges, and path variables, which range over path values. For a graph pattern $\Gamma$, we write

for the finite set of graph-pattern variables declared by $\Gamma$. We distinguish:

• node variables, bound to nodes;

• edge variables, bound to edges;

• path variables, bound to path values computed during matching;

• subpath variables, declared at the head of a parenthesized path pattern but not bound to a value and not referenceable; they distinguish reduced matches for multiset alternation.

Let ${vars}_{bind}(\Gamma )$ be the node, edge, and path variables of $\Gamma$, and let

where ${vars}_{exp}(\Gamma )$ is the set of variables exposed by the pattern. Only binding variables (node, edge, and path variables) can contribute columns to the resulting binding table. Anonymous node and edge positions participate in matching without declaring graph-pattern variables; they and temporary symbols are removed during reduction.

Local and global constraints. A graph pattern may contain constraints at two different levels. First, local constraints occur inside node patterns, edge patterns, and parenthesized path patterns. These include label tests, property tests, direction constraints, and locally scoped predicates. Second, a graph pattern may contain a global WHERE clause whose search condition is evaluated after the path-pattern components have produced compatible bindings.

We therefore distinguish:

where ${\phi }_{loc}$ denotes constraints evaluated during local path-pattern matching, while ${\phi }_{glob}$ denotes the graph-pattern search condition applied to the combined bindings of the graph pattern. This distinction is important for selective path search: local predicates may reduce the candidate paths before selective search is applied, whereas the global WHERE clause filters already combined matches.

Reduced matches. The immediate semantic result of a graph pattern is a set of reduced matches. A raw match may contain temporary symbols, anonymous element positions, and auxiliary information introduced by the machinery of path-pattern evaluation. Reduction removes these internal artefacts and keeps only the information that is semantically relevant for subsequent query processing.

We write

for the reduced matches of a graph pattern $\Gamma$ over a property graph $G$. The value-bearing component $\mu$ of a reduced match is a finite assignment, possibly structured, from the exposed binding variables of $\Gamma$ to graph elements, path values, or groups of such values:

Here $𝕍$ includes reference values for graph elements and constructed path values. A reduced match may additionally retain non-referenceable subpath-marker information used to distinguish the branches of multiset alternation; that information is not a value assignment in $\mu$. We write $REDUCE(m)$ for the reduction of a raw match $m$: it removes temporary symbols and anonymous structure and retains the exposed binding information described above. Thus the notation is available before it is used in the staged matching account below.

From graph patterns to binding tables. Graph-pattern matching itself is not the final query result. The reduced matches are subsequently lifted to a binding table whose columns correspond to the exposed binding variables of the pattern, possibly restricted by an explicit YIELD clause. At the level of this chapter, we separate these two steps:

The first step is graph-pattern matching; the second step is binding-table formation. This separation is useful because the same graph-pattern machinery is used by different language constructs: ordinary MATCH statements, OPTIONAL MATCH statements, nested match blocks, and predicates such as EXISTS.

Role in the query pipeline. Within a linear query statement, a graph pattern is evaluated relative to the current working graph and the current working table. Existing bindings may be used to correlate the pattern with earlier query clauses, and newly introduced bindings extend the working table. Thus, graph patterns provide the graph-facing part of the language, while binding-table operations provide the algebraic part: selection, projection, joins, grouping, aggregation, and ordering.

The remainder of this chapter develops this pipeline in stages. We first specify the syntax of path patterns and their path-specific controls. We then define variable exposure and safety conditions, describe the matching pipeline, and finally explain how matches are represented as binding tables and consumed by MATCH statements.

7.2 Pattern Syntax

A path pattern is a declarative description of a family of admissible paths between graph elements (nodes and edges) in a graph pattern, together with bindings for their endpoints and, optionally, for the path value itself. It consists of: (1) an optional path variable declaration, (2) an optional prefix specifying the path mode and, optionally, a selective search prefix, and (3) a pattern expression built recursively from element patterns (nodes and edges), with quantification/alternation/concatenation.

Path modes. A path mode determines which repetitions of graph elements are permitted in a path binding. The available modes are: $WALK$, the default mode, which imposes no restrictions on repeated nodes or edges; $TRAIL$, which excludes path bindings containing a repeated edge; $ACYCLIC$, which excludes path bindings containing a repeated node; and $SIMPLE$, which excludes repeated nodes except when the repeated node is the first and last node of the path, thus permitting a closed path whose interior nodes are distinct.

Using one of the restrictive modes $TRAIL$, $ACYCLIC$, or $SIMPLE$ for every unbounded repetition guarantees that the result set of graph-pattern matching is finite. The same finiteness guard can instead be supplied by a selective path-search prefix or by the DIFFERENT EDGES match mode, as required by the static rules for every unbounded quantifier.

A selective path search prefix (SPSP) further restricts the candidate path bindings produced by a path pattern. It partitions the candidate bindings according to their endpoints, that is, the first and last nodes of the paths, and selects a finite subset separately from each partition. Depending on the SPSP form, the selection may comprise a specified number of arbitrary paths, all shortest paths, a specified number of shortest paths, or all paths belonging to a specified number of the shortest path-length groups. Consequently, the use of an SPSP guarantees a finite result set regardless of the path mode.

The path modes do not form a total order under implication. In particular, $SIMPLE$ and $TRAIL$ are incomparable: in a graph containing undirected edges, a simple path may traverse the same edge twice in opposite directions and therefore need not be a trail.

Availability. The explicit $WALK$ keyword, the restrictive path modes, and the individual SPSP forms are controlled by separate optional features. In ISO/IEC 39075, an optional feature is identified by a Feature ID and defined by its Conformance Requirements (Subclause 5.3.7); Annex D, GQL optional feature taxonomy, collects the optional features informatively.

Stored vs. computed paths. A computed path is a path value produced on the fly by evaluating the regular path expression of a path pattern over the current graph during matching. Some graph-query formalisms (and some implementations) also admit stored paths, i.e., persistent path objects with identity that can be referenced later (for example, as elements of a constructed graph). In this chapter, path patterns are treated as producing computed path values by default; when stored paths exist, they matter only if a specific language feature ranges over those stored path objects rather than enumerating paths from the underlying graph connectivity.

Path restrictors as admissibility filters. For a regular path expression $R$ and path mode $pm$, let $Cand(R,pm)$ denote abstractly the candidate path bindings that satisfy the local element predicates and the chosen mode. For a candidate family, let ${\mathrm{\Pi }}_{u,v}$ denote restriction to the endpoint pair $(u,v)$, and let ${SPSP}_s$ denote abstractly the partition-wise selector determined by selective prefix $s$. Their witness-level definitions and the concrete selector variants are given in Section 11.2. Although the concrete syntax calls them path modes, it is helpful to view $WALK$, $TRAIL$, $ACYCLIC$, and $SIMPLE$ as restrictors: they act as predicates on the space of candidate paths that a regular path expression would otherwise admit. Concretely, for a fixed regular path expression $R$ and endpoints $(u,v)$, the candidate space for matching is first generated and then filtered by the chosen mode. Only the surviving paths are passed to the selective path-search procedure ${SPSP}_s$, where $s$ specifies the applicable path-selection policy; the selected paths are then available for joins and $REDUCE$.

Selective path search prefixes (SPSP). The (potentially infinite) space of path bindings is partitioned by the pair of endpoints $(u,v)$; we write ${\mathrm{\Pi }}_{u,v}(\cdot )$ for the $(u,v)$-partition selector. A search-prefix selector (e.g., $shortest$, $allshortest$, $any$, $countedshortest$) chooses subsets inside each $(u,v)$-partition independently; we denote the resulting selection operator abstractly by ${SPSP}_s(\cdot )$, where $s$ is the chosen SPSP variant. Even under $WALK$, any selective path search prefix (that is, any path-search prefix other than ALL PATHS, including the ANY and SHORTEST-family prefixes) returns a finite set of path bindings; hence the set of reduced matches is finite.

Concrete syntax for path patterns. At the level of concrete syntax, a $⟨\mathit{\text{path pattern}}⟩$ associates an optional path variable and prefix with a regular path expression. Listing 7.1 isolates the spine of path-pattern declarations; the full grammar of path-expr is given in the chapter on regular path expressions (see Chapter 11).

path-pattern   ::= [ path-var "=" ] [ path-prefix ] path-expr

path-prefix    ::= path-mode-prefix | search-prefix

path-mode-prefix ::= path-mode [ "PATH" | "PATHS" ]

path-mode      ::= "WALK"
                 | "TRAIL"
                 | "ACYCLIC"
                 | "SIMPLE"

search-prefix  ::= "ALL" [ path-mode ] [ "PATH" | "PATHS" ]
                 | "ANY" [ non-negative-int ] [ path-mode ] [ "PATH" | "PATHS" ]
                 | "ALL SHORTEST" [ path-mode ] [ "PATH" | "PATHS" ]
                 | "ANY SHORTEST" [ path-mode ] [ "PATH" | "PATHS" ]
                 | "SHORTEST" non-negative-int [ path-mode ] [ "PATH" | "PATHS" ]
                 | ...  /* other GQL search modes */

path-var       ::= identifier
path-expr      ::= ...  /* defined in the regular-path-expression chapter */

Intuitively, path-var names the binding position for the path value, path-mode selects the admissible class of paths (walks, trails, acyclic paths, or simple paths), and search-prefix chooses, for each pair of endpoints, which paths (e.g., a single shortest path, all shortest paths, or all paths) are materialized as bindings. If no path mode is specified, WALK applies. If no path-search prefix is specified, the path pattern is non-selective; there is no implicit ANY selection. Omitting path-var yields an anonymous path whose value is not directly exposed as a binding, although its endpoints and other incident variables may still participate in joins and projections.

7.3 Variable Exposure and Safety

We distinguish (for any $⟨$path pattern$⟩$) boundary variables (visible at the point of composition and eligible for joins), interior variables (scoped to the component), and strict interior variables (interior variables that are not boundary).

Named degrees. For any graph-pattern variable $x$ within a component $C$, exposure has a degree

For a referenceable binding variable $x$, we additionally use

A subpath variable has an exposure degree only for its non-value marker; it is not bound to a value, cannot be referenced, and therefore has no degree of reference.

• Unconditional vs. conditional exposure. $x$ is unconditionally exposed in $C$ iff every reduced match of $C$ contains $x$, as a value-bearing binding or, for a subpath variable, as a marker. Otherwise, if some reduced matches of $C$ do not contain $x$, $x$ is conditionally exposed. If $x$ is interior (non-boundary), it is not-exposed outside $C$.

• Singleton. $x$ is a singleton in $C$ iff, per reduced match of $C$, $x$ contributes at most one binding value.

• Effectively bounded group. $x$ is an effectively-bounded group in $C$ iff there exists a finite bound $B_C$ determined syntactically by $C$ (e.g., finite upper bounds in repetition, finite alternation/branching that does not depend on data cardinalities) such that each reduced match of $C$ contributes at most $B_C$ bindings for $x$.

• Effectively unbounded group. Otherwise $x$ is an effectively-unbounded group (e.g., due to unbounded repetition like Kleene ${}^{+}$ or ${}^{\ast }$ without further syntactic bounds).

For referenceable binding variables, we order reference degrees by

Remark (groups and optionality). Referenceable variables with $D_{ref}(x,C)\ne \mathit{\text{singleton}}$ are referred to as group variables. A group variable may be bound to an empty group in a reduced match (e.g., due to zero repetitions), and such an empty group still counts as a binding for purposes of exposure.

Path-variable degree (local). If a path pattern declares a path variable $p$ (i.e., it has the form $\mathtt{\text{p = …}}$), then $D_{ref}(p,C)=\mathit{\text{singleton}}$ and $D_{expo}(p,C)=\mathit{\text{unconditional}}$ for the component $C$ itself : every reduced match produced by that component binds $p$ to exactly one path value. Remark. Statement-level optionalization (e.g., OPTIONAL MATCH) may later turn any newly introduced binding (including a path variable) into a conditional output column by filling it with $null$ when the optional match fails; this is treated in the statement semantics, not as a path-pattern constructor.

In the GQL grammar, a path primary is an element pattern, a parenthesized path pattern expression, or a simplified path pattern expression.

Propagation rules. Let $P,Q$ be path-pattern primaries; the propagation of exposure and reference degrees over the corresponding pattern constructors is summarized in Table 7.1. For a subpath variable, only the exposure clauses apply; clauses about reference degree or bound values apply only to binding variables.

Constraints. The following static side-conditions constrain how variables with the degrees from Table 7.1 may be referenced; they are taken as part of the well-formedness conditions for path patterns and aggregates in the remainder of this chapter.

1. Non-local reference is permitted only for references with singleton degree, i.e., when $D_{ref}(x,C)=\mathit{\text{singleton}}$.

2. In any aggregate, all group references must range over the same GPV (graph-pattern variable).

3. For selective components, joins are permitted only on boundary variables.

4. A selective $⟨$path pattern$⟩$ (selective path pattern, SPP) shall not reference any graph-pattern variable not declared within this SPP.

7.4 Matching Semantics

Sketch of matching semantics. This section does not introduce a new formal semantics; instead, it gives an informal, staged account of how the graph-pattern matching machinery (path evaluation, selective search, joins, and binding reduction) behaves in our notation. The numbered steps below should be read as an operational pipeline that explains how a graph pattern is turned into a binding table, complementing the more formal binding-table semantics in Sections 7.5 and 7.6.

For a given graph pattern $\Gamma$ in the context of graph $G$:

1. Syntactic normalization. Distribute a graph-level KEEP prefix to every path pattern and remove the KEEP clause. Determine the explicit or implementation-defined match mode.

2. Local generation (with scoped filters). For each $⟨$path pattern$⟩$ component with regular path expression $R$ and path mode $pm$, compute the candidate set $Cand(R,pm)$ of its path bindings that satisfy the local predicates of the element pattern and the chosen path mode. If the component is a parenthesized path pattern with an attached WHERE clause, that clause is evaluated here, before any SPSP selection. A non-local reference is permitted only at singleton reference degree; a selective path pattern cannot reference a graph-pattern variable declared outside that selective component. No selective search is applied at this stage.

3. Selective stage (per component). If a component is selective with selective prefix $s$, apply its selector independently inside each endpoint partition: for each endpoint pair $(u,v)$, replace the candidate partition ${\mathrm{\Pi }}_{u,v}(Cand(R,pm))$ by the selected subset ${SPSP}_s({\mathrm{\Pi }}_{u,v}(Cand(R,pm)))$. If DIFFERENT EDGES applies to the single selective component, discard repeated-edge bindings before selection. The result is a finite set of bindings for that component. Non-selective components keep their full candidate sets $Cand(R,pm)$ unchanged.

4. Product and joins. Form the set-theoretic Cartesian product and enforce natural equijoins on the shared boundary variables that are unconditionally exposed singletons. For selective $⟨$path pattern$⟩$ components, joins are restricted: strict interior variables of a given SPP MUST NOT join with exterior variables or with interior variables of another SPP; only joins on boundary variables are permitted.

5. Match-mode filtering. Under DIFFERENT EDGES, retain only multi-path bindings in which no graph edge occurs in two different edge-binding positions. Under REPEATABLE ELEMENTS, no such filter is applied.

6. Global filtering. Apply WHERE search conditions (non-local predicates and selections), thereby reducing the set of bindings.

7. Reduction. Apply the $REDUCE$ function: remove temporary symbols, reduce anonymous nodes/edges, merge adjacent anonymous nodes, retain subpath-marker distinctions introduced for multiset alternation, and deduplicate results under set semantics at the level of reduced matches.

8. Binding-table formation. The final result of matching is the binding table ${BT}_{\Gamma }$ over the columns corresponding to the exposed binding variables and projections from the pattern by appending one record for every reduced match for each occurrence of an incoming working-table record. The reduced-match result itself is a set; duplicate binding-table records may nevertheless arise from duplicate incoming records or from distinct reduced matches whose yielded records are equal. See Availability above for the applicable optional-feature mechanism.

Informative homomorphism analogy. In general graph-query formalisms, a common distinction is whether a pattern is matched by homomorphisms (structure-preserving mappings that may identify distinct pattern variables) or by injective matches (structure-preserving mappings in which distinct pattern variables must be mapped to distinct graph elements, corresponding to subgraph-isomorphism-style matching). Both notions preserve the intended incidence constraints of the pattern; the difference is whether distinct variables are allowed to map to the same graph object. This is a graph-theoretic analogy, not an additional GQL match mode: the standard match modes are REPEATABLE ELEMENTS and DIFFERENT EDGES, with the semantics given above.

Formally, let $P$ be a pattern with node variables $V_P$ and edge variables $E_P$, and let $G$ be a graph with node set $V_G$ and edge set $E_G$. A match is a pair of total functions $h_V:V_P\to V_G$ and $h_E:E_P\to E_G$ that preserves the required incidence and typing constraints of $P$ in $G$ (labels/types, directions, endpoint compatibility, and any explicitly stated property tests). We write $h=(h_V,h_E)$.

Homomorphic matching admits all such structure-preserving mappings $h$. Injective matching further requires injectivity on the chosen variable sets:

A fully isomorphic regime typically enforces ${Inj}_V(h)\wedge {Inj}_E(h)$, and, if the model treats nodes and edges as disjoint carriers, optionally also a cross-sort disjointness condition (implementation-dependent).

Example (a concrete match-function pair). For the pattern

one match in the library graph is

Reduced matches and binding-table multiplicities. Graph-pattern evaluation produces a set of reduced matches. If two raw matches become equal after $REDUCE$, they contribute only one reduced match. For each occurrence of an incoming working-table record, graph-pattern binding table formation appends one record per reduced match. Equal output records can nevertheless have multiplicity greater than one when distinct reduced matches have equal yielded fields or when the incoming table contains duplicate records.

Let $Hom(P,G)$ be the set of all distinct complete homomorphic matches of $P$ in $G$, including assignments to internal variables and any path witnesses that distinguish matches. Let $bind(h)$ denote the binding extracted from $h$, restricted to the variables exported by $P$, and let $r(h)$ be the reduced match induced by $h$. For this analogy, a set-valued formulation is:

Changing the admissible raw mappings changes this set, but equal reduced matches are still deduplicated before binding-table formation.

Excluding classes of matches via explicit guards. Rather than baking a single global choice (homomorphism vs. isomorphism) into the core semantics, it is often preferable to keep homomorphic matching as the baseline and let users rule out unwanted matches by adding guards that constrain identifications. This captures a spectrum of behaviors between pure homomorphism and full isomorphism.

Let $\Phi$ be a predicate over bindings (e.g., conjunctions of inequalities between variables). Define guarded matching by filtering the match set:

A common family of guards are injectivity guards on selected variable subsets. For any $S\subseteq V_P$ define

and analogously for edge variables. Then “node-isomorphic” matching is obtained by choosing $\Phi :={Inj}_{V_P}$, while full isomorphism corresponds to $\Phi :={Inj}_{V_P}\wedge {Inj}_{E_P}$ (and any additional disjointness conditions required by the underlying data model).

7.5 Binding Tables

A binding table is the descriptor-bearing object fixed in Section 6.1: it comprises a finite collection of records of one record type, an ordered/unordered indication, and an optional preferred column-name sequence. Thus, for

we use $bag(T)=⟨{\tau }_{rec},B⟩$ only as its order-insensitive bag projection; it is not an identification of the complete binding-table object with that pair. There is a distinguished unordered unit table containing the unique unit record $⟨⟩$. Columns are the fields of the record type; operations such as Cartesian product and column-wise operations rely on the compatibility of field/column names and types. Records of a binding table are not modified once the table is built; new tables arise by construction (e.g., products, selections, projections).

Example (a complete binding-table object). Consider the result of the simple rigid-pattern query in Section 4.4. Let $d_1$ and $d_2$ denote the $DATE$ values displayed there as 2025-12-01 and 2025-12-10, respectively. Its closed record type is

The two records shown in the result table are

Thus the bag component is determined by

and the preferred column-name sequence established by the RETURN item order is

Because the query contains no ORDER BY clause, its complete binding-table object is

Consequently, the order in which the two records are printed has no semantic significance. The pair $bag(T_{lib})=⟨{\tau }_{lib},B_{lib}⟩$ is only the order-insensitive bag projection, not the complete binding-table object.

Bag-semantics convention. The multiplicity of a record in $BT$ models duplicate table records, not duplicate reduced matches (which are deduplicated as a set). For natural joins, equality on shared fields (natural joinability) is required – formal conditions are given by the specification.

7.6 MATCH Statements

A MATCH statement is the primitive query statement that turns graph patterns into binding tables and thereby expands the current working table of a linear query statement. In the ISO standard, it appears as a primitive query statement inside a linear query statement, whose incoming and outgoing working record and table types are threaded left–to–right through the sequence of simple query statements. In this section, we give an abstract syntax for MATCH, and a denotational semantics that factors through the graph pattern semantics and the binding–table operators of Chapter 9. Examples of a single rigid MATCH and successive MATCH statements appear in Section 4.4.

Abstract syntax. Let $GPat$ be the set of well-formed graph patterns, including their optional WHERE clauses, and let $GPBT$ be the set of graph pattern binding tables, each consisting of a graph pattern optionally followed by a YIELD clause. At the statement level, we distinguish simple and optional match statements.

We write:

Intuitively:

• $Match({\mathrm{\Delta }}_{gpbt})$ corresponds to a simple match statement MATCH ${\mathrm{\Delta }}_{gpbt}$.

• $OptMatch(Match({\mathrm{\Delta }}_{gpbt}))$ corresponds to OPTIONAL MATCH ${\mathrm{\Delta }}_{gpbt}$.

• $OptMatch(⟨S_1;\dots <!--FUNCTION\; APPLICATION-->;S_n⟩)$ corresponds to an optional match block OPTIONAL { $S_1$ … $S_n$ } or OPTIONAL ( $S_1$ … $S_n$ ), where the inner $S_i$ are themselves match statements (simple or optional).

For concreteness, we use the following simplified BNF, which is a faithful abstraction of the ISO Formats for MATCH:

match-stmt   ::= "MATCH" graph-pattern-binding-table
               | "OPTIONAL" match-operand

match-operand ::= "MATCH" graph-pattern-binding-table
                | "{" match-block "}"
                | "(" match-block ")"

match-block ::= match-stmt { match-stmt }

graph-pattern-binding-table ::=
    graph-pattern [ graph-pattern-yield-clause ]

All the syntactic complexity related to linear query statements, focused versus ambient use of graphs, and the detailed declaration of working record types is pushed into other chapters. Here we focus on the semantic contribution of MATCH itself.

Semantic setting. Let $BT$ be the domain of descriptor-bearing binding tables fixed in Section 6.1 and recalled in Section 7.5. Its bag projection is finite and has a common header (a set of column names with value types); selection, projection, and joins are developed in Chapter 9.

For each graph pattern binding table ${\mathrm{\Delta }}_{gpbt}\in GPBT$ we assume a graph pattern binding table operator

that lifts the reduced matches of the graph pattern contained in ${\mathrm{\Delta }}_{gpbt}$ (as defined in Chapter 7) to a binding table, applies its explicit or implicit YIELD clause, and may be correlated with an incoming binding table of outer variables. This abstracts the ISO notion of a “$⟨\mathit{\text{graph pattern binding table}}⟩$” that combines graph pattern matching with an incoming working table.

For a correlated binding-table transformer $\mathcal{F}$, let ${OptExpand}_{\mathcal{F}}(T)$ denote the per-record optional expansion of $T$: every input record occurrence is extended by every row produced by $\mathcal{F}$ for that occurrence, or once with nulls in all statically declared new columns if $\mathcal{F}$ produces no row. The bag formula for this operator is given in Section 9.2; this declaration fixes the operator before its uses below.

For a binding table $T\in BT$ we write:

• $cols(T)$ for the finite set of column names of $T$;

• $T(X)$ for the restriction of $T$ to a subset $X\subseteq cols(T)$ of columns (projection);

• $T⋊⋉U$ for the natural join (bag-valued) of $T$ and $U$ on common column names, as in Chapter 9;

• $T⊲U$ for the left outer join of $T$ and $U$, reusing the left-outer-join operator from Chapter 9 (in particular, abbreviating the guarded operator $T<msub><mrow>⊲</mrow><mrow>𝜃</mrow></msub>U$ where $𝜃$ is the standard equality guard on shared columns).

In a linear query statement, a match statement $S$ acts on the current working table $T$ and produces a new working table $T^{\prime }$ (that is, the outgoing working table obtained from $T$ by applying the semantics of $S$, so $T^{\prime }=⟦S{⟧}_{match}(T)$). At our level of abstraction, we therefore model $MatchStmt$ by a semantic function

Simple MATCH. Let $S=Match({\mathrm{\Delta }}_{gpbt})$ be a simple match statement and let $T\in BT$ be the incoming working table.

The ISO semantics for a simple match statement proceeds by constructing a graph pattern binding table ${\mathrm{\Delta }}_{gpbt}$ (using the current working table as input), and then setting the current working table to (a copy of) that result, taking care not to duplicate columns already present in the incoming working types. In the ISO standard, compatibility between incoming bindings and newly produced bindings is enforced inside the construction of the graph pattern binding table.

We capture this behavior at our level of abstraction by taking the output of the graph-pattern binding table operator as the denotation of MATCH. Let

We define:

In a query block that begins with a single MATCH and whose incoming working table is the singleton table with one empty record, this definition reduces to the binding table semantics for the graph pattern:

where ${BT}_{unit}$ is the distinguished unit table (see Section 7.5), with empty header (no columns) and a single empty record $⟨⟩$.

Optional MATCH with a single pattern. Consider an optional match statement of the form $S=OptMatch(Match({\mathrm{\Delta }}_{gpbt}))$. The ISO semantics does not define an independent denotation for this construct, but instead desugars it into an OPTIONAL CALL with an explicit list of input binding variables (taken from the incoming working record and table types) and an explicit list of output binding variables (the new bindings supplied by the graph pattern binding table). The semantics of OPTIONAL CALL then implements a left outer join between the incoming bindings and the results of the call.

At the level of pure binding-table semantics this is the correlated optional expansion from Section 9.2. Let $T\in BT$ be the incoming working table and let ${\mathcal{F}}_{{\mathrm{\Delta }}_{gpbt}}(U)={GPBT}_{{\mathrm{\Delta }}_{gpbt}}(U)$. We define:

The correlated expansion:

• preserves every row of $T$;

• when there is at least one match produced by ${\mathrm{\Delta }}_{gpbt}$ compatible with a given row of $T$, duplicates that row for each such match and fills the newly introduced columns according to the match; but

• when there is no such match, preserves the row once and fills the newly introduced columns with the null value (or the appropriate representation of “no binding”).

This is exactly the behavior of optional pattern matching familiar from property-graph practice and from Section 9.2.

Example (an unsuccessful optional match).

USE libraryGraph
MATCH (r:Reader)
OPTIONAL MATCH (r)-[:USES]->(c:LibraryCard)
  WHERE c.num = 'CARD-9999'
RETURN r.firstname AS firstname, c.num AS card_number

because the incoming reader record is retained when the optional pattern has no compatible match.

Optional MATCH blocks. A match block $\mathcal{Q}=⟨S_1;\dots <!--FUNCTION\; APPLICATION-->;S_n⟩$ represents a non-empty sequence of match statements. Its semantics as a block (ignoring optionality) is just functional composition:

An optional match statement with a block, $S=OptMatch(\mathcal{Q})$, is then interpreted as a correlated left outer join between each incoming occurrence and the overall effect of the block evaluated with that occurrence as input. Let ${\mathcal{F}}_{\mathcal{Q}}(U)=⟦\mathcal{Q}{⟧}_{match}(U)$. Then:

Informally, the block $\mathcal{Q}$ is evaluated as if it were a sequence of ordinary MATCH statements, producing extended rows that may introduce fresh binding variables. The optional wrapper then ensures that every input row is preserved: rows that admit at least one successful extension through $\mathcal{Q}$ are duplicated for each such extension (with the new bindings filled in), while rows that admit no extension through $\mathcal{Q}$ are preserved once, with the new columns filled with nulls. This is equivalent to the standard’s translation of OPTIONAL MATCH blocks into OPTIONAL CALL statements with explicit input and output binding variable lists.

This same notion of a match block is also reused by the ISO semantics of the EXISTS predicate, which rewrites EXISTS { MATCH …} or EXISTS { …match-block …} into a nested query whose body consists of the match block followed by a trivial RETURN of a Boolean column.

Interaction with linear query statements. In a full linear query statement,

the match statements occur as primitive query statements in the sequence governed by the linear query statement syntax. Let

be the MATCH or OPTIONAL MATCH statements in the order in which they appear. At the level of binding tables, their combined effect on an initial working table $T_0$ is the composition

and it is $T_k$ that is subsequently consumed by the selection, projection, aggregation and ordering operators that make up the rest of the query block (Chapter 9). In the “whole-query denotation” of a query block, MATCH thus serves as the bridge between pattern-based access to the graph and the relational-style algebra over binding tables.

7.7 Key Scopes and Finiteness

Let $T\in BT$ be a binding table with $bag(T)=⟨{\tau }_{rec},B⟩$ (see Section 7.5). In this section, displayed pairs denote bag projections; descriptor metadata are propagated by the applicable table operator. The abbreviation $⟦E⟧(r)$ means evaluation of $E$ in the row environment induced by $r$, as defined formally in Chapter 8. We work throughout with bag semantics: the multiset component $B$ records the multiplicity of each record, and each operator below acts on $B$ so that it propagates and combines multiplicities in the standard way (for example, selection preserves the multiplicities of surviving rows; projection does not perform duplicate elimination and its output multiplicities are obtained by summing multiplicities of preimages; unions add multiplicities; joins multiply them). Unless explicitly stated otherwise (in particular for DISTINCT and UNION without ALL), the operators defined in this section are multiset-preserving in this sense.

Extend. The extension with projection for expressions $E_1,\dots <!--FUNCTION\; APPLICATION-->,E_k$ and fresh names $n_1,\dots <!--FUNCTION\; APPLICATION-->,n_k$ is typed by ${\mathrm{\Xi }}_{{\tau }_{rec}}⊢E_i:{\tau }_i$ for $1\le i\le k$, where ${\mathrm{\Xi }}_{{\tau }_{rec}}$ is the type environment induced by ${\tau }_{rec}$. The extension operator is defined by

where the output multiplicity function $B^{\prime }$ is defined by

Equivalently (bag-sum form),

Projection. Projection ${\pi }_X$ onto a set (or list) $X$ of field names is the bag-valued pushforward along record restriction:

In particular, projection ${\pi }_{n_1,\dots <!--FUNCTION\; APPLICATION-->,n_k}$ onto the field names $n_1,\dots <!--FUNCTION\; APPLICATION-->,n_k$ is the special case that keeps exactly these fields and discards all others.

Selection. ${\sigma }_{\phi }(⟨{\tau }_{rec},B⟩)$ keeps those $r$ for which $⟦\phi {⟧}^{tv}(r)=\top <!--FUNCTION\; APPLICATION-->$; $\perp$ and $U$ are rejected, i.e.,

Name-compatible join (natural join). Let $bag(T_i)=⟨{\tau }_i,B_i⟩$ for $i\in \{1,2\}$, and let $S=dom({\tau }_1)\cap dom({\tau }_2)$. Records $r_1,r_2$ are naturally joinable iff, for every $n\in S$, their fields have equal values in the value-level sense used by the GQL definition of natural joinability. This is not an evaluation of the three-valued GQL comparison predicate; in particular, two fields containing the null value have equal values. Define

Theta-join ${⋊⋉}_{𝜃}$ is $⋊⋉$ followed by ${\sigma }_{𝜃}$.

Semi/anti join. The semi-join ${BT}_1{⋉}_{𝜃}{BT}_2$ keeps those rows of ${BT}_1$ that have at least one join partner in ${BT}_2$ satisfying $𝜃$. The anti-join ${BT}_1{⋫}_{𝜃}{BT}_2$ keeps exactly those rows of ${BT}_1$ that do not have any join partner in ${BT}_2$ satisfying $𝜃$.

Union and duplicate control. If $bag(T_i)=⟨\tau ,B_i⟩$ for $i\in \{1,2\}$, $UNIONALL$ is a bag union:

on a common type $\tau$, after any permitted coercion to that common type. $UNION$ (distinct) is set union over records (multiplicity truncated to 0/1).

Distinct (deduplication). $DISTINCT(BT)$ maps multiplicities $m\ge 1$ to $1$.

Ordering and slicing. ${ORDERBY}_{\overrightarrow{o}}(BT)$ enriches $BT$ with an order descriptor (it does not change the multiset). For integers $k,\ell \ge 0$, $SKIPk$ and $LIMIT\ell$ are applied to the emission of results in that order: $SKIPk$ discards the first $k$ rows of the ordered sequence, and $LIMIT\ell$ keeps at most $\ell$ subsequent rows.

Constraint (primitive result statement). In a RETURN result with ORDER BY, OFFSET, or LIMIT, (i) sort keys MUST NOT contain subqueries; (ii) order-by references are restricted to the statement’s admissible ORDER_REFS (as determined by preceding DISTINCT/GROUP BY and the projection); (iii) availability of OFFSET/LIMIT is governed by conformance options (e.g., ORDER BY and page statement: OFFSET clause and ORDER BY and page statement: LIMIT clause).

Unwind. For a list-valued field $L$ of declared type $LIST⟨{\tau }_{elem}⟩$ and target name $n$,

where each record with $L=[v_1,\dots <!--FUNCTION\; APPLICATION-->,v_m]$ yields $m$ records with $n:=v_i$. If $L=null$, that incoming record produces no output record.