Nested Set Trees in ColdFusion (v0.8)

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.

This project provides a library of ColdFusion code that you may like to use to help manage your hierarchical data using the nested set model.

Links

This project can be downloaded from RIAForge:

http://nstree.riaforge.org

The documentation for this release:

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

Changes in this release

This release involved a significant rewrite of the library’s structure, but I kept the API as similar as possible.

The main changes include:

  • Introduction of a NestedSetTreeTable object, which allows the creation of multiple NestedSetTree objects per table. So the creation of the NestedSetTree objects has now changed.
  • Introduction of a Node object to replace the previous struct nodes. So previous code that referred to node.id, node.l and node.r should be changed to use node.getId(), node.getLeft() and node.getRight()

Please add any comments/problems regarding this release to this entry, thanks.

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

22 Comments

  1. Hussein Grant
    Posted August 25, 2008 at 7:20 pm | Permalink

    WOO! HOO!

    Excellent Work Kevan! :)

    I will be trying this out right away with my current flex implementation. I was holding off on certain things simply because I wanted the multi-tree features. I will keep you posted with my experience and hopefully if time allows I’ll post a flex example for those interested in the flex side A.S.A.P.

    Thanks Again,
    Hussein

  2. Posted August 26, 2008 at 7:07 am | Permalink

    Top stuff, I did a fair bit of work with nested set trees a couple of years ago and built a library I used internally from scratch but this looks like a huge step forward from what I was working with back then.

    Love the simplicity and how well genericised the API is!

  3. Posted August 27, 2008 at 3:51 am | Permalink

    Hussein, Craig, thanks.

    If you have any further ideas I would be keen hear them.

    At this stage I am still considering how the original NestedSetTreeTable object is created. It might be a nice to put all of it’s setup in an xml config (similar to how ColdSpring or Transfer is configured). This XML would contain the datasources and definitions of all Nested Set Tree tables in the application. We would probably then have a NestedSetTreeTableFactory to work with, but I am not sure if this just adds unnecessary complexity for most use cases. Anyway I will think about this a bit further.

  4. Hussein Grant
    Posted August 28, 2008 at 8:29 pm | Permalink

    XML is not a bad idea although I would rather the equivalent approach done using object instantiation via good old cf syntax. The "NestedSetTreeTableFactory" is a decent idea I think. I can see this being useful in a framework.

    ON another note, In your query examples I noticed that you use cftransaction and cflocks around your database calls. This might be ok if you are using Access which doesn’t support transactions but If you are using MSSQL, ORACLE or MySQL (Innodb) for example, this is an overkill and a potential performance hit under serious load, unless only a very small number of users interact with the category table, then I suppose it wouldn’t matter greatly. Just my 2 cents.

  5. Posted August 29, 2008 at 12:46 pm | Permalink

    Hussein, thanks. My goal with the transactions and locking is as follows:

    1) Transactions to provide a rollback mechanism in the case of a thrown error; such as adding a new node to the tree but the parent is no longer available (perhaps deleted by another user).

    2) Locking to ensure the primary table data and NST table remain correctly aligned.

    On thinking this though it would appear I don’t need the locking on the code that calls the NST functions and the transaction would provide the rollback required if an error was thrown. Is that what you were thinking?

    Your 2 cents is of great value :)

  6. Hussein Grant
    Posted August 30, 2008 at 7:03 pm | Permalink

    Hi Kevan,

    Yes, that was part of my thinking. I don’t think as long as your database supports its own level of locking that you need to use cflocks around select queries in most cases. I guess some people use it along with cftransaction as a double safety measure, especially on query inserts which to me is more understandable than locking a select query. Truthfully the area of database locking and transactions is really not a straightforward beast to tackle as I am sure you already know. It really all depends.

  7. Hussein Grant
    Posted September 1, 2008 at 6:29 am | Permalink

    I should had mentioned in my last comment that using cflock around a potentially user-intensive query insert could cause loads of timeouts. I’ve experienced this first hand and was truly a pain in the behind. I ended up using cftransaction with read_committed isolation and haven’t had the problem since.

  8. Posted September 2, 2008 at 4:04 am | Permalink

    Hi Hussein

    I would consider that in a site with a heavy load of updates/inserts then the use of this library would perhaps not be recommended – custom built nested set management with stored procedures would be a more efficient approach. However, that being said, I would still like this library to be as efficient as it can be.

    I am sure that you are correct that the example usage can be improved. I will put some more thought into them.

    Thanks for the feedback.

  9. Hussein Grant
    Posted September 2, 2008 at 9:30 am | Permalink

    Hi Kevan,

    Here are some of my immediate thoughts of an xml implementation:

    XML Config: tree.xml
    <nstrees>

    <nstree name="ProductCategoryTree" class="shopNutz.com.model.product.ProductCategoryTree">
    <datasource>
    <property name="NAME" value="shopNutz" />
    <property name="USERNAME" value="admin" />
    <property name="PASSWORD" value="rubberducky" />
    </datasource>
    <table>
    <property name="NAME" value="categoryNST" />
    <property name="TREE_ID" value="1" />
    <property name="TREE_ID_COLUMN" value="treeID" />
    <property name="ID_COLUMN" value="categoryID" />
    <property name="LEFT_COLUMN" value="indexLeft" />
    <property name="RIGHT_COLUMN" value="indexRight" />
    </table>
    </nstree>

    </nstrees>

    Inside your onApplicationStart() method
    //Set up NSTree
    <cfset application.nstree = CreateObject(‘component’, ‘nstree.NestedSetTreeTableFactory’).init(‘/shopNutz/config/nstree/tree.xml’) />

    //Set up Product Category Service
    <cfset application.productCategory = CreateObject(‘component’, ”).init( application.nstree.getTree(‘ProductCategoryTree’) ) />

    //Calling the Product Category Service to move a category from within your application controller
    <cfset application.productCategory.moveCategory(form.sourceID, form.destinationID) />

    Inside your Product Category Service component
    //Move A Category Example

    <cffunction name="moveCategory" access="public" output="false" returntype="boolean">
    <cfargument name="sourceID" type="numeric" required="true" />
    <cfargument name="destinationID" type="numeric" required="true" />
    <cfset var isMoved = false />

    <cfset isMoved = getProductCategoryTree().moveCategory(arguments.sourceID, arguments.destinationID) />

    <cfreturn isMoved />
    </cffunction>

    Thanks,
    Hussein

  10. Hussein Grant
    Posted September 2, 2008 at 9:35 am | Permalink

    Oops! Forgot to include the service component reference.
    "shopNutz.com.model.product.ProductCategoryService"

    //Set up Product Category Service
    <cfset application.productCategory = CreateObject(‘component’, ‘shopNutz.com.model.product.ProductCategoryService’).init( application.nstree.getTree(‘ProductCategoryTree’) ) />

    That is what it should be.

  11. Posted September 3, 2008 at 5:22 am | Permalink

    Hi Hussein, thanks for putting your thoughts down – much appreciated. I will think this through and come back with some ideas.

  12. Mark Ireland
    Posted November 13, 2008 at 4:40 am | Permalink

    There is a similar idea to this in farCry.

    Its always worth a look.

  13. Posted March 15, 2009 at 11:45 am | Permalink

    Hello Kevan,

    thanks a lot for this cfc; have used this in a shopping cart – app with about 7000 categories and 60.000 products. Former we had performance problems, now we are going very fine.

  14. Posted March 15, 2009 at 2:47 pm | Permalink

    Hi Christian

    That’s great to hear. Thanks for the feedback.

  15. Hussein Grant
    Posted March 17, 2009 at 10:17 am | Permalink

    WOW! That is very encouraging news. My current project will be using the heck out of the new tree features so this is just fabulous.

  16. Laker Netman
    Posted March 19, 2009 at 10:03 am | Permalink

    First let me say "Thank you!" for this library.

    I am starting a huge rewrite of the company web sites of my employer, from the DB on up. The current category management system is, well, "poor" to say the least. I’m moving our product categories into a nested set model and had begun writing my own routines when I found your library.

    However, I am running into some trouble utilizing the data I already have. Let me elaborate…
    I dropped 0.8.0 into one of my beta sites and began doing some testing via the Demo app. Everything worked as expected, so I changed the datasource in the application.cfc to point to one of my beta DB instances (on MSSQL2K). All I had to do was modify a couple field names (e.g. category_id to categoryId) and proceeded to index my data without incident. The hierarchy and node values appeared correctly in the demo app. The issue is that none of the functions (Delete,New,Move Up,Move Down) now work correctly. Clicking the "Delete" link refreshes the page, but the node or branch is not removed, which I confirmed by inspecting the raw tables. The "Move" links throw "Invalid sibling" errors. I have added cfdumps at various points and found that in the case of the siblings errors the getLeft() and getRight() methods are returning 0 [zero] which is, of course, not correct. The "Delete" has me baffled. The links are populated with the correct categoryId values when the page renders.

    Obviously, I believe it’s an issue with my data, but I’m not sure what to do next. My category table schema is: categoryId, categoryName, categoryDescription, categoryURL, parentCategoryId. The categoryId and parentCategoryId fields are integers and the current convention stores depth information by using increments of 1000 in the categoryId (i.e., 3000s are under 2000s, 2000s under 1000s, where "1000" if the root).

    Any thoughts?

    TIA,
    Laker

  17. Posted March 21, 2009 at 3:12 am | Permalink

    Had a chat with Laker offline. The problem was due to the reindexing utility using a default treeId of 1, while the library assumes a default treeId of 0 (when there is only one tree in use).

    I think a default value of 1 is probably a better choice so I am planning to make the following minor change to the library:

    NestedSetTreeTable.cfc

    Change the default value of the treeId argument in the getNestedSetTree() function from 0 to 1:

    <cffunction name="getNestedSetTree" output="false" returntype="NestedSetTree">
    <cfargument name="treeId" type="numeric" required="false" default="1">
    <cfreturn createObject("component","NestedSetTree").init(this,arguments.treeId)>
    </cffunction>

  18. Laker Netman
    Posted April 2, 2009 at 2:30 pm | Permalink

    Hi. I ran into an issue where I needed a sub tree without including the sub tree root node itself in the results.
    After some thought and useless coding :) I came up with this solution; I duplicated the "getCategorySubtree" method and renamed the copy "getCategorySubtreeBelowNode". The only change required was in the query.
    This line:
    nst.lft >= <cfqueryparam cfsqltype="cf_sql_integer" value="#node.getLeft()#">
    Becomes:
    nst.lft > <cfqueryparam cfsqltype="cf_sql_integer" value="#node.getLeft()#">

    By using "greater than" instead of "greater than or equal" the subtree root node is excluded from the results.

    In my case, I am using the results to produce an unordered list for a suckerfish menu and kept getting the sub tree root as the top menu item, rather than the contents of the sub tree, which is what I really wanted.

    Now it works as expected. Hope this helps someone else.

    Laker

    P.S. If you try this, don’t forget to change the method name in the calling page ;-)

  19. Posted April 2, 2009 at 2:35 pm | Permalink

    Laker, thanks for the note!

  20. Ben
    Posted June 10, 2009 at 8:20 pm | Permalink

    does the latest zip contain the MySQL.sql file? I only see the mssql. Thanks.

  21. Posted June 10, 2009 at 9:00 pm | Permalink

    Ben, you know I think I forgot to include it. I will add and upload asap.

  22. Posted June 11, 2009 at 1:31 am | Permalink

    Ben, new zip is up. Let me know if any problems with the mysql script – I haven’t tried it myself.

    Thanks