Recursive CTE for graph traversal in PostgreSQL - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ query_result

intermediate

Find all reachable nodes from node 1

Given the table edges with columns source and target, what is the output of this recursive CTE query that finds all nodes reachable from node 1?

PostgreSQL

WITH RECURSIVE reachable AS (
  SELECT source, target FROM edges WHERE source = 1
  UNION
  SELECT e.source, e.target FROM edges e
  INNER JOIN reachable r ON e.source = r.target
)
SELECT DISTINCT target FROM reachable ORDER BY target;

A [2, 3]

B [1, 2, 3, 4]

C [2, 3, 4]

D [3, 4]

💡 Hint

Think about how the recursive part expands the reachable nodes starting from source 1.

The base case selects edges starting at node 1. The recursive part joins on the target to find further reachable nodes. The distinct targets collected are nodes 2, 3, and 4.

📝 Syntax

intermediate

Identify the syntax error in recursive CTE

Which option contains a syntax error in this recursive CTE that tries to find all nodes reachable from node 1?

PostgreSQL

WITH RECURSIVE reachable AS (
  SELECT source, target FROM edges WHERE source = 1
  UNION
  SELECT e.source, e.target FROM edges e
  JOIN reachable r ON e.source = r.target
)
SELECT DISTINCT target FROM reachable ORDER BY target;

A No syntax error; query is valid

B Missing keyword RECURSIVE after WITH

C Using JOIN instead of INNER JOIN causes syntax error

D Missing alias for recursive CTE

💡 Hint

Check if JOIN without INNER is valid in PostgreSQL.

In PostgreSQL, JOIN is shorthand for INNER JOIN and is valid syntax. The query has no syntax errors.

❓ optimization

advanced

Optimize recursive CTE to avoid duplicates

Which option optimizes this recursive CTE to avoid revisiting nodes and duplicates in the result?

PostgreSQL

WITH RECURSIVE reachable(node) AS (
  SELECT 1
  UNION
  SELECT e.target FROM edges e
  JOIN reachable r ON e.source = r.node
)
SELECT node FROM reachable ORDER BY node;

A Use UNION ALL instead of UNION

B Add WHERE e.target NOT IN (SELECT node FROM reachable) in recursive part

C Add DISTINCT in the final SELECT

D Add a LIMIT clause to restrict recursion depth

💡 Hint

Prevent revisiting nodes by filtering them out in recursion.

Adding a WHERE clause to exclude already visited nodes prevents infinite loops and duplicates.

🧠 Conceptual

advanced

Understanding recursive CTE termination

What causes a recursive CTE for graph traversal to stop recursing?

A When no new rows are added in the recursive part

B When a maximum recursion depth is reached

C When the base case returns no rows

D When the query uses UNION ALL instead of UNION

💡 Hint

Think about how recursion ends naturally in SQL.

The recursion stops when the recursive SELECT adds no new rows to the result set.

🔧 Debug

expert

Diagnose infinite recursion in recursive CTE

Given this recursive CTE, why does it cause infinite recursion or run indefinitely?

PostgreSQL

WITH RECURSIVE reachable(node) AS (
  SELECT 1
  UNION ALL
  SELECT e.target FROM edges e
  JOIN reachable r ON e.source = r.node
)
SELECT node FROM reachable ORDER BY node;

A Missing ORDER BY in recursive part causes infinite recursion

B Base case selects node 1 incorrectly

C Using UNION instead of UNION ALL causes infinite recursion

D Edges contain cycles and no check prevents revisiting nodes

💡 Hint

Consider what happens if the graph has loops.

If the graph has cycles and the query does not exclude already visited nodes, recursion never ends.