Nested Set Trees in ColdFusion (v1.0)

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

Download from here:

http://nstree.riaforge.org

Documentation is here:

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

Changes in this release

  • Fix category gateway getCategorySubtree() and getCategoryChildren() bugs in the demo app.
  • Add an MySQL script for the demo app (thanks to Will Tomlinson).

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

Thanks To …

A few people have helped find and fix problems as well as provide great feedback. So thanks to Hussein Grant, Laker Netman, automaxion, Will Tomlinson, Marwan Narian, Adam Cameron and Dan Sorensen

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

Trees in SQL: Nested Sets and Materialized Path

http://www.dbazine.com/oracle/or-articles/tropashko4

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

30 Comments

  1. Raul Riera
    Posted June 6, 2009 at 11:12 am | Permalink

    There is no link or SVN to download the code on riaforge

  2. Posted June 6, 2009 at 3:32 pm | Permalink

    Hi Raul

    Thanks for letting me know. Should have a download link now.

    http://nstree.riaforge.org/

  3. Posted June 6, 2009 at 8:47 pm | Permalink

    oracle has had "connect by" for donkey years, plus some tweaks in 10g

    it make tree a total walk in the park

    wish the other dbs would support it

  4. Posted June 6, 2009 at 9:08 pm | Permalink

    Hi Zac, thanks, good to know. At least MSSQL 2008 is supporting hierarchical structures now as well.

  5. Posted June 6, 2009 at 9:13 pm | Permalink

    cool, that’s good to know

  6. Hussein Grant
    Posted July 3, 2009 at 8:18 am | Permalink

    Congrats on the 1.0 release.
    This is great!

  7. Posted July 3, 2009 at 2:39 pm | Permalink

    Thanks Hussein, and thanks for all of your feedback along the way.

  8. John Lampacher
    Posted July 26, 2009 at 11:58 pm | Permalink
  9. Posted July 27, 2009 at 12:52 am | Permalink

    John, thanks for the link!

    For anyone reading, the link John provided demonstrates an alternative technique for managing hierarchical data which is based on maintaining a "lineage" column which is essentially a string of delimited values.

  10. Laker Netman
    Posted October 19, 2009 at 1:57 pm | Permalink

    I am trying to devise a query that will return the oldest parent node "X" of a specific child node "Y", i.e., the first node immediately below the root that is in the hierarchy where "Y" lives.
    I have Celko’s "Trees And Hierarchies…" book which provides an SQL-92 query that outlines a solution, but I am having trouble getting it working in MSSQL 2000.
    Can anyone post a query or link to an article that might help?

    TIA,
    Laker

  11. Posted October 20, 2009 at 2:22 am | Permalink

    Hi Laker

    You might be able to get this working using a slight variation of the query that you’d use for getting a breadcrumb list.

    The normal breadcrumb query is:

    select
    c.*,
    nstB.lft,
    nstB.rgt
    from
    categoryNST nstA
    cross join categoryNST nstB
    inner join category c on nstB.id = c.categoryId
    where
    nstA.lft between nstB.lft and nstB.rgt
    and nstA.id = {categoryId}
    order by
    nstB.lft

    The modified version that just returns the first node immediately below the root is:

    select top 1 — ONLY USE THE FIRST NODE
    c.*,
    nstB.lft,
    nstB.rgt
    from
    categoryNST nstA
    cross join categoryNST nstB
    inner join category c on nstB.id = c.categoryId
    where
    nstA.lft between nstB.lft and nstB.rgt
    and nstB.lft > 1 — EXCLUDE THE ROOT NODE
    and nstA.id = #categoryId#
    order by
    nstB.lft

  12. Laker Netman
    Posted October 20, 2009 at 9:04 am | Permalink

    Brilliant! Thank you very much. That’s exactly what I was looking to do.

    Cheers,
    Laker

  13. Adam
    Posted December 2, 2009 at 4:51 pm | Permalink

    I can’t seem to move a node between the root node and the first level 1 node.

    I something like:

    -root
    –cat 1
    —cat 1a
    —-cat 1b
    —cat 1aa
    —-cat 1bb
    –cat 2
    –cat 3
    —cat 3a

    and I want to move cat2 to between root and cat 1. Should this be possible – I have made some changes to the downloaded templates which may be breaing something?

  14. Posted December 2, 2009 at 7:51 pm | Permalink

    Hi Adam

    Yes, that’s a valid move. I just tested using the nstreedemo app from the download and was able to make ‘cat 2′ the first child of ‘root’ (i.e. between root and cat 1)

  15. Adam
    Posted December 3, 2009 at 3:13 am | Permalink

    Hmmm. I replaced the showtree.cfm view with the one from the download package but still I cannot move the node to where I want it. This was the only file I changed so not sure why I can’t move it.

    The node I want to move is a direct child of the root node and I simply want to move it above the current first node as you mention. The current first child has several sub cats so not sure if that is an issue?

  16. Adam
    Posted December 3, 2009 at 5:10 am | Permalink

    Hi Kevan,

    Thanks for your reply. I haven’t been able to make the move as described. I’ve copied the showtree.cfm view from the download package over the modified version I was using and it still doesn’t work. This is the only file I’ve changed so I’m not sure why it doesn’t perform the move.

    Any help appreciated.

  17. Posted December 3, 2009 at 2:39 pm | Permalink

    Hi Adam

    In the demo app are you using the "Move To" drop down or the "Move Up/Move Down" links? The Move To drop down is for effectively changing the "parent" of a node, rather than for reordering nodes. The library supports what you are trying to do but the nstreedemo only shows a subset of functionality and achieves this via the move up/move down links.

    If this is not what you are experiencing can you describe how you are trying to move the nodes?

    Thanks

  18. Adam
    Posted December 3, 2009 at 3:16 pm | Permalink

    Apologies for the multiple posts – I wasn’t sure that the post was sticking.

    I’m trying to move the node using the Move Up/Move Down links and not the ‘move to’ dropdown. I’m using the nstree to drive the sections of my site (e.g. the main section navigation) and I want to add a ‘home’ node. Of course I want this to be the first child of the root so that it appears first in the main nav.

    After I create the new node I can move it up once but then it won’t move up again past the current first node (which has nested nodes itself)…! There are currently only three child nodes off the root.

    Are you saying that the demo does or doesn’t support what I am trying to do? I don’t see why I shouldn’t be able to move it up to the first child position (as you state that you can do it)…

    I can post a link tomorrow to show you what is happening if that helps explain?

    Thanks,

    Adam

  19. Posted December 5, 2009 at 4:06 am | Permalink

    Hi Adam, yes demo code certainly can do what you describe. It sounds like there may be a problem with the data. You can perhaps either delete the data and re-enter, or run the reindex utility to ensure the left and right values are correct. Otherwise feel free to put something online or email me whatever you’ve got and I’ll take a quick look (kevan at this domain).

  20. Adam
    Posted December 5, 2009 at 2:31 pm | Permalink

    Hi Kevan, I ran the reindex utility and it’s working fine now! Many thanks for your help.

  21. Posted March 23, 2010 at 4:51 am | Permalink

    Hey Kevin, been a long time since we talked. I have a question. I’m trying to get the nested set tree system working on Railo, but encountering a few issues.

    If you have a spare moment, could you shoot me an email so I can show you what it’s doing.

    Thanks,
    Will

  22. Adam Rifat
    Posted March 24, 2010 at 4:54 am | Permalink

    Hi Kevan,

    Another issue which I’m not sure if you can shed any light on. I’m trying to set up a server running railo with F/W1 and your nested set tree component. However, I’m getting the following error message:

    the function init has a invalid return value , can’t cast Object type [Component admin.com.nstree.Node] to a value of type [xml]

    which seems to be related to the nst component. I will also post on the Railo mailing list but is there anything obvious that I’m missing. This works on CF8 of course so I assume it is Railo related….

    Thanks in advance,

    Adam

  23. Posted March 24, 2010 at 3:18 pm | Permalink

    I spoke with Will and Adam offline on this.

    There seems to be a compatibility issue with Railo that is causing this problem. The workaround for now is to do a global search and replace:

    Replace returntype="Node" with returntype="any"
    Replace type="Node" with type="any"

    I am investigating and will post an upate when I have more details.

  24. Posted November 18, 2010 at 5:14 pm | Permalink

    I really enjoy using this lib. Thanks a lot.

    R U planing on creating a ORACLE sql setup script?

    Again, great lib.

  25. Posted November 18, 2010 at 10:28 pm | Permalink

    Thanks John. I don’t have an oracle db setup at the moment to test a setup script, but it would be nice to add in at some time.

  26. Posted November 22, 2010 at 9:13 pm | Permalink

    Hey Kevan,
    Can I get with you via email, off this thread, to discuss Oracle Support? I have a working version for Oracle, but some tiny code changes needed to be made.

    Thanks, again, enjoying the lib.

  27. Hussein Grant
    Posted February 4, 2011 at 2:45 am | Permalink

    Hi Kevan,

    I just had a thought about adding a “level“ field to the NST table, which can then be adjusted during inserts, updates and move operations instead of generating all the category levels on the fly each time you retrieve a category tree. I was thinking this could help improve query performance when calling a large category tree. Thanks.

  28. Posted February 5, 2011 at 11:11 am | Permalink

    Hi Hussein, thanks, sounds like a good idea. I am actually planning to get the code out onto github to hopefully make it a bit easier for anyone to play around with it.

  29. TikiHowpu
    Posted February 8, 2011 at 1:43 pm | Permalink

    Hi Kevan,

    Thanks for sharing this.
    Is it also possible to have multiple trees within the same table?

    I would like to have something like this: “Dutch” (treeID:1), “English” (treeID:2), “German” (treeID:3) and each with their own nodes. It seems that only one treeID is supported ?

  30. Posted February 8, 2011 at 9:21 pm | Permalink

    Hi TikiHowpu

    Yes, you can have multiple trees in the one table. You just need to pass in the treeId to the NestedSetTreeTable getNestedTree() function:

    dut = nstTable.getNestedSetTree(1);
    eng = nstTable.getNestedSetTree(2);
    ger = nstTable.getNestedSetTree(3);