CS Paper Radar

MGQL: An Executable, Small-Step Semantics of GQL

Aditya Thimmaiah, Tong-Nong Lin, Milos Gligoric

cs.PL cs.DB ·submitted 2026-08-25 13:48 UTC · v1
publishedtheory

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.

Comment
Accepted at OOPSLA 2026
DOI
10.1145/3839459

Closest papers

Nearest neighbours by meaning across the whole index.

Rewriting Ontology-Mediated Property Graph Queries into GQL

cs.DB ·2026-08-20 ·Bianca Löhnert, Nikolaus Augsten, Cem Okulmus, Magdalena Ortiz
top venue similarity 0.75
Abstract

Ontology-based data access is intended for graph data, but practical support remains limited to SQL-like languages lacking the navigational and path-matching features fundamental to graph querying. Theoretical algorithms for navigational queries have long been available. Still, they have never been implemented, largely because practical graph query languages fell short of their theoretical counterparts and lacked the expressive power needed to support rewriting common ontology languages. The recent standardisation efforts around GQL and SQL/PGQ finally allow us to overcome this barrier and present a practical query rewriting technique for ontology-mediated navigational graph queries. Ontologies are written in a DL-Lite variant tuned to property graphs, and the queries in a GQL fragment with nested two-way regular path queries and which can be evaluated in Cypher. Preliminary experiments with our proof-of-concept prototype suggest that querying graph data with ontological knowledge may finally be within reach.

0.31

GQL Datatypes as an RDF Vocabulary

cs.DB ·2026-10-12 ·Dominik Tomaszuk, Daniel Szałaj
similarity 0.71
Abstract · 13 pages, 7 figures, 3 tables. Accepted for DMKG 2026 (2nd International Workshop on Data Management for Knowledge Graphs), Bari, Italy

The ISO GQL standard introduces a rich value-type system for property graphs, including scalar, temporal, byte-string, list, record, and dynamic union datatypes. The vocabulary presented here additionally covers a vector extension. At the same time, RDF-based knowledge graph systems identify literal datatypes by IRIs and interpret typed literals through value spaces, lexical spaces, and lexical-to-value mappings. This paper presents the GQL Datatypes RDF Vocabulary, a lightweight RDF vocabulary that represents selected GQL datatypes and the vector extension as RDF datatype IRIs and describes their hierarchy, aliases, and selected constraints using RDF, RDFS, OWL, and XML Schema Datatypes vocabulary terms. The vocabulary is intended to support interoperability between GQL-oriented property graph systems and RDF-based knowledge graph systems. We describe its namespace and datatype model, summarize its datatype coverage, and show how the accompanying generator and validator use the vocabulary. In the reference implementation, RDF literals retain GQL datatype IRIs; XSD mappings declared in the vocabulary support scalar validation, while lists, records, and vectors are encoded directly as JSON lexical forms of vocabulary-typed literals.

0.28

Build2SPARQL: A Large-Scale Text-to-SPARQL Benchmark Dataset for Building Knowledge Graph Querying

cs.AI ·2026-09-22 ·Wooyoung Jung
benchmarkcode/data similarity 0.65
Abstract · 26 pages, 2 figures, 16 tables. Data paper. Dataset openly available at https://zenodo.org/records/20451474. Under review at the ASCE Journa…

Building automation systems are increasingly represented as semantic knowledge graphs (KGs) using ontologies such as Brick and ASHRAE 223P, creating a machine-readable substrate for artificial-intelligence applications. One promising application is translating natural-language questions into SPARQL (text-to-SPARQL), which would let building operators query these graphs through language agents, but progress is limited by the scarcity of large natural-language/SPARQL benchmarks. This paper presents Build2SPARQL, a large-scale benchmark for building KGs generated by a KG-grounded pipeline: SPARQL queries are produced and validated entirely by graph-traversal code, while large language models generate only the natural-language questions, keeping query correctness independent of model behavior. The pipeline mines six query-pattern families -- linear chains, branching, UNION, aggregation, OPTIONAL, and attribute-filtered -- and phrases each query across five vocabulary registers. Applied to 201 building KGs (180 Brick, 21 ASHRAE 223P), it yields 6,136 executable SPARQL queries and 30,680 questions. A two-rater human validation of 300 questions found 98.8% semantic fidelity, 98.8% naturalness, and 84.0% operational plausibility. A retrieval-augmented evaluation across three open-weight language models raised exact-match accuracy from 0.2-20% (zero-shot) to 56-65% (three-shot retrieved).

0.21

Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer's Perspective

cs.DB ·2026-09-03 ·Lander Maes, Bryan-Elliott Tam, Jitse De Smet, Jos De Roo, Pieter Colpaert +1 more
similarity 0.65
Abstract

The Shape Rules Language (SRL) Working Draft defines how to derive new RDF triples from an RDF graph using inference rules. Each rule matches graph patterns and instantiates triple templates whose output feeds into validation pipelines, SPARQL queries, or further inference. RDF reasoning has traditionally relied on fixed entailment regimes (RDFS, OWL), rule-based ad-hoc languages such as N3, or other implementation-specific solutions without a shared standard. SRL introduces user-defined production rules with a defined grammar, dependency analysis, execution ordering, and termination guarantees. However, no authoritative implementation exists, leaving practitioners with little guidance on how to build a conformant engine or on what problems the language can solve. We implemented two SRL engines and evaluated both on classical RDF reasoning tasks for soundness, completeness, and speed. The first reuses an existing SPARQL query engine and its query parser; the second is a dedicated engine. The SPARQL-based engine reused an existing modular parser for query construction and SPARQL CONSTRUCT for triple production, reducing engine-specific work. The dedicated engine was two to six times faster, the gap widening as rule sets grow. Both engines were validated against the SRL conformance test suite, supplemented by additional use-case-driven tests. A usable SRL engine can be built inexpensively on top of a SPARQL engine, with a moderate speed trade-off that a dedicated implementation recovers. Despite the specification's immaturity, the language already supports practically useful reasoning tasks.

0.19

Same Pattern, Different Answer: A Reference Semantics and Divergence Map for GQL and SQL/PGQ Path Patterns

cs.DB cs.PL ·2026-09-19 ·Madhulatha Mandarapu, Sandeep Kunkunuru
code/data similarity 0.65
Abstract · 13 pages, 3 figures. Artifact: https://github.com/samyama-ai/gpml-conformance

GQL (ISO/IEC 39075:2024) is the first international standard for a graph query language, and SQL/PGQ (ISO/IEC 9075-16:2023) embeds the same pattern-matching core, GPML, in SQL. Both fix a precise semantics for path patterns: four path modes, four selectors, quantified segments. What engines compute for those patterns has never been measured. Work on GQL is theoretical and runs no engine; cross-engine work measures performance and normalises the semantics away. We build an executable reference semantics for the GPML path core and gate it against the six worked answers printed in the standard's own reference exposition. We then run a 17-construct suite against six releases of five products - Kuzu, DuckPGQ, Neo4j at 5.26 and 2026.04, Memgraph, Apache AGE - scoring each cell as conforming, diverging, rejected, or inexpressible in that dialect. Nine of seventeen constructs draw more than one answer across the engines that accepted them. Of 26 disagreements, 15 are silent - the query runs, returns a different multiset, raises no error - a silence ratio of 0.58. Scoring each divergence against the path mode each engine's manual declares separates language from implementation: 9 of 15 are documented differences, 6 are departures from the standard the engine implements. A metamorphic layer needing no reference semantics finds 39 self-consistency violations, yielding two minimal defects. No engine we measured parses the order the standard's own examples are written in, except the authors' own, which added it after this suite reported the gap. Suite, semantics, reproducers and results are open source.

0.34

Property Graph Techniques in Relational Databases

cs.DB ·2026-08-11 ·Malcolm Crowe, Fritz Laux
published similarity 0.64
Abstract · 6 pages, 1 figure

Current developments in standardization activities for database management systems include the development of the next versions of the Structured Query Language (SQL), and related standards for labelled property graphs. This short paper explores mechanisms for unified implementation of record-based relational and property graph databases: its contribution is that modeling SQL foreign keys as reference keys facilitates the graph insert and advanced pattern matching mechanisms of Property Graph Database Management Systems (PGDMS) and allows the construction of multiple type graph models on a single relational database.

0.60

Notation3: Graph Terms for RDF

cs.LO cs.AI ·2026-10-22 ·Dörthe Arndt, Pierre-Antoine Champin
similarity 0.64
Abstract · Submitted to TGDK

Notation3 Logic was introduced as an extension of RDF allowing the user to express rules on top of triples and to make statements about graphs. The original proposal of the logic only came with an informal specification of its semantics which has been refined later on. While this refinement clarified the meaning of rules and implicitly quantified variables, it left the meaning of graphs used as terms - so-called graph terms - open. In this paper we aim to close this gap. We discuss in detail, how graph terms are used in Notation3, which formal requirements they need to meet, and provide examples to illustrate the difficulties when defining their semantics. We then introduce an abstract syntax for the logic and define its semantics in two steps: similarly to RDF's simple interpretations, we define interpretations and basic entailment for Notation3 which covers plain RDF triples but also triples containing graph terms. N3-entailment is then an extension of basic entailment which assigns meaning to the different special predicates of the logic like for example the implication symbol. N3-entailment is defined in a way that it can be extended whenever a new predicate is added to the logic. As Notation3 Logic is currently under development, we expect many predicates to be added. Our research provides and important step towards the full standardisation of the logic.

0.24

Translating RDF 1.2 Graphs to Property Graphs

cs.DB ·2026-10-24 ·Maxime Jakubowski, Dominik Tomaszuk, Daniel Fernández-Álvarez, Ruben Taelman, Ruben Dedecker +2 more
similarity 0.63
Abstract · 13 pages, 5 figures. Accepted for the 2nd International Workshop on Data Management for Knowledge Graphs (DMKG 2026), Bari, Italy

RDF 1.2 introduces statement-level constructs, such as triple terms, reifiers, and descriptions, that pose new challenges for transforming RDF data into labeled property graphs (LPGs). This work presents and compares three algorithms for translating RDF 1.2 data into LPGs, each interpreting a different amount of the RDF 1.2 reification vocabulary. Algorithm Structural interprets no vocabulary and losslessly supports arbitrary RDF 1.2 graphs by representing triple terms explicitly as nodes; Direct interprets rdf:reifies to recover annotated edges while preserving reifiers as graph objects; and Fold additionally folds reifier descriptions into edge properties, resulting in a more concise, albeit lossy, LPG representation. We define the three translations, analyze which class of RDF 1.2 graphs each preserves, and experimentally evaluate their implementations. The experiments confirm the predicted trade-offs: all variants scale linearly on the tested workloads, the generality of Structural has no runtime penalty, and folding descriptions into edge records can significantly reduce the number of edges on description-heavy data.

0.35