MGQL: An Executable, Small-Step Semantics of GQL
Aditya Thimmaiah, Tong-Nong Lin, Milos Gligoric
cs.PL
Aug 25, 2026 · v1
cs.DB
TL;DR
Mechanizes a small-step semantics, schema-aware type system, and type soundness proof for a GQL fragment in Lean 4, totaling about 23,000 lines.
Abstract
ISO Graph Query Language (GQL) is the first international standard for property graph-based graph query languages, standardized as ISO/IEC 39075 in 2024. However, ISO/IEC 39075 codifies its semantics informally across 600+ pages of prose, making it difficult to formally reason about the standard or for a standard-faithful implementation. Existing formalizations are not adequate because they either: (1) significantly reduce the semantic complexity by omitting bag semantics, schemas, and composite queries on multiple graphs; (2) or significantly reduce the syntactic complexity by only considering isolated fragments such as pattern-matching, leaving the full query pipeline unformalized. Yet it is these semantic-syntactic features that make formalizing GQL non-trivial. We present MGQL, the first mechanized, small-step operational semantics for a substantial read-only fragment of GQL that is grounded in the ISO/IEC 39075 standard. Our formalization models multi-graph property graphs with mixed edge directionality and supports a large fraction of GQL pattern constructs: quantified paths and edges, directional and undirected matching, label expressions, pattern lists, and composite queries. The semantics is supported by a schema-aware type system that refines variable types via closed-graph schemas, tracks nullability, supports multiple composite query operators, and models quantified-path bindings with list types. We prove that our type system is sound, ensuring an end-to-end guarantee of well-formed queries yielding results that conform to their declared schemas. MGQL provides the first bridge between GQL's informal specification and a mechanized implementation, enabling formal reasoning about correctness.
Problem
ISO GQL (ISO/IEC 39075) specifies its semantics informally across 600+ pages of prose. Existing formalizations omit bag semantics, schemas, and composite queries, or cover only isolated fragments such as pattern matching.
Approach
MGQL defines an executable small-step operational semantics for a substantial read-only GQL fragment. The fragment covers multi-graph property graphs, quantified paths, directional and undirected matching, label expressions, pattern lists, and composite queries. A schema-aware type system refines types via closed-graph schemas, tracks nullability, and types quantified-path bindings as lists. Everything is mechanized in Lean 4 with inductive typing and step relations, plus an executable type checker.
Results
A type soundness theorem is proved: well-formed queries yield binding tables conforming to their declared schemas, with progress and preservation for the small-step layer. The mechanization spans about 23,655 lines in 14 modules, has zero sorry or user axioms, and is tested on LDBC SNB queries.
| Module | Content | LoC |
|---|
| Typing.lean | Typing judgments | 1,133 |
| SmallStep.lean | Step relations | 2,267 |
| Metatheory.lean | Soundness proofs | 14,057 |
| TypeChecker.lean | Executable checker | 1,364 |
| Total | | 23,655 |
Selected modules of the Lean 4 mechanization