Chapter 06Data Model

This chapter fixes the abstract data model that underlies the semantics of GQL and serves as the common reference point for later chapters. It introduces the basic universes of identifiers, types, and values, defines the property-graph structure used for stored graphs, and explains how paths, lists, and records are treated as first-class values. The presentation is independent of any particular physical representation and is parameterized by the conformance options of the GQL standard (for example, with respect to supported property value types).

6.1 Universes and Notation

Let

The abstract three-valued truth carrier used throughout is ${𝔹}_3=\{\top <!--\; FUNCTION\; APPLICATION\; -->,\perp ,U\}$; its connection to GQL Boolean values is defined in Section 8.3. Types and their characteristics (material/nullable/immaterial) as well as the naming of types and base types are defined by the GQL specification. Availability of the null and empty immaterial value types and explicit nullability follows the standard’s conformance options; the empty type contains no value and therefore contributes no additional element to $𝕍$. No cardinality assumption is imposed on these ambient universes; by contrast, the node and edge carriers of every concrete graph are finite, as is every binding table used below.

Notational convention. We reserve blackboard-bold symbols such as $𝕍$ for universes (e.g., the universe of values), and we use plain symbols such as $V$ only for graph-specific carriers (e.g., the node set of a concrete graph).

A partial function is written $f:A\rightharpoonup B$. The powerset of $X$ is $\mathcal{P}(X)$. Let $\mathbb{N}$ denote the set of natural numbers. A multiset (bag) over $X$ is identified with a multiplicity function $B:X\to \mathbb{N}$. The set of all such multisets is denoted $\mathcal{M}(X)$, and its finite-support subset is denoted ${\mathcal{M}}_{\mathrm{fin}}(X)$. We also write $B(X):={\mathcal{M}}_{\mathrm{fin}}(X)$ when a finite bag is used as a meta-level type. Pointwise bag sum is written $B_1\uplus B_2$, and ${\uplus <!--\; FUNCTION\; APPLICATION\; -->}_i{B}_i$ denotes its indexed iteration. For bags $B^{\prime },B\in \mathcal{M}(X)$, $B^{\prime }$ is a submultiset of $B$, written $B^{\prime }{⊑}_{\mathrm{bag}}B$, iff $B^{\prime }(x)\le B(x)$ for every $x\in X$. For a bag $B$, $\mathrm{supp}(B):=\{x\mid B(x)>0\}$ is its support, and $1[P]$ is $1$ when proposition $P$ holds and $0$ otherwise.

Finite sequences over $X$ are denoted $X^{\ast }$. Binding-table records use closed (material) record types: a record type is a total function ${\tau }_{\mathrm{rec}}:\mathrm{fields}({\tau }_{\mathrm{rec}})\to 𝕋$, where $\mathrm{fields}({\tau }_{\mathrm{rec}})\subseteq 𝔸$ is its declared field set; a record over ${\tau }_{\mathrm{rec}}$ is a total assignment $r:\mathrm{fields}({\tau }_{\mathrm{rec}})\to 𝕍$ (each declared field has a value; $\mathrm{null}$ is a value of an appropriate null-containing type). The set of well-typed records inhabiting ${\tau }_{\mathrm{rec}}$ is

To retain the metadata of the GQL binding-table descriptor, we model a binding table as

where $\mathrm{ord}$ is either $\mathrm{unordered}$ or determines an ordering of the record occurrences of $B$, and $\mathrm{pcs}$ is either $\mathrm{notSet}$ or a preferred permutation of the field names of ${\tau }_{\mathrm{rec}}$. The effective column-name sequence is $\mathrm{pcs}$ when a preferred sequence is set and, otherwise, is the field names of ${\tau }_{\mathrm{rec}}$ in ascending order. We write $\mathrm{BT}$ for this domain and $\mathrm{bag}(T)=⟨{\tau }_{\mathrm{rec}},B⟩$ for the bag projection used by order-insensitive algebra. The unit binding table is the unordered table with the unit record $⟨⟩$, an empty record type, and no preferred column-name sequence.

6.2 Property-Graph Structure

The term property graph has been used in the literature for several closely related graph models whose formalizations are not identical (Angles 2012; Angles 2018). Depending on the formalization, differences may concern, among other things, element identities, the cardinality and applicability of labels and properties, edge direction, and the treatment of parallel edges (Angles 2018; Francis et al. 2018; Deutsch et al. 2022). In this book, the term is used in a deliberately broad sense, while the concrete model adopted below is closely aligned with the property-graph data structures defined by the GQL standard (International Organization for Standardization 2024). We refer to an instance of this model as a GQL graph.

The tuple below models only a graph’s structural contents; its optional constraining graph type and graph constraint dictionary are descriptor-level information modeled by the graph entry in Section 15.5. A GQL graph is modeled as a 9-tuple

where:

When $\mathrm{dir}(e)=\leftrightarrow$, $\mathrm{src}(e)$ and $\mathrm{dst}(e)$ are only a representational ordering of the two endpoints; they do not assign source and destination semantics to an undirected edge. Loops are allowed (edges $e\in E$ with $\mathrm{src}(e)=\mathrm{dst}(e)$), as are mixed graphs and multigraphs; each property name is unique within its carrier (node/edge), and property values belong to the supported value types. This abstract structure is instantiated by the library schema and graph instance introduced in Section 4.1.

For example, in that instance $V=\{r,a,c,l,b_1,b_2\}$ and $E$ contains the six displayed edges. For the OWNS edge $e_{\mathrm{owns}}$, ${\lambda }_V(r)=\{\mathtt{\text{Reader}}\}$, ${\rho }_V(r)(\mathtt{\text{firstname}})=\mathtt{\text{’Alice’}}$, ${\lambda }_E(e_{\mathrm{owns}})=\{\mathtt{\text{OWNS}}\}$, $\mathrm{src}(e_{\mathrm{owns}})=r$, $\mathrm{dst}(e_{\mathrm{owns}})=a$, and $\mathrm{dir}(e_{\mathrm{owns}})=\to$; the edge-property map is illustrated by ${\rho }_E(e_{\mathrm{inc},1})(\mathtt{\text{late\_fee}})=0.0$ for the first INCLUDES edge.

Because property maps are partial, let $\mathrm{absent}\notin 𝕍$ denote absence of a property, rather than a GQL value, and use the totalized lookup notation

Evaluation of a property reference is a separate operation: in particular, when its declared type is nullable, a reference to an absent property evaluates to $\mathrm{null}$, as specified by GQL.

Remark on “openness/closedness”. If a graph has an associated graph type, it is closed (it permits only elements conforming to that type); otherwise it is open.

Modeling choices. Although the tuple definition already fixes the types of ${\lambda }_V,{\lambda }_E$ and ${\rho }_V,{\rho }_E$, we make two conventional but important choices explicit: (i) Labels as sets. By typing ${\lambda }_V:V\to \mathcal{P}(𝕃)$ and ${\lambda }_E:E\to \mathcal{P}(𝕃)$ we treat labels as sets (unordered, without duplicates). Thus, label membership is the primitive notion (e.g., $\ell \in {\lambda }_V(v)$), and adding/removing a label is idempotent at the semantic level. (ii) Properties as partial maps. By typing ${\rho }_V:V\to (𝕂\rightharpoonup 𝕍)$ and ${\rho }_E:E\to (𝕂\rightharpoonup 𝕍)$ we model properties as partial functions from keys to values. For a particular node or edge, a property key may be absent from its property map, that is, it may lie outside the domain of the corresponding partial function. This is semantically distinct from the property being present with value null, when null is supported.

6.3 Values and Types

Base universes. We use the single universes $𝔸,𝕃,𝕂,𝕋$, and $𝕍$ fixed in Section 6.1; no second value or type universe is introduced here. Let $⊑\subseteq 𝕋\times 𝕋$ be a reflexive, transitive subtyping relation, where ${\tau }_1⊑{\tau }_2$ is read as “${\tau }_1$ is a subtype of ${\tau }_2$”, meaning that every value of type ${\tau }_1$ is also admissible as a value of type ${\tau }_2$.

Type constructors.

Chapter 17

Typing contexts. A type environment $\mathrm{\Xi }$ is a finite map from names to types (for properties, parameters, and binding variables). We write the standard judgment $\mathrm{\Xi }⊢e:\tau$ for expressions. Subsumption: if $\mathrm{\Xi }⊢e:\tau$ and $\tau ⊑{\tau }^{\prime }$, then $\mathrm{\Xi }⊢e:{\tau }^{\prime }$.

Expression-evaluation interface. Let $\mathrm{Err}$ be an abstract carrier of error or exception-condition tokens. For an expression $E$ and a record $r$, we reserve $\mathit{⟦E⟧}(r)\in 𝕍\cup \mathrm{Err}$ for evaluation in the row environment induced by $r$, with the store and global environment fixed by the surrounding execution context. For a Boolean expression $\phi$, $\mathit{⟦\phi }{⟧}^{\mathrm{tv}}(r)$ analogously denotes a member of ${𝔹}_3$ or an error. The complete evaluation judgment is given in Chapter 8.

6.4 Basics of Paths as Data

A path in a graph $G$ is a finite sequence of graph elements of odd length that starts and ends at a node, i.e., a node–edge–$\dots <!--\; FUNCTION\; APPLICATION\; -->$–edge–node sequence $⟨v_0,e_1,v_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,e_n,v_n⟩$ of length $2n+1$; the orientation of each edge in the path is determined relative to the order of nodes in the sequence ($\to$ to the left/right, or undirected). We distinguish the following classes: trail (no repeated edges), simple (no repeated nodes, except possibly first $=$ last), and acyclic (no repeated nodes). Formally, $w=⟨v_0,e_1,v_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,e_n,v_n⟩$ is simple iff $v_i\ne v_j$ for all $0\le i<j\le n$ except possibly the pair $(i,j)=(0,n)$, allowing $v_0=v_n$. We write $\mathrm{Path}(G)$ for the set of all such paths in $G$. The full treatment of path values, concatenation, path modes, and result projection is given in Chapter 10.

Material path values and length. We write $\mathrm{PathVal}$ for the carrier of material path values. In accordance with the GQL value model, a path value encapsulates a path element list of graph-element reference values; whenever none of those references is invalidated, their referents identify a path, independently of the current working graph. Concretely, a material path value is written as

where $k\ge 0$, each $n_i$ is a node reference value, each $e_i$ is an edge reference value, and the list alternates starting and ending with a node reference (hence has odd length $2k+1$). The path length is the number of edge references:

In particular, the length-zero path $\mathrm{PATH}[⟨n_0⟩]$ is well-formed and satisfies

Null-propagation. If $p=\mathrm{null}$ (i.e., $p$ is the null value admitted by a nullable path value type), then $\mathrm{PATH}\text{\_}\mathrm{LENGTH}(p)=\mathrm{null}$. Malformed representations (that do not alternate or do not start/end in a node reference) are outside this well-formed path domain; the standard path-value constructions do not produce them. A full formalization of path values, path modes, finiteness and selection, and path accessors is given in Chapter 10.

6.5 Lists and Structural Access

List, record, and path types are constructed value types. They provide the abstract carriers for nested and structured values that occur as property values, as components of binding tables, and as results of expressions (including path-returning queries). By fixing their behavior here, we obtain a uniform basis for the typing and evaluation rules for structural accessors and functions in later chapters.

• Lists. A list value is a finite sequence $[v_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,v_n]$. Conceptually we describe indexing in ordinal (1-based) terms: $[v_1,\dots <!--\; FUNCTION\; APPLICATION\; -->,v_n][i]=v_i$ if $1\le i\le n$; the precise mapping from index expressions to positions (ordinal vs. offset indexing, from-end handling, and out-of-range behavior) follows the session’s list-behavior policy. The declared type of list concatenation is determined by GQL’s general combination of value types; evaluation then follows the standard null and maximum-cardinality rules.
• Records. A record value is a finite mapping from field names to values, written $r.n$ for the value in field $n$. For records with a closed record type ${\tau }_{\mathrm{rec}}$, a record value $r$ supports field access $r.n$ whenever $n\in \mathrm{dom}({\tau }_{\mathrm{rec}})$. If the source record has no field named $n$, the reference returns $\mathrm{null}$ when its declared type is nullable; otherwise it raises data exception 22G03. Records model structured values such as rows of binding tables or compound results of expressions (e.g., a RETURN item with multiple named components), so that field access in the language can be defined once in terms of this generic record notion.
• Paths. For the path values defined above, we use nodes(p), edges(p), and length(p) as meta-level shorthands derived from the standard accessors $\mathrm{ELEMENTS}(p)$ and $\mathrm{PATH}\text{\_}\mathrm{LENGTH}(p)$; both standard accessors return null when their path input is null. By treating paths as first-class values with these primitive operations, we can later give uniform typing and evaluation rules for path-returning patterns and path functions, independently of how paths are physically represented in an implementation.