The GQL Expressiveness Gap: What the New ISO Standard Can't Do
gqlcyphersqlgraph-databasestandardsisoproperty-graphquery-language
Loading…
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.
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.
Recent academic work has formally characterized what GQL cannot express. Four findings stand out.
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.
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.
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;
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.
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 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.
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.
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.
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 | 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 |
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 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.