Model / graph · All operations

Walk a parent-child hierarchy

A variant of Analyse a network

Follow parent-child links to build ancestor paths, a closure table of every ancestor and descendant, or totals rolled up each level.

Status

In arcform

Runs as a SQL step

arcform carries it as a sql: step today.

The DuckDB step

Build ancestor paths, a closure table and rolled-up totals from parent-child links

SQL
-- an organisation as parent links: two roots, and nodes 7 and 8 that name each other as parent (a loop no root reaches)
CREATE TEMP TABLE nodes AS SELECT * FROM (VALUES
  (1, NULL, 'company', 10), (2, 1, 'sales', 5), (3, 1, 'support', 7), (4, 2, 'emea', 3), (5, 2, 'apac', 2), (6, 4, 'uk', 1), (9, NULL, 'foundation', 4), (7, 8, 'loop a', 100), (8, 7, 'loop b', 100)) t(id, parent, name, amount);
-- ancestor paths: walk down from the roots, adding each node's name to its parent's path
CREATE TEMP TABLE paths AS
WITH RECURSIVE walk(id, path, depth) AS (
  SELECT id, name, 0 FROM nodes WHERE parent IS NULL
  UNION ALL
  SELECT n.id, w.path || ' > ' || n.name, w.depth + 1 FROM walk w JOIN nodes n ON n.parent = w.id)
SELECT * FROM walk;
-- closure table: one row for every node and each of its ancestors, with the distance between them (a node is its own ancestor at distance 0)
CREATE TEMP TABLE closure AS
WITH RECURSIVE up(descendant, ancestor, distance) AS (
  SELECT id, id, 0 FROM nodes WHERE id IN (SELECT id FROM paths)
  UNION ALL
  SELECT u.descendant, n.parent, u.distance + 1 FROM up u JOIN nodes n ON n.id = u.ancestor WHERE n.parent IS NOT NULL)
SELECT * FROM up;
-- roll up: each node's own amount plus those of everything beneath it, from the closure table
CREATE TEMP TABLE rolled AS
SELECT c.ancestor AS id, sum(n.amount) AS total, count(*) - 1 AS below FROM closure c JOIN nodes n ON n.id = c.descendant GROUP BY c.ancestor;
SELECT * FROM paths ORDER BY id;
SELECT p.id, n.name, r.total, r.below FROM rolled r JOIN nodes n USING (id) JOIN paths p USING (id) ORDER BY id;
-- the loop at nodes 7 and 8 has no root above it, so the walk from the roots never reaches it and cannot run on forever
SELECT CASE WHEN ((SELECT count(*) = 7 FROM paths)
  AND (SELECT path = 'company > sales > emea > uk' AND depth = 3 FROM paths WHERE id = 6)
  AND (SELECT path = 'foundation' AND depth = 0 FROM paths WHERE id = 9)
  AND (SELECT count(*) = 16 FROM closure)
  AND (SELECT list(ancestor ORDER BY distance) = [6, 4, 2, 1] FROM closure WHERE descendant = 6)
  AND (SELECT map_from_entries(list((id, total) ORDER BY id)) = MAP {1: 28, 2: 11, 3: 7, 4: 4, 5: 2, 6: 1, 9: 4} FROM rolled)
  AND (SELECT map_from_entries(list((id, below) ORDER BY id)) = MAP {1: 5, 2: 3, 3: 0, 4: 1, 5: 0, 6: 0, 9: 0} FROM rolled)
  AND (SELECT count(*) = 0 FROM closure WHERE descendant IN (7, 8))) THEN 'as expected' ELSE error('the walk should give 7 paths, the closure table 16 rows, the company a total of 28 over 5 descendants, and nothing for the loop') END AS verdict;
  • The statement builds its own data.
  • It needs nothing installed beyond DuckDB itself.
  • The statement checks its own result and raises an error when it is wrong: “the walk should give 7 paths, the closure table 16 rows, the company a total of 28 over 5 descendants, and nothing for the loop”.
  • It passed on DuckDB v2.0.0 (Cyanoptera) d54cbbe3df.

What other tools call it

Meridian's classification; an independent blind rating agreed on 95.7% of 324 rows (variant, version 3).

Apache Hop (1)
  • Closureread 2026-09-27

    Build a reflexive transitive closure table with distances from parent-child pairs

EasyMorph (2)
  • Hierarchy pathread 2026-09-27

    Build a pipe-delimited ancestor path for each row of a parent-child table

  • Roll upread 2026-09-27

    Sum amounts upward through each level of a parent-child hierarchy

Pentaho Data Integration (1)
  • Closure Generatorread 2026-09-27

    Build a closure table from parent-child relationships

Background

A hierarchical query is an SQL query for hierarchical data, useful with graph-structured data such as river networks, file system trees or threaded comments.[1] A hierarchy expressed as a parent-child relation is what Joe Celko called the adjacency list model.[2] Apache Hop's Closure transform builds a closure table: every possible parent-child relationship in a hierarchy, with the distance in levels between them.[3]

When to use it

EasyMorph's Roll up action generates summed totals for each level of a hierarchy, such as a chart of accounts or an employee hierarchy.[4] EasyMorph's Hierarchy path action is meant for parent-child relationships such as company organisational charts, and generates a pipe-delimited path for every value that references a parent value in the same table.[5]

For a hierarchy of arbitrary depth, the adjacency list model does not allow the expression of operations such as determining whether an element is somewhere in the subhierarchy of another.[2] Reach for a recursive walk or a closure table whenever the depth of the hierarchy is not known in advance. (Meridian's view)

EasyMorph's Hierarchy path and Roll up actions require every primary key to be unique, and a parent-child loop, such as Key01 and Key10 naming each other as parent, results in an error.[5][4] In DuckDB, a recursive common table expression (CTE), written WITH RECURSIVE, must be formulated in a way that ensures termination, otherwise it may run into an infinite loop.[6] Apache Hop's Closure transform has a Root is zero option for a tree whose root has a parent of zero rather than an empty (null) one.[3] Check how the source marks a root, whether by an empty parent, a zero or a row that names itself, before choosing the rows the walk starts from. (Meridian's view)

The method

In standard SQL:1999, hierarchical queries are implemented by way of recursive CTEs, which were designed with fixed-point semantics from the beginning, unlike Oracle's earlier CONNECT BY clause.[1] In DuckDB, WITH RECURSIVE can traverse trees, for example to return the path from a node in a hierarchy of tags up to the root of its tree.[6] Recursive CTEs create no automatic pseudo-columns such as a level, so if a level is wanted it has to be created in the query's own code.[1]

Apache Hop's Closure transform reads all input rows in memory, and takes a parent ID field, a child ID field and the name of the distance field it adds to the output.[3] EasyMorph's Hierarchy path action can build each path from labels or from keys, and can reverse the order of the path.[5] EasyMorph's Roll up action adds amounts up through each level of a hierarchy, putting the rolled-up values either in the amounts column or in a new column.[4] In EasyMorph's chart of accounts example for Roll up, Inventory totals 60000 from its two widget lines, and Asset totals 120000 from Cash, Accounts Receivable and Inventory.[4]

Compared with the alternatives

Oracle introduced the non-standard CONNECT BY construct in the 1980s, and before Oracle 10g it returned an error on detecting a cycle; 10g added the NOCYCLE keyword so that traversal works with cycles.[1]

The nested set model numbers the nodes of a tree in the order of a traversal that visits each node twice, storing two numbers for each node.[2] In the nested set model, querying is inexpensive because hierarchy membership can be tested by comparing the numbers, but updating requires renumbering and is expensive.[2] Recursive SQL queries can be expected to perform comparably to nested sets for finding immediate descendants, and much faster for other depth searches, in databases that provide them.[2] Hierarchies may also be expressed easily by switching to a graph database.[2] A closure table is worth building when the same hierarchy is asked about many times; a recursive query is enough for a one-off question. (Meridian's view)

Sources

  1. [1]Hierarchical and recursive queries in SQL - Wikipediasecondary source
  2. [2]Nested set model - Wikipediasecondary source
  3. [3]Closure | Apache Hopdocumentation
  4. [4]ROLL UP [EasyMorph Help]documentation
  5. [5]HIERARCHY PATH [EasyMorph Help]documentation
  6. [6]WITH Clause – DuckDBdocumentation