Hierarchical Data and Recursive Queries

Concept

Trees appear everywhere in relational data: staff reporting lines, category hierarchies, threaded comments, bill of materials. The relational model has no native tree type, so the structure is encoded in columns - and the choice of encoding decides which queries are cheap.

The adjacency list

-- Each row points at its parent. The sample schema already does this.
CREATE TABLE categories (
    id        INT PRIMARY KEY,
    name      VARCHAR(60) NOT NULL,
    parent_id INT NULL,
    CONSTRAINT fk_cat_parent FOREIGN KEY (parent_id) REFERENCES categories(id)
);

Simple to store and to modify - moving a subtree is one UPDATE - but reading a whole branch needs recursion.

Walking down: descendants

WITH RECURSIVE subtree AS (
    SELECT id, first_name, manager_id, 1 AS depth,
           CAST(first_name AS CHAR(300)) AS path
    FROM   employees
    WHERE  id = 1                                    -- start at Asha

    UNION ALL

    SELECT e.id, e.first_name, e.manager_id, s.depth + 1,
           CONCAT(s.path, ' > ', e.first_name)
    FROM   employees e
    JOIN   subtree s ON s.id = e.manager_id
    WHERE  s.depth < 50                              -- cycle guard
)
SELECT depth, first_name, path FROM subtree ORDER BY path;

Walking up: ancestors

-- The management chain above one employee: reverse the join direction
WITH RECURSIVE chain AS (
    SELECT id, first_name, manager_id, 1 AS level
    FROM   employees
    WHERE  id = 7                                    -- start at Divya

    UNION ALL

    SELECT m.id, m.first_name, m.manager_id, c.level + 1
    FROM   employees m
    JOIN   chain c ON m.id = c.manager_id
    WHERE  c.level < 50
)
SELECT level, first_name FROM chain ORDER BY level;

The only difference is which side of the join carries the CTE. Down the tree: ON s.id = e.manager_id. Up the tree: ON m.id = c.manager_id.

Useful aggregates over a tree

-- Leaf nodes: rows nobody reports to
SELECT e.first_name
FROM   employees e
WHERE  NOT EXISTS (SELECT 1 FROM employees c WHERE c.manager_id = e.id);

-- Direct report count per manager
SELECT m.first_name AS manager, COUNT(e.id) AS direct_reports
FROM   employees m
LEFT JOIN employees e ON e.manager_id = m.id
GROUP BY m.first_name
ORDER BY direct_reports DESC;

Alternative encodings

-- Closure table: one row for every ancestor-descendant pair, including self
CREATE TABLE employee_tree (
    ancestor_id   INT NOT NULL,
    descendant_id INT NOT NULL,
    depth         INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id)
);

-- Every descendant of employee 1, with no recursion at all
SELECT e.first_name, t.depth
FROM   employee_tree t
JOIN   employees e ON e.id = t.descendant_id
WHERE  t.ancestor_id = 1 AND t.depth > 0;

Important rules

• An adjacency list needs a recursive CTE, available in MySQL 8, MariaDB 10.2+, PostgreSQL, SQL Server, Oracle and SQLite - but not MySQL 5.7.
• Always carry a depth column and cap it; cyclic data otherwise runs to the engine limit.
• Index parent_id - every recursion step joins on it.
• Cast growing text columns to their final width in the anchor member.
• Oracle also offers CONNECT BY, and SQL Server has no equivalent - the recursive CTE is the portable form.

Common mistakes

• Joining the wrong way round and walking up when you meant to walk down.
• No cycle guard, on data where a cycle is possible.
• Using stacked self joins for a tree of unknown depth - it only ever handles the levels you wrote.
• Choosing nested sets for a tree that changes often.
• Forgetting the depth 0 self row when reading a closure table, and including the root in a descendants list.

Best practices

• Start with an adjacency list. Move to a closure table only when read performance demands it.
• Keep a depth and a path column in the recursive result; both make debugging far easier.
• Index the parent column and, for closure tables, both directions.
• If you maintain a materialised path or closure table, maintain it in a trigger or in one place in the application - never in several.

Practice

1. List every employee under Asha with their depth in the tree.
2. List the full management chain above Divya.
3. Design a closure table for the sample employees hierarchy and write the insert that populates it from the adjacency list.