The GQL Expressiveness Gap: What the New ISO Standard Can't Do

Introduction

In 2024, ISO released GQL (ISO 39075), the first international standard for property graph querying — a milestone that promised to unify the fragmented landscape of Cypher, Gremlin, and SPARQL extensions.

But formal analysis at VLDB 2025 and ICDT 2025-2026 reveals uncomfortable truths. GQL has expressiveness gaps. Some are carryovers from Cypher. Others are surprising: queries that recursive SQL can express but GQL cannot, despite complexity-theoretic expectations that they should be equivalent. This article examines what GQL can't do, why it matters, and how to work around these gaps while waiting for GQL v2.

What GQL Gets Right

Before diving into limitations, acknowledge what GQL achieves:

Property graphs as first-class citizens. GQL treats nodes, edges, and their properties as native constructs — unlike SQL's tables or SPARQL's triples — matching how engineers think about connected data.

Linear recursion via Kleene star. GQL introduces arbitrary pattern repetition with the * operator, solving Cypher's fixed-pattern limitation that prevented even-length path queries.

// GQL: Find all pairs connected by any-length KNOWS path
MATCH (a:Person)-[:KNOWS*]->(b:Person)
RETURN a.id, b.id

Path restrictors. GQL provides fine-grained path semantics: SHORTEST, SIMPLE (no repeated nodes), TRAIL (no repeated edges), ACYCLIC, and WALK. This precision matters for correctness in fraud detection.

SQL-like relational algebra. Familiar GROUP BY, ORDER BY, aggregation, and projection — engineers don't need an entirely new paradigm.

These are genuine advances. But they don't close all the gaps.

The Expressiveness Gap: Formal Results

Recent academic work has formally characterized what GQL cannot express. Four findings stand out.

1. Even-Length Path Query (ICDT 2025)

For years, the database community suspected Cypher couldn't express the regular path query (ℓℓ)* — finding node pairs connected by an even-length path. ICDT 2025 provided the formal proof: Cypher requires hardcoding each length. GQL fixes this with arbitrary pattern repetition:

MATCH (a)-[(e:REL*1..)]->(b)
WHERE length(e) % 2 = 0
RETURN a, b

This Cypher limitation is resolved. Other gaps persist.

2. GQL vs Recursive SQL (VLDB 2025, Libkin et al.)

The VLDB 2025 paper by Libkin et al. delivered a surprise: Core GQL and Core PGQ cannot express queries expressible in positive recursive SQL and linear Datalog.

This contradicts complexity-theoretic expectations — both languages operate in similar complexity classes. The gap stems from how GQL handles recursion: it recurses over patterns (graph structure), while recursive SQL recurses over values. When queries need value-based recursion — checking properties across recursive steps — GQL hits a wall.

3. Edge-Property Monotonicity

The canonical example from VLDB 2025: a money transfer graph where edges carry transaction amounts. Finding chains where amounts strictly increase at each hop is a classic fraud detection pattern.

// GQL: Can check NODE property monotonicity
MATCH path = (n:Account)-[:TRANSFER*]->(m:Account)
WHERE all(i IN range(0, length(path.nodes)-2) 
          WHERE path.nodes[i].balance < path.nodes[i+1].balance)
RETURN path

This works because path.nodes provides access along the path. But the same query with EDGE properties fails:

// GQL: CANNOT check EDGE property monotonicity
MATCH path = (n)-[r:TRANSFER*]->(m)
WHERE all(i IN range(0, length(path.relationships)-2)
          WHERE path.relationships[i].amount < path.relationships[i+1].amount)
RETURN path

GQL cannot compare consecutive edge properties within a recursive pattern match. The same limitation affects temporal queries — "find event sequences where timestamps strictly increase" — when timestamps live on edges.

Recursive SQL handles this naturally:

-- Recursive SQL: CAN check edge-property monotonicity
WITH RECURSIVE increasing_paths(start_id, end_id, last_amount, path) AS (
  -- Base case: single edge
  SELECT src, dst, amount, ARRAY[edge_id]
  FROM transfers
  
  UNION ALL
  
  -- Recursive case: extend path only if amount increases
  SELECT ip.start_id, t.dst, t.amount, ip.path || t.edge_id
  FROM increasing_paths ip
  JOIN transfers t ON ip.end_id = t.src
  WHERE t.amount > ip.last_amount
)
SELECT * FROM increasing_paths;

4. Meta-Property Queries

GQL does not support quantification over properties or labels. You cannot query the schema itself:

// "List all relationship types connecting Person to Company"
// "Find all nodes that have a property named 'status'"

This affects schema discovery, dynamic query generation, and multi-tenant systems. Workarounds — storing schema metadata as graph nodes — exist but are awkward.

Why This Matters Practically

These aren't academic. They block production queries.

Fraud detection. "Find transfer chains where amounts strictly increase at each hop" requires edge-property monotonicity. Financial institutions need this to spot structuring patterns. GQL cannot express it directly.

Temporal analysis. "Find event sequences where timestamps strictly increase" is fundamental to process mining and audit trails. When timestamps live on edges — as they should, because events are transitions — GQL hits the same wall.

Schema discovery. "What relationship types exist between these entity types?" requires workarounds where SQL's INFORMATION_SCHEMA provides first-class metadata access.

The VLDB 2025 analysis is blunt: current workarounds are "impractical even for small-sized graphs." Application-level post-processing sacrifices the declarative benefits GQL promises.

The ISO Committee Response

The GQL standards committee knows about these gaps. "Language opportunity" items — features explicitly deferred — are documented in the standard. The Meta-Property Graph extension (Sadoughi et al., 2025) would enable schema introspection within GQL. Complexity analysis at ICDT 2026 shows GQL with path restrictors is P-NP[log]-complete; without them it drops to NL-complete. Path algebra approaches beyond current scope would enable 1,960+ query combinations versus GQL's 28 supported path modes. The committee is active, but GQL v2 timelines remain uncertain.

Workaround Patterns in Practice

A GQL-only architecture is not yet viable for every workload. The practical response is two-phase retrieval: structural matching in GQL, value-based recursion on top.

Pattern: Hybrid GQL + Application-Level Filtering

from dataclasses import dataclass
from typing import List


@dataclass
class TransferPath:
    src: str
    dst: str
    amounts: List[float]


def find_increasing_transfer_paths(
    driver, min_length: int = 2, max_length: int = 5
) -> List[TransferPath]:
    # Phase 1: GQL handles graph traversal
    gql = """
    MATCH path = (a:Account)-[r:TRANSFER*""" + str(min_length) + """..""" + str(max_length) + """]-(b:Account)
    RETURN id(a) AS src, id(b) AS dst,
           [rel IN r | rel.amount] AS amounts
    LIMIT 10000
    """
    results = driver.execute_query(gql)

    # Phase 2: Application code checks monotonicity — GQL cannot
    valid = []
    for record in results:
        amounts = record["amounts"]
        if all(amounts[i] < amounts[i + 1] for i in range(len(amounts) - 1)):
            valid.append(TransferPath(
                src=record["src"], dst=record["dst"], amounts=amounts
            ))
    return valid

This pulls more data over the wire than a declarative solution would, but it works today. For high-volume pipelines, push the monotonicity check into PostgreSQL with recursive SQL CTEs and use GQL only for neighbourhood expansion.

Pattern: Schema Metadata as Nodes

For meta-property queries, reify the schema as data:

CREATE (rt:RelationshipType {
    name: "TRANSFER",
    source_label: "Account",
    target_label: "Account",
    properties: ["amount", "timestamp"]
})

MATCH (rt:RelationshipType)
WHERE rt.source_label = "Account"
RETURN rt.name, rt.properties

Clunkier than SQL's INFORMATION_SCHEMA but provides runtime introspection within the same query engine. The tradeoff is keeping schema-as-nodes synchronised with the actual database schema.

Gap Workaround Reference

Gap	GQL v1 Status	Recommended Workaround	Best For
Edge-property monotonicity	Not expressible	Two-phase: GQL for traversal, application/SQL for property checks	Fraud detection, temporal analysis, process mining
Value-based recursion	Not expressible	Recursive SQL CTEs or Datalog for the value-recursive fragment	Supply chain traceability, audit trails
Meta-property queries	Not expressible	Schema metadata stored as first-class graph nodes	Schema discovery, multi-tenant systems, dynamic query generation
Even-length paths	Expressible (GQL fix)	Native operator WHERE length(e) % 2 = 0	General graph analytics, network cycle detection

Architecture Guidance

GQL v1 is a foundation, not the final word. Auditing your query workload before committing to GQL-only is essential: how many queries need value-based recursion or schema introspection? Where the answer is "many," design a hybrid stack:

• GQL for navigation — structural pattern matching, shortest paths, node-property filtering.
• Recursive SQL or Datalog for value recursion — edge-property monotonicity, temporal chain analysis, cumulative aggregations.
• Application plumbing — orchestrate both engines and merge results.

GQL v2 will likely close these gaps within 2-4 years, but the workaround patterns above are production-tested now and will become thinner intermediate layers as the standard evolves.

Further Reading

• From Knowledge Graphs to Context Graphs — How temporal validity windows and policy nodes address similar expressiveness gaps at the data model level.
• Ontology in Graph Databases — Ontology-driven graph design principles covering node labels, edge semantics, and signal normalisation from a production Neo4j project.
• Neo4j Database Adapters Compared — Bolt protocol support, type handling, and transaction models across five official and five community drivers.
• GraphRAG Variants Compared in 2026 — Six GraphRAG variants compared with a decision framework that mirrors the query-pattern audit recommended here.