Write a SQL query to simulate the behavior of a graph database.

Instruction: Using PostgreSQL 16, nodes(id integer PRIMARY KEY) and edges(node_start integer NOT NULL REFERENCES nodes, node_end integer NOT NULL REFERENCES nodes) represent a small undirected unweighted graph; an edge may be stored in either direction. Find one shortest path from node 1 to node 4, returning its node sequence and hop count. Handle cycles and explain unreachable and equal-endpoint cases and scalability limits.

Context: Candidates must showcase their ability to work with advanced SQL concepts and algorithms to simulate complex data structures and operations.

Updated

Official answer

For a small unweighted graph, enumerate simple paths, then select the fewest hops. Expand stored edges in both directions and keep a visited-node array:

WITH RECURSIVE
adjacency(src, dst) AS (
  SELECT node_start, node_end FROM edges
  UNION
  SELECT node_end, node_start FROM edges
), paths(node_id, path, hops) AS (
  SELECT id, ARRAY[id], 0
  FROM nodes
  WHERE id = 1
  UNION ALL
  SELECT a.dst, p.path || a.dst, p.hops + 1
  FROM paths AS p
  JOIN adjacency AS a ON a.src = p.node_id
  WHERE p.node_id <> 4
    AND NOT (a.dst = ANY(p.path))
)
SELECT path, hops
FROM paths
WHERE node_id = 4
ORDER BY hops, path
LIMIT 1;

The array rejects every repeated node on a path, not just a return to the start. A shortest path in an unweighted graph can be simple, so this restriction preserves a shortest solution. Ordering by the path makes ties deterministic.

No row means the destination is unreachable or absent. If start and destination are the same existing node, the zero-hop seed is the answer. A missing start produces no seed.

This query can enumerate exponentially many simple paths. It is a small-graph demonstration, not a scalable breadth-first search implementation or a weighted shortest-path algorithm. For large graphs, use an appropriate traversal algorithm and resource limits; ORDER BY with LIMIT does not guarantee that recursion stops early.

Source

PostgreSQL: recursive queries and cycle handling.

Related Questions