Skip to content

About

An implementation of the closure table pattern in Python + SQL

Topics

Resources

Stars

16 stars

Watchers

1 watching

Forks

Latest commit

 

History

16 Commits

Folders and files

Repository files navigation

Closure-Table

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.

How it works

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.

Requirements

Python 3 only. There are no dependencies outside the standard library.

Usage

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]

API

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.

Queries

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 [].

Modifications

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.

Things to know

  • The library never commits. Every change happens in the connection's current transaction. Call conn.commit() when you are done, or conn.rollback() if something failed. This also lets you group several operations into one transaction.
  • Only the tree table is managed. You insert, update and delete the rows of data_table yourself. delete_descendants removes nodes from the tree but leaves their rows in data_table. Since foreign keys are enforced, remove a node from the tree before deleting its data_table row.
  • Several roots are allowed. The structure is really a forest: insert_root can be called more than once, and unlinked nodes become roots of their own trees.
  • data_table is an example schema (id, updated, version, dummy). Adapt it in build_schema to your own data. The library only relies on the id column.

Running the tests

python -m unittest closure_table_test   # or: pytest

The tests use a SQLite file named closure.db in the current directory.

License

Published under the MIT license.

About

An implementation of the closure table pattern in Python + SQL

Topics

Resources

Stars

16 stars

Watchers

1 watching

Forks

Releases

Packages

Used by

Contributors

Languages