Welcome!

You will be redirected in 30 seconds or close now.

ColdFusion Authors: Yakov Fain, Jeremy Geelan, Maureen O'Gara, Nancy Y. Nee, Tad Anderson

Related Topics: ColdFusion

ColdFusion: Article

Implementing a Nested Set Model in ColdFusion

Building and using a flexible categorization system

When building applications, from content management to product catalogs, your project will typically be impacted by the method you choose for categorization. Designing code that is flexible enough to allow for ease of reuse, but simple enough to allow for ease of implementation, can often tie a developer in knots. The nested set model can help you fulfill both those goals.

This article will cover a simple implementation of this model, and draws extensively from two sources, Joe Celko's SQL for Smarties and Benjamin Elmore's Dynamic Publishing with ColdFusion MX. Both are recommended reading for a more in-depth look at the nested set model.

What Is the Nested Set Model?
In order to better understand the advantages of the nested set model in representing category trees within relational databases, we will first look at an alternate, commonly used method, the adjacency list model. The standard adjacency list model can be comprised of simply a categoryID, category, and parent field (see Figure 1).

 

Using the adjacency list model, a root node - a category that has no parent - is signified by a null value in the parent field (from here on out, node and category will often be used interchangeably). A leaf node is a category that has no children and can be determined through the use of a simple query. Determining the immediate parent or children of a given category also requires only a simple query. However, any function that would require traversing the tree beyond either the immediate parent or children of a given category would require complex recursive queries that are difficult to code, particularly when the depth of the tree is unknown. Similar problems occur when you wish to create functions for removing a sub tree. As adjacency list models are quite common, most experienced developers are well aware of their many deficiencies.

Rather than depend upon explicitly defined parents, the nested set model uses a set of left and right position integers to establish any given category's position within the tree structure. The left and right positions establish a range within which the left and right positions of any children will fall. The range between the left and right positions can easily be expanded to accommodate growth of the tree, and can be contracted just as easily when nodes are removed. In addition, determining the parents or children of a given node within a tree or even determining a given node's depth within the tree is a simple process regardless of the total depth of the tree.

In order to visualize this concept, let's take a root node (i.e., a node that has no parent) named "Macromedia," which is assigned the left and right positions of 1 and 20 respectively. A child of Macromedia called "ColdFusion" could have a left position of 2 and a right position of 9. Furthermore, a child of ColdFusion called "MX" could have a left position of 7 and a right position of 8, in which case it would be automatically recognizable as a leaf node given that the difference between the left and right positions is 1. See Figure 2 for a visual representation of a nested set model.

 

Building the CFC
Before I begin delving into the code of our component, I would first like to cover some assumptions I used in building it. Although the code is based upon examples from Dynamic Publishing with ColdFusion MX and SQL for Smarties, it has been modified in part to allow for compatibility with an Access database and also so that all public methods of the component return queries. While there are certainly benefits to using a more object-oriented approach within your components, and this component could be easily modified to meet that goal, I am choosing to return queries as I believe this makes the component easier to understand and implement for beginners and advanced users alike.

Before using this component, you first must create a table named "categories" in your database. If you are using Access, you would structure it as follows (see Figure 3):

 
  1. CategoryID is your primary key and has a data type of text with a field size of 40.
  2. Category has a data type of text with a field size of 255.
  3. Lpos has a data type of number and a field size of long integer.
  4. Rpos has a data type of number and a field size of long integer.
The first method of our component is called new (see Listing 1: categories.cfc)). This method is designed to simply create an empty query containing the columns defined within our table. A row is then inserted and a value set for categoryID, which is a ColdFusion UUID. When building components structured to return queries, I always add this method. The primary function of this method is to make it easier to build a form to update the database. Later we will cover building this form, at which time the purpose of this method will be more obvious.

The save method is fairly straightforward as it simply determines whether to call the Add or the Edit method depending on whether the categoryID sent already exists in the database.

The add, edit, and delete methods are fairly standard representations of their SQL counterparts (insert, update, and delete respectively), except for a few important points that we will cover. The first is that before a category is inserted, either the createRootNode or the createChildNode method must be called depending upon whether a parent category ID has been sent, keeping in mind that a root node is a node without a parent. We will discuss both methods in more detail later, but it is important to note that they both return a structure containing the left and right position integers.

Second, you should be aware that the edit method only allows changing of the text in the category field. This is because, as we discussed before, one of the few drawbacks of the nested set model is that it is extremely difficult to move a sub tree. Therefore, for simplicity's sake, this component simply disallows moving a category once it has been created.

Third, you will note a series of queries within the delete function called CloseGap 1, 2, 3, and 4. To understand the reason for these queries, you must first understand the logic behind including them, which is that, rather than delete a node (category) along with its entire subtree, I have chosen to promote the child nodes of any deleted node. For instance, let's take a category tree containing Grandpa Abe, which has a child, Homer; and Homer has three children, Bart, Lisa, and Maggie. Should something befall Homer, say an accident at the nuclear plant, Bart, Lisa, and Maggie would be adopted by Grandpa Abe. Thus the CloseGap queries are designed to do just that, close any gaps in the left and right position fields within the database, thereby promoting any children of the deleted node.

The get function within our component has been customized to implement a variety of different common queries required when integrating the category system into your site. This method takes four arguments: categoryID, children, parents, and immediate, all of which are optional. Due to the structure of the if statement, the Boolean argument children takes precedence over the Boolean argument parents. In addition, the Boolean argument immediate relates specifically to the children argument but is ignored otherwise. The method is as follows:

  • If children is true and a categoryID is supplied, then the component will retrieve the children of a given node
    -If immediate is true, only the immediate children are returned (i.e., one level below the level of a given node), otherwise all children are returned
  • If parents is true and a categoryID is supplied, then the component will return all parents of a given node
  • If only a categoryID is supplied, then only the information for the specific node is returned
  • If no arguments are supplied, then a raw query of all category data is returned
We will discuss later how this method is implemented within your application.

The getAllNodes method is a variation on the get method that returns all categories, with the difference being that getAllNodes returns a lvl column in the query that specifies the depth within the tree of any given node. For instance, given our example from earlier, the Bart category would have a value for lvl equal to 3, as it is three levels deep in the category tree. In addition, you can specify a lvl argument that will filter the returned results by a given depth. Again, using our previous example, specifying the value of 3 in the lvl argument would return only the categories of Bart, Lisa, and Maggie. Being able to retrieve the depth information for categories is a useful feature that you will find yourself using repeatedly throughout your application.

The remaining methods, createRootNode and createChildNode are both private methods, meaning they can only be called from inside the component. They are both designed to return the pos structure used within the add method as we saw earlier. The createChildNode method also updates the tree structure to make room for the node to be created.

Using the Component
Let's cover some basic implementations of the categories component by first looking at how to build a form to update the category tree. We will do this in the context of creating and organizing categories for Web site navigation. The form we will create is missing a lot of niceties, which I will leave for you to add at your leisure. For these examples to work, you must first create the database as explained earlier in this article and add that as a dsn within the ColdFusion administrator called CFDJ.

Our form is self-submitting and includes only two fields, one a text field to enter the name of the category and the other a select box to choose a parent category if applicable (see Listing 2: addCategories.cfm). The select box uses the lvl integer returned by the getAllNodes method to structure the list so that the depth within the category tree is visible (see Figure 4). The form is prefilled with either the value of a category determined by URL.categoryID or by the values returned by the new method, which is empty except for the categoryID. Note that when the form is prefilled with an existing category, the parent category select box is disabled because, as we discussed earlier, the component disallows changing the parent of an existing category.

 

When the form is submitted, we first run it through basic server-side error processing. Then we remove any empty values from the form structure so that they are not passed on to our component through the argumentCollection (this is simply a shortcut I prefer to use for submitting forms to a component). Finally, we call the save method, which, if you recall, determines whether the category should be added or edited.

Once submitted, you can view your category added to the tree within your select box, or view the test page, the basic code which I have also included (see Listing 3: index.cfm). The test page shows some standard uses for the different get methods within the component, such as getting the root level categories to propagate a category menu, getting the immediate children of a given category to propagate a submenu, and getting the parents of a given category to propagate breadcrumbs (see Figure 5). As you can see, all of these functions are exceedingly easy to use, as they require very little coding.

 

Conclusion
Using the nested set model, we have built a component and category structure that is flexible enough to use in a variety of applications with little to no modification. In addition, by abstracting this model into a component, we have made it portable enough to reuse relatively effortlessly.

More Stories By Brian Rinaldi

Brian Rinaldi, a member of the Editorial Board of CFDJ, is a web developer at Hasbro. He is also a member of the Adobe Community Experts program, the manager of the Boston ColdFusion User Group and an Advanced Certified ColdFusion MX Developer, as well as a Microsoft Certified Professional. Brian is most well known for his efforts promoting open-source projects in ColdFusion, especially for maintaining the ColdFusion open-source list as well as the weekly updates, both of which you can find via his web site at remotesynthesis.com.

Comments (1) View Comments

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.


Most Recent Comments
Abraham Lloyd 01/15/04 09:42:27 AM EST

Having worked quite a bit with this model in the past, one point to note is that this model should only be recommended for hierarchies that are static (never change) or that infrequently change. Inserting new nodes or moving nodes require that all elements in hierarchy that are affected be renumbered and ordered.

If you have a hierarchy that contains several hundred/thousand rows, this could result in every record in the hierarchy being updated (which clearly is less than ideal). If your hierarchies are static, however, then this model will scale and perform well under heavy load.

@ThingsExpo Stories
With major technology companies and startups seriously embracing Cloud strategies, now is the perfect time to attend @CloudExpo | @ThingsExpo, June 6-8, 2017, at the Javits Center in New York City, NY and October 31 - November 2, 2017, Santa Clara Convention Center, CA. Learn what is going on, contribute to the discussions, and ensure that your enterprise is on the right path to Digital Transformation.
In order to meet the rapidly changing demands of today’s customers, companies are continually forced to redefine their business strategies in order to meet these needs, stay relevant and continue to see profitable growth. IoT deployment and development is integral in this transformation, and today businesses are increasingly seeing the value of investing their resources into IoT deployments. These technologies are able increase ROI through projects such as connecting supply chains or enabling sm...
DevOps is often described as a combination of technology and culture. Without both, DevOps isn't complete. However, applying the culture to outdated technology is a recipe for disaster; as response times grow and connections between teams are delayed by technology, the culture will die. A Nutanix Enterprise Cloud has many benefits that provide the needed base for a true DevOps paradigm.
SYS-CON Events announced today that Outscale, a global pure play Infrastructure as a Service provider and strategic partner of Dassault Systèmes, will exhibit at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. Founded in 2010, Outscale simplifies infrastructure complexities and boosts the business agility of its customers. Outscale delivers a secure, reliable and industrial strength solution for its customers, which in...
SYS-CON Events announced today that Progress, a global leader in application development, has been named “Bronze Sponsor” of SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. Enterprises today are rapidly adopting the cloud, while continuing to retain business-critical/sensitive data inside the firewall. This is creating two separate data silos – one inside the firewall and the other outside the firewall. Cloud ISVs ofte...
SYS-CON Events announced today that Tintri, Inc, a leading provider of enterprise cloud infrastructure, will exhibit at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. Tintri offers an enterprise cloud platform built with public cloud-like web services and RESTful APIs. Organizations use Tintri all-flash storage with scale-out and automation as a foundation for their own clouds – to build agile development environments...
In his opening keynote at 20th Cloud Expo, Michael Maximilien, Research Scientist, Architect, and Engineer at IBM, will motivate why realizing the full potential of the cloud and social data requires artificial intelligence. By mixing Cloud Foundry and the rich set of Watson services, IBM's Bluemix is the best cloud operating system for enterprises today, providing rapid development and deployment of applications that can take advantage of the rich catalog of Watson services to help drive insigh...
SYS-CON Events announced today that DivvyCloud will exhibit at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. DivvyCloud software enables organizations to achieve their cloud computing goals by simplifying and automating security, compliance and cost optimization of public and private cloud infrastructure. Using DivvyCloud, customers can leverage programmatic Bots to identify and remediate common cloud problems in rea...
The 21st International Cloud Expo has announced that its Call for Papers is open. Cloud Expo, to be held October 31 - November 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA, brings together Cloud Computing, Big Data, Internet of Things, DevOps, Digital Transformation, Machine Learning and WebRTC to one location. With cloud computing driving a higher percentage of enterprise IT budgets every year, it becomes increasingly important to plant your flag in this fast-expanding busin...
A strange thing is happening along the way to the Internet of Things, namely far too many devices to work with and manage. It has become clear that we'll need much higher efficiency user experiences that can allow us to more easily and scalably work with the thousands of devices that will soon be in each of our lives. Enter the conversational interface revolution, combining bots we can literally talk with, gesture to, and even direct with our thoughts, with embedded artificial intelligence, whic...
SYS-CON Events announced today that Cloudistics, an on-premises cloud computing company, has been named “Bronze Sponsor” of SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. Cloudistics delivers a complete public cloud experience with composable on-premises infrastructures to medium and large enterprises. Its software-defined technology natively converges network, storage, compute, virtualization, and management into a ...
Every successful software product evolves from an idea to an enterprise system. Notably, the same way is passed by the product owner's company. In his session at 20th Cloud Expo, Oleg Lola, CEO of MobiDev, will provide a generalized overview of the evolution of a software product, the product owner, the needs that arise at various stages of this process, and the value brought by a software development partner to the product owner as a response to these needs.
New competitors, disruptive technologies, and growing expectations are pushing every business to both adopt and deliver new digital services. This ‘Digital Transformation’ demands rapid delivery and continuous iteration of new competitive services via multiple channels, which in turn demands new service delivery techniques – including DevOps. In this power panel at @DevOpsSummit 20th Cloud Expo, moderated by DevOps Conference Co-Chair Andi Mann, panelists will examine how DevOps helps to meet th...
Most technology leaders, contemporary and from the hardware era, are reshaping their businesses to do software in the hope of capturing value in IoT. Although IoT is relatively new in the market, it has already gone through many promotional terms such as IoE, IoX, SDX, Edge/Fog, Mist Compute, etc. Ultimately, irrespective of the name, it is about deriving value from independent software assets participating in an ecosystem as one comprehensive solution.
SYS-CON Events announced today that EARP will exhibit at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. "We are a software house, so we perfectly understand challenges that other software houses face in their projects. We can augment a team, that will work with the same standards and processes as our partners' internal teams. Our teams will deliver the same quality within the required time and budget just as our partn...
SYS-CON Events announced today that delaPlex will exhibit at SYS-CON's @ThingsExpo, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. delaPlex pioneered Software Development as a Service (SDaaS), which provides scalable resources to build, test, and deploy software. It’s a fast and more reliable way to develop a new product or expand your in-house team.
SYS-CON Events announced today that Tappest will exhibit MooseFS at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. MooseFS is a breakthrough concept in the storage industry. It allows you to secure stored data with either duplication or erasure coding using any server. The newest – 4.0 version of the software enables users to maintain the redundancy level with even 50% less hard drive space required. The software func...
SYS-CON Events announced today that A&I Solutions has been named “Bronze Sponsor” of SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. Founded in 1999, A&I Solutions is a leading information technology (IT) software and services provider focusing on best-in-class enterprise solutions. By partnering with industry leaders in technology, A&I assures customers high performance levels across all IT environments including: mai...
In his keynote at @ThingsExpo, Chris Matthieu, Director of IoT Engineering at Citrix and co-founder and CTO of Octoblu, focused on building an IoT platform and company. He provided a behind-the-scenes look at Octoblu’s platform, business, and pivots along the way (including the Citrix acquisition of Octoblu).
SYS-CON Events announced today that Systena America will exhibit at SYS-CON's 20th International Cloud Expo®, which will take place on June 6-8, 2017, at the Javits Center in New York City, NY. Systena Group has been in business for various software development and verification in Japan, US, ASEAN, and China by utilizing the knowledge we gained from all types of device development for various industries including smartphones (Android/iOS), wireless communication, security technology and IoT serv...