Chapter 08Expressions and Evaluation

This chapter specifies how GQL expressions are typed and evaluated with respect to the current database state (store state) and the relevant environments. It makes explicit the interaction between value domains, implicit casts, errors, and three-valued logic, and clarifies how nulls affect the outcome of expression evaluation.

8.1 Expression Domains

Let $Ω$ denote the store state. A row environment for evaluating expressions in the context of a record $r$ is a partial mapping

η_{r} : 𝔸 ⇀ 𝕍 with η_{r} (n) = r (n) for all n \in dom (r),

and undefined for $n \notin dom (r)$ . A global environment $η_{g}$ binds constants (catalog objects, procedures, named graphs, types, etc.). An evaluation environment is the pair $⟨ η_{g}, η_{r} ⟩$ .

8.2 Typing and Evaluation

Typing and casting. Let $⊢ E : τ$ denote the statically derived typing judgment that expression $E$ has type $τ \in 𝕋$ . A (partial) implicit cast relation $⇝ \subseteq 𝕋 \times 𝕋$ determines where a value of type $τ$ may be coerced to $τ^{'}$ at use sites (e.g., integer $⇝$ decimal). We write $v : τ ⇝ τ^{'}$ when the coerced value exists.

Evaluation judgment. Using the abstract error carrier $Err$ declared in Chapter 6, whose tokens include, for example, division-by-zero, type-mismatch, and overflow, we write

⟨ Ω, η_{g}, η_{r} ⟩ ⊢ E ⇓ u

where $u \in 𝕍 \cup Err$ . Evaluation is total into $u$ but may yield errors (note that $null \in 𝕍$ ). When $r$ is a record, $η_{r}$ is the row environment induced by $r$ , and $Ω, η_{g}$ are fixed by the surrounding context, we use the abbreviation

⟦E⟧ (r) = u \Leftrightarrow ⟨ Ω, η_{g}, η_{r} ⟩ ⊢ E ⇓ u .

For a Boolean expression $φ$ , $⟦φ ⟧^{tv} (r)$ denotes the corresponding member of $𝔹_{3}$ , or an element of $Err$ , under the same convention.

Evaluation order. ISO/IEC 39075 specifies expression results through the General Rules but does not classify built-in functions as $pure$ , $stable$ , or $volatile$ . Unless precedence, parentheses, or a specific General Rule determines otherwise, effective evaluation is generally from left to right; whether expressions are actually evaluated in that order is implementation-dependent, particularly when an operand can raise a condition or when the result can be obtained without evaluating every part. Consequently, no stronger repeatability or evaluation-order guarantee is assumed here than the guarantee stated for the particular expression in the standard.

8.3 Truth Values and NULL

Three-valued logic. Boolean contexts range over the three-valued domain fixed in Section 6.1,

𝔹_{3} = {⊤, ⊥, U},

read as true, false, and unknown, respectively. The connective tables follow Kleene’s strong three-valued logic; for example:

\begin{aligned} \neg U & = U, \\ ⊤ \land U & = U, \\ ⊥ \land U & = ⊥, \\ etc. \end{aligned}

In concrete GQL, the abstract truth values $⊤$ and $⊥$ correspond to the Boolean constants TRUE and FALSE, and $U$ is represented by the Boolean null value, as specified in the standard; here, $𝔹_{3}$ is used as an abstract carrier for the three-valued semantics. A comparison $x 𝜃 y$ ( $𝜃 \in {=, \neq, <, \leq, >, \geq}$ ) evaluates to $U$ if either operand is $null$ . Predicates such as IS NULL and IS NOT NULL are two-valued (they never yield $U$ ).

Example (a library evaluation judgment). Let ${er}_{inc, 2} \in 𝕍$ denote an edge reference value whose referent is the second INCLUDES edge $e_{inc, 2}$ . Let the current row bind that reference:

η_{r} (i) = {er}_{inc, 2}, ρ_{E} (e_{inc, 2}) (late_fee) = 2.5 .

For the library store state $Ω_{lib}$ ,

⟨ Ω_{lib}, η_{g}, η_{r} ⟩ ⊢ i.late_fee > 0.0 ⇓ ⊤ .

Ordering and sorting. For each base type whose values admit ordering, let $≼$ denote the corresponding weak order. Values of different types are compared only when their types are comparable, possibly after applying permitted implicit casts to a common comparable type. If universal comparison is supported, values that are not otherwise comparable may instead be ordered according to an implementation-defined total order that remains stable throughout the execution of a GQL request.

The ordering used by ORDER BY additionally determines the placement of $null$ through either NULLS FIRST or NULLS LAST. This placement rule is specific to sorting: comparisons of $null$ with a material value using $<$ or $>$ yield $U$ , rather than treating $null$ as smaller or greater than that value.

Domains. Let $Var$ denote the (countable) universe of graph-pattern and scalar variables. A (variable) mapping is a partial function

μ : Var ⇀ 𝕍 .

We thus distinguish two forms of absence: (i) unbound variables, i.e., those $x \in Var ∖ dom (μ)$ for which $μ (x)$ is undefined, and (ii) the distinguished constant $null \in 𝕍$ among scalar values. Expressions may evaluate to a value $v \in 𝕍$ (including $null$ ), or they may raise a runtime error $err$ .

Truth values and evaluation. A predicate (Boolean) expression $ϕ$ is evaluated under a mapping $μ$ and graph $G$ as

⟦ϕ ⟧_{G, μ}^{tv} \in 𝔹_{3} \cup {err} .

Atomic comparisons use SQL-style three-valued logic:

\begin{aligned} ⟦ e_{1} = e_{2} ⟧_{G, μ}^{tv} & = {\begin{matrix} ⊤ & if the equality rules establish that the values are equal, \\ ⊥ & if the equality rules establish that the values are unequal, \\ U & otherwise, because a required comparison is unknown \end{matrix} \\ (for essentially comparable operands). \end{aligned}

In particular, the result is $U$ if either operand is $null$ . Equality of lists and records is determined recursively, so a material list or record containing a null value can also produce $U$ : an unequal component decides $⊥$ , all components equal decide $⊤$ , and an otherwise undecided component comparison gives $U$ . The other comparison operators follow their standard transformations and ordering rules; non-comparable operands raise the specified data exception. If evaluation of a required sub-expression raises $err$ , evaluation of the comparison raises the corresponding dynamic exception. The treatment of an error in an inessential part of a containing expression follows the implementation-dependent rule described below.

Connectives. We use Kleene’s strong truth tables:

\begin{matrix} \land & ⊤ & U & ⊥ \\ ̲ & ̲ & ̲ & ̲ \\ ⊤ & ⊤ & U & ⊥ \\ U & U & U & ⊥ \\ ⊥ & ⊥ & ⊥ & ⊥ \end{matrix} \begin{matrix} \lor & ⊤ & U & ⊥ \\ ̲ & ̲ & ̲ & ̲ \\ ⊤ & ⊤ & ⊤ & ⊤ \\ U & ⊤ & U & U \\ ⊥ & ⊤ & U & ⊥ \end{matrix} \neg ⊤ = ⊥, \neg ⊥ = ⊤, \neg U = U .

These tables determine the result but do not impose operational short-circuiting. For example, after $⊥$ in a conjunction or $⊤$ in a disjunction, the other operand is inessential to the truth value. If evaluating such an inessential part would raise an exception, ISO/IEC 39075 leaves it implementation-dependent whether that exception is raised.

Null-intolerant and null-tolerant predicates. The null behavior of each built-in is determined by its rules in the standard. As derived terminology in this formalization, a function $f$ is strict if any $null$ argument yields $null$ . A predicate $p$ is null-intolerant if any $null$ argument yields $U$ . Non-strict/total built-ins may map $null$ to a concrete value (e.g., $coalesce$ ).

Null predicates for composites (conformance). For list and record values the null check also includes IS [NOT] CONTAINING NULL, which inspects elements/fields for the presence of $null$ ; availability of this predicate follows the corresponding conformance feature in the GQL standard.

SAME predicate. The optional SAME predicate (Feature G114) takes at least two permitted arguments; generalized arguments require Feature G117. If an argument is null, it raises 22004, and if two arguments are not comparable, it raises 22G04. Otherwise, its result is $⊤$ exactly when every pair of arguments compares equal, and $⊥$ otherwise.

Filtering. For a bag $B$ of mappings, the WHERE filter $ϕ$ is

{filter}_{ϕ} (B) : = \underset{μ \in B}{⊎} {\begin{matrix} μ & if ⟦ϕ ⟧_{G, μ}^{tv} = ⊤, \\ (omit) & if ⟦ϕ ⟧_{G, μ}^{tv} \in {⊥, U} \end{matrix}

and is undefined (signals a dynamic exception) if $⟦ϕ ⟧_{G, μ}^{tv} = err$ for any $μ$ .

Chapter 8 — Takeaways.

Purpose: Specified how expressions were typed and evaluated relative to a graph store state and variable environments.
Introduced: A static typing discipline for expressions; evaluation rules for arithmetic, comparisons, and predicates; a three-valued truth model driven by unknown values.
Key distinctions: Static typing versus dynamic evaluation; ordinary Boolean reasoning versus three-valued reasoning in the presence of unknowns.
Consequences: Made filtering semantics precise under unknowns and errors; identified the specified implementation-defined and implementation-dependent evaluation choices; provided reusable evaluation machinery for grouping, ordering, and updates.
Bridge: Enabled the algebraic layer to treat queries as compositions of operators over binding tables.