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. This milestone finally gave the industry a unified query language for property graphs, just as SQL unified relational databases decades ago. After years of fragmented implementations—Cypher, Gremlin, SPARQL with property graph extensions—GQL promised to be the common ground.

But recent formal analysis published at VLDB 2025 and ICDT 2025-2026 reveals uncomfortable truths. GQL has expressiveness gaps. Some are expected carryovers from Cypher's limitations. 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 for production systems, and how architects should plan 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. Unlike SQL's table-centric model or SPARQL's RDF triples, GQL treats nodes, edges, and their properties as native constructs. The mental model matches how engineers actually think about connected data.

Linear recursion via Kleene star. Cypher's regular path queries (RPQs) were limited to fixed patterns. GQL introduces arbitrary pattern repetition with the * operator, solving the even-length path problem that plagued Cypher (more on this below).

// 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 control over path semantics: SHORTEST, SIMPLE (no repeated nodes), TRAIL (no repeated edges), ACYCLIC, and WALK (no restrictions). This precision matters for correctness in domains like fraud detection.

SQL-like relational algebra. The language includes familiar constructs: GROUP BY, ORDER BY, aggregation functions, and projection. Engineers don't need to learn 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 pairs of nodes connected by an even-length path. ICDT 2025 provided the formal proof.

// Cypher: CANNOT express even-length paths
// This is NOT valid Cypher - shown for illustration
MATCH (a)-[:REL{2,4,6,8,...}]->(b)  // Doesn't exist

The problem: Cypher's pattern syntax couldn't express "repeat this edge an even number of times" without hardcoding each length. GQL fixes this with arbitrary pattern repetition:

// GQL: Can express even-length paths via pattern composition
MATCH (a)-[(e:REL*1..)]->(b)
WHERE length(e) % 2 = 0
RETURN a, b

This was a known Cypher limitation that GQL addresses. But other gaps remain unaddressed.

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 (Property Graph Query language) cannot express queries that ARE expressible in positive recursive SQL and linear Datalog.

This contradicts complexity-theoretic expectations. Both languages operate in similar complexity classes, so researchers assumed they'd be expressively equivalent. They're not.

The gap stems from how GQL handles recursion. GQL recurses over patterns (graph structure), while recursive SQL recurses over values (arbitrary computations). When queries need value-based recursion—checking properties across recursive steps—GQL hits a wall.

3. Edge-Property Monotonicity

Here's the canonical example from VLDB 2025. Consider a money transfer graph where edges carry transaction amounts. You want to find transfer chains where amounts strictly increase at each hop—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 gives access to node properties along the path. But try the same query with EDGE properties:

// GQL: CANNOT check EDGE property monotonicity
// This pattern is NOT expressible in GQL v1
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 can access edge properties individually, but cannot compare consecutive edge properties within a recursive pattern match. The same limitation applies to temporal queries: "find event sequences where timestamps strictly increase" fails 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 write queries that reason about the schema itself:

// GQL: CANNOT express these meta-queries
// "Find all nodes that have a property named 'status'"
// "List all relationship types connecting Person to Company"

This matters for schema discovery, dynamic query generation, and multi-tenant systems where schemas vary per tenant. Workarounds exist—storing schema metadata as regular nodes and edges—but they're awkward and require separate query phases.

Why This Matters Practically

These aren't academic curiosities. They block real production queries.

Fraud detection. "Find money transfer paths where transaction amounts increase at each hop" requires edge-property monotonicity. Financial institutions need this to spot structuring patterns. GQL can't express it directly.

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

Schema discovery. "What relationship types exist between these entity types?" seems basic, but GQL requires workarounds. Compare to SQL's INFORMATION_SCHEMA or PostgreSQL's pg_catalog—first-class metadata access.

The VLDB 2025 analysis is blunt: current workarounds like "enumerate all path lengths and take the complement" are "impractical even for small-sized graphs." Application-level post-processing shifts complexity to code, losing the declarative benefits GQL promises.

The ISO Committee Response

The GQL standards committee knows about these gaps. The standard includes "language opportunity" items—features explicitly deferred for future versions.

Early proposals address pattern matching extensions. The Meta-Property Graph extension (Sadoughi et al., 2025) proposes first-class treatment of labels and properties as queryable objects, enabling schema introspection within GQL itself.

Recent complexity analysis (ICDT 2026) shows GQL with path restrictors is P-NP[log]-complete. Without restrictors, it drops to NL-complete. This suggests restrictors are the complexity bottleneck—and the expressiveness bottleneck. Path algebra approaches beyond current GQL scope would enable 1960+ query combinations versus GQL's 28 supported path modes.

The committee is active. Fixes are in discussion. But timelines are uncertain, and GQL v2 remains undefined.

What This Means for Your Architecture

If you're evaluating GQL for production, plan around these constraints:

GQL v1 is a foundation, not the final word. It's a solid start for standard graph patterns. Don't expect it to handle every query you'll need.

Edge-property reasoning requires workarounds. For queries like monotonicity checks, use recursive SQL CTEs or application-level post-processing. Some organizations will run hybrid architectures: GQL for navigation, SQL for analytical queries needing edge-level recursion.

Meta-querying needs separate handling. Store schema metadata as regular graph elements if you need dynamic introspection. Query it separately from your main graph queries.

The gap will narrow, but not soon. GQL v2 discussions are underway, but ISO standardization moves slowly. Plan for 2-4 years before edge-property recursion and meta-properties land in a ratified standard.

Evaluate your query patterns now. Before committing to GQL-only architecture, audit your query workload. How many queries need edge-property recursion? How many need schema introspection? If the answer is "many," hybrid approaches make sense.

Conclusion

GQL is a historic achievement. It gives the industry its first standard property graph language, with genuine advances over predecessor systems. For standard graph navigation patterns—friend-of-friend queries, shortest paths, pattern matching with node properties—it works well.

But GQL v1 has formally-proven expressiveness gaps that matter for production use. Edge-property monotonicity, meta-property queries, and certain recursive patterns fall outside what GQL can express. These aren't edge cases. They're core requirements for fraud detection, temporal analysis, and schema discovery.

Architects should evaluate whether their query patterns fall into the gap before committing to GQL-only strategies. Hybrid approaches—GQL for standard patterns, recursive SQL for complex analytical queries—may be necessary for the foreseeable future.

The standards process is already working on fixes. GQL v2 will likely address these gaps. Until then: use GQL where it excels, plan workarounds where it doesn't, and watch the committee's progress. The property graph ecosystem is maturing, but v1 is just the beginning.