Skip to main content

Nested Sets SQL Tree for Python

Project description


Nested Sets aka Modified Pre-order Tree Traversal (MPTT) SQL tree implemented in Python for MySQL and SQLite. Uses both traversal markup (left, right) and adjacency list parentId for more ad-hoc query flexibility.

Provides tree structure validation and “memorisation” via SQLite :memory: for quick reads.


We want to achieve the following tree. Node is represented by name id → parentId (l, r). To output a tree this way fangorn.test.visualize function can be used.

R 1 → None (1, 18)
└─A1 2 → 1 (2, 5)
  └─B1 3 → 2 (3, 4)
└─A2 4 → 1 (6, 13)
  └─B2 5 → 4 (7, 8)
  └─B3 6 → 4 (9, 12)
    └─C1 7 → 6 (10, 11)
└─A3 8 → 1 (14, 17)
  └─B4 9 → 8 (15, 16)

First we need a table to represent the tree. And we want a tree node to have a name.

import MySQLdb as mysql
conn = mysql.connect(user = 'guest', db = 'test')
  CREATE TABLE `node` (
    `node_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
    `parent_id` int(10) unsigned DEFAULT NULL,
    `l` int(10) unsigned NOT NULL,
    `r` int(10) unsigned NOT NULL,
    `name` varchar(8) NOT NULL,
    PRIMARY KEY (`node_id`),
    KEY `l` (`l`),
    KEY `r` (`r`),
    KEY `parent_id` (`parent_id`),
    CONSTRAINT `node_has_node` FOREIGN KEY (`parent_id`)
      REFERENCES `node` (`node_id`)
  ) ENGINE=InnoDB;

Now we can create tree instance. Note that DAO that the tree relies on is expected to support named DB-API paramstyle (i.e. WHERE node_id = :nodeId). Also transaction control methods are recommended to implement nested transaction support. However test suite requires nested transactions to run. For MySQLdb and sqlite3 there’re compatibility wrappers under fangorn.compat.

import fangorn
from fangorn.compat.mysqldb import Mysqldb as MysqldbWrapper
tree = fangorn.NestedSetsTree(MysqldbWrapper(conn), 'node', ('name',))

rId  = tree.add(dict(name = 'R'))
a1Id = tree.add(dict(name = 'A1'), parentId = rId)
tree.add(dict(name = 'B1'), parentId = a1Id)
a2Id = tree.add(dict(name = 'A2'), parentId = rId)
b2Id = tree.add(dict(name = 'B2'), parentId = a2Id)
b3Id = tree.add(dict(name = 'B3'), prevId = b2Id)
tree.add(dict(name = 'C1'), parentId = b3Id)
a3Id = tree.add(dict(name = 'A3'), parentId = rId)
tree.add(dict(name = 'B4'), parentId = a3Id)

tree.move(a1Id, rId)
tree.move(a3Id, prevId = a2Id)

Now we can play with the tree.

print(tree.isDescendantOf(a2Id, 4)) # False
print(tree.isDescendantOf(a2Id, 6)) # True
print(tree.isDescendantOf(a2Id, 7)) # True
print(tree.isDescendantOf(a2Id, 9)) # False

print([n['name'] for n in tree.getChildren(a2Id)])    # ['B2', 'B3']
print([n['name'] for n in tree.getDescendants(a2Id)]) # ['B2', 'B3', 'C1']
print([n['name'] for n in tree.getPath(7)])           # ['R', 'A2', 'B3', 'C1']

print(tree.getNode(8))   # {'left': 14L, 'right': 17L, 'nodeId': 8L, 'name': 'A3', 'parentId': 1L}
print(tree.getParent(8)) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}
print(tree.getRoot())    # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'R', 'parentId': None}

tree.edit(1, dict(name = 'RR'))
print(tree.getRoot()) # {'left': 1L, 'right': 18L, 'nodeId': 1L, 'name': 'RR', 'parentId': None}

print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2', 'B3', 'C1'])
print([n['name'] for n in tree.getDescendants(a2Id)] # ['B2'])

For more usage examples look at project’s test suite.

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for Fangorn, version 0.3.2
Filename, size & hash File type Python version Upload date
Fangorn-0.3.2.tar.gz (52.6 kB) View hashes Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page