Data Modeling & Schema Design
Modeling Hierarchies and Graphs
Hierarchical data can be stored with parent references, encoded paths, subtree intervals, or an explicit transitive closure. The right model follows the dominant reads, mutation rate, integrity rules, and whether the structure is truly a tree.
- An adjacency list stores the direct edge and is the simplest normalized tree model.
- A materialized path makes ancestry visible in each node.
- Nested sets encode containment with left and right bounds.
- A closure table stores every ancestor–descendant pair.
- Cycles, multiple parents, sibling order, and orphan policy are separate constraints that the storage shape does not solve automatically.
- When edges have identity or attributes such as rank, validity, or provenance, model them as first-class relationship rows.
Four models for commerce categories
| Model | Subtree read | Insert or move | Storage | Characteristic risk |
|---|---|---|---|---|
| Adjacency list | Recursive traversal | Local parent update | One parent key per node | Cycles and deep recursive reads |
| Materialized path | Path-prefix predicate | Rewrite moved subtree paths | Path repeated per node | Encoding and stale descendant paths |
| Nested sets | Range predicate on bounds | Potentially broad renumbering | Two bounds per node | Write amplification and concurrent moves |
| Closure table | Direct lookup by ancestor | Insert/delete closure rows | One row per reachable pair | Maintenance bugs and quadratic growth in chains |
CREATE TABLE categories (
category_id BIGINT PRIMARY KEY,
parent_category_id BIGINT REFERENCES categories(category_id),
name VARCHAR(200) NOT NULL,
CHECK (parent_category_id IS NULL OR parent_category_id <> category_id)
);
CREATE TABLE category_closure (
ancestor_id BIGINT NOT NULL REFERENCES categories(category_id),
descendant_id BIGINT NOT NULL REFERENCES categories(category_id),
depth INTEGER NOT NULL CHECK (depth >= 0),
PRIMARY KEY (ancestor_id, descendant_id)
);