Chapter 09Algebra of Binding Tables

This chapter introduces the algebra of binding tables, which forms the intermediate value domain on which query blocks and statements operate. We treat binding tables as bags of records and present selection, projection, joins, unwinding, and subquery composition as operations that transform them. The algebra is formulated with explicit bag semantics, three-valued logic, and ordering metadata, in a manner that aligns with the GQL standard’s treatment of optional pattern matching, correlation, and primitive result statements.

Classical bag-query algebras provide background on duplicates, aggregation, nesting, and expressive power (Grumbach and Milo 1996; Libkin and Wong 1997). They serve here only as mathematical background; binding-table descriptors, ordering metadata, preferred column names, and the operator rules remain governed by GQL.

9.1 Selection and Projection

Let $T\in \mathrm{BT}$ be a binding table with $\mathrm{bag}(T)=⟨{\tau }_{\mathrm{rec}},B⟩$. The formulas below act on this bag projection; each operator separately preserves or updates the ordered/unordered and preferred-column metadata of the complete binding-table descriptor. Projecting actions are modeled as functions on multisets of records:

• Selection: ${\sigma }_{\phi }(\mathrm{BT})$ — the submultiset of records satisfying predicate $\phi$ (evaluated in GQL types, with null handling according to the comparison semantics and the three-valued truth tables from Chapter 8).
• Projection: ${\pi }_{E_1\mapsto n_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,E_k\mapsto n_k}(\mathrm{BT})$ — each input record occurrence contributes once to a new record $r^{\prime }$ with fields named $n_i$ taking values $⟦E_i⟧(r)$; multiplicities of equal projected records are summed.
• Natural join: ${\mathrm{BT}}_1⋊⋉{\mathrm{BT}}_2$ — join based on name compatibility and equal values of shared fields; the bag multiplicity is consistent with the product of multiplicities of the paired records.
• Ordering: ordering metadata may be included in the descriptor of a binding table, distinguishing ordered from unordered tables; it does not affect the underlying bag semantics but determines the order in which records are emitted.²

For example, let $T_{\mathrm{fees}}$ have the two rows

Then ${\sigma }_{\mathtt{\text{late\_fee}}>0}(T_{\mathrm{fees}})$ retains only $r_2$, and projecting it onto title yields the singleton row $⟨\mathtt{\text{title}}\mapsto \mathtt{\text{’Graph Theory’}}⟩$.

9.2 Joins and OPTIONAL (Left-Outer Join)

Compatibility and merge. Mappings $\mu ,\nu$ are naturally compatible, written $\mu \sim \nu$, iff their fields with the same name 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 comparison predicate; in particular, two common fields that both contain the null value have equal values. Their merge $\mu \bigsqcup \nu$ is the union partial map after any required common-type coercion and is well-defined when $\mu \sim \nu$.

Binding-table semantics of OPTIONAL MATCH. Let $\mathrm{BT}$ be the current table, let ${\Gamma }^{\prime }$ be a pattern, and let ${\mathrm{\Delta }}_{\mathrm{gpbt}}^{\prime }$ be its graph pattern binding table with an explicit or implicit YIELD clause. In ISO/IEC 39075, OPTIONAL MATCH is specified via a translation to an OPTIONAL CALL whose RETURN list contains only the new output bindings. The call is evaluated separately for every occurrence of an incoming record, so the correlation columns must not be projected away before the optional expansion.

More generally, let $\mathcal{F}$ be a correlated binding-table transformer and let $C_{\mathrm{new}}$ be the columns in its declared output record type that are not columns of $\mathrm{BT}$. For every occurrence of $\mu$ in $\mathrm{BT}$, put

where the singleton is an incoming table occurrence and the final parentheses denote projection. Define the correlated optional expansion by

Thus, with $\mathcal{F}={\mathrm{GPBT}}_{{\mathrm{\Delta }}_{\mathrm{gpbt}}^{\prime }}$, ${\mathrm{OPT}\text{\_}\mathrm{MATCH}}_{{\Gamma }^{\prime }}(\mathrm{BT})={\mathrm{OptExpand}}_{\mathcal{F}}(\mathrm{BT})$. This preserves correlation with each incoming record and fills all statically declared new fields with $\mathrm{null}$ exactly when that record has no matching extension.

Bag join. For bags ${\mathcal{B}}_1,{\mathcal{B}}_2$ of mappings, define the (natural) bag join

Guarded join (ON-condition). Given a Boolean guard $𝜃$, the guarded join is

where $𝜃$ is evaluated over $\mu \bigsqcup \nu$. Note that $U$ or $\perp$ in $𝜃$ discards the pair (no match), $\top <!--\; FUNCTION\; APPLICATION\; -->$ keeps it. If $𝜃$ evaluates to $\mathrm{err}$ for some pair, the join is undefined (signals a dynamic exception).

Left outer join. Let $\mathrm{hdr}(\mathcal{B})$ be the set of variables in the declared record type of $\mathcal{B}$, including when $\mathcal{B}$ is empty. Let ${\pi }_L$ project a merged mapping to the left variables $\mathrm{hdr}({\mathcal{B}}_1)$, let $\ominus$ denote bag difference on these left projections, and let ${\mathrm{pad}}_R$ map each remaining left mapping $\mu$ to $\mu \bigsqcup \eta$, where $\eta$ binds every right-only variable in $\mathrm{hdr}({\mathcal{B}}_2)\setminus \mathrm{hdr}({\mathcal{B}}_1)$ to $\mathrm{null}$. For ${\mathcal{B}}_1,{\mathcal{B}}_2$ and guard $𝜃$, the left outer join is the bag

Denotational semantics of OPTIONAL MATCH. For a basic pattern $P$ and an optional pattern $Q$ with internal guard $𝜃$ (e.g., a WHERE-predicate inside the optional clause), denotation is

where ${\mathcal{F}}_Q(\{\{\mu \}\})=\mathit{⟦Q}{⟧}_{G,\mu }$ includes the internal guard $𝜃$. A separate FILTER WHERE$\varphi$ after OPTIONAL is applied by ${\mathrm{filter}}_{\varphi }$ to the outer-join result (hence $\mathrm{null}$-sensitive); a WHERE belonging to the optional graph pattern remains inside ${\mathcal{F}}_Q$.

OPTIONAL Block Denotation For a block consisting of a basic pattern $P$, an optional pattern $Q$ with guard $𝜃$, a separate trailing filter $\varphi$, and a projection $\stackrel{}{s\to }$, let ${\mathrm{proj}}_{\stackrel{}{s\to }}$ denote the corresponding record projection, including evaluation of its expressions with the null-and-error semantics of Chapter 8 and preservation of bag multiplicities. Then

9.3 FOR and List Unnesting

FOR on a list is modeled by ${\mathrm{unnest}}_{n:L}(\mathrm{BT})$. For each occurrence of a record $r\in \mathrm{BT}$, if the field $L$ contains the list $(v_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,v_m)$, the operator produces the $m$ records

Under bag semantics, each generated record inherits the multiplicity of $r$; thus, multiplicities are multiplied when identical output records arise from different input occurrences or list positions. If $L$ evaluates to $\mathrm{null}$, no output record is generated for $r$.

9.4 Subqueries and Scope

A query block is a triple $⟨\Gamma ,\Phi ,\mathrm{\Pi }⟩$:

• $\Gamma$: (possibly empty) conjunction of graph/path patterns with a WHERE-predicate producing a base binding table as in Section 7.1.
• $\Phi$: a sequence of algebraic operators over binding tables ($\mathrm{select}$, $\mathrm{extend}$, $\mathrm{join}$, $\mathrm{unwind}$, $\mathrm{group}$, $\mathrm{distinct}$, $\mathrm{order}$, $\mathrm{slice}$).
• $\mathrm{\Pi }$: a final projection (RETURN-style) specifying visible columns and expressions to emit.

The grouping, ordering, and slicing stages are defined in Chapters 12 and 13. For a store state $\mathrm{\Omega }$, let ${\mathrm{BT}}_{\Gamma }(\mathrm{\Omega })$ denote the base binding table obtained by evaluating $\Gamma$ in the working graph and correlation environment of $\mathrm{\Omega }$; for empty $\Gamma$, it is the unit binding table. The denotation of a block is

Example (query-block decomposition). For the second query in Section 4.4, which computes total_late_fee, let ${\Gamma }_{\mathrm{fee}}$ denote its two path patterns together with the two ISBN conditions in their WHERE clause. In the abstraction above,

Thus the graph-pattern WHERE belongs to ${\Gamma }_{\mathrm{fee}}$; LET and the subsequent FILTER WHERE determine ${\Phi }_{\mathrm{fee}}$, while RETURN determines ${\mathrm{\Pi }}_{\mathrm{fee}}$.

Linear-query pipelining. ISO/IEC 39075 does not use a WITH clause as a query-block boundary. Instead, the incoming and outgoing working record and working table types are threaded from each simple query statement to the next in a linear query statement. Projection and renaming are performed by the applicable result statement, and only the columns of its outgoing working table type are visible to a following statement.

Subqueries. A subquery evaluates to a binding table in the current $\mathrm{\Omega }$. When the subquery is correlated, references to names from the enclosing query are resolved in the current outer-row environment. The resulting binding table is consumed according to the surrounding evaluation context, as specified below for relational, scalar, and row-producing subqueries.

Environments and scopes. A static environment $\mathcal{E}$ maps names (variables, parameters, functions, and relevant catalog objects) to denotations. A dynamic environment $\mathrm{Dyn}$ provides the current graph $G$ and the current outer-row mapping ${\mu }_o$ during correlated evaluation.

Uncorrelated subquery. A subquery $Q$ that contains no reference to an outer binding is independent of the outer row. Its result is consumed according to its surrounding context; the additional static restrictions for a value query expression are stated below under scalar subqueries.

Correlated subquery. A subquery referencing outer attributes is a function of the outer row:

The EXISTS context consumes the resulting bag as follows:

Row-producing subqueries. In the FROM/pattern position, a subquery $Q$ contributes its bag of rows to the surrounding algebra just like a base pattern.

Dynamic-context notation. In the formulas below, $(G,{\mu }_o)$ abbreviates the corresponding components of $\mathrm{Dyn}$; function and procedure registries continue to be resolved through the static environment $\mathcal{E}$. The outer mapping ${\mu }_o$ may be empty.

Variable hygiene. Each subquery has its own local variable namespace $V_{\mathrm{loc}}$ disjoint from outer variables by $\alpha$-renaming, except for explicitly correlated references to outer names, which are resolved in ${\mu }_o$. Shadowing of names by aliases is disallowed unless explicitly stated.

Relational subqueries. A subquery $Q$ used by an EXISTS predicate is evaluated as a bag ${\mathcal{B}}_Q=\mathit{⟦Q}{⟧}_{G,{\mu }_o}$ in environment $(G,{\mu }_o)$. Here ${\mu }_o$ is the current left-row mapping.

(never $U$); errors from inside the subquery propagate to the enclosing expression.

Scalar subqueries. A scalar subquery is a value query expression $\mathtt{\text{VALUE }}Q$. Its nested query has a single result column, and its emitting RETURN is statically required either to use LIMIT 1 or to contain an aggregate without GROUP BY; hence its result has at most one record. Formally, with ${\mathcal{B}}_Q=\mathit{⟦Q}{⟧}_{G,{\mu }_o}$:

Subquery in OPTIONAL. When $Q$ is correlated and appears on the right of OPTIONAL, the correlation uses the left-row mapping $\mu$ at the point of join; each $\mu$ yields $\mathit{⟦Q}{⟧}_{G,\mu }$ independently, composing via $⊲$ as above.

9.5 Whole-Query Denotation

A full read-only query is a pipeline of blocks

Each block is evaluated with respect to the fixed store state $\mathrm{\Omega }$ and transforms the binding table produced by its predecessor. Let ${\mathrm{BT}}_0={\mathrm{BT}}_{\mathrm{unit}}$, and, for $1\le i\le m$, define

The denotation of the complete query is therefore

Equivalently,

Example (linear-query pipeline). The linear-composition query in Line 14 instantiates this recurrence with four successive transformations. Let ${\mathrm{\Delta }}_{\mathrm{gpbt},1}$ denote the first MATCH graph pattern together with its last-name WHERE predicate and its implicit YIELD clause, let ${\mathrm{\Delta }}_{\mathrm{gpbt},2}$ denote the corresponding graph pattern binding table for the second MATCH, and let

be the predicate of the subsequent FILTER WHERE. At the level of the abstraction above, $Q_{\mathrm{lin}}=⟨B_1;B_2;B_3;B_4⟩$, where

Here ${\mathrm{order}}_{\mathtt{\text{due\_date}}\uparrow }$ denotes ascending ordering by the projected due_date field. Consequently, $⟦Q_{\mathrm{lin}}⟧(\mathrm{\Omega })={\mathrm{BT}}_4$.

An updating statement is modeled separately because its evaluation may change the store state. Given an input binding table $\mathrm{BT}$, its denotation has the form

where ${\mathrm{\Omega }}^{\prime }$ is the resulting store state and $R$ is either a result binding table or an omitted result. When no preceding query blocks supply bindings to the update, $\mathrm{BT}$ is typically the unit binding table.

Soundness checks and algebraic laws (selected) Let $\equiv$ denote bag-equivalence of binding tables (same records with same multiplicities, ignoring order). The following laws are intended only when every relevant expression evaluation yields the same value and raises no dynamic exception:

• ${\sigma }_{{\phi }_1}({\sigma }_{{\phi }_2}(\mathrm{BT}))\equiv {\sigma }_{{\phi }_1\wedge {\phi }_2}(\mathrm{BT})$.
• ${\pi }_X({\sigma }_{\phi }(\mathrm{BT}))\equiv {\sigma }_{\phi {|}_X}({\pi }_X(\mathrm{BT}))$ when $\phi$ mentions only $X$.
• $⋊⋉$ is associative and commutative up to field renaming and multiplicity algebra.
• $\mathrm{DISTINCT}(\mathrm{DISTINCT}(\mathrm{BT}))\equiv \mathrm{DISTINCT}(\mathrm{BT})$.

9.6 Composite Queries and Set Operators

A composite query combines the results of one or more linear query pipelines using set-like operators UNION, EXCEPT, INTERSECT and the fallback operator OTHERWISE. At the semantic level, a composite query expression denotes a binding table obtained by composing the binding tables produced by its constituent linear queries.

Syntactic shape. The grammar fragment

introduces a left-associative composition of query-parts. Each query-part is a linear-query. A query-conj is one of UNION, EXCEPT, INTERSECT, or OTHERWISE, with the set operators optionally qualified by a set quantifier ALL or DISTINCT. In line with the GQL standard, the following constraints are imposed:

• If a set operator (UNION, EXCEPT, INTERSECT) is specified without an explicit set quantifier, the quantifier DISTINCT is implicit.
• Within a single composite-query, all occurrences of query-conj must be the same query conjunction: the same operator and, for a set operator, the same ALL/DISTINCT choice after applying the implicit DISTINCT. Thus neither mixed operators such as UNION ... EXCEPT ... nor mixed quantifiers such as UNION ALL ... UNION DISTINCT ... are permitted.

Thus, each well-formed composite query expression has the form

for a fixed query conjunction $\mathrm{op}$, including its fixed set quantifier when applicable, and $n\ge 0$, and is interpreted as left-associative:

Typing and column combination. Each linear-query is a (possibly focused) linear query statement in the sense of the standard. We assume that evaluation of a linear query $L$ produces a binding table $T_L=\mathit{⟦L⟧}\in \mathrm{BT}$ whose bag projection is

where ${\tau }_L$ is a record type describing the columns and their value types, and $B_L$ is a finite multiset of records of type ${\tau }_L$.

Let $Q_0,\dots <!--\; FUNCTION\; APPLICATION\; -->,Q_n$ be the query parts of a composite query, $T_i=⟦Q_i⟧$, and $\mathrm{bag}(T_i)=⟨{\tau }_i,B_i⟩$ (these are the results of the immediately contained linear queries). Typing of the composite query is governed by the following constraints, mirroring Subclause 14.2:

• All ${\tau }_i$ must be column name-equal: they have the same set of column names.
• The ${\tau }_i$ must be column-combinable, in the sense of the type-combination relation: for each column name, the corresponding value types in ${\tau }_i$ admit a combined type, possibly a dynamic union type.
• Let $\tau$ be the combined record type obtained from ${\tau }_0,\dots <!--\; FUNCTION\; APPLICATION\; -->,{\tau }_n$. The declared type of the composite query is the material binding table type with column type $\tau$.

Operationally, each operand $T_i=⟦Q_i⟧$ can be coerced to the common type $\tau$ before applying the set operator, using the same coercion and dynamic-union rules as for column-combinable record types. When the operator is one of $\mathtt{\text{UNION DISTINCT}}$, $\mathtt{\text{EXCEPT ALL}}$, $\mathtt{\text{EXCEPT DISTINCT}}$, $\mathtt{\text{INTERSECT ALL}}$, $\mathtt{\text{INTERSECT DISTINCT}}$, the standard additionally requires that no column in $\tau$ has a dynamic union type that mixes incomparable value types; otherwise, the composite query fails static validation. In these cases, every column acts as a grouping key, and the general grouping rules apply to the composite query.

Bag-based semantics of set operators. We now describe the algebraic semantics in terms of the binding-table algebra. Recall that a binding table is the descriptor-bearing object in $\mathrm{BT}$ fixed in Section 6.1. The equations below determine its bag projection $⟨\tau ,B⟩$; the ordered/unordered indicator and preferred column-name sequence remain components of the complete result descriptor and are determined by the corresponding operation. Bag union is written $B_1\uplus B_2$, with multiplicities added element-wise.

For a binary composite expression of the form $Q_L{\mathrm{op}}_q{Q}_R$, where $Q_L$ and $Q_R$ denote, respectively, the left and right query part, with set operator

and quantifier $q\in \{\mathtt{\text{ALL}},\mathtt{\text{DISTINCT}}\}$ (with DISTINCT as the default), let $T_L=⟦Q_L⟧$ and $T_R=⟦Q_R⟧$, with $\mathrm{bag}(T_L)=⟨\tau ,B_L⟩$ and $\mathrm{bag}(T_R)=⟨\tau ,B_R⟩$ after coercion to the common type $\tau$. For any record $r$ of type $\tau$, write $M=B_L(r)$ and $N=B_R(r)$ for its multiplicities in the left and right operand (with $M,N\ge 0$).

UNION ALL.

The result is the bag union

$$\mathrm{bag}\left(⟦Q_L\mathit{UNION}\mathit{ALL}{Q}_R⟧\right)=⟨\tau ,B⟩\text{with}B(r)=M+N.$$

This is the bag analog of GQL UNION ALL: duplicates from both operands are preserved, and their multiplicities added.

UNION (distinct).

The result is the set-union of the supports of the two bags:

$$B(r)=\{\begin{array}{cc}1\hfill & \text{if }M+N>0,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

Equivalently, $⟦Q_L\mathit{UNION}{Q}_R⟧$ is obtained by applying the DISTINCT operator to $⟦Q_L\mathit{UNION}\mathit{ALL}{Q}_R⟧$.

EXCEPT ALL.

The result is bag difference:

$$B(r)=\max <!--\; FUNCTION\; APPLICATION\; -->(M-N,0).$$

Intuitively, duplicates of $r$ in the right operand cancel duplicates in the left operand, but never below zero.

EXCEPT (distinct).

The result is set difference:

$$B(r)=\{\begin{array}{cc}1\hfill & \text{if }M>0\text{ and }N=0,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

Equivalently, one can first apply DISTINCT to both operands and then form their EXCEPT ALL bag difference.

INTERSECT ALL.

The result is bag intersection:

$$B(r)=\min <!--\; FUNCTION\; APPLICATION\; -->(M,N).$$

Each duplicate appears as many times as it is present in both operands.

INTERSECT (distinct).

The result is set intersection:

$$B(r)=\{\begin{array}{cc}1\hfill & \text{if }M>0\text{ and }N>0,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

Again, this can be seen as INTERSECT ALL followed by DISTINCT.

For any of the distinct variants, and for EXCEPT ALL and INTERSECT ALL, if a record of the left operand and a record of the right operand are not comparable values, evaluation raises the data exception “values not comparable” (22G04) instead of producing a binding table.

Fallback semantics of OTHERWISE. The operator OTHERWISE is a fallback query conjunction rather than a set operator. For a binary composite

where $Q_L$ and $Q_R$ denote the left and right operands, respectively, let $T_L=⟦Q_L⟧$ and $T_R=⟦Q_R⟧$, with

where $\tau$ is their common combined type. Then

For a longer chain

the result is the binding table produced by the leftmost query operand whose result is non-empty, or the empty binding table of the combined type if all operands produce empty results. The same column-combination discipline as for the set operators applies; no duplicate elimination or bag arithmetic is performed. This describes result selection, not short-circuit evaluation: the General Rules for a composite query expression obtain the results of its query parts before choosing between them, so an operand is not skipped merely because an earlier result is non-empty.

Folding over multiple query parts. Let a composite query be written, after enforcing the uniform-operator rule, as

and let $\mathrm{Comb}\text{\_}\mathrm{op},q$ be the binary operation on binding tables induced by the chosen operator and quantifier (one of the six set operations, or the OTHERWISE fallback). Then the denotation of the composite query is the left fold

This algebraic account is extensionally equivalent to the stepwise binding table construction described for the composite query expression in the GQL standard and provides a compact description of how composite queries act on the intermediate binding tables produced by linear query statements.