Schema Patterns: Closure Tables, Inheritance and Versioned History

Hierarchies. Comments with replies, categories, an org chart and folders are trees. The simplest layout (an adjacency list) stores a parent_id on each row; finding all descendants then needs a recursive query. Materialized paths store the full path as text. A closure table trades space for simple, fast reads.

The closure table. Keep the nodes in their own table, and add a second table with one row for every ancestor and descendant pair, including each node paired with itself at depth 0. A node three levels deep appears in four closure rows (itself and its three ancestors). To get a whole subtree, join on the ancestor; to get the path to the root, join on the descendant.

import sqlite3

db = sqlite3.connect(':memory:')
db.executescript("""
CREATE TABLE node (id INTEGER PRIMARY KEY, name TEXT);
CREATE TABLE closure (ancestor INT, descendant INT, depth INT, PRIMARY KEY (ancestor, descendant));
""")

def add(node_id, name, parent=None):
    db.execute('INSERT INTO node VALUES (?, ?)', (node_id, name))
    db.execute('INSERT INTO closure VALUES (?, ?, 0)', (node_id, node_id))
    if parent:                                   # copy every ancestor row of the parent
        db.execute('INSERT INTO closure SELECT ancestor, ?, depth + 1 FROM closure WHERE descendant = ?',
                   (node_id, parent))

add(1, 'Electronics'); add(2, 'Phones', 1); add(3, 'Android', 2); add(4, 'Laptops', 1)
rows = db.execute("""SELECT n.name FROM closure c JOIN node n ON n.id = c.descendant
                     WHERE c.ancestor = 1 AND c.depth > 0 ORDER BY n.id""").fetchall()
print([r[0] for r in rows])       # ['Phones', 'Android', 'Laptops']   the whole subtree, no recursion

Cost of a closure table. Inserting a leaf copies its parent's ancestor rows, which is cheap. Moving a subtree means deleting and recreating the closure rows between the moved nodes and their old ancestors, which is more work. The table also grows with depth times nodes. It fits trees that are read far more than they are rearranged, such as threaded comments and permission inheritance.

Inheritance in tables. A relational database has no subclasses, so a hierarchy (a payment method that is a card, a bank account or a wallet) is mapped by one of three layouts. Single-table puts every subtype in one table with a type column and many nullable columns: simple and fast, but loose constraints. Table-per-type has a base table with the shared columns and one table per subtype joined by primary key: tidy and constrainable, but reads need a join. Table-per-class repeats the shared columns in each concrete table: no joins, but a query across all types needs a union.

Versioned history. To keep history, never update in place. Insert a new row for each change, with valid_from and valid_to (or a version number), and leave the old row as it was. The current version is the row with no end date. A copy-on-write document works the same way: each edit creates a new immutable version row and moves a pointer to it, so you can show any past version and restore one by pointing back.

Optimistic locking. When two people edit the same record, add a version column. The edit carries the version it started from, and the update says WHERE id = ? AND version = ? and sets version = version + 1. If another save got there first, no row matches, and the application tells the user instead of silently overwriting. Combined with versioned history, a rejected edit can show who changed what.

Choosing. Use a closure table when you query subtrees constantly; keep an adjacency list when trees are small or rearranged often. Use table-per-type when subtypes have different columns you want to constrain. Use versioned rows when you must answer 'what did this look like last Tuesday', and say plainly which table holds the current version and which holds history.