ORM and the Nested Set Model

November 12, 2009

I'm working on a ColdFusion 9, ORM project at the moment that uses The Nested Set Model to manage Hierarchical Data. If you're not familiar with The Nested Set Model, there is a nice article on the MySQL site comparing it to the Adjacency List Model which is well worth reading.

I have a category table in my database with the following structure:

Column Datatype
categoryid int
title nvarchar
positionleft int
positionright int

 

In SQL you would write something like this to retrieve all the categories in a tree:


<cfquery name="categories">
  select 
    category.*
    , ( select Count(*) 
      from category as categorySubQuery 
      where categorySubQuery.positionleft < category.positionleft
        and categorySubQuery.positionright > category.positionright
    ) as level 
    , ( 
      ( category.positionright - category.positionleft - 1) / 2 
    ) as descendants
  FROM category 
  order by positionleft
</cfquery>

With ORM and HQL you can do it like this:


categories = ORMExecuteQuery
  (
    "select 
      new map( 
        category as category
        , ( select Count(categorySubQuery) 
          from Category as categorySubQuery 
          where categorySubQuery.positionleft < category.positionleft
            and categorySubQuery.positionright > category.positionright
        ) as level 
        , ( ( category.positionright - category.positionleft - 1) / 2 ) as descendants
      )
      FROM Category as category 
      order by positionleft"
  );

To display the tree as a nested list, you can use the following code:

<cfset categoryCount = ArrayLen( categories )>

<cfoutput>

<ul id="nav">
<cfloop from="1" to="#categoryCount#" index="index">



  <cfset item = categories[ index ]>
  <cfset depth = item[ "level" ]>
  <cfset descendants = item[ "descendants" ]>
  <cfset Category = item[ "category" ]>
  <cfif categoryCount gt index>
    <cfset nextdepth =  categories[ index+1 ][ "level" ]>
  <cfelse>
    <cfset nextdepth = 0>
  </cfif>
  <li><a href="list.cfm?catid=#Category.getCategoryID()#">#Category.getTitle()#</a>
  <cfif descendants gt 0>
    <ul>
  <cfelse>
    </li>
    <cfif nextdepth lt depth></ul></li></cfif>
  </cfif>
</cfloop>
<cfloop from="1" to="#depth#" index="index">
  </ul></li>
</cfloop>
</ul>

</cfoutput>

As you can see, with hibernate you can return objects and simple values in the same result. Powerful stuff!

4 comments

  1. Thank you.

    Comment by John Allen – November 12, 2009
  2. Very good. This is a topic that is on my core DB thoughts also. Nothing makes a forum run sweeter than this type of relationships. :)

    Comment by John Farrar – May 07, 2010
  3. Hey John, thanks. The nested set model is definitely the way to go! I've actually revisited this recently and think that maybe using plain SQL is easier in this instance than using the array returned from my HQL.

    Comment by John Whish – May 08, 2010
  4. recently did a study for using this at work, we came up with the ideal solution is to perform all node changes (add, delete, etc) as stored procedures, have the ORM native engine invoke the procs and put a worker massage the resultset into a nested set model API (basically a linked list with an internal indexed tree for extra performance). So the orm engine will get all the records desired in a single collection, then the collection is passed to the massager. if the massager is in the presentation tier, no problemo, the resultset can be bundled as a DTO (dont say Yuck! dto's still have their place in true multi-tier apps)

    nice article.

    Billy Vandory

    Comment by billy vandory – June 27, 2010

Leave a comment

If you found this post useful, interesting or just plain wrong, let me know - I like feedback :)

Please note: If you haven't commented before, then your comments will be moderated before they are displayed.