Graph Queries in SQL

Example 3-3 suggested that graph data can be represented in a relational database. But if we put graph data in a relational structure, can we also query it using SQL?

The answer is yes, but with some difficulty. Every edge that you traverse in a graph query is effectively a join with the edges table. In a relational database, you usually know in advance which joins you need in your query. On the other hand, in a graph query, you may need to traverse a variable number of edges before you find the vertex you’re looking for—that is, the number of joins is not fixed in advance.

In our example, that happens in the () -[:WITHIN*0..]-> () pattern in the Cypher query. A person’s LIVES_IN edge may point to any kind of location, such as a street, a city, a district, a region, or a state. A city may be WITHIN a region, a region WITHIN a state, a state WITHIN a country, and so on. The LIVES_IN edge may point directly to the location vertex you’re looking for, or it may be several levels away in the location hierarchy.

In Cypher,:WITHIN*0.. expresses that fact very concisely: it means “follow a WITHIN edge, zero or more times.” It’s like the * operator in a regular expression.

This idea of variable-length traversal paths in a query can be expressed using recursive common table expressions (the WITH RECURSIVE syntax). Example 3-6 shows the same query—finding the names of people who emigrated from the US to Europe—expressed in SQL using this technique (the lines starting with -- are comments). As you can see, the syntax is very clumsy in comparison to Cypher.

Example 3-6. The same query as Example 3-5, written in SQL using recursive common table expressions

WITH RECURSIVE

  -- in_usa is the set of vertex IDs of all locations within the United States
  in_usa(vertex_id) AS (
      SELECT vertex_id FROM vertices
        WHERE label = 'Location' AND properties->>'name' = 'United States' 1
    UNION
      SELECT edges.tail_vertex FROM edges 2
        JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
        WHERE edges.label = 'within'
  ),

  -- in_europe is the set of vertex IDs of all locations within Europe
  in_europe(vertex_id) AS (
      SELECT vertex_id FROM vertices
        WHERE label = 'location' AND properties->>'name' = 'Europe' 3
    UNION
      SELECT edges.tail_vertex FROM edges
        JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
        WHERE edges.label = 'within'
  ),

  -- born_in_usa is the set of vertex IDs of all people born in the US
  born_in_usa(vertex_id) AS ( 4
    SELECT edges.tail_vertex FROM edges
      JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
      WHERE edges.label = 'born_in'
  ),

  -- lives_in_europe is the set of vertex IDs of all people living in Europe
  lives_in_europe(vertex_id) AS ( 5
    SELECT edges.tail_vertex FROM edges
      JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
      WHERE edges.label = 'lives_in'
  )

SELECT vertices.properties->>'name'
FROM vertices
-- join to find those people who were both born in the US *and* live in Europe
JOIN born_in_usa     ON vertices.vertex_id = born_in_usa.vertex_id 6
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

1

First find the vertex whose name property has the value United States, and make it the first element of the set of vertices in_usa.

2

Follow all incoming within edges from vertices in the set in_usa and add them to the same set, until all incoming within edges have been visited.

3

Do the same starting with the vertex whose name property has the value Europe, and build up the set of vertices in_europe.

4

For each of the vertices in the set in_usa, follow incoming born_in edges to find people who were born in some place within the US.

5

Similarly, for each of the vertices in the set in_europe, follow incoming lives_in edges to find people who live in Europe.

6

Finally, intersect the set of people born in the US with the set of people living in Europe by joining them.

The fact that a 4-line Cypher query requires 31 lines in SQL shows how much of a difference the right choice of data model and query language can make. And this is just the beginning; there are more details to consider, for example, around handling cycles and choosing between breadth-first or depth-first traversal. Oracle has a different SQL extension for recursive queries, which it calls hierarchical. Other graph query languages include TigerGraph’s GSQL and the Property Graph Query Language (PGQL).

The Graph Query Language (GQL) ISO standard, which is based on Cypher, was published in 2024. Although it is not widely adopted yet, hopefully it will lead to greater uniformity among graph databases in the coming years.