← All papers
First page of MGQL: An Executable, Small-Step Semantics of GQL

MGQL: An Executable, Small-Step Semantics of GQL

Aditya Thimmaiah, Tong-Nong Lin, Milos Gligoric

cs.PL Aug 25, 2026 · v1 cs.DB
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.
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.

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.

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.

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.

ModuleContentLoC
Typing.leanTyping judgments1,133
SmallStep.leanStep relations2,267
Metatheory.leanSoundness proofs14,057
TypeChecker.leanExecutable checker1,364
Total23,655
Selected modules of the Lean 4 mechanization