Graph Query Languages: SPARQL, Cypher and GQL

"Find people two hops from Alice who work at a company founded before 2000." In SQL that is a self-join on a friendship table, another join to employment, a third to companies, and a rewrite every time the hop count changes. Graph query languages exist to make that question as short as it sounds. The two that dominate practice come from different worlds: SPARQL from the W3C's RDF stack, where triples and the open world assumption set the rules, and Cypher from the property-graph databases led by Neo4j.

SPARQL: patterns over triples

A SPARQL query is a set of triple patterns with variables, joined wherever variables are shared:

SELECT ?person WHERE {
  :alice   :knows      ?friend .
  ?friend  :knows      ?person .
  ?person  :worksAt    ?company .
  ?company :foundedIn  ?year .
  FILTER (?year < 2000)
}

Each line is a triple pattern and the whole block is a basic graph pattern, evaluated as a join. OPTIONAL gives left-outer-join behaviour, UNION combines alternatives, and property paths such as :knows+ express arbitrary-length traversal. SPARQL 1.1 became a W3C Recommendation in 2013; as of September 2026 the SPARQL 1.2 Query Language is still a W3C Working Draft (W3C, SPARQL 1.2 Query Language).

Its semantics were formalised early, and the results were sobering. Pérez, Arenas and Gutierrez showed that evaluating general SPARQL graph patterns is PSPACE-complete, with the combination of OPTIONAL and nesting driving the hardness (Pérez, Arenas & Gutierrez, 2009, Semantics and Complexity of SPARQL, ACM TODS 34(3), doi:10.1145/1567274.1567278). A short query is not necessarily a cheap one.

Cypher: patterns that look like the graph

Cypher writes the pattern as a picture of the subgraph:

MATCH (:Person {name: 'Alice'})-[:KNOWS*2]->(p:Person)-[:WORKS_AT]->(c:Company)
WHERE c.founded < 2000
RETURN DISTINCT p.name

Nodes are in parentheses, relationships in brackets, and *2 asks for exactly two hops. The data model differs from RDF in one consequential way: relationships carry properties directly, so (a)-[:KNOWS {since: 2019}]->(b) needs no extra machinery. In plain RDF the same annotation requires reification, and standard reification spends four triples just to name the statement (rdf:type rdf:Statement, rdf:subject, rdf:predicate, rdf:object) before the since value is attached.

Cypher 9 received a formal semantics in 2018, which also made a key design decision explicit: pattern matching uses relationship isomorphism, meaning one match never binds the same relationship twice. The authors state that this reduces the number of matches and guarantees that variable-length patterns never produce infinite result sets (Francis et al., 2018, Cypher: An Evolving Query Language for Property Graphs, SIGMOD, doi:10.1145/3183713.3190657).

Why path semantics decide whether a query finishes

Arbitrary-length paths are where graph languages diverge most, and the reason is arithmetic. In a graph where every node has 10 outgoing edges, the number of walks of length 8 from one start node is \(10^8\). Allow cycles and there are infinitely many walks of unbounded length. A language must decide which paths count.

SPARQL learned this in public. Draft SPARQL 1.1 property paths required counting every path, and Arenas, Conca and Pérez showed that any conforming implementation would hit severe performance problems in simple scenarios, with result counts in their examples growing past a yottabyte (Arenas, Conca & Pérez, 2012, Counting Beyond a Yottabyte, or how SPARQL 1.1 Property Paths will Prevent Adoption of the Standard, WWW). The final standard treats arbitrary-length paths as a reachability test: :knows+ asks whether some path exists, not how many there are. Cypher, by contrast, chose edge-distinct trails.

GQL, SQL/PGQ and what remains contested

GQL was published as ISO/IEC 39075:2024 in April 2024, a standalone property-graph query language drawing heavily on Cypher's MATCH syntax (ISO, ISO/IEC 39075:2024 Database languages: GQL). Instead of fixing one path semantics, it lets the query state a path mode (WALK, TRAIL, SIMPLE, ACYCLIC) and a selector such as ANY SHORTEST, with bounded quantifiers like ->{1,3}:

MATCH ANY SHORTEST TRAIL (a:Person {name: 'Alice'})-[:knows]->{1,4}(p:Person)
RETURN p.name

Its sibling, SQL/PGQ, published as ISO/IEC 9075-16:2023, adds CREATE PROPERTY GRAPH views over existing relational tables and a GRAPH_TABLE function that runs a pattern match inside a SQL FROM clause (ISO, ISO/IEC 9075-16:2023). Oracle Database 23ai ships it. The two standards share a pattern-matching core, so the same path expression means the same thing in a graph database and a relational one.

The RDF and property-graph communities still argue about the data model rather than the syntax. RDF advocates point to global identifiers, federation across endpoints and formal reasoning; property-graph advocates point to edge properties and a model that matches how developers draw graphs. Matching semantics is contested too: homomorphism (reuse anything), node isomorphism and edge isomorphism return different answers to the same pattern, and the Cypher authors themselves list configurable semantics as future work.

When it breaks

Empty results do not mean false. Under open-world semantics a SPARQL query returning nothing has not shown the fact is absent, and applications that treat it as a negative answer are wrong in a way no query rewrite fixes.

Multi-hop joins defeat planners. Cardinality estimates compound across hops, so a planner that is off by 10x per hop is off by 10,000x after four, and picks a join order that materialises millions of intermediate rows.

Unbounded quantifiers are a denial-of-service vector. A user-supplied * over a dense graph can exhaust memory. Production systems cap depth and time, which silently changes the semantics users think they are getting.

Dialects drift from the standard. Vendors implement subsets and extensions of Cypher, GQL and SPARQL, so a query that runs on one engine may parse differently or not at all on another.