|
In the article Managing Hierarchical Data in MySQL, by Mike Hillyer, I read about using nested sets as an efficient way to model hierarchical data in a relational database. I wanted to try and do this using Django models.
Models
from django.utils.datastructures import SortedDict
from django.db import models, connection
class NestedCategory(models.Model):
"""This was a really good use-case
"""
name = models.CharField(max_length=20)
lft = models.IntegerField()
rgt = models.IntegerField()
def get_depth(self):
"""Return the depth of this node relative to the top-level node, which
has a depth of 0.
"""
return NestedCategory.objects.filter(
lft__lt=self.lft,
rgt__gt=self.rgt
).count()
def get_tree(self, depth=False):
"""Return a QuerySet containing this node followed by all the nodes
under it in the hierarchy.
depth -- If True, add a "depth" member to each item in the QuerySet.
This node (self) will have a depth of 0
"""
qs = NestedCategory.objects.filter(
lft__range=(self.lft, self.rgt)
).order_by('lft')
if depth:
qn = connection.ops.quote_name
subquery="""
SELECT COUNT(*)
FROM %(self_table)s parent
WHERE parent.%(lft)s between %%s AND %(self_table)s.%(lft)s AND
parent.%(rgt)s > %(self_table)s.%(rgt)s
""" % {
'self_table': qn(NestedCategory._meta.db_table),
'lft': qn('lft'),
'rgt': qn('rgt')
}
qs = qs.extra(
select = SortedDict({'depth': subquery}),
select_params = [self.lft]
)
return qs
def get_leafs(self):
"""Return a QuerySet containing all leaf nodes under this one.
"""
return NestedCategory.objects.filter(
lft__range=(self.lft, self.rgt)
).extra(
where=['rgt=lft+1']
)
def get_path(self):
"""Return a QuerySet showing the path from the root of the
hierarchy all the way to this node.
"""
return NestedCategory.objects.filter(
lft__lte=self.lft,
rgt__gte=self.rgt
)
def get_immediate_children(self):
"""Return a QuerySet containing all of the immediate
children of this node, if any.
"""
qn = connection.ops.quote_name
extra_where="""
(
SELECT COUNT(*)
FROM
%(self_table)s parent
WHERE
parent.%(lft)s BETWEEN %%s and %(self_table)s.%(lft)s AND
parent.%(rgt)s > %(self_table)s.%(rgt)s
) = 1
""" % {
'self_table': qn(NestedCategory._meta.db_table),
'lft': qn('lft'),
'rgt': qn('rgt')
}
qs = NestedCategory.objects.filter(
lft__range=(self.lft, self.rgt)
).order_by('lft').extra(
where=[extra_where],
params=[self.lft]
)
return qs
def get_parent(self):
"""Return the parent node of this one or None if this node the root.
"""
qs = NestedCategory.objects.filter(
lft__lt=self.lft, rgt__gt=self.rgt
).order_by("-lft")
if qs.count() > 0:
return qs[0]
return None
Test Data
My test was in an app called hb7, so the SQL to populate the test data has hb7_nestedcategory as a table name.
insert into hb7_nestedcategory (id,name,lft,rgt) values (1,'ELECTRONICS',1,20);
insert into hb7_nestedcategory (id,name,lft,rgt) values (2,'TELEVISIONS',2,9);
insert into hb7_nestedcategory (id,name,lft,rgt) values (3,'TUBE',3,4);
insert into hb7_nestedcategory (id,name,lft,rgt) values (4,'LCD',5,6);
insert into hb7_nestedcategory (id,name,lft,rgt) values (5,'PLASMA',7,8);
insert into hb7_nestedcategory (id,name,lft,rgt) values (6,'PORTABLE ELECTRONICS',10,19);
insert into hb7_nestedcategory (id,name,lft,rgt) values (7,'MP3 PLAYERS',11,14);
insert into hb7_nestedcategory (id,name,lft,rgt) values (8,'FLASH',12,13);
insert into hb7_nestedcategory (id,name,lft,rgt) values (9,'CD PLAYERS',15,16);
insert into hb7_nestedcategory (id,name,lft,rgt) values (10,'2 WAY RADIOS',17,18);
Small Sample Test Program
#!/usr/bin/env python
"""Experiments with nested sets. Assumes we have access to the NestedCategory model and
that it has been populated with data that matches the hierarchy from the article
Managing Hierarchical Data in MySQL at this URL:
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
"""
import os
import sys
script_dir = os.path.dirname(os.path.abspath(__file__))
app_dir = os.path.dirname(script_dir)
project_dir = os.path.dirname(app_dir)
sys.path.append(project_dir)
os.environ['DJANGO_SETTINGS_MODULE'] = 'settings'
from hb7.models import *
for r in NestedCategory.objects.all().order_by('lft'):
print "*" * 80
print "Starting Point: %s (id=%d, depth=%d)" % (r.name, r.id, r.get_depth())
print "*" * 80
print "\nTree:"
print "%8s %-30s%8s" % ('id', 'name', 'depth')
for x in r.get_tree(depth=True):
print "%8s %-30s%8s" % (x.id, " " * x.depth + x.name, x.depth)
print "\nLeafs:"
print "%8s %-30s" % ('id', 'name')
for x in r.get_leafs():
print "%8s %-30s" % (x.id, x.name)
print "\nPath:"
print "%8s %-30s" % ('id', 'name')
for x in r.get_path():
print "%8s %-30s" % (x.id, x.name)
print "\nImmediate Children:"
print "%8s %-30s" % ('id', 'name')
for x in r.get_immediate_children():
print "%8s %-30s" % (x.id, x.name)
print "\nParent Node:"
print "%8s %-30s" % ('id', 'name')
x = r.get_parent()
if x:
print "%8s %-30s" % (x.id, x.name)
else:
print "None"
Output from Test Program
********************************************************************************
Starting Point: ELECTRONICS (id=1, depth=0)
********************************************************************************
Tree:
id name depth
1 ELECTRONICS 0
2 TELEVISIONS 1
3 TUBE 2
4 LCD 2
5 PLASMA 2
6 PORTABLE ELECTRONICS 1
7 MP3 PLAYERS 2
8 FLASH 3
9 CD PLAYERS 2
10 2 WAY RADIOS 2
Leafs:
id name
3 TUBE
4 LCD
5 PLASMA
8 FLASH
9 CD PLAYERS
10 2 WAY RADIOS
Path:
id name
1 ELECTRONICS
Immediate Children:
id name
2 TELEVISIONS
6 PORTABLE ELECTRONICS
Parent Node:
id name
None
********************************************************************************
Starting Point: TELEVISIONS (id=2, depth=1)
********************************************************************************
Tree:
id name depth
2 TELEVISIONS 0
3 TUBE 1
4 LCD 1
5 PLASMA 1
Leafs:
id name
3 TUBE
4 LCD
5 PLASMA
Path:
id name
1 ELECTRONICS
2 TELEVISIONS
Immediate Children:
id name
3 TUBE
4 LCD
5 PLASMA
Parent Node:
id name
1 ELECTRONICS
********************************************************************************
Starting Point: TUBE (id=3, depth=2)
********************************************************************************
Tree:
id name depth
3 TUBE 0
Leafs:
id name
3 TUBE
Path:
id name
1 ELECTRONICS
2 TELEVISIONS
3 TUBE
Immediate Children:
id name
Parent Node:
id name
2 TELEVISIONS
********************************************************************************
Starting Point: LCD (id=4, depth=2)
********************************************************************************
Tree:
id name depth
4 LCD 0
Leafs:
id name
4 LCD
Path:
id name
1 ELECTRONICS
2 TELEVISIONS
4 LCD
Immediate Children:
id name
Parent Node:
id name
2 TELEVISIONS
********************************************************************************
Starting Point: PLASMA (id=5, depth=2)
********************************************************************************
Tree:
id name depth
5 PLASMA 0
Leafs:
id name
5 PLASMA
Path:
id name
1 ELECTRONICS
2 TELEVISIONS
5 PLASMA
Immediate Children:
id name
Parent Node:
id name
2 TELEVISIONS
********************************************************************************
Starting Point: PORTABLE ELECTRONICS (id=6, depth=1)
********************************************************************************
Tree:
id name depth
6 PORTABLE ELECTRONICS 0
7 MP3 PLAYERS 1
8 FLASH 2
9 CD PLAYERS 1
10 2 WAY RADIOS 1
Leafs:
id name
8 FLASH
9 CD PLAYERS
10 2 WAY RADIOS
Path:
id name
1 ELECTRONICS
6 PORTABLE ELECTRONICS
Immediate Children:
id name
7 MP3 PLAYERS
9 CD PLAYERS
10 2 WAY RADIOS
Parent Node:
id name
1 ELECTRONICS
********************************************************************************
Starting Point: MP3 PLAYERS (id=7, depth=2)
********************************************************************************
Tree:
id name depth
7 MP3 PLAYERS 0
8 FLASH 1
Leafs:
id name
8 FLASH
Path:
id name
1 ELECTRONICS
6 PORTABLE ELECTRONICS
7 MP3 PLAYERS
Immediate Children:
id name
8 FLASH
Parent Node:
id name
6 PORTABLE ELECTRONICS
********************************************************************************
Starting Point: FLASH (id=8, depth=3)
********************************************************************************
Tree:
id name depth
8 FLASH 0
Leafs:
id name
8 FLASH
Path:
id name
1 ELECTRONICS
6 PORTABLE ELECTRONICS
7 MP3 PLAYERS
8 FLASH
Immediate Children:
id name
Parent Node:
id name
7 MP3 PLAYERS
********************************************************************************
Starting Point: CD PLAYERS (id=9, depth=2)
********************************************************************************
Tree:
id name depth
9 CD PLAYERS 0
Leafs:
id name
9 CD PLAYERS
Path:
id name
1 ELECTRONICS
6 PORTABLE ELECTRONICS
9 CD PLAYERS
Immediate Children:
id name
Parent Node:
id name
6 PORTABLE ELECTRONICS
********************************************************************************
Starting Point: 2 WAY RADIOS (id=10, depth=2)
********************************************************************************
Tree:
id name depth
10 2 WAY RADIOS 0
Leafs:
id name
10 2 WAY RADIOS
Path:
id name
1 ELECTRONICS
6 PORTABLE ELECTRONICS
10 2 WAY RADIOS
Immediate Children:
id name
Parent Node:
id name
6 PORTABLE ELECTRONICS
|
Computers 
