Chapter 16Constraints

This chapter formalizes integrity constraints for property graphs in GQL and explains how they interact with the underlying typing discipline. We begin with key and uniqueness constraints based on constraint graph patterns, and then describe their enforcement during updates and transactions. Finally, we connect these dynamic checks to a lightweight effect system, which approximates write footprints and write conflicts without claiming to determine evaluation-order or context dependence, or result determinism.

16.1 Keys and Uniqueness

Recall from Section 15.3 that a key label set identifies a keyed node or edge type in a graph type and is not itself an integrity constraint.

Remark (scope as a graph pattern). The scope of a constraint is a deterministic constraint graph pattern $P$ introduced by FOR. Its main element variable identifies the constrained node or edge; an edge scope also declares its endpoint variables.

Key specifications. A key or unique specification is a tuple

where $\stackrel{}{c¯}=⟨c_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,c_n⟩$ is a sequence of $n\ge 0$ key value components. A component is the main element variable, an endpoint variable of an edge scope, or a property reference rooted at one of those variables. For a binding $b$ matched by $P$, let

Property references use the expression semantics of GQL: an absent property yields $\mathrm{null}$ when the declared result type is nullable, and otherwise raises the prescribed data exception. Thus $\mathrm{absent}$ never becomes a key value component.

Non-distinctness (for KEY and UNIQUE). Write $a\approx b$ when $a$ and $b$ are not distinct under GQL’s recursive value-comparison rules, and lift this relation pointwise to key tuples:

In particular, two null values are non-distinct; the rule also applies recursively to composite supported property values.

Constraint-scope notation. For a deterministic constraint graph pattern $P$, let ${\mathrm{match}}_G(P)$ be the set of bindings in its match result over $G$, with multiplicities ignored. For $b\in {\mathrm{match}}_G(P)$, $\mathrm{main}(b)$ is the graph element bound to the main element variable of $P$. The predicate $\mathrm{nullContaining}(v)$ holds exactly when $v$ is the null value or is a composite value having a recursively null-containing component.

Key constraint (KEY). A graph $G$ satisfies $\mathrm{KEY}(\chi )$ iff every key tuple is not null-containing and any two constrained elements with non-distinct key tuples are identical:

Null-containment is recursive, so a composite component containing the null value also violates the key constraint.

Uniqueness constraint (UNIQUE). A graph $G$ satisfies $\mathrm{UNIQUE}(\chi )$ iff any two constrained elements with non-distinct key tuples are identical:

No separate null-containment test is performed for $\mathrm{UNIQUE}$. When $n=0$, all empty key tuples compare alike, so either form permits at most one constrained element.

Example: BookHasKey. The BookHasKey declaration in Section 4.2 has the key specification

For the bindings ${\beta }_1$ and ${\beta }_2$ produced by this constraint pattern for the two book nodes in the library example,

Both tuples are non-null-containing and they are unequal, so the two book nodes satisfy the KEY requirement. If two bindings for distinct book nodes instead produced the same non-null ISBN tuple, then $\mathrm{main}({\beta }_1)\ne \mathrm{main}({\beta }_2)$ would violate $\mathrm{KEY}({\chi }_{\mathtt{\text{Book}}})$. Under a hypothetical UNIQUE declaration with the same specification, equal ISBN tuples would be non-distinct and would likewise require the main elements to be identical; unlike KEY, UNIQUE performs no separate null-containment test.

General constraint specifications. Let $\mathrm{CDesc}$ be the disjoint union of the carriers of key-constraint and unique-constraint descriptors. Every constraint defined by this edition is of exactly one of those two kinds. Its descriptor contains its name, registered-subject set, deterministic scope, and key value component specification. Constraints in a graph type apply to all graphs registered as subjects of that graph type; constraints defined in a graph apply only to that graph. Concrete examples are shown in Section 4.2.

For each constraint body $C$, let $\mathrm{CBNF}(C)$ be the implementation-defined, deterministic and idempotent normal form representing its equivalence class. Two bodies are body-equivalent exactly when their normal forms are equal; equivalence accounts for both equivalent constraint scopes and equivalent key value component specifications. The analogous normal form $\mathrm{CSNF}$ for a constraint specification also retains its constraint name. These normal forms determine the scope and requirement information represented in constraint descriptors.

Syntactic form of constraint specifications. Constraint specifications occur as CONSTRAINT body items of a nested graph type specification and in standalone constraint-management statements:

graph-type-body-item ::= ... | "CONSTRAINT" constraint-spec
constraint-spec ::= constraint-name constraint-body
constraint-body ::= "FOR" constraint-graph-pattern
                    "REQUIRE" constraint-requirement
constraint-requirement ::= key-value-spec "IS" "KEY"
                         | key-value-spec "IS" "UNIQUE"
key-value-spec ::= key-value-component
                 | "(" [ key-value-component-list ] ")"
key-value-component-list ::= key-value-component
                             { "," key-value-component }
key-value-component ::= element-variable [ "." property-name ]

create-constraint-stmt ::=
  "CREATE" ( "CONSTRAINT" [ "IF" "NOT" "EXISTS" ]
             | "OR" "REPLACE" "CONSTRAINT" )
  [ constraint-parent-graph-spec ] constraint-spec

drop-constraint-stmt ::= "DROP" "CONSTRAINT" [ "IF" "EXISTS" ]
                         [ constraint-parent-graph-spec ] constraint-name

constraint-parent-graph-spec ::= graph-expression "."

If the parent graph specification is omitted, CURRENT_GRAPH is implicit. Let ${\mathcal{I}}_G$ be the selected graph’s direct constraint dictionary and, when it has a constraining graph type, let ${\mathcal{I}}_{\mathrm{GT}}$ be that type’s constraint dictionary. Constraint names are unique independently of origin, so their domains are disjoint. A plain CREATE CONSTRAINT using a name already in ${\mathcal{I}}_G$ raises G1004; without IF NOT EXISTS, a name already in ${\mathcal{I}}_{\mathrm{GT}}$ is not permitted. If the new body is body-equivalent to a constraint in either dictionary and IF NOT EXISTS is absent, creation raises G1006. With IF NOT EXISTS, an existing name or a body-equivalent constraint in either dictionary makes the statement a no-op. OR REPLACE can replace only a same-named constraint in ${\mathcal{I}}_G$; it cannot replace an inherited constraint, and the body-equivalence rule still applies. Otherwise, creation validates the constraint against the selected graph before adding it to ${\mathcal{I}}_G$; dropping removes a direct constraint from that dictionary. An inherited constraint cannot be dropped in this way.

16.2 Constraint Enforcement and Effects

Graph-type conformance ${\mathrm{\Sigma }}_{\text{typing}}$. For an optional constraining graph-type reference, define ${\mathrm{\Sigma }}_{\text{typing}}({\mathrm{GT}}^{?})$ as follows. When ${\mathrm{GT}}^{?}=\mathrm{GT}$, it is the clause requiring every node and edge to be of a node or edge type specified by the resolved graph type, including exact label/property sets, property value types, directionality, and endpoint node types, and requiring every constraint of that graph type to be satisfied. Failure means that the graph is no longer of its constraining graph type and is reported as graph type violation G2000. For ${\mathrm{GT}}^{?}=\mathrm{none}$ the component is empty.

Direct graph constraints and graph-type conformance. Let $\mathrm{GE}=⟨G,{\mathrm{GT}}^{?},{\mathcal{I}}_G⟩$ be the active graph entry. Its direct constraint set is

The derived set ${\mathcal{I}}_{\mathrm{active}}(\mathrm{GE})$ from Section 15.5 remains useful when referring collectively to every constraint registered for the graph, but validation retains the two origins: graph-type constraints are part of the graph-type-conformance test, while ${\mathcal{I}}_{\mathrm{direct}}$ is validated directly. Define

The first component is empty for an open graph and otherwise states that the graph is of its constraining graph type, including satisfaction of that graph type’s constraints. The second contains the key or unique constraints defined directly on this graph. No declaration from an unrelated graph entry or graph type is consulted.

Satisfaction of a constraint set. Each semantic clause $\sigma \in ⟦\mathrm{GE}⟧$ has a satisfaction relation $G\vDash \sigma$. For any set of clauses $S$, write

This is the meaning of the satisfaction test used by the enforcement below. The effect of these checks on insertion, update, and deletion is illustrated in Section 4.3.

Key and uniqueness constraints. Every descriptor in ${\mathcal{I}}_{\mathrm{active}}(\mathrm{GE})$ contributes exactly the $\mathrm{KEY}(\chi )$ or $\mathrm{UNIQUE}(\chi )$ clause described in Section 16.1. This uses the descriptor’s deterministic constraint graph pattern as scope and retains its complete key value component sequence; it is not reduced to a global label/property dictionary.

Validation predicate. For an active graph entry $\mathrm{GE}$ with pre-state graph $G$ and a coalesced update delta $\mathrm{\Delta }$, define

Constraint enforcement. After a primitive data-modifying statement has produced its provisional graph, every constraint in ${\mathcal{I}}_{\mathrm{direct}}(\mathrm{GE})$ is dynamically validated by that statement’s General Rules; failure raises integrity constraint violation (23000). The separate graph-type-conformance test also checks the structural requirements and every constraint of the resolved graph type; failure raises graph type violation G2000. The statement cannot complete successfully while either validation fails.

16.3 Effect System and Write-Purity

The following informative effect system is defined only for query statements and data-modifying statements. Catalog-modifying statements are outside its domain and retain their statement-specific rules.

Here $\mathrm{\Sigma }$ is the applicable static graph-type descriptor and $\mathcal{T}$ is a finite typing environment for binding variables. For $X\in \{V,E\}$, let ${\mathcal{T}}_X$ be the restriction of $\mathcal{T}$ to variables whose declared graph-element reference type has kind $X$; membership of a variable in ${\mathcal{T}}_X$ abbreviates membership in the domain of that restricted environment. The carrier of static effects is written $𝔈$, so it is distinct from the typing environment. Effects form a commutative idempotent monoid $(𝔈,{\bigsqcup }_{\mathrm{eff}},\varnothing )$, where ${\bigsqcup }_{\mathrm{eff}}$ combines effects and $\varnothing$ denotes the absence of effects.

Let $P$ range over read parts, $S$ over query or data-modifying statements, $a$ over primitive update-action templates, $U$ over finite write parts composed of such templates, ${\mathcal{T}}^{\prime }$ over output typing environments, and ${𝜀}_{\mathrm{eff}}\in 𝔈$. The rules below use two auxiliary static judgments:

The first holds when the read part $P$ is well typed under $\mathrm{\Sigma }$ and $\mathcal{T}$, producing the extended environment ${\mathcal{T}}^{\prime }$. The second holds when every target and embedded expression of the action template $a$ is well typed in the given environment. For a write part $U$, $\mathrm{fv}(U)$ is the set of binding variables occurring free in its action templates.

We use the following effect-oriented judgments:

The static effect ${𝜀}_{\mathrm{eff}}$ is a conservative description, derived without executing the statement, of the kinds of state changes that the evaluated construct may perform. A statement is write-pure in this effect model iff its static effect is empty, that is, iff ${𝜀}_{\mathrm{eff}}=\varnothing$. This says only that the statement has no modeled graph-data write. It does not imply that evaluated expressions are deterministic, exception-free, independent of evaluation order, or independent of observable context.

Primitive update actions (meta-language). The operational semantics of DML (cf. Chapter 14) produces a coalesced update delta $\mathrm{\Delta }$, understood as a finite sequence of primitive actions over the store. We write $a\in \mathrm{\Delta }$ for such actions and use the following representative constructors: Here $i,u,v\in V$ are node identities, $j\in E$ is an edge identity, $k\in 𝕂$ is a property key, $w\in 𝕍$ is a value, $\ell \in 𝕃$ is a label, $d$ is directedness, $W$ is an initializer map from property keys to concrete values, and ${\Lambda }_V,{\Lambda }_E$ are the node- and edge-label sets assigned at creation time.

These constructors are not user syntax; they are meta-level names for the store-level steps that realize the write part $U$. Where we use schematic typing-level actions such as $\mathrm{Create}⟨\cdot ⟩$, they are understood as abstracting the same runtime updates that are ultimately lowered to the corresponding $\mathrm{insNode}$ or $\mathrm{insEdge}$ actions.

Primitive effects and algebra. For static analysis, each primitive update action is abstracted by a primitive effect that records its write footprint while omitting runtime-specific information such as element identities, endpoint identities, and computed property values. We model these effects by a small set of constructors used in the meta-language.

Parameters range over vertex-label sets ${\Lambda }_V\subseteq 𝕃$, edge-label sets ${\Lambda }_E\subseteq 𝕃$, property keys $k\in 𝕂$, element kinds $X\in \{V,E\}$, and labels $\ell \in 𝕃$. The symbol ${\top <!--\; FUNCTION\; APPLICATION\; -->}_{\Lambda }$ denotes an implementation-agnostic “unknown or unconstrained” label-set abstraction.

The effect combination introduced above is commutative, so the order in which effects are combined is irrelevant, while idempotence means that recording the same effect more than once does not change the combined effect.

We write $e_{\mathrm{eff},1}{\le }_{\mathrm{eff}}{e}_{\mathrm{eff},2}$ when $e_{\mathrm{eff},2}$ is a less specific abstraction of $e_{\mathrm{eff},1}$; for example,

The join operator is monotone with respect to this order. In particular, for every finite family of effects, if $e_{\mathrm{eff},i}{\le }_{\mathrm{eff}}{e}_{\mathrm{eff},i}^{\prime }$ for each $i\in \{1,\dots <!--\; FUNCTION\; APPLICATION\; -->,n\}$, then

Thus, replacing any component effect by a less specific abstraction yields a correspondingly less specific abstraction of the combined effect.

Effect of actions (representative). The abstraction function $\mathrm{peff}$ maps primitive runtime actions to their corresponding primitive static effects:

Template sets. Let $U$ be a finite, textually ordered list of action templates.

Here ${\bigsqcup <!--\; FUNCTION\; APPLICATION\; -->}_{\mathrm{eff}}$ is the finite join in the effect algebra defined above.

Statement typing with effects. Let a statement be $S\equiv P⊳U$, where $P$ is the read part, such as a pattern and its filters, and $U$ is the write part.

Hence, query-only statements, which have no write part, satisfy ${𝜀}_{\mathrm{eff}}=\varnothing$ and are write-pure in this limited sense.

No unbound writers. A write part may refer only to variables bound by its preceding read part:

Meta-level single-writer approximation (informative). For optimizer analysis only, call a statement stat-det with respect to writes if, for each entity variable $x$ and property key $k$, at most one $\mathrm{setProp}\ast (x,k,\cdot )$ template remains after static simplification of $U$. This is neither GQL syntax nor a conformance condition; the concrete data-modifying statements retain their own static and dynamic rules for repeated target properties.

Static conflict approximation and ordering constraints Let $\mathrm{MayConflict}$ be a symmetric predicate on pairs of effects. It holds for ${𝜀}_{\mathrm{eff},1}$ and ${𝜀}_{\mathrm{eff},2}$ if

contains, up to ${\le }_{\mathrm{eff}}$, a potentially conflicting pair of the primitive effect constructors defined above, possibly on aliased targets. A conservative alias analysis may mark bindings that can denote the same runtime element. The predicate $\mathrm{MayConflict}$ is only a meta-level optimizer aid: it may prevent a reordering whose equivalence has not otherwise been established, but it introduces no GQL isolation-barrier annotation and no additional rejection rule.

CREATE (schematic). In the schematic rules below, $\mathsf{storeAssignableTo}$ abbreviates the applicable GQL store- assignment check. Predicates $\mathrm{closed}(x)$ and $\mathrm{open}(x)$ classify the declared graph-element reference type of $x$. A closed type supplies property signature $\mathrm{\Psi }$; an open type admits any supported property value type. For vertex creation with initializer map $P$:

SET/DELETE.

Null assignment and property removal. A SET property item performs store assignment to the property’s declared type. The null value is therefore stored only when that type is nullable; otherwise it is not assignable and the prescribed error is raised. Assigning null is never lowered to property removal. Property removal is a separate data-modifying operation expressed by REMOVE.

Effect soundness (informative) Let ${𝜀}_{\mathrm{eff},S}$ be the static effect of $S$ and let $\mathrm{\Delta }$ be the coalesced sequence of primitive actions produced at runtime. Every primitive action in $\mathrm{\Delta }$ refines some $e_{\mathrm{eff}}\in {𝜀}_{\mathrm{eff},S}$ under ${\le }_{\mathrm{eff}}$. This establishes soundness only for the write-footprint abstraction. A rewrite cannot be justified from ${𝜀}_{\mathrm{eff},S}$ alone: it must separately preserve evaluation order, exceptions, result bags, context-dependent expression behavior, and all other observable behavior.

Micro-derivation: write-purity of query-only statements (informative) If $S$ has no write part (i.e. $S\equiv P$ with result production only), then $\mathrm{\Sigma };\mathcal{T}⊢S:\varnothing$. Therefore $S$ performs no writes described by this effect algebra. Reordering or common-subexpression elimination additionally requires the relevant expressions to be independent of the changed evaluation order and context, to preserve exception behavior, and to preserve the result bag.

Constraint-Preserving Execution Recall the graph-entry validation set $⟦\mathrm{GE}⟧$ and validation predicate ${\mathrm{ok}}_{\mathrm{GE}}(G,\mathrm{\Delta })$ from the previous section. An execution of a data-modifying statement within a transaction, with pre-state $G$ and coalesced delta $\mathrm{\Delta }$, is constraint-preserving if ${\mathrm{ok}}_{\mathrm{GE}}(G,\mathrm{\Delta })$ holds, that is, if the post-state $G\oplus \mathrm{\Delta }$ satisfies its constraining graph type and all key/unique constraints defined directly on that graph. The operational semantics of DML rejects a structural graph-type violation or a violation of any direct graph constraint. Thus a primitive data-modifying statement completes successfully only if its post-state is constraint-preserving. Catalog-modifying statements are not modeled as $G\oplus \mathrm{\Delta }$; each uses the checks specified by its own Syntax and General Rules.