Nested Set Trees in ColdFusion (v0.2)

A new version of this project 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

http://nstree.riaforge.org/

This download file contains:

  • /nstree – Directory containing a sample application
  • /nstree/com/nstree/NestedSetTree.cfc – The base NST function library
  • /nstree/com/nstree/ThreadSafeNestedSetTree.cfc – A thread safe version of the base function library

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

About Locking and Exceptions

All of the operations in the library need locking applied to prevent corruption of the partner table data. The ThreadSafeNestedSetTree.cfc component provides the locking required to ensure the partner table does not become corrupted in a multithreaded/multiuser environment. The NestedSetTree.cfc has no locking applied.

You will need to consider locking issues in your own code that manages the primary data table.
The examples that follow will show how you might implement this.

The ThreadSafeNestedSetTree.cfc performs additional queries to ensure that operations are valid
(such as checking a parent node exists before attempting to append children to it).
Exceptions will be thrown if these preconditions are not met.

(Thanks Adam Cameron for raising this issue!)

Implementing Locking

The ThreadSafeNestedSetTree.cfc contains four lock related functions:

setLockName(name)

getLockName()

setLockTimeout(seconds)

getLockTimeout()

You can use these functions to set or retrieve the lock name and timeout being used by the library.

Generally, functions that read data use a READONLY lock. Functions that change data use an EXCLUSIVE lock.

In your code, you can use locking as follows.

<cflock
	name="#variables.nst.getLockName()#"
	timeout="#variables.nst.getLockTimeout()#"
	type="exclusive">
	<!--- Your code plus calls to the library here --->
</cflock>

The default lock name is "NESTEDSETTREE-NSTTableName".

About Transactions

No transactions are implemented within the library. You should implement transactions in the code that uses the library.

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:

<cfset variables._nst = createObject("component","ThreadSafeNestedSetTree").init(
					"nstree",
					"nstreeuser",
					"nstreepass"
					"categoryNST",
					"categoryId",
					"lft",
					"rgt"
				)>

These examples will use a simple private function for easy access to the library:

<cffunction name="nst" output="false" access="private">
	<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:

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
 
<!--- 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>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>

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

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
 
<!--- 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 nst().newLastChild(parentCategoryId, categoryId)>
 
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>

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:

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
 
<!--- Get the node to delete --->
<cfset node = nst().getNode(categoryId)>
 
<!--- Delete the category and all children. --->
<cfquery ... >
	delete cat
	from
		category cat
		inner join categoryNST nst on cat.categoryId = nst.categoryId
	where
		nst.lft >= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.l#">
		and
		nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.r#">
</cfquery>
 
<!--- Then delete the NST record. --->
<cfset nst().delete(categoryId)>
 
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>

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 = 0>
<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
	<cfset prevNode = nst().prevSibling(categoryId)>
	<cfset nst().moveToPrevSibling(categoryId,prevNode.id)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>

Moving a node ‘down’

Example code to move a node down/right within the same parent.

<cfset var nextNode = 0>
<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
	<cfset nextNode = nst().nextSibling(categoryId)>
	<cfset nst().moveToNextSibling(categoryId,nextNode.id)>
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>

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.

 
<!--- If the destination node is a child of the source node, then the move is not permitted. --->
<cfset var moveAllowed = false>
<cftry>
<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
	<cfset moveAllowed = not nst().isChildOrEqual(dstId,srcId)>
</cflock>
<cfcatch>
<!--- Handle errors (such as the src or dst nodes not existing --->
</cfcatch>
</cftry>
 
<cfif not moveAllowed>
	<cfreturn>
</cfif>
 
<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="exclusive">
<cftry>
<cftransaction>
 
<!--- 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(srcId,dstId)>
 
</cftransaction>
<cfcatch>
<!--- Handle error here --->
</cfcatch>
</cftry>
</cflock>

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.

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfquery name="q" ...>
	select
		d.*,
		nst.lft,
		nst.rgt
	from
		category d
		inner join categoryNST nst on d.categoryId = nst.categoryId
	order by
		nst.lft
</cfquery>
</cflock>

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.

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
 
<!--- Get the 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>
 
</cflock>
 
<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.

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<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.categoryId
	order by
		nst.lft
</cfquery>
</cflock>

Getting a subtree with depth levels

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfset node = nst().getNode(categoryId)>
<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>
</cflock>

Getting a breadcrumb record set

Use the following to get a query of the breadcrumb links for a node.

<cflock	name="#nst().getLockName()#" timeout="#nst().getLockTimeout()#" type="readonly">
<cfquery name="q" ...>
	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>
</cflock>

Rendering nested set output as an unordered list

You can display a nested set query’s output as nested unordered lists using the following code.

First you would need to execute a query that returned either the entire tree or a subtree plus corresponding depth levels (as described above).

In this example, the “treeQuery” query contains a “level” column and a “categoryName” column.

<cfset prevLevel = -1>
<cfset currLevel = -1>
<cfloop query="treeQuery">
	<cfset currLevel = level>
	<cfif currLevel gt prevLevel>
		<ul><li>#categoryName#
	<cfelseif currLevel lt prevLevel>
		<cfset tmp = prevLevel>
		<cfloop condition="tmp gt currLevel">
			</li></ul>
			<cfset tmp = tmp - 1>
		</cfloop>
		</li><li>#categoryName#
	<cfelse>
		</li><li>#categoryName#
	</cfif>
	<cfset prevLevel = level>
</cfloop>
<cfset tmp = currLevel>
<cfloop condition="tmp ge 0">
	</li></ul>
	<cfset tmp = tmp - 1>
</cfloop>

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 rootNodeId = 1>
<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

This entry was posted in Nested Set Trees and tagged . Bookmark the permalink. Both comments and trackbacks are currently closed.

48 Comments

  1. Posted June 16, 2008 at 7:29 am | Permalink

    very nice blog…..

  2. Posted June 19, 2008 at 3:50 am | Permalink

    Any particular reason for using two tables instead of one…

    category & categorynst?

  3. Posted June 19, 2008 at 4:33 am | Permalink

    Having two tables allows more flexibility in how the nested set fields are used and also allows the library to be more generic.

    For example, inserting records would become more complicated and less generic with one table. If you wanted to have "soft" deletes in your application, then the primary table could flag records as deleted, but the partner NST table could have actual deletes.

    To get the best performance, a single table (with stored procedures for the NST insert/update operations) would perhaps be the best way to go, but separating out the NST table provides a bit more flexibility.

  4. Posted June 19, 2008 at 7:30 pm | Permalink

    Thanks Kevan.

    Been working it with OpenBD/MySQL. Had to do a few mods but it seems to be working so far with the exception of the following:

    - Initial Create Node Fails to update the NST table, so I had to manually enter the 1st rgt / lft data. It worked fine after that (to create nodes in the proper hierarchy.)

    - IDENTITYCOL (MS SQLServer) / GENERATED_KEY (MySQL) is not passed from OpenBD (for inserts) so I had to add the following to the createCategory Method within the cftransaction tags:

    <cfquery name="q" datasource="#getDatasource().getName()#" username="#getDatasource().getUsername()#" password="#getDatasource().getPassword()#">
    select max(categoryId) as IDENTITYCOL
    from category
    </cfquery>

    Note: You could probably also do a switch/case to identify the database to dynamically determine they return variable as in: IDENTITYCOL (MS SQLServer) / GENERATED_KEY (MySQL) / Etc.

    -The "Move To" dropdowns did not execute any action (could be work in progress…)

    - Here are the tables for MySQL:
    ———————————————————————-
    CREATE TABLE `spifo`.`category` (
    `categoryid` int(11) NOT NULL AUTO_INCREMENT,
    `categoryName` varchar(50) DEFAULT NULL,
    `parentCategoryId` int(10) unsigned DEFAULT NULL,
    PRIMARY KEY (`categoryid`)
    ) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=utf8 ROW_FORMAT=COMPACT;

    CREATE TABLE `spifo`.`categorynst` (
    `categoryid` int(11) DEFAULT NULL,
    `lft` int(11) DEFAULT NULL,
    `rgt` int(11) DEFAULT NULL
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8 ROW_FORMAT=COMPACT;
    ———————————————————————-

  5. Posted June 19, 2008 at 7:36 pm | Permalink

    Please make the correction for the above statement…

    Remove the `spifo` from both create statements:

    CREATE TABLE `spifo`.`categorynst`

    Thanks.

  6. Posted June 19, 2008 at 10:29 pm | Permalink

    I will update the sample code to support MySQL.

    Was it the creation of the root node that failed? I will see if I can set up the same environment and test.

    The "Move To" code is dependent on jQuery adding an onchange event to each of the drop downs. Perhaps this did not work?

    Thanks for the excellent feedback.

  7. Posted June 19, 2008 at 11:33 pm | Permalink

    Q. Was it the creation of the root node that failed?
    A. Yes

    Q. The "Move To" code is dependent on jQuery adding an onchange event to each of the drop downs. Perhaps this did not work?
    A. Got it to work! – I just had to modify it based on where I had it in the directory structure.

    "Delete" is the only thing not working for me now…

    Initially trying to troubleshoot why some things were not working, it became more of a challenge because of the try/catch statements. The catch statement was empty shielding the cf error from displaying to the browser – the click would just do nothing but return to the originating page. It would be nice to have a variable: isDebugMode = True|False; during the pre 1.0 version (maybe even in post 1.0 versions.)

  8. Posted June 20, 2008 at 2:13 pm | Permalink

    Just uploaded a new version of the library (v0.2.1). Changes in this update:

    * Fix creation of root node in demo app

    Old code had a line:
    nst().newRoot(cat.categoryId)>

    New code changed this to:
    <cfset nst().newRoot(cat.categoryId)>

    Interesting that I did not get a CF error for this.

    * Remove cftry/cfcatch from demo app.

    These are not required for a single user demo. I may put them back in again later, but they should only catch the specific errors being thrown by the demo app rather than every error.

    * Added mysql script to create demo tables.

  9. Posted June 21, 2008 at 4:01 am | Permalink

    My attempt at creating the 1st node went well – your change fixed the issue.

    Noticed a small issue from my original code (just for consistency:)
    CHANGE:
    `parentCategoryId` int(10) unsigned DEFAULT NULL,
    TO:
    `parentCategoryId` int(11) DEFAULT NULL,
    in the MySQL Script. All the other INTs are 11 as well.

    Great Job!

  10. Posted June 21, 2008 at 8:00 pm | Permalink

    Have you got nstree working with extJs Ext.Tree?

    Thanks

  11. Posted June 22, 2008 at 3:29 am | Permalink

    in the deleteCategory method

    Change:
    delete category…
    To:
    delete from category…

  12. Posted June 22, 2008 at 2:05 pm | Permalink

    Automaxion, MySQL script and deleteCategory() method updated (v0.2.2). Thanks for your work!

    Hi Mark, I have not tried the library with ExtJS yet, but from what I can see it should work fine.

  13. Posted June 24, 2008 at 1:25 pm | Permalink

    Released version 0.2.3. Just a small change in this release:

    The default lock name is changed from being a UUID to be based on the NST table name instead. The lock name is now the NST table name prefixed with "NESTEDSETTREE-".

    This will provide safer usage if the library is not loaded in the application scope and no specific lock name is set.

  14. Dan Sorensen
    Posted June 25, 2008 at 10:41 am | Permalink

    To make it simpler to initialize, I wonder if some of the init columns could be made optional with good defaults.

    Current:
    .init("datasource","username","password","table","id","left","right")

    .init("datasource","table","id")

    Username and password are redundant if they are saved in the datasource setup, but obviously necessary if they are not.

    Left and right could default to "lft" and "rgt" as stated in all of the documentation, and be overriden if needed. (I guess ID could have a default as well.)

    Overall, it’s been eally great to work with this CFC! Nested set trees are useful, but challenging to work with. This makes it really easy! :-)

  15. Posted June 26, 2008 at 3:51 am | Permalink

    Hi Dan, thanks for your feedback. Having default parameters would be a nice idea, but I am not too keen on changing the parameter order as it would be a bit less tidy when all parameters were required:

    .init("datasource","table","id","username","password","lft","rgt")

    An alternative would be to require named parameters, then the order is unimportant:

    .init(datasourceName="datasource",table="table",id="id")

    But this seems to defeat the purpose of having a more succinct initialisation.

    So I’m still considering how the initialisation is done, but it is good to have another perspective, thanks.

  16. Dan Sorensen
    Posted June 26, 2008 at 8:25 am | Permalink

    Good point. Another idea would be to leave the order the same, but provide a default for lft and rgt so that only 4 parameters would be required with 2 optional. Additionally, if username and password could optionally be left blank it would be nice in my situation, however I doubt the CFQuery tags would cooperate with that. It would probably require two much logic to make the username and password optional and would become more of a pain than a blessing.

    I thought about the named parameters too, but I came to the same conclusion as you.

    Just throwing this all out there to ponder, overall I’m very pleased with how it’s working! It’s a very understandable implementation of Nested Set Trees. It’s working great in static CFM pages. My next challenge is to see if I can get it to work with a Javascript tree control. (preferably a JQuery tree, but any would be a good step forward).

    Thanks for your work on this project!

    Dan
    Vancouver, WA

  17. Posted June 27, 2008 at 11:54 pm | Permalink

    Hi Dan, thanks for your thoughts.

    I also need to use the NST query result to generate an unordered list.

    I have update this post to include a section "Rendering nested set output as an unordered list".

    I have also updated RIAForge (http://nstree.riaforge.org/) with a new version (v0.2.4) that includes a simple jquery treeview example as part of the demo.

  18. Hussein Grant
    Posted June 29, 2008 at 3:42 pm | Permalink

    Hi Kevan,

    I love your work and greatly appreciate the tremendous effort. This will save me loads of time.

    I have a question concerning the possibility of multiple root nodes. I have a table called "catalog" and I’ve added a "catalogID" to the the "category" table. I basically want to have multiple collections of "tree roots". That way I can implement as many trees as I like with distinct features Whereby I can set the Maximum Category Levels per tree or select which View Template displays a particular category collection. Would implementing this cause problems? How much customization do you foresee is necessary for the core components? In my mind I know how I would normally handle this but I am concern about the left and right index values being corrupted.

    Thanks,
    Hussein

  19. Posted June 29, 2008 at 9:17 pm | Permalink

    Hi Hussein

    Yes, using a nested set tree model you are limited to a single root node per table (otherwise the left/right values from each separate tree will interfere with each other).

    For your situation, perhaps you could still have a single top level root category node, but all of it’s immediate child nodes are your "virtual" root nodes. You would then associate your distinct features against each virtual root node.

  20. Hussein Grant
    Posted June 30, 2008 at 8:45 am | Permalink

    Hi Kevan,

    Thanks for the response. So basically what you are suggesting is that I make all my level 1 category nodes a catalog container. Right? If so I think this makes sense. This simplifies a lot of things; however I still need all the children of each catalog to know which catalog they belong to. Any suggestions would be appreciated.

    How do I reference the Catalog/Virtual Root Node? Is it by ID or could It be referenced by a unique name? In my gateway component I could have a function called getCatalogByName() or getCatalogByID(). Can I achieve this with your NSTree component? I assume so. What would be the best approach? I am still learning to use your component so please bear with me a little. I promise I won’t ask so many questions after this. :)

    Thanks,
    Hussein

  21. Posted July 1, 2008 at 3:43 am | Permalink

    Hi Hussein

    The best way to organise this (as I understand what you need) would be to have two tables:
    - catalog
    - catalogNST

    The catalogNST table just has a catalogId, lft and rgt columns. This table is managed by the library.

    The catalog table has catalogId, parentCatalogId, catalogName, plus any other fields you need.

    To know which catalog container a child belongs to could be worked out with a query, but it might be easier to just keep a reference to the container catalog in every node. So add a containerCatalogId to the catalog table. So whenever you add a new catalog child record, you need to know in advance which container catalog it belongs to.

    Your gateway functions getCatalogById() and getCatalogByName() would work very well. In both cases you would need to do a query that performs an inner join on your catalog and catalogNST tables, then has an appropriate where clause to get the records you need.

    Hope that helps. Feel free to ask as many questions as you like!

  22. Hussein Grant
    Posted July 1, 2008 at 6:04 am | Permalink

    Hi Kevan,

    This helps big time. Thanks for clearing up a few things in my mind. Very much appreciated.

    Hussein

  23. Dan Sorensen
    Posted July 8, 2008 at 10:21 am | Permalink

    The demo seems to want to be at the root of my site. I had trouble running it in a subfolder titled "nstree". The demo should probably be designed to run anywhere (as long as the directory structure in the download remains intact) or else to run in a specified demo subdirectory. (probably not the web root)

  24. Posted July 8, 2008 at 12:25 pm | Permalink

    Dan, good suggestion – I will look into it.

  25. Hussein Grant
    Posted July 10, 2008 at 12:04 pm | Permalink

    Hi Kevan,

    I have a small suggestion for true multiple and independent tree nodes. Consider creating a table called CategoryTree comprising of the following fields: CategoryTreeID, CategoryTreeName. Assign the "CategoryTreeID" as a foreign key to both Category and CategoryNST. When you do the regeneration of the CategoryNST values, let it filter in the where clause by CategoryTreeID and that I think should prevent the entire category structure from being recalculated, which to me would be an extra performance gain especially in large collections.

    The plus with this is that you are allowed to have several applications using the same table, however only the respective root tree node would be visible to a particular app. Maybe a function like getTreeByID(1) or getTreeByName(‘products’) could do the trick.

    In essence, if you are editing the “products” tree root, you still have all the same functions to move up or down tree branches and siblings. The only difference from what little I can interpret would be to include the CategoryTreeID in the where clause to ensure that other roots aren’t affected. This is just an idea that I’m throwing out there.

    Thanks,
    Hussein

  26. Hussein Grant
    Posted July 21, 2008 at 12:50 pm | Permalink

    Is there a bug with coldfusion 7 whereby the "move" select list in your original example doesn’t allow anything to be selected? I implemented your example in an app and all works great in cf8 but the move select list is buggy in cf7. Could this have anything to do with the duplicate function? "<cfset variables.moveto = duplicate(variables.subtree)>"

    I’m also doing a flex version of the NSTree UI using the AdvanceDataGrid, I have most of the functions working nicely. The only tough part left is the MoveTo feature. I thought this would have been easy but working with Hierarchical data in flex isn’t always smooth sailing if ever (considering I am no flex guru). I will post an example when I’ve made some progress for some feedback, but in the meantime I would love some advice about the bug I am experiencing.

    Thanks
    Hussein

  27. Posted July 22, 2008 at 3:58 am | Permalink

    Hi Hussein

    Great idea for supporting multiple trees within the same table, adding a "treeId" type column may work well. I have put some thought into this – couple of things to think through:

    1. Needing to pass a new treeId parameter for each call, not sure I want this as base functionality. This would be worthwhile if multiple tree support in a single table was a common requirement/preference.

    3. Possibly move to a more OO style to get around this (where each node is a real object rather than a struct). This would be very nice to use, but what would be the performance impact? Would possibly need to look into caching. May be a bit of work.

    3. Locking should be fine as we could use named CF locks for each tree.

    4. Need an index on the treeId column – easy to include as part of the NST db script.

    Just a note that I don’t see there being any performance gain in moving to this strategy as the number of records modified in each update would remain the same (just limited to the specific tree).

    Thanks for the suggestion.

    Kevan

  28. Posted July 22, 2008 at 4:04 am | Permalink

    Hmmm, odd the bug you described. I am running CF8 here but will see if I can test on CF7 tomorrow.

    What do you see in the select list? Is the list empty or are all nodes present, but just greyed out?

    Looking forward to seeing your Flex app!

  29. Posted July 22, 2008 at 4:15 am | Permalink

    Released version 0.2.5

    Demo changed so that it runs in a subdirectory or root directory.

    (Dan, thanks for the suggestion)

  30. Hussein Grant
    Posted July 22, 2008 at 6:47 am | Permalink

    Hi Kevan,

    Thanks for the feedback.

    Re: MoveTo List
    Yes the options are grayed out.

    Re: Multiple Trees

    On point one (1) I was thinking of passing the treeid on the init() method of the gateway that handles the tree functions. E.G.: ProductGateway could be extended with the CategoryGateway.

    Re: Performance

    If I created four virtual parent category groups in the current system and each group had an average of 200 sub categories, wouldn’t all the left and right indexes for the entire tree be rebuilt every time you moved a single item?
    If that is not true, my understanding of the inner workings of NSTree is somewhat flawed.
    If this is true however, the performance improvement would be that the entire tree is not rebuilt, only the tree that the change was made on. This is more from an administrative point of view, but then this brings up the argument of one table vs multiple tables design. For something like categories I personally prefer one table to copy the data I need and cache it for data presentation usages. Where as others might prefer a different approach like using a different table for each category implementation.

    Sorry, but I don’t want to take up anymore of your time with this. Thanks for listening and I think your NSTree implementation is still awesome just the way it is.

    Thanks Again,
    Hussein

  31. Posted July 22, 2008 at 4:30 pm | Permalink

    Re: MoveTo List

    Found the problem, it is related to how CF7 handles nested loops differently to CF8. I will upload a fix shortly.

    Short story is that subtree.lft and subtree.rgt need to be set to variables in the outer loop (say subtreeLft and subtreeRgt), and these variables should be referenced in the inner loop.

    Re: Multiple Trees

    Yes the treeId could be in the gateway, but imagine it would be provided by the NST library in some way. i.e. You would ask the NST library to create a new tree and it would return an id for that tree. I will put some more thought into this, but I am liking the idea quite a lot at this point.

    Re: Performance

    Hussein, you are absolutely correct! There would certainly be a performance gain using real multiple trees within one table compared to simulating multiple trees using the current library. I should remember to think before typing :)

    Kevan

  32. Posted July 23, 2008 at 12:33 am | Permalink

    Released version 0.2.6

    Fixed a CF7 bug in the demo for the "move to" drop down.

    Change mssql demo script to work on MSSQL 2000 as well as MSSQL 2005.

    http://nstree.riaforge.org/

  33. Hussein Grant
    Posted July 23, 2008 at 3:51 am | Permalink

    This is great news. Thank you so much. A quick question about deleting categories. When you delete a category the parent category is removed from the category table but the children still remain but not displayed on the nstree ui. Any thoughts on the best way to delete the children from the table as well?

  34. Posted July 23, 2008 at 5:13 am | Permalink

    Hi Hussein

    Thanks for highlighting this – I completely overlooked the delete.

    The can be handled as follows:

    1) Get the node to delete from the NST

    <cfset node = nst().getNode(arguments.categoryId)>

    2) Delete the main table records (main record plus all children)

    <cfquery …>
    delete cat
    from
    category cat
    inner join categoryNST nst on cat.categoryId = nst.categoryId
    where
    nst.lft >= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.l#">
    and nst.rgt <= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.r#">
    </cfquery>

    3) Delete the NST record

    <cfset nst().delete(node)>

    This should work in MSSQL but not sure about MySQL or others.

    I will also amend the examples and demo.

    Thanks!

  35. Posted July 23, 2008 at 5:34 am | Permalink

    Released version 0.2.7

    Fixed delete node bug in the demo app.

    http://nstree.riaforge.org/

  36. John Farrar
    Posted July 23, 2008 at 7:28 am | Permalink

    One: Great work

    Two: I want optional values, even if that means the extreme concept of building my own CFC handler. (Sure would prefer a community project though… but this is in Beta, not a gold release so doing something like that and moving to say .3 version with a warning seems appropriate.)

    Three: I am looking at doing a forum app, that will have categories, and threads. Each time a post is made in one forum category it seems odd to reindex all the threads in other categories. I would like the thread table to include a "branch" ID… to allow the same table to be used more dynamically for this kind of thing.

  37. Hussein Grant
    Posted July 23, 2008 at 7:50 am | Permalink

    Thanks Kevan,

    I am using MySql but it looks fine to me. If I encounter any problems I will let you know.
    On an aesthetic note for the "getNode()" properties, I think it would be cleaner to state the full name of the property versus the one letter thingy.

    "node.l" vs node.left
    or
    node.leftIndex
    or maybe
    node.indexLeft

    I know it is more typing but it immediately says to me what it represents.

    I hope you don’t think I am nitpicking :)
    I just generally stay away from shorten or abbreviated terms with variables.

    Thanks again,
    Hussein

  38. Hussein Grant
    Posted July 23, 2008 at 1:01 pm | Permalink

    The delete code works great. Now I know this is just a demo but you may need to disable the "move up" link when the child is first and the "move down" link when the child is last else you get the following error "MoveToPrevSibling: The "dst" node (0) is invalid." etc..

    I got around this in flex easily since I had to convert the raw query into a hierarchical array before passing it to Flex anyway; I then set isFirst:boolean, isLast:boolean and indexPosition:Numeric properties for each child within its parent. The same could be done here too unless you have some really slick way of getting around this. Would love to see! :)

  39. Posted July 24, 2008 at 3:40 am | Permalink

    Hi John

    Re: Optional values

    Can you expand on your idea here? Where would the optional values be used?

    Re: Forum App

    This is a great example of where multiple tree support would be required. I am looking into this as the moment.

  40. Posted July 24, 2008 at 4:47 am | Permalink

    Hi Hussein

    Yes, node.left etc. is a much nicer syntax. Definitely worth reviewing.

    The "move up" and "move down" error should be fixed in the current release.

    To identify the first and last children of a node the first thought that comes to mind is:

    firstChild.left = parentNode.left + 1
    lastChild.right = parentNode.right – 1

    I’ll add something to the demo that uses this idea, but it requires some extra subqueries to look up the parent node details.

  41. John Farrar
    Posted July 24, 2008 at 6:04 am | Permalink

    @Kevan

    By optional values I mean the <cfargument> params. I realize this is a pain if someone has software already built on the platform… but having fixed required arguments for things like dbusername, dbpassword are not compliant with how most people use CF. In fact many developers don’t even have access to that information! There are many shops that have coders and DBAs and hardware guys maintaining the web in three different layers. In those cases your tool is totally without use to the coders. (And occasionally some of those are my clients.)

  42. Posted July 26, 2008 at 4:56 am | Permalink

    Hi John

    Thanks. Since Dan’s comments above I have been considering ways in which to supply default values. I am planning to make a change as follows:

    Either

    a) Supply all parameters implicitly:
    init(dsName,dsUser,dsPass,nstTable,nstId,nstLeft,nstRight), or

    b) Supply mandatory parameters explicitly:
    init(datasource="dsName",nstTable="nstTable")

    The parameters for the library initialisation would then be

    datasourceName – required
    datasourceUsername – optional, default=""
    datasourcePassword – optional, default=""
    nstTable – required
    nstId – optional, default="id"
    nstLeft – optional, default="lft"
    nstRight – optional, default="rgt"

  43. John Farrar
    Posted July 26, 2008 at 6:29 am | Permalink

    The model of required declarations is a good one. It would allow compadibility with current users and provide a path where we don’t have to include them. I think this would bring your CFC up to at least a .8 version.

    (What is the roadmap that you have set the version numbers on? Not getting to 1.0 can hurt a project very deeply.)

  44. Posted July 28, 2008 at 4:03 am | Permalink

    Hi John

    I have several enhancements planned but honestly had not considered a roadmap. Even though the overall scope of the project is relatively small, a roadmap may be worthwhile to at least gauge progress to 1.0.

    In the meantime, some of the enhancements planned include:
    * Multi-tree support
    * Move to more OO style API
    * General performance enhancements.

    Thanks for the suggestion.

  45. Hussein Grant
    Posted August 20, 2008 at 9:17 am | Permalink

    Hi Kevan,

    I hope you are in good shape.

    I was wondering when you will be rolling out the next NSTree version with real Multi-Tree support and the likes. I am really excited about this next release as I plan on making it an integral part of most systems I build in the future.

    Thanks,
    Hussein

  46. Posted August 21, 2008 at 2:40 am | Permalink

    Hi Hussein

    It should be ready within the next two weeks (all going well it may be ready this coming weekend).

    The primary changes include multi-tree support and object nodes (rather than struct nodes) that you can use for some nicer syntax.

    Rather than:
    nst().newFirstChild(node,5)

    you can use:
    node.newFirstChild(5)

    The previous syntax will continue to be available.

    So, should have an update shortly!

    Kevan

  47. Hussein Grant
    Posted August 21, 2008 at 3:31 pm | Permalink

    Music to my ears! Looking forward to this release.

    Thanks for the feedback,
    Hussein

  48. Posted August 25, 2008 at 4:11 pm | Permalink

    Released version 0.8.0.

    Blog entry describing some changes here:
    http://stannard.net.au/blog/index.cfm/2008/8/25/Nested-Set-Trees-in-ColdFusion-v08

    Documentation here:
    http://stannard.net.au/blog/page.cfm/nested-set-trees

    Download here:
    http://nstree.riaforge.org

    Please add any comments on this new version against the new blog entry, thanks.