Nested Set Trees in ColdFusion
A new version of this entry is available.
A common technique to manage hierarchical data in a relational database is to use an "Adjacency List" model, where you have both an ID column and a Parent ID column in a table. This is easy to understand and maintain but can be difficult or inefficient when you want to retrieve hierarchies of records.
The "Nested Set" model provides an alternative technique for managing this kind of data and is more efficient at reading a hierarchy but requires a little more work for inserts, updates, deletes and moves.
See the references below for some good links that describe the Nested Set model in more detail (or just try a search in Google).
This entry provides a library of ColdFusion code that you may like to use to help manage your hierarchical data using the nested set model.
About the Code
This code is based on a PHP/mysql implementation by Rolf Brugger (thanks Rolf!), so have a quick read through that page before getting started.
This code is also based around creating an additional "partner" table that is used with an existing data table.
The library should work in ColdFusion 6.1 and above and any common database but I have only tested in MS SQL Server.
Download the Code
You can download this code from RIAForge
This download file contains:
NestedSetTree.cfc - the function library
nstree - directory containing a sample application
Getting Started
To get started, you will need to have a primary data table and a partner Nested Set Tree (NST) table. For this entry we will create a hierarchical set of categories.
The primary data table has the following structure:
Table: category
| Column Name | Column Type | Description |
| categoryId | int, PK | Unique primary key |
| parentCategoryId | int | Reference to parent category record |
| categoryName | varchar(50) | Category name |
Note that the parentCategoryId column is not required to use the NST library, but can be useful to maintain.
For each record in the primary category table you will need to maintain a partner record in a NST table. For convention the partner table will the same name as the primary table but with an "NST" suffix.
Table: categoryNST
| Column Name | Column Type | Description |
| categoryId | int, PK | Unique primary key |
| lft | int | Left index |
| rgt | int | Right index |
Creating the NST library object
The library requires the following parameters when created:
| Parameter | Description |
| datasourceName | The datasource name |
| datasourceUsername | The datasource user name |
| datasourcePassword | The datasource password |
| table | The name of the NST table |
| id | The name of the NST table Id column |
| left | The name of the NST table left column |
| right | The name of the NST table right column |
Example of creating the library object:
"nstree",
"nstreeuser",
"nstreepass"
"categoryNST",
"categoryId",
"lft",
"rgt"
)>
These examples will use a simple private function for easy access to the library:
<cfreturn variables._nst>
</cffunction>
Creating the root node of a new tree
Nested set trees need to have a top level root node which is the parent of all other nodes. When you have no current records in your data table, then you can use the following code to create your first record.
If you are converting an existing data table to use the NST model, then see "Creating a NST for existing data" below.
To create a new root node in the NST, use the newRoot() function
| Function | Description |
| newRoot(id) | Creates a new root node. |
Example code:
<!--- Create the category record. --->
<cfquery result="q" ... >
insert into category
(
parentCategoryId,
categoryName
)
values
(
<cfqueryparam cfsqltype="cf_sql_integer" value="#parentCategoryId#">,
<cfqueryparam cfsqltype="cf_sql_varchar" value="#categoryName#">
)
</cfquery>
<cfset categoryId = q.IDENTITYCOL>
<!--- Update the NST. --->
nst().newRoot(categoryId)>
</cftransaction>
Retrieving nodes from the tree
You can retrieve nodes using the following functions.
| Function | Description |
| root() | Returns the root node. |
| getNode(id) | Returns a node with the specified id |
| firstChild(node) | Returns the first child of the specified node. |
| lastChild(node) | Returns the last child of the specified node. |
| prevSibling(node) | Returns the previous sibling of the specified node. |
| nextSibling(node) | Returns the next sibling of the specified node. |
| ancestor(node) | Returns the parent of the specified node. |
These functions always return a node. When you have the result node, you should test if the node is valid.
Testing for a valid node
Use isValidNode() to test if a node is valid. An invalid node is essentially equivalent to receiving a null or undefined value.
| Function | Description |
| isValidNode(node) | Returns true if the node is valid. |
Querying for nodes in the tree
The following functions return a true or false value:
| Function | Description |
| hasAncestor(node) | Returns true if the node has a parent. |
| hasPrevSibling(node) | Returns true if the node has a previous sibling |
| hasNextSibling(node) | Returns true if the node has a next sibling. |
| hasChildren(node) | Returns true if the node has children. |
| isRoot(node) | Returns true if the node is a root node. |
| isLeaf(node) | Returns true if the node is a leaf node. |
| isChild(node1,node2) | Returns true, if 'node1' is a direct child or in the subtree of 'node2' |
| isChildOrEqual(node1,node2) | Returns true, if 'node1' is a direct child or in the subtree of 'node2' or is the same node as 'node2' |
| isEqual(node1,node2) | Returns true if 'node1' and 'node2' are the same node. |
Adding new nodes
The following functions are provided to add nodes to a tree.
| Function | Description |
| newFirstChild(node,id) | Creates a new node before all other children. |
| newLastChild(node,id) | Creates a new node after all other children. |
| newPrevSibling(node,id) | Creates a new node before the current node. |
| newNextSibling(node,id) | Creates a new node after the current node. |
Example code to add new children
<!--- Create the category record. --->
<cfquery result="q" ... >
insert into category
(
parentCategoryId,
categoryName
)
values
(
<cfqueryparam cfsqltype="cf_sql_integer" value="#parentCategoryId#">,
<cfqueryparam cfsqltype="cf_sql_varchar" value="#categoryName#">
)
</cfquery>
<cfset categoryId = q.IDENTITYCOL>
<!--- Update the NST. --->
<cfset parentNode = nst().getNode(parentCategoryId)>
<cfset nst().newLastChild(parentNode, categoryId)>
</cftransaction>
Deleting nodes
The NST library provides two delete functions
| Function | Description |
| delete(node) | Deletes the specified node. |
| deleteTree() | Deletes all nodes in the tree. |
Example code to delete a node:
<!--- First delete the category. --->
<cfquery ... >
delete category
where categoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#categoryId#">
</cfquery>
<!--- Then delete the NST record. --->
<cfset node = nst().getNode(categoryId)>
<cfset nst().delete(node)>
</cftransaction>
Moving nodes
The following functions are available to move nodes within your tree:
| Function | Description |
| moveToNextSibling(src,dst) | Moves the node 'src' and all its children (subtree) so that it is the next sibling of 'dst'. |
| moveToPrevSibling(src,dst) | Moves the node 'src' and all its children (subtree) so that it is the prev sibling of 'dst'. |
| moveToFirstChild(src,dst) | Moves the node 'src' and all its children (subtree) so that it is the first child of 'dst'. |
| moveToLastChild(src,dst) | Moves the node 'src' and all its children (subtree) so that it is the last child of 'dst'. |
Note that in these examples, the order of the nodes is managed by the NST rather than the primary data table (via a 'sort' column).
Moving a node 'up'
Example code to move a node up/left within the same parent.
<cfset var prevNode = nst().prevSibling(node)>
<cfif nst().isValidNode(prevNode)>
<cfset nst().moveToPrevSibling(node,prevNode)>
</cfif>
Moving a node 'down'
Example code to move a node down/right within the same parent.
<cfset var nextNode = nst().nextSibling(node)>
<cfif nst().isValidNode(nextNode)>
<cfset nst().moveToNextSibling(node,nextNode)>
</cfif>
Moving a node to another branch in the tree
Note that nodes may only be moved to either parent or sibling nodes, so we need to ensure the move is permitted.
<cfset var src = nst().getNode(srcId)>
<cfset var dst = nst().getNode(dstId)>
<!--- If the destination node is a child of the source node, then the move is not permitted. --->
<cfif nst().isChildOrEqual(dst,src)>
<cfreturn>
</cfif>
<!--- Change the node's parent in the primary table. --->
<cfquery ...>
update category
set parentCategoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#dstId#">
where categoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#srcId#">
</cfquery>
<!--- Move the node in the NST. --->
<cfset nst().moveToLastChild(src,dst)>
Querying the data
The library provides some functions to query the NST table:
| Function | Description |
| numChildren(node) | Returns a recursive count of all children in the subtree of the node. |
| level(node) | Returns the node depth level, with the root level starting at 0. |
| getSubtree(node) | Returns the complete subtree of the specified node. |
| walkPreorder() | Returns the complete tree hierarchy. |
However, these functions are typically not very useful on their own as they do not provide data from the primary table.
A better technique is to understand how the NST model works and take advantage of this fact in your queries.
Getting the complete tree hierarchy
The 'left' column in the NST provides all we need to get a complete hierarchy of the tree.
select
d.*,
nst.lft,
nst.rgt
from
category d
inner join categoryNST nst on d.categoryId = nst.categoryId
order by
nst.lft
</cfquery>
It is often useful to get the depth level of the nodes at the same time.
Getting the level of a node
First let's look at getting the depth of a single node.
<cfset node = nst().getNode(categoryId)>
<!--- Get the level --->
<cfquery name="q" ...>
select count(*) as level
from categoryNST
where
lft < #node.l#
and rgt > #node.r#
</cfquery>
<cfreturn q.level>
Getting the complete tree hierarchy with depth levels
Now we can combine the complete tree hierarchy and level queries together. The level query is included as a subquery.
select
d.*,
(
select count(*)
from categoryNST d2
where
d2.lft < nst.lft
and d2.rgt > nst.rgt
) as level,
nst.lft,
nst.rgt
from
category d
inner join categoryNST nst on d.categoryId = nst.categoryId
order by
nst.lft
</cfquery>
Getting a subtree with depth levels
<cfquery name="q" ...>
select
d.*,
(
select count(*)
from categoryNST d2
where
d2.lft < nst.lft
and d2.rgt > nst.rgt
) as level,
nst.lft,
nst.rgt
from
category d
inner join categoryNST nst on d.categoryId = nst.id
where
nst.lft >= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.l#">
and nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.r#">
order by
nst.lft
</cfquery>
Getting a breadcrumb record set
Use the following to get a query of the breadcrumb links for a node.
select
c.*,
nstB.lft,
nstB.rgt
from
categoryNST nstA
cross join categoryNST nstB
inner join category c on nstB.categoryId = c.categoryId
where
nstA.lft between nstB.lft and nstB.rgt
and nstA.categoryId = <cfqueryparam cfsqltype="cf_sql_integer" value="#categoryId#">
order by
nstB.lft
</cfquery>
Creating a NST for existing data
If you have existing data that you want to convert to use the NST model, then the library provides a rebuildIndex() function to help you with this conversion:
This function has four parameters:
| Parameter | Description |
| primaryTable | The name of your primary table |
| primaryTableId | The name of your primary table's primary key column (integer only) |
| primaryTableParentId | The name of your primary table's parent id column (integer only) |
| rootId | The id of the root record in your primary table. This is the start record for the conversion. |
When run, all records in the NST table will be deleted and recreated.
Example usage:
<cfset nst().rebuildIndex("category","categoryId","parentCategoryId",rootNodeId)>
References
Nested Set Trees, a PHP/mysql implementation
http://www.edutech.ch/contribution/nstrees/index.php
Managing Hierarchical Data in MySQL
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
Storing Hierarchical Data in a Database
http://www.sitepoint.com/article/hierarchical-data-database
Using the Nested Set Data Model for Breadcrumb Links
http://www.developer.com/db/article.php/3517366
A Look at SQL Trees (Joe Celko)
http://www.dbmsmag.com/9603d06.html
Request 1: updateLeft
Request 2: updateLeft
Request 1: updateRight
Request 2: updateRight
Rather then the required:
Request 1: updateLeft
Request 1: updateRight
Request 2: updateLeft
Request 2: updateRight
Your tree data will become corrupted. I was caught out by this with my initial implementation of this sort of thing, in high-traffic situations.
You might want to put some locking or transactionality around your queries.
--
Adam
Have you tried integrating this with Transfer ORM? I'd love to hear your thoughts on this.
Aaron
Putting something together about integration with Transfer is a great idea. I will put up some thoughts about it shortly. Thanks for the suggestion.
That's great! I will certainly look forward to it.