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
Recently, WebRTC has a lot of eyes from market. The use cases of WebRTC are expanding - video chat, online education, online health care etc. Not only for human-to-human communication, but also IoT use cases such as machine to human use cases can be seen recently. One of the typical use-case is remote camera monitoring. With WebRTC, people can have interoperability and flexibility for deploying monitoring service. However, the benefit of WebRTC for IoT is not only its convenience and interopera...
With tough new regulations coming to Europe on data privacy in May 2018, Calligo will explain why in reality the effect is global and transforms how you consider critical data. EU GDPR fundamentally rewrites the rules for cloud, Big Data and IoT. In his session at 21st Cloud Expo, Adam Ryan, Vice President and General Manager EMEA at Calligo, examined the regulations and provided insight on how it affects technology, challenges the established rules and will usher in new levels of diligence arou...
SYS-CON Events announced today that Evatronix will exhibit at SYS-CON's 21st International Cloud Expo®, which will take place on Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA. Evatronix SA offers comprehensive solutions in the design and implementation of electronic systems, in CAD / CAM deployment, and also is a designer and manufacturer of advanced 3D scanners for professional applications.
SYS-CON Events announced today that Synametrics Technologies will exhibit at SYS-CON's 22nd International Cloud Expo®, which will take place on June 5-7, 2018, at the Javits Center in New York, NY. Synametrics Technologies is a privately held company based in Plainsboro, New Jersey that has been providing solutions for the developer community since 1997. Based on the success of its initial product offerings such as WinSQL, Xeams, SynaMan and Syncrify, Synametrics continues to create and hone inn...
To get the most out of their data, successful companies are not focusing on queries and data lakes, they are actively integrating analytics into their operations with a data-first application development approach. Real-time adjustments to improve revenues, reduce costs, or mitigate risk rely on applications that minimize latency on a variety of data sources. In his session at @BigDataExpo, Jack Norris, Senior Vice President, Data and Applications at MapR Technologies, reviewed best practices to ...
The 22nd International Cloud Expo | 1st DXWorld Expo has announced that its Call for Papers is open. Cloud Expo | DXWorld Expo, to be held June 5-7, 2018, at the Javits Center in New York, NY, brings together Cloud Computing, Digital Transformation, Big Data, Internet of Things, DevOps, 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...
Smart cities have the potential to change our lives at so many levels for citizens: less pollution, reduced parking obstacles, better health, education and more energy savings. Real-time data streaming and the Internet of Things (IoT) possess the power to turn this vision into a reality. However, most organizations today are building their data infrastructure to focus solely on addressing immediate business needs vs. a platform capable of quickly adapting emerging technologies to address future ...
No hype cycles or predictions of a gazillion things here. IoT is here. You get it. You know your business and have great ideas for a business transformation strategy. What comes next? Time to make it happen. In his session at @ThingsExpo, Jay Mason, an Associate Partner of Analytics, IoT & Cybersecurity at M&S Consulting, presented a step-by-step plan to develop your technology implementation strategy. He also discussed the evaluation of communication standards and IoT messaging protocols, data...
Product connectivity goes hand and hand these days with increased use of personal data. New IoT devices are becoming more personalized than ever before. In his session at 22nd Cloud Expo | DXWorld Expo, Nicolas Fierro, CEO of MIMIR Blockchain Solutions, will discuss how in order to protect your data and privacy, IoT applications need to embrace Blockchain technology for a new level of product security never before seen - or needed.
In his session at 21st Cloud Expo, Raju Shreewastava, founder of Big Data Trunk, provided a fun and simple way to introduce Machine Leaning to anyone and everyone. He solved a machine learning problem and demonstrated an easy way to be able to do machine learning without even coding. Raju Shreewastava is the founder of Big Data Trunk (www.BigDataTrunk.com), a Big Data Training and consulting firm with offices in the United States. He previously led the data warehouse/business intelligence and B...
Cloud Expo | DXWorld Expo have announced the conference tracks for Cloud Expo 2018. Cloud Expo will be held June 5-7, 2018, at the Javits Center in New York City, and November 6-8, 2018, at the Santa Clara Convention Center, Santa Clara, CA. Digital Transformation (DX) is a major focus with the introduction of DX Expo within the program. Successful transformation requires a laser focus on being data-driven and on using all the tools available that enable transformation if they plan to survive ov...
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...
"Evatronix provides design services to companies that need to integrate the IoT technology in their products but they don't necessarily have the expertise, knowledge and design team to do so," explained Adam Morawiec, VP of Business Development at Evatronix, in this SYS-CON.tv interview at @ThingsExpo, held Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA.
Recently, REAN Cloud built a digital concierge for a North Carolina hospital that had observed that most patient call button questions were repetitive. In addition, the paper-based process used to measure patient health metrics was laborious, not in real-time and sometimes error-prone. In their session at 21st Cloud Expo, Sean Finnerty, Executive Director, Practice Lead, Health Care & Life Science at REAN Cloud, and Dr. S.P.T. Krishnan, Principal Architect at REAN Cloud, discussed how they built...
Digital Transformation (DX) is not a "one-size-fits all" strategy. Each organization needs to develop its own unique, long-term DX plan. It must do so by realizing that we now live in a data-driven age, and that technologies such as Cloud Computing, Big Data, the IoT, Cognitive Computing, and Blockchain are only tools. In her general session at 21st Cloud Expo, Rebecca Wanta explained how the strategy must focus on DX and include a commitment from top management to create great IT jobs, monitor ...
"Digital transformation - what we knew about it in the past has been redefined. Automation is going to play such a huge role in that because the culture, the technology, and the business operations are being shifted now," stated Brian Boeggeman, VP of Alliances & Partnerships at Ayehu, in this SYS-CON.tv interview at 21st Cloud Expo, held Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA.
In his Opening Keynote at 21st Cloud Expo, John Considine, General Manager of IBM Cloud Infrastructure, led attendees through the exciting evolution of the cloud. He looked at this major disruption from the perspective of technology, business models, and what this means for enterprises of all sizes. John Considine is General Manager of Cloud Infrastructure Services at IBM. In that role he is responsible for leading IBM’s public cloud infrastructure including strategy, development, and offering m...
Nordstrom is transforming the way that they do business and the cloud is the key to enabling speed and hyper personalized customer experiences. In his session at 21st Cloud Expo, Ken Schow, VP of Engineering at Nordstrom, discussed some of the key learnings and common pitfalls of large enterprises moving to the cloud. This includes strategies around choosing a cloud provider(s), architecture, and lessons learned. In addition, he covered some of the best practices for structured team migration an...
22nd International Cloud Expo, taking place June 5-7, 2018, at the Javits Center in New York City, NY, and co-located with the 1st DXWorld Expo will feature technical sessions from a rock star conference faculty and the leading industry players in the world. Cloud computing is now being embraced by a majority of enterprises of all sizes. Yesterday's debate about public vs. private has transformed into the reality of hybrid cloud: a recent survey shows that 74% of enterprises have a hybrid cloud ...
22nd International Cloud Expo, taking place June 5-7, 2018, at the Javits Center in New York City, NY, and co-located with the 1st DXWorld Expo will feature technical sessions from a rock star conference faculty and the leading industry players in the world. Cloud computing is now being embraced by a majority of enterprises of all sizes. Yesterday's debate about public vs. private has transformed into the reality of hybrid cloud: a recent survey shows that 74% of enterprises have a hybrid cloud ...