Simulating Graph Queries in Relational Databases

1. Why you do not always need a graph database

Graph queries are often seen as a classic argument for switching to a dedicated graph database like Neo4j. In reality, however, many use cases do not need a general purpose graph engine with arbitrarily many edge types and complex traversal algorithms, but rather a limited set of clearly defined relationships: employee hierarchies, category trees, simple friend networks, or dependency graphs between components.

For exactly these cases, relational databases offer a powerful tool with recursive common table expressions, CTEs for short, to formulate graph queries directly in SQL, without introducing a second system. The advantage: the data stays within the same transaction, the same backups, and the same operational model as the rest of the application, with full ACID guarantees for the underlying relationships.

This article shows the three most important techniques for graph queries in SQL: the adjacency list model with recursive CTEs, the closure table as a materialized alternative, and the concrete performance limits at which an actual graph database really becomes the better choice.

2. The adjacency list model as the foundation

The adjacency list model is the simplest way to model relationships for graph queries in a relational table: each row references exactly one direct neighbor via a foreign key, for example an employee pointing to their direct manager. This structure is compact, easy to maintain, and covers inserting, updating, and deleting individual edges with minimal effort.

The downside of the pure adjacency list model: a single SQL query without recursive extension can only query a fixed number of levels, for example with several consecutive self joins for each additional level. For an unknown or variable depth, as graph queries typically need in hierarchies, the model alone is not enough and must be combined with recursive CTEs.

-- Adjacency list model: each row only knows its direct manager
CREATE TABLE employees (
  employee_id   INT PRIMARY KEY,
  name          VARCHAR(255) NOT NULL,
  manager_id    INT REFERENCES employees(employee_id)
);

INSERT INTO employees (employee_id, name, manager_id) VALUES
  (1, 'Anna Vogel', NULL),        -- CEO, has no manager
  (2, 'Ben Krueger', 1),
  (3, 'Clara Sommer', 2),
  (4, 'David Winter', 2),
  (5, 'Erik Falk', 3);

-- Querying direct neighbors is trivial, a single join is enough
SELECT e.name AS employee, m.name AS manager
FROM employees e LEFT JOIN employees m ON e.manager_id = m.employee_id;

3. Recursive CTEs for traversals and path search

A recursive CTE consists of an anchor part that defines the starting points of the traversal, and a recursive part that references itself and gradually adds further levels until no new rows are found. For graph queries in a hierarchy that means: the anchor selects the root, for example the CEO without a manager, and each recursive iteration adds the next level of direct reports.

-- Recursive CTE: complete organizational hierarchy from the root
WITH RECURSIVE org_chart AS (
  -- Anchor: root of the hierarchy (no manager)
  SELECT employee_id, name, manager_id, 1 AS level,
         ARRAY[employee_id] AS path
  FROM employees
  WHERE manager_id IS NULL

  UNION ALL

  -- Recursion: next level of direct reports
  SELECT e.employee_id, e.name, e.manager_id, oc.level + 1,
         oc.path || e.employee_id
  FROM employees e
  JOIN org_chart oc ON e.manager_id = oc.employee_id
  WHERE NOT e.employee_id = ANY(oc.path)  -- cycle protection
)
SELECT level, name, path FROM org_chart ORDER BY path;

-- Result shows every level of the hierarchy with the complete
-- path from the root to the respective employee

The array path in this query serves two purposes: it documents the complete traversal route for each row, and it prevents infinite loops on cyclic data, which is a real risk for graph queries over faulty or unforeseen data constellations. Without this cycle check, a recursive CTE would never terminate in the presence of an accidental cycle in the data.

4. Transitive closure and reachability queries

A common form of graph queries is the reachability question: is node B reachable from node A through any number of edges? This so called transitive closure can be answered with the same recursive CTE technique by allowing a general directed graph instead of a tree structure, where a node can have several predecessors.

-- General directed graph instead of a tree: dependencies between modules
CREATE TABLE module_dependencies (
  module_id      INT NOT NULL,
  depends_on_id  INT NOT NULL,
  PRIMARY KEY (module_id, depends_on_id)
);

-- Reachability query: which modules transitively depend on "core"?
WITH RECURSIVE reachable AS (
  SELECT module_id, depends_on_id
  FROM module_dependencies
  WHERE depends_on_id = (SELECT module_id FROM modules WHERE name = 'core')

  UNION

  SELECT md.module_id, md.depends_on_id
  FROM module_dependencies md
  JOIN reachable r ON md.depends_on_id = r.module_id
)
SELECT DISTINCT module_id FROM reachable;
-- UNION instead of UNION ALL deduplicates automatically, important for
-- graphs with several paths between the same two nodes

5. Simulating shortest path with weighted edges

For weighted graph queries, for example the shortest route between two cities in a route network, you extend the recursive CTE with a cumulative weight sum and sort the final result by it. This technique essentially implements a simplified breadth first search, but is not as efficient as a dedicated Dijkstra or A star algorithm of an actual graph engine, because SQL has no priority queue and searches every possible route completely up to a termination condition.

-- Weighted edges: shortest path between two cities
CREATE TABLE routes (
  from_city  VARCHAR(50) NOT NULL,
  to_city    VARCHAR(50) NOT NULL,
  distance_km INT NOT NULL
);

WITH RECURSIVE path_search AS (
  SELECT from_city, to_city, distance_km AS total_distance,
         ARRAY[from_city, to_city] AS route
  FROM routes
  WHERE from_city = 'Hamburg'

  UNION ALL

  SELECT ps.from_city, r.to_city, ps.total_distance + r.distance_km,
         ps.route || r.to_city
  FROM routes r
  JOIN path_search ps ON r.from_city = ps.to_city
  WHERE NOT r.to_city = ANY(ps.route)     -- cycle protection
    AND ps.total_distance < 2000          -- termination condition against explosion
)
SELECT route, total_distance
FROM path_search
WHERE to_city = 'Munich'
ORDER BY total_distance
LIMIT 1;

6. Closure table as an alternative to the recursive query

A closure table explicitly materializes all ancestor descendant relationships of a hierarchy into a dedicated table, instead of recomputing them on every query. For graph queries that are read frequently but written rarely, this approach is often faster than a recursive CTE, because the expensive traversal happens once at write time, not on every read.

-- Closure table: every ancestor descendant relationship as its own row,
-- including the distance between the nodes (depth = 0 for itself)
CREATE TABLE employee_hierarchy (
  ancestor_id    INT NOT NULL REFERENCES employees(employee_id),
  descendant_id  INT NOT NULL REFERENCES employees(employee_id),
  depth          INT NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

-- All reports of Ben Krueger (employee_id = 2), any depth
SELECT e.name, eh.depth
FROM employee_hierarchy eh
JOIN employees e ON e.employee_id = eh.descendant_id
WHERE eh.ancestor_id = 2 AND eh.depth > 0
ORDER BY eh.depth;

-- This query needs no recursion at runtime anymore,
-- the traversal was already materialized in the closure table
-- when the new employee relationship was inserted

7. Performance limits of recursive SQL queries

Recursive graph queries with CTEs hit clear limits: every recursive iteration is essentially an additional join, and with very deep hierarchies with many levels or dense graphs with many edges per node, the number of intermediate rows to process quickly grows exponentially. PostgreSQL and MySQL do not optimize recursive CTEs with the same graph specific index structures that a dedicated graph database uses for traversals.

As a rule of thumb: up to a few thousand nodes and a traversal depth of ten to twenty levels, recursive graph queries remain performant enough for most use cases. With millions of nodes, dense networks with many edges per node, or queries like shortest path across thousands of possible routes, a dedicated graph database like Neo4j with its native adjacency indexes and specialized traversal algorithms becomes significantly more efficient.

-- EXPLAIN ANALYZE shows the actual cost explosion
-- as recursion depth increases
EXPLAIN ANALYZE
WITH RECURSIVE org_chart AS (
  SELECT employee_id, manager_id, 1 AS level FROM employees WHERE manager_id IS NULL
  UNION ALL
  SELECT e.employee_id, e.manager_id, oc.level + 1
  FROM employees e JOIN org_chart oc ON e.manager_id = oc.employee_id
)
SELECT * FROM org_chart;

-- For shallow hierarchies (under 20 levels, a few thousand rows):
-- CTE Scan with reasonable runtime in the millisecond range
-- For deep, dense graphs: runtime grows disproportionately,
-- a signal for a migration to a dedicated graph database

8. Practical example: organizational hierarchy and friend network

An organizational hierarchy with a few thousand employees and a depth rarely exceeding eight to ten levels is a textbook example of successful graph queries via recursive CTE directly in the existing relational database. Reporting chains, approval workflows, and responsibility queries run performantly without operating a second system, and benefit from the same transaction guarantees as the rest of the employee data.

A social network with millions of users and the requirement to calculate second and third degree friends in real time is instead the classic counterexample: the number of possible paths grows so fast here that recursive SQL graph queries hit limits even with good indexing. Exactly in this area, a dedicated graph database with native traversal algorithms delivers noticeably better response times.

9. SQL graph simulation versus native graph database

The following table summarizes when SQL based graph queries are enough and when a dedicated graph database is the better choice.

As long as node count and traversal depth remain moderate, graph queries with recursive CTEs are the more pragmatic choice, because they require no second system. Only with true big graph requirements involving millions of nodes and complex traversal algorithms does a dedicated graph database become the better investment.

10. Summary

Graph queries can be modeled with the adjacency list model and recursive CTEs directly in PostgreSQL or MySQL, for hierarchies, reachability questions, and even simple shortest path calculations over weighted edges. A closure table materializes these relationships ahead of time for read heavy use cases, saving expensive recursion at runtime. Both techniques stay within the same transaction boundaries as the rest of the application data, without needing a second system.

The limit lies in node count, traversal depth, and edge density: as long as these stay moderate, SQL based graph queries are the most pragmatic solution. Once node count grows into the millions or complex path search becomes a core feature of the application, a dedicated graph database with native traversal algorithms delivers better performance, at the cost of an additional system to operate.

11. FAQ: Simulating Graph Queries in Relational Databases