Modelling hierarchies

A hierarchy records which things sit beneath which others. The shop puts Blue mugs beneath Mugs, and Mugs beneath Teaware. An application might need only the immediate children of Teaware, or it might need everything below it, however deep the catalogue grows. Those are different queries over the same relationships.

The simplest representation stores one parent ID on each category. Other representations store complete paths, every ancestor–descendant pair, or numbers that enclose a subtree. They make some reads more direct by storing answers that a parent chain would otherwise have to calculate. Moving a branch then changes those stored answers too.

Every example uses the same five invented categories. Their IDs are Catalogue 0, Teaware 10, Mugs 11, Blue mugs 12 and Gifts 20. Catalogue is a synthetic root added to the modelling article’s categories. Each variation starts from the same tree unless stated otherwise. We will move Mugs from Teaware to Gifts, leaving Blue mugs beneath it, then consider a different rule that permits Mugs under both.

The SQL uses PostgreSQL 18. The worked scenarios model rows and algorithms, rather than a particular physical execution. The complete example script builds the data, maintenance functions and consistency checks in a disposable database. It keeps direct parentage as the authority for a tree, and direct edges for the multiple-parent alternative.

Parents and ancestry

A parent is one immediate step above a category. An ancestor is reached through one or more parent steps. Teaware is Mugs’ parent; Catalogue is its ancestor. In the other direction, Mugs and Blue mugs are both descendants of Teaware. A subtree includes a category and everything beneath it, so the Mugs subtree contains Mugs itself and Blue mugs.

Initially Catalogue is the parent of both Teaware and Gifts. Moving Mugs beneath Gifts changes Mugs’ parent from 10 to 20; Blue mugs remains attached to Mugs. A separate alternative keeps Mugs beneath both Teaware and Gifts at once, which changes the kind of hierarchy being represented.

A rooted tree has one root, one parent for every other node, and no cycles: following parent links never brings you back to a category you already visited. Several disconnected trees make a forest. A nullable parent column can represent a forest just as easily as a tree; it does not choose the root policy for you.

With two parents, Mugs still has one category identity, 11. Giving each occurrence a new category ID would turn a shared category into two separate categories whose names merely agree. The edge-table alternative permits several routes to the same node. If it forbids cycles, the result is a directed acyclic graph, usually shortened to DAG. A tree is a restricted DAG with a single route from its root to each node.

That choice affects the application as well as the storage. A tree has one ancestor chain for a breadcrumb. A shared category can have several breadcrumbs. Before choosing its tables, decide whether the application wants one category, one route to it, or one displayed occurrence on a chosen route.

Adjacency lists

An adjacency list stores each node’s immediate neighbour: here, its parent. One row records one category, its current name and its current parent ID.

CREATE TABLE categories (
  category_id integer PRIMARY KEY,
  name text NOT NULL,
  parent_id integer REFERENCES categories(category_id) ON DELETE RESTRICT,
  CHECK (category_id <> parent_id),
  CHECK ((category_id = 0 AND parent_id IS NULL)
      OR (category_id <> 0 AND parent_id IS NOT NULL))
);
CREATE INDEX categories_parent ON categories(parent_id);
INSERT INTO categories VALUES
  (0, 'Catalogue', NULL), (10, 'Teaware', 0),
  (11, 'Mugs', 10), (12, 'Blue mugs', 11), (20, 'Gifts', 0);

The self-referencing foreign key requires a non-null parent ID to name an existing category. CHECK (category_id <> parent_id) rejects a category naming itself. It still accepts Teaware naming Blue mugs while Blue mugs names Mugs and Mugs names Teaware. Every target exists, yet the three links form a cycle.

The second check makes Catalogue the only row allowed to have a null parent, and requires every other category to have a parent. It does not require the Catalogue row to exist in an empty table, or rule out a disconnected cycle. The starting insert supplies the root; the maintenance procedure must preserve connectivity and acyclicity. Constraints and data integrity distinguishes row rules from invariants spanning several rows.

Children and sibling order

Direct children need no recursion. WHERE parent_id = 10 finds Mugs. Roots satisfy parent_id IS NULL. The parent index helps a query find children without searching every category; it does not enforce any hierarchy rule.

Keep identity separate from display. Renaming Blue mugs leaves ID 12 and its links intact. If the shop wants an editorial order among siblings, store an explicit sibling position and order by it with a stable tie-breaker such as category ID. Neither insertion order nor the name supplies an editorial order automatically. The examples order siblings by ID to keep their results reproducible.

Recursive queries

A fixed number of joins can follow a fixed number of levels. It cannot answer “all descendants” when the tree may grow deeper. A recursive common table expression, or recursive CTE, repeatedly applies the same relationship to the rows it found last time.

The query below starts with Teaware and includes that starting category in its answer. depth counts edges from Teaware. route carries the visited category IDs.

WITH RECURSIVE below(category_id,name,depth,route) AS (
  SELECT category_id,name,0,ARRAY[category_id] FROM categories WHERE category_id=10
  UNION ALL
  SELECT c.category_id,c.name,b.depth+1,b.route||c.category_id
  FROM below b JOIN categories c ON c.parent_id=b.category_id
  WHERE NOT c.category_id=ANY(b.route)
) SELECT category_id,name,depth,route FROM below ORDER BY route;

The first SELECT is the starting term. The SELECT after UNION ALL is the recursive term: join a category’s parent_id to an ID in the current working rows. Each round supplies the parents for the next round, until no further child is found.

The result contains Teaware at depth 0, Mugs at 1 and Blue mugs at 2. The working set is replaced at each round; the accumulated result is retained. When Blue mugs produces no child, the empty working set ends the recursion. To ask for strict descendants only, filter depth > 0 in the outer query.

Breadcrumbs

Reverse the join to go upwards. Carry the current row’s parent ID, then find the category whose own ID matches it. Starting at Blue mugs, those successive matches find Mugs, Teaware and Catalogue.

WITH RECURSIVE above(category_id,name,parent_id,depth,route) AS (
  SELECT category_id,name,parent_id,0,ARRAY[category_id]
  FROM categories WHERE category_id=12
  UNION ALL
  SELECT c.category_id,c.name,c.parent_id,a.depth+1,a.route||c.category_id
  FROM above a JOIN categories c ON c.category_id=a.parent_id
  WHERE NOT c.category_id=ANY(a.route)
) SELECT category_id,name FROM above ORDER BY depth DESC;

This query starts at Blue mugs, so its working rows arrive in the opposite direction from the displayed breadcrumb. ORDER BY depth DESC puts Catalogue first: Catalogue → Teaware → Mugs → Blue mugs.

Ordering and cycle detection

The descendant query sorts by its ID array. A prefix sorts before an extension, so Mugs comes before Blue mugs, and a complete branch precedes the next sibling. For level order, use ORDER BY depth, category_id. Both specify the final presentation order. Neither instructs PostgreSQL to physically visit nodes in that order.

The visited-ID condition prevents a path from revisiting a category. It makes the read terminate on malformed data, but silently omits the repeated step. PostgreSQL’s CYCLE clause can instead report the repeated row and stop expanding it:

WITH RECURSIVE below(category_id,parent_id,depth) AS (
  SELECT category_id,parent_id,0 FROM categories WHERE category_id=10
  UNION ALL
  SELECT c.category_id,c.parent_id,b.depth+1
  FROM below b JOIN categories c ON c.parent_id=b.category_id
) CYCLE category_id SET is_cycle USING route
SELECT category_id,depth,is_cycle FROM below ORDER BY route;

On the valid tree every is_cycle value is false. Now change Teaware’s parent to Blue mugs. The walk from Teaware visits 10, 11 and 12, then arrives back at 10. That last row is marked true. Detecting it during a query does not prevent the bad links from being stored.

Replacing UNION ALL with UNION is sufficient only when revisiting a node produces the same complete row. A result containing just category IDs can discard a repeated ID. A row holding both ID and depth is new on every lap of a cycle, because the depth keeps growing. Category 10 appears at depth 0, then 3, then 6. Whole-row duplicate removal cannot stop that walk. Track the visited identity or use CYCLE when carrying changing path information.

Moving a subtree

In the adjacency list, moving Mugs under Gifts changes one stored relationship: Mugs’ parent_id becomes 20. Blue mugs continues to reference 11. No descendant row needs a new parent merely because an ancestor moved.

Before making that change, find the entire moving subtree, including its root. The proposed parent must exist and must be outside that set. Mugs cannot move beneath itself or Blue mugs. Teaware cannot move beneath Blue mugs either: the proposed 12 → 10 edge would close the cycle Teaware → Mugs → Blue mugs → Teaware.

Checking and updating in one transaction is necessary, but the check must also be protected from concurrent topology changes. Suppose one request moves Teaware under Gifts while another moves Gifts under Teaware. Each request looks valid against the starting tree. If both commit, Teaware and Gifts become each other’s parent, creating a cycle.

The two moves update different rows, so locking only each moving row leaves room for both checks to pass. A conservative protocol instead makes all category writers take turns across the whole table, before they inspect the hierarchy.

A protected PostgreSQL move

For a small catalogue, the following complete transaction is a practical starting point. It uses Read Committed and acquires a SHARE ROW EXCLUSIVE table lock before reading categories. That lock conflicts with another such lock and with ordinary inserts, updates and deletes, while ordinary readers can continue.

BEGIN ISOLATION LEVEL READ COMMITTED;
LOCK TABLE categories IN SHARE ROW EXCLUSIVE MODE;
DO $$
DECLARE moving integer := 11; new_parent integer := 20;
BEGIN
  IF moving = 0 OR moving IS NULL OR new_parent IS NULL
     OR NOT EXISTS (SELECT FROM categories WHERE category_id = moving)
     OR NOT EXISTS (SELECT FROM categories WHERE category_id = new_parent) THEN
    RAISE EXCEPTION 'invalid category or root move';
  END IF;
  IF EXISTS (
    WITH RECURSIVE subtree(id) AS (
      SELECT category_id FROM categories WHERE category_id = moving
      UNION
      SELECT c.category_id FROM categories c JOIN subtree s ON c.parent_id = s.id
    ) SELECT FROM subtree WHERE id = new_parent
  ) THEN RAISE EXCEPTION 'new parent is inside the moving subtree'; END IF;
  UPDATE categories SET parent_id = new_parent WHERE category_id = moving;
END $$;
ROLLBACK; -- Use COMMIT to keep an accepted move; this example restores its baseline.

The example rolls back so the next experiment starts from the same tree. Use COMMIT to retain an accepted move. An exception aborts the attempt; the caller must roll back. The recursive membership test uses UNION over IDs alone, so it terminates even if the input already contains a cycle. Establish that imported data forms a valid tree before enabling moves; a terminating membership query is not a complete data audit.

Acquire the lock as the first hierarchy operation in a fresh transaction, then read and validate in a subsequent statement. If another writer held the table, the lock waits for it to finish; the following Read Committed query sees its committed result. Reusing an earlier Repeatable Read snapshot would defeat that reasoning. Keep the lock through every maintained copy and the final commit.

The cost is broad contention: a move also blocks an unrelated category insert or name edit until the transaction ends. More selective locking and serializable execution can allow more concurrency, but need a complete protocol and, where required, retries. Transactions and isolation develops those choices. Changing the lock without revisiting the invariant is not a safe optimisation.

Deleting a category

Decide what deletion means before choosing its SQL. The example’s ON DELETE RESTRICT refuses to delete Mugs while Blue mugs references it. That makes “remove this one category” fail instead of silently choosing what happens to its children.

A subtree deletion deliberately selects the moving-style descendant set and removes all its nodes and associated derived rows within the protected transaction. Promoting children instead assigns Mugs’ direct children to Mugs’ former parent, then removes Mugs; their descendants remain attached to them. Both need the same topology boundary and subsequent consistency checks. Neither operation should delete the synthetic root. Retention and the decision to erase or retire business records belong in History, correction and deletion; the hierarchy procedure implements the policy it is given.

Edge tables and multiple parents

Now take the independent alternative in which Mugs belongs under both Teaware and Gifts. Remove the single-parent fact from the node table. Store each immediate parent–child association as an edge:

CREATE TABLE category_edges (
  parent_id integer REFERENCES dag_categories,
  child_id integer REFERENCES dag_categories,
  PRIMARY KEY(parent_id,child_id),
  CHECK(parent_id <> child_id), CHECK(child_id <> 0)
);

The separate dag_categories table contains one row per category ID and name. Both foreign keys require existing endpoints. The pair is unique, so Teaware → Mugs cannot be recorded twice. There is deliberately no UNIQUE (child_id): that would restrict a child to one parent again. The checks reject self-edges and any incoming edge to Catalogue.

The root now has two routes to Mugs, and two to Blue mugs: one through Teaware and one through Gifts. They reach the same category IDs. There are still five categories, even though enumerating every root-to-category path produces seven occurrences.

One reachable node, or every path?

For “which categories can Catalogue reach?”, the recursive row can be just an ID. Use UNION to keep each reachable ID once:

WITH RECURSIVE reachable(id) AS (
  SELECT 0
  UNION
  SELECT e.child_id FROM reachable r JOIN category_edges e ON e.parent_id=r.id
) SELECT id FROM reachable ORDER BY id;

For “which paths can a shopper follow?”, keep the route and preserve its occurrences:

WITH RECURSIVE routes(id,route) AS (
  SELECT 0,ARRAY[0]
  UNION ALL
  SELECT e.child_id,r.route||e.child_id
  FROM routes r JOIN category_edges e ON e.parent_id=r.id
  WHERE NOT e.child_id=ANY(r.route)
) SELECT * FROM routes ORDER BY route;

Mugs and Blue mugs each appear twice in the path result. Removing duplicates on ID afterwards would discard path information. Choosing the minimum depth would define “shortest route”, not a unique inherent depth of the category. A breadcrumb needs a chosen route, perhaps the route by which the shopper arrived.

Changing edges

Adding parent → child is forbidden if the proposed parent is already reachable from the child, including the child itself. Apply that test while holding the topology lock on the edge table and its node table, then insert and maintain any derived reachability before committing. Every edge-changing procedure must use the same lock order.

Removing Gifts → Mugs deletes one association. It does not delete Mugs, Blue mugs or Teaware → Mugs. The download’s change_edge(20,11,false) procedure deletes that edge, rechecks reachability from Catalogue and rebuilds the DAG closure in one protected transaction. Mugs and Blue mugs remain reachable through Teaware. The chosen shop policy rejects an edge removal that leaves any category unreachable; a system permitting disconnected roots would choose another policy.

A tree’s “delete this subtree” has no automatic equivalent here. Some reachable nodes may still belong under another branch. First decide whether the operation removes an edge, every path from a chosen root, or the categories themselves. Weighted parts explosions and general graph algorithms introduce further meanings; this category model does not calculate quantities along paths.

Materialised paths

An adjacency list stores one step and calculates ancestry when asked. A materialised path stores the whole sequence from root to node. Blue mugs’ path is 0.10.11.12. Its ancestors are the preceding segments; all descendants of Mugs share the complete segment prefix 0.10.11.

Stable IDs keep a category rename from rewriting every descendant path. Compare whole segments, not arbitrary text prefixes: a prefix ending partway through an ID is not an ancestor. A delimited text format needs an unambiguous encoding and segment-aware comparisons.

PostgreSQL’s ltree extension supplies a path type and operators for this purpose. Store path ltree, then path <@ '0.10.11'::ltree selects Mugs and Blue mugs. The descendant operator includes equality, so use an additional inequality if the starting category must be excluded. @> reads the relationship in the other direction. GiST indexes support these ancestry tests; whether one pays for the workload remains a measured query question.

A move rewrites descendant paths

Moving Mugs means replacing its old prefix in every subtree path, preserving each suffix. Capture Mugs’ old path and Gifts’ destination path after taking the topology lock. Validate the move against authoritative parentage. The download’s move function then applies this update:

UPDATE category_paths SET path = destination ||
    CASE WHEN path = old_path THEN text2ltree(moving::text)
         ELSE text2ltree(moving::text) || subpath(path, nlevel(old_path)) END
  WHERE path <@ old_path;

Here old_path is 0.10.11 and destination is 0.20. Mugs becomes 0.20.11. For Blue mugs, subpath retains the remaining 12 and appends it to that new prefix. The special equality case handles Mugs itself, which has no remaining suffix. These are function-body statements; the complete function, declarations and transaction call are in the download.

Update the authoritative parent and all paths in that same transaction. Afterwards, rebuild expected root-to-node paths from the parent references and compare both directions: every expected row must exist, and no stored row may be extra or different. Checking only that a path ends in its category ID would miss a wrong ancestor.

A single path per category represents one parentage route. It cannot hold both the Teaware and Gifts routes to Blue mugs. A separate table can store every route to a shared category, but a graph with many branching and rejoining routes can have far more paths than nodes. A move or edge removal may then rewrite many occurrences. Store those paths because their reads justify that maintenance, not merely because the first example is small.

Closure tables

A closure table stores the answer to reachability directly. Each row says that one category is an ancestor of, or equal to, another. For a tree, a depth column records the number of edges between them.

CREATE TABLE category_closure (
  ancestor_id integer REFERENCES categories,
  descendant_id integer REFERENCES categories,
  depth integer NOT NULL CHECK (depth >= 0),
  PRIMARY KEY (ancestor_id, descendant_id)
);

Write a closure row as (ancestor, descendant, depth). Include every node’s self-pair at depth 0. Mugs’ outgoing pairs are (11,11,0) for itself and (11,12,1) for Blue mugs, its direct child.

To read Mugs’ subtree, find closure rows with ancestor_id = 11 and join their descendant IDs to categories. For its breadcrumb, find rows with descendant_id = 11 and join the ancestor IDs; descending depth puts the root first. There is no recursive read because the reachability has already been stored.

Inserting a leaf

Imagine building the starting tree by adding Blue mugs last. Every ancestor of its parent, Mugs, becomes an ancestor of Blue mugs one edge further away. Add the new self-pair too:

INSERT INTO category_closure
  SELECT ancestor_id, 12, depth + 1 FROM category_closure WHERE descendant_id = 11
  UNION ALL SELECT 12,12,0;

That adds four rows, written as ancestor, descendant and depth:

• (12,12,0) for Blue mugs itself
• (11,12,1) for Mugs
• (10,12,2) for Teaware
• (0,12,3) for Catalogue

Insert the category and these rows inside the protected topology transaction. A missing self-pair would make the same recipe miss the direct parent, so self-pairs are part of the invariant rather than optional decoration.

Moving the Mugs subtree

Internal subtree ancestry survives the move: Mugs still reaches Blue mugs in one edge. What changes is the ancestry entering the subtree from outside. Under the topology lock, remove those outside-to-inside pairs, then form every new-ancestor × subtree-descendant combination.

DELETE FROM category_closure c
  WHERE c.descendant_id IN (
    SELECT descendant_id FROM category_closure WHERE ancestor_id = moving
  ) AND c.ancestor_id NOT IN (
    SELECT descendant_id FROM category_closure WHERE ancestor_id = moving
  );
  -- Add all new ancestors x subtree descendants. The retained self pairs
  -- make both the destination and the moving root participate in this product.
  INSERT INTO category_closure(ancestor_id, descendant_id, depth)
  SELECT a.ancestor_id, d.descendant_id, a.depth + 1 + d.depth
  FROM category_closure a CROSS JOIN category_closure d
  WHERE a.descendant_id = new_parent AND d.ancestor_id = moving;

For this move, the outside ancestors before the change are Catalogue and Teaware; the subtree nodes are Mugs and Blue mugs. The general procedure removes their four crossing pairs. It then combines Catalogue and Gifts with the two subtree nodes, adding four pairs. The depth is distance to Gifts + one new edge + distance down from Mugs.

Catalogue’s two pairs return at the same depths because this move leaves the subtree at the same level. The net difference is that Teaware loses its two pairs and Gifts gains two. Retain the self-pairs and all internal pairs. Update parentage, then compare the entire stored closure with reachability freshly derived from it before accepting the transaction.

Closure trades traversal work for stored pairs. A chain of n nodes has 1 + 2 + … + n pairs when self-pairs are included: n(n + 1)/2. A wide shallow tree stores fewer. Count the expected pairs for the actual depth and shape before choosing it.

Closure with shared ancestry

The tree move recipe depends on unique parentage. In the DAG, removing Gifts → Mugs must remove Gifts’ reachability to Mugs and Blue mugs, but Catalogue still reaches both through Teaware. Deleting every pair once supported by the removed edge would remove valid answers too.

There may also be several path lengths between the same two nodes. This shop’s DAG closure therefore stores distinct (ancestor, descendant) pairs with no unqualified depth column. After a protected edge change, it rebuilds those pairs from the authoritative edges:

CREATE FUNCTION expected_dag_closure()
RETURNS TABLE(ancestor_id integer, descendant_id integer) LANGUAGE sql STABLE AS $$
  WITH RECURSIVE reach(a,d) AS (
    SELECT category_id, category_id FROM dag_categories
    UNION
    SELECT r.a,e.child_id FROM reach r JOIN category_edges e ON e.parent_id = r.d
  ) SELECT a,d FROM reach
$$;

Delete the old derived rows and insert this result in the same transaction as the edge change; the download’s procedure does both. UNION compares the pair alone, so another path to an existing pair contributes no second row. Rebuilding is simple and checkable for a small catalogue. If its pair count and change rate make the rebuild too costly, a more elaborate incremental reachability scheme needs its own accounting of alternative support. Reusing a tree’s deletion rule is not that scheme.

Nested sets

Nested sets encode a tree by numbering a traversal. Give a node an entry number when entering it, visit its children, then give it an exit number when leaving. An ancestor’s interval encloses every descendant’s interval.

Visit siblings by category ID. Teaware receives interval (2,7), enclosing its descendants. Blue mugs’ interval (4,5) lies inside those bounds. Gifts occupies (8,9), outside them. Containment therefore answers an ancestry question without following the parent chain.

The subtree query becomes a range condition. Join the chosen category’s bounds as parent, then select nodes whose entry number satisfies node.lo BETWEEN parent.lo AND parent.hi. This includes the chosen category. Ancestors instead have a lower entry and a higher exit; make comparisons inclusive when self is wanted.

CHECK (lo < hi) is far from enough to establish this representation. Two rows can reuse an endpoint or cross, such as intervals (2,6) and (4,8), while both pass that check. A correct numbering has unique endpoints across both columns, properly nested or disjoint intervals, and ancestry agreeing with the source tree.

Insertions and moves renumber the tree

Without Blue mugs, the baseline has Catalogue (1,8) and Gifts (6,7). Teaware is (2,5) and Mugs is (3,4). Making room before Mugs’ exit shifts every endpoint at 4 or above by two. The four existing category rows change; Blue mugs takes (4,5). One new leaf can therefore affect rows outside its branch.

A subtree move has to remove one numbered region and open another without leaving crossings, collisions or stale bounds. For this small, infrequently changed catalogue, a simpler maintenance route keeps direct parents authoritative and regenerates all bounds deterministically under the topology lock. The download creates two events per node, orders entry before descendants and exit after them, then numbers the events:

CREATE FUNCTION expected_bounds()
RETURNS TABLE(category_id integer, lo integer, hi integer)
LANGUAGE sql STABLE AS $$
  WITH events AS (
    SELECT category_id, route || -1 AS event_path, false AS exiting FROM tree_walk
    UNION ALL
    SELECT category_id, route || 2147483647, true FROM tree_walk
  ), numbered AS (
    SELECT category_id, exiting,
           row_number() OVER (ORDER BY event_path)::integer AS n
    FROM events
  )
  SELECT category_id, min(n), max(n) FROM numbered GROUP BY category_id
$$;

The tree_walk view supplies root-to-node ID arrays. The extra markers sort entry before any child and exit after all children; this example reserves those marker values outside its allowed category IDs. Every node’s first event is its entry and its second its exit.

After updating the parent, delete the old derived bounds and insert the regenerated result before committing. Readers see committed versions according to their isolation level; an ordinary query does not see the intermediate empty table. Use a DELETE here rather than replacing this procedure with TRUNCATE, which has different locking and snapshot behaviour. A reader issuing several queries at Read Committed can still cross a commit between queries; use one query or a suitable snapshot if those answers must describe one version.

The Mugs move changes four categories’ bounds, although this rebuild replaces all five stored bound rows. Check endpoint uniqueness, reject crossings and compare the result with the deterministic source-tree traversal. That last comparison also catches a perfectly nested numbering that encloses the wrong category.

A single interval per category gives every node one place in a tree. It cannot place Mugs inside both disjoint Teaware and Gifts intervals while retaining those branches. Duplicating intervals creates route occurrences and brings back the identity and maintenance questions of materialised paths.

Choosing and checking a representation

Start with the questions and changes the application actually needs. Direct children, breadcrumbs and whole subtrees place different demands on a representation. So do a narrow chain, a shallow catalogue, frequent branch moves and shared ancestry.

The worked move makes the write differences concrete. The counts below concern logical example rows, excluding indexes, row versions and logging. They are not speed measurements.

For a changing category tree, an adjacency list often supplies enough with the fewest stored answers to maintain. Add paths when route reads justify rewriting descendant paths; closure when reachability reads justify its pair count; nested sets when interval reads justify renumbering. There is no universal read-speed order among them: indexes, result size, shape, cache state and query plans still matter. Index design and query execution cover how to measure that work.

If several parents are a real requirement, start with edges and be precise about nodes versus paths. The single-path and single-interval tree representations do not acquire DAG semantics merely by allowing duplicate category IDs somewhere. A reachability closure can support a DAG, but its maintenance must preserve pairs still supported by another route.

For every derived representation, name one authority and one update boundary. The download deliberately maintains all three beside parentage to compare their procedures; an application need not store all three. Its move_tree_node function locks categories and the derived tables in a fixed order, validates, updates each representation and rejects any mismatch before the transaction can commit. A production interface must also control direct writes so other writers cannot bypass that boundary.

A useful consistency check rebuilds the expected answer from the direct facts, then compares in both directions. An expected row absent from storage is missing data. A stored row absent from the expected result is stale or invented data. Equal row counts alone cannot distinguish them. The example’s assert_derived() checks paths, closure and bounds this way, as well as verifying that every category is reachable from Catalogue.

Try a move, a forbidden descendant-parent link, a leaf insertion and an edge removal with another route left intact. Remove one derived pair deliberately and confirm that the checker finds it. Test opposing moves with two real sessions, because a single successful move cannot establish concurrency protection. Those checks turn a convenient representation into a maintainable contract.