|By Brian Rinaldi||
|January 13, 2004 12:00 AM EST||
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):
- CategoryID is your primary key and has a data type of text with a field size of 40.
- Category has a data type of text with a field size of 255.
- Lpos has a data type of number and a field size of long integer.
- Rpos has a data type of number and a field size of long integer.
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
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.
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.
|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.
Explosive growth in connected devices. Enormous amounts of data for collection and analysis. Critical use of data for split-second decision making and actionable information. All three are factors in making the Internet of Things a reality. Yet, any one factor would have an IT organization pondering its infrastructure strategy. How should your organization enhance its IT framework to enable an Internet of Things implementation? In his session at Internet of @ThingsExpo, James Kirkland, Chief Architect for the Internet of Things and Intelligent Systems at Red Hat, described how to revolutioniz...
May. 22, 2015 02:00 PM EDT Reads: 4,588
For IoT to grow as quickly as analyst firms’ project, a lot is going to fall on developers to quickly bring applications to market. But the lack of a standard development platform threatens to slow growth and make application development more time consuming and costly, much like we’ve seen in the mobile space. In his session at @ThingsExpo, Mike Weiner is Product Manager of the Omega DevCloud with KORE Telematics Inc., will discuss the evolving requirements for developers as IoT matures and conduct a live demonstration of how quickly application development can happen when the need to comply...
May. 22, 2015 01:00 PM EDT Reads: 1,712
Container frameworks, such as Docker, provide a variety of benefits, including density of deployment across infrastructure, convenience for application developers to push updates with low operational hand-holding, and a fairly well-defined deployment workflow that can be orchestrated. Container frameworks also enable a DevOps approach to application development by cleanly separating concerns between operations and development teams. But running multi-container, multi-server apps with containers is very hard. You have to learn five new and different technologies and best practices (libswarm, sy...
May. 22, 2015 12:00 PM EDT Reads: 1,934
SYS-CON Events announced today that DragonGlass, an enterprise search platform, will exhibit at SYS-CON's 16th International Cloud Expo®, which will take place on June 9-11, 2015, at the Javits Center in New York City, NY. After eleven years of designing and building custom applications, OpenCrowd has launched DragonGlass, a cloud-based platform that enables the development of search-based applications. These are a new breed of applications that utilize a search index as their backbone for data retrieval. They can easily adapt to new data sets and provide access to both structured and unstruc...
May. 22, 2015 12:00 PM EDT Reads: 1,741
Converging digital disruptions is creating a major sea change - Cisco calls this the Internet of Everything (IoE). IoE is the network connection of People, Process, Data and Things, fueled by Cloud, Mobile, Social, Analytics and Security, and it represents a $19Trillion value-at-stake over the next 10 years. In her keynote at @ThingsExpo, Manjula Talreja, VP of Cisco Consulting Services, will discuss IoE and the enormous opportunities it provides to public and private firms alike. She will share what businesses must do to thrive in the IoE economy, citing examples from several industry sector...
May. 22, 2015 12:00 PM EDT Reads: 1,982
With major technology companies and startups seriously embracing IoT strategies, now is the perfect time to attend @ThingsExpo in Silicon Valley. Learn what is going on, contribute to the discussions, and ensure that your enterprise is as "IoT-Ready" as it can be! Internet of @ThingsExpo, taking place Nov 3-5, 2015, at the Santa Clara Convention Center in Santa Clara, CA, is co-located with 17th Cloud Expo and will feature technical sessions from a rock star conference faculty and the leading industry players in the world. The Internet of Things (IoT) is the most profound change in personal an...
May. 22, 2015 11:30 AM EDT Reads: 2,521
The security devil is always in the details of the attack: the ones you've endured, the ones you prepare yourself to fend off, and the ones that, you fear, will catch you completely unaware and defenseless. The Internet of Things (IoT) is nothing if not an endless proliferation of details. It's the vision of a world in which continuous Internet connectivity and addressability is embedded into a growing range of human artifacts, into the natural world, and even into our smartphones, appliances, and physical persons. In the IoT vision, every new "thing" - sensor, actuator, data source, data con...
May. 22, 2015 11:00 AM EDT Reads: 6,200
Disruptive macro trends in technology are impacting and dramatically changing the "art of the possible" relative to supply chain management practices through the innovative use of IoT, cloud, machine learning and Big Data to enable connected ecosystems of engagement. Enterprise informatics can now move beyond point solutions that merely monitor the past and implement integrated enterprise fabrics that enable end-to-end supply chain visibility to improve customer service delivery and optimize supplier management. Learn about enterprise architecture strategies for designing connected systems tha...
May. 22, 2015 10:00 AM EDT Reads: 5,858
There's Big Data, then there's really Big Data from the Internet of Things. IoT is evolving to include many data possibilities like new types of event, log and network data. The volumes are enormous, generating tens of billions of logs per day, which raise data challenges. Early IoT deployments are relying heavily on both the cloud and managed service providers to navigate these challenges. In her session at Big Data Expo®, Hannah Smalltree, Director at Treasure Data, discussed how IoT, Big Data and deployments are processing massive data volumes from wearables, utilities and other machines...
May. 22, 2015 10:00 AM EDT Reads: 3,932
SYS-CON Events announced today that the "First Containers & Microservices Conference" will take place June 9-11, 2015, at the Javits Center in New York City. The “Second Containers & Microservices Conference” will take place November 3-5, 2015, at Santa Clara Convention Center, Santa Clara, CA. Containers and microservices have become topics of intense interest throughout the cloud developer and enterprise IT communities.
May. 22, 2015 10:00 AM EDT Reads: 2,029
Buzzword alert: Microservices and IoT at a DevOps conference? What could possibly go wrong? In this Power Panel at DevOps Summit, moderated by Jason Bloomberg, the leading expert on architecting agility for the enterprise and president of Intellyx, panelists will peel away the buzz and discuss the important architectural principles behind implementing IoT solutions for the enterprise. As remote IoT devices and sensors become increasingly intelligent, they become part of our distributed cloud environment, and we must architect and code accordingly. At the very least, you'll have no problem fil...
May. 22, 2015 10:00 AM EDT Reads: 1,832
IoT is still a vague buzzword for many people. In his session at @ThingsExpo, Mike Kavis, Vice President & Principal Cloud Architect at Cloud Technology Partners, discussed the business value of IoT that goes far beyond the general public's perception that IoT is all about wearables and home consumer services. He also discussed how IoT is perceived by investors and how venture capitalist access this space. Other topics discussed were barriers to success, what is new, what is old, and what the future may hold. Mike Kavis is Vice President & Principal Cloud Architect at Cloud Technology Pa...
May. 22, 2015 10:00 AM EDT Reads: 7,721
SYS-CON Events announced today that MetraTech, now part of Ericsson, has been named “Silver Sponsor” of SYS-CON's 16th International Cloud Expo®, which will take place on June 9–11, 2015, at the Javits Center in New York, NY. Ericsson is the driving force behind the Networked Society- a world leader in communications infrastructure, software and services. Some 40% of the world’s mobile traffic runs through networks Ericsson has supplied, serving more than 2.5 billion subscribers.
May. 22, 2015 09:45 AM EDT Reads: 1,321
The 4th International Internet of @ThingsExpo, co-located with the 17th International Cloud Expo - to be held November 3-5, 2015, at the Santa Clara Convention Center in Santa Clara, CA - announces that its Call for Papers is open. The Internet of Things (IoT) is the biggest idea since the creation of the Worldwide Web more than 20 years ago.
May. 22, 2015 09:00 AM EDT Reads: 1,515
The 17th International Cloud Expo has announced that its Call for Papers is open. 17th International Cloud Expo, to be held November 3-5, 2015, at the Santa Clara Convention Center in Santa Clara, CA, brings together Cloud Computing, APM, APIs, Microservices, Security, Big Data, Internet of Things, DevOps 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 business opportunity. Submit your speaking proposal today!
May. 22, 2015 08:00 AM EDT Reads: 4,194
Since 2008 and for the first time in history, more than half of humans live in urban areas, urging cities to become “smart.” Today, cities can leverage the wide availability of smartphones combined with new technologies such as Beacons or NFC to connect their urban furniture and environment to create citizen-first services that improve transportation, way-finding and information delivery. In her session at @ThingsExpo, Laetitia Gazel-Anthoine, CEO of Connecthings, will focus on successful use cases.
May. 22, 2015 06:00 AM EDT Reads: 4,846
The explosion of connected devices / sensors is creating an ever-expanding set of new and valuable data. In parallel the emerging capability of Big Data technologies to store, access, analyze, and react to this data is producing changes in business models under the umbrella of the Internet of Things (IoT). In particular within the Insurance industry, IoT appears positioned to enable deep changes by altering relationships between insurers, distributors, and the insured. In his session at @ThingsExpo, Michael Sick, a Senior Manager and Big Data Architect within Ernst and Young's Financial Servi...
May. 22, 2015 06:00 AM EDT Reads: 4,716
The recent trends like cloud computing, social, mobile and Internet of Things are forcing enterprises to modernize in order to compete in the competitive globalized markets. However, enterprises are approaching newer technologies with a more silo-ed way, gaining only sub optimal benefits. The Modern Enterprise model is presented as a newer way to think of enterprise IT, which takes a more holistic approach to embracing modern technologies.
May. 22, 2015 06:00 AM EDT Reads: 5,954
One of the biggest impacts of the Internet of Things is and will continue to be on data; specifically data volume, management and usage. Companies are scrambling to adapt to this new and unpredictable data reality with legacy infrastructure that cannot handle the speed and volume of data. In his session at @ThingsExpo, Don DeLoach, CEO and president of Infobright, will discuss how companies need to rethink their data infrastructure to participate in the IoT, including: Data storage: Understanding the kinds of data: structured, unstructured, big/small? Analytics: What kinds and how responsiv...
May. 22, 2015 05:00 AM EDT Reads: 4,391
17th Cloud Expo, taking place Nov 3-5, 2015, at the Santa Clara Convention Center in Santa Clara, CA, 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 strategy. Meanwhile, 94% of enterprises are using some form of XaaS – software, platform, and infrastructure as a service.
May. 22, 2015 05:00 AM EDT Reads: 2,331