Adjacency Lists and Recursive Hierarchies

Learning outcomes

Many business structures are hierarchical: categories contain subcategories, organizational units contain teams, assets contain subassemblies, and locations contain sublocations. The simplest relational representation is the adjacency list, where each row stores a reference to its parent.

Adjacency-list schema

FailureCategory(  category_id,  parent_category_id,  code,  display_name)FOREIGN KEY (parent_category_id)REFERENCES FailureCategory(category_id)

Root rows

A root usually has:

parent_category_id IS NULL

or references a dedicated synthetic root, depending on model requirements.

Example hierarchy

One row per node

Each category stores only its immediate parent. The full path is derived by traversal.

Recursive query

WITH RECURSIVE tree AS (  SELECT category_id, parent_category_id, display_name, 0 AS depth  FROM failure_category  WHERE category_id = :root  UNION ALL  SELECT c.category_id, c.parent_category_id, c.display_name, t.depth + 1  FROM failure_category c  JOIN tree t    ON c.parent_category_id = t.category_id)SELECT *FROM tree;

Ancestor traversal

The same technique can walk upward by joining parent rows instead of children.

Index the parent reference

INDEX(parent_category_id)

supports “find children of this node” efficiently.

Moving a subtree

With adjacency lists, moving a node and all descendants usually requires changing only the moved node's parent reference. This is a major write-side advantage.

Cycle problem

Invalid:

A parent=BB parent=CC parent=A

The foreign keys are individually valid, yet the hierarchy contains a cycle.

Cycle prevention

Possible strategies include:

• recursive validation before parent update;
• triggers;
• closure-table constraints;
• application/domain service checks;
• database-specific cycle detection features.

Multiple roots

Decide whether multiple independent trees are allowed. If not, enforce a single-root business rule.

Depth limits

Some taxonomies permit only a fixed maximum depth. If this is a business rule, validate it explicitly rather than assuming the UI will prevent deeper nesting.

Sibling uniqueness

You may require category code unique within parent:

UNIQUE(parent_category_id, code)

NULL/root semantics need careful handling depending on DBMS.

Ordering siblings

sort_order

belongs on the child row if it controls display order within the parent.

Soft deletion in hierarchies

Deleting a parent raises lifecycle questions:

• cascade delete descendants?
• reject while children exist?
• reparent children?
• soft-delete the subtree?

Choose based on domain meaning.

WorkshopHub hierarchy candidates

When adjacency list is enough

Use it when:

• moves are common;
• depth is modest;
• recursive queries are supported;
• ancestor/descendant reads are not extreme hot paths.

Practice: model an organization

Summary and next lesson

Adjacency lists are the simplest relational hierarchy model: easy to understand, easy to move, and compatible with recursive SQL. Their main costs are recursive traversal and cycle enforcement. The next lesson compares alternative hierarchy structures optimized for faster subtree and ancestor queries.

References

• Joe Celko, Trees and Hierarchies in SQL for Smarties.
• PostgreSQL documentation on recursive queries.
• SQL standard recursive common table expression concepts.