An implementation of the closure table pattern in Python + SQL.
A closure table stores hierarchical data (a tree) in a relational database so that it can be queried efficiently without recursive queries.
See for instance: https://technobytz.com/closure_table_store_hierarchical_data.html
This implementation targets SQLite, through Python's standard sqlite3 module. The SQL is mostly standard, so porting it to another database should be straightforward.
Your data lives in data_table. The tree is stored in a separate table, tree. That table holds one row for every (ancestor, descendant) pair, not only for direct parent/child links:
| column | meaning |
|---|---|
parent |
id of the ancestor |
child |
id of the descendant |
depth |
distance between them (0 = the node itself, 1 = direct child, …) |
For the tree 0 → 1 → 2, tree contains (0,0,0), (1,1,0), (2,2,0), (0,1,1), (1,2,1) and (0,2,2).
Every node in the tree has a row pointing to itself at depth 0. The library uses that row to tell whether a node belongs to the tree.
With this layout, each query (subtree, ancestors, depth) is a single non-recursive SELECT. The price is that writes touch more rows: linking or unlinking a subtree updates one row per (ancestor, descendant) pair.
Python 3 only. There are no dependencies outside the standard library.
import sqlite3
from closure_table import ClosureTable
conn = sqlite3.connect('my.db')
ct = ClosureTable(conn) # creates the tables if they don't exist yet
# 1. Insert the data rows yourself: the library only manages the tree
ct.cursor.executemany(
'INSERT INTO data_table (id, updated, dummy) VALUES (?, ?, ?)',
[(n, '2024-01-01', n) for n in range(5)])
# 2. Build the tree: 0 ─ 1 ─┬─ 2
# └─ 3 ─ 4
ct.insert_root(0)
ct.insert_child(0, 1)
ct.insert_child(1, 2)
ct.insert_child(1, 3)
ct.insert_child(3, 4)
conn.commit()
# 3. Query it (select_* methods return full data_table rows)
[row[0] for row in ct.select_children(1)] # [2, 3]
[row[0] for row in ct.select_descendants(1)] # [2, 3, 4]
[row[0] for row in ct.select_ancestors(4)] # [0, 1, 3]
ct.select_parent(4)[0] # 3
ct.ancestors_depth(4) # 3
ct.descendants_depth(1) # 2
# 4. Move the subtree rooted at 3 under 2
ct.unlink_child(3)
ct.link_child(2, 3)
conn.commit()
[row[0] for row in ct.select_ancestors(4)] # [0, 1, 2, 3]ClosureTable(conn) takes an open sqlite3.Connection. It enables foreign keys (PRAGMA foreign_keys = ON) and creates data_table, tree and their indexes if they don't exist. Existing data is kept.
The connection and a shared cursor are available as ct.connexion and ct.cursor.
| method | returns |
|---|---|
select_parent(n) |
the parent's data_table row, or None for a root |
select_children(n) |
the direct children's rows, ordered by id |
select_ancestors(n) |
all the ancestors' rows, from the root down to the direct parent |
select_descendants(n) |
the rows of the whole subtree under n (without n itself), ordered by depth then by id |
ancestors_depth(n) |
distance between n and its root (0 for a root) |
descendants_depth(n) |
height of the subtree under n (0 for a leaf) |
For a node that is not in the tree, the depth functions return None. The select_* functions return None or [].
| method | effect |
|---|---|
insert_root(n) |
adds n to the tree as a root |
insert_child(parent, child) |
adds child, which must not be in the tree yet, as a direct child of parent |
link_child(parent, child) |
attaches child and its whole subtree under parent. child must already be in the tree and must have no parent. |
unlink_child(n) |
detaches n from its parent. n keeps its subtree and becomes a root. |
unlink_parent(n) |
detaches every direct child of n. Each child keeps its subtree and becomes a root. |
delete_descendants(n) |
removes the whole subtree under n from the tree. n itself stays. |
To move a subtree, call unlink_child(n) and then link_child(new_parent, n).
Invalid operations raise ValueError before anything is written. These include:
- a node that is missing from
data_table; - a parent that is not in the tree;
- a child that already has a parent;
- a link that would create a cycle;
- a node linked to itself.
- The library never commits. Every change happens in the connection's current transaction. Call
conn.commit()when you are done, orconn.rollback()if something failed. This also lets you group several operations into one transaction. - Only the
treetable is managed. You insert, update and delete the rows ofdata_tableyourself.delete_descendantsremoves nodes from the tree but leaves their rows indata_table. Since foreign keys are enforced, remove a node from the tree before deleting itsdata_tablerow. - Several roots are allowed. The structure is really a forest:
insert_rootcan be called more than once, and unlinked nodes become roots of their own trees. data_tableis an example schema (id,updated,version,dummy). Adapt it inbuild_schemato your own data. The library only relies on theidcolumn.
python -m unittest closure_table_test # or: pytestThe tests use a SQLite file named closure.db in the current directory.
Published under the MIT license.