|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.
Things are changing so quickly in IoT that it would take a wizard to predict which ecosystem will gain the most traction. In order for IoT to reach its potential, smart devices must be able to work together. Today, there are a slew of interoperability standards being promoted by big names to make this happen: HomeKit, Brillo and Alljoyn. In his session at @ThingsExpo, Adam Justice, vice president and general manager of Grid Connect, will review what happens when smart devices don’t work togethe...
Mar. 29, 2017 06:30 PM EDT Reads: 2,708
SYS-CON Events announced today that SoftLayer, an IBM Company, has been named “Gold Sponsor” of SYS-CON's 18th Cloud Expo, which will take place on June 7-9, 2016, at the Javits Center in New York, New York. SoftLayer, an IBM Company, provides cloud infrastructure as a service from a growing number of data centers and network points of presence around the world. SoftLayer’s customers range from Web startups to global enterprises.
Mar. 29, 2017 03:15 PM EDT Reads: 2,225
SYS-CON Events announced today that CA Technologies has been named “Platinum 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, and the 21st International Cloud Expo®, which will take place October 31-November 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA. CA Technologies helps customers succeed in a future where every business – from apparel to energy – is being rewritten by software. From ...
Mar. 29, 2017 02:30 PM EDT Reads: 2,280
SYS-CON Events announced today that Technologic Systems Inc., an embedded systems solutions company, 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. Technologic Systems is an embedded systems company with headquarters in Fountain Hills, Arizona. They have been in business for 32 years, helping more than 8,000 OEM customers and building over a hundred COTS products that have never been discontinued. Technologic Systems’ pr...
Mar. 29, 2017 02:30 PM EDT Reads: 3,820
SYS-CON Events announced today that Auditwerx 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. Auditwerx specializes in SOC 1, SOC 2, and SOC 3 attestation services throughout the U.S. and Canada. As a division of Carr, Riggs & Ingram (CRI), one of the top 20 largest CPA firms nationally, you can expect the resources, skills, and experience of a much larger firm combined with the accessibility and attent...
Mar. 29, 2017 02:30 PM EDT Reads: 695
SYS-CON Events announced today that HTBase 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. HTBase (Gartner 2016 Cool Vendor) delivers a Composable IT infrastructure solution architected for agility and increased efficiency. It turns compute, storage, and fabric into fluid pools of resources that are easily composed and re-composed to meet each application’s needs. With HTBase, companies can quickly prov...
Mar. 29, 2017 02:15 PM EDT Reads: 3,269
SYS-CON Events announced today that Loom Systems 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 2015, Loom Systems delivers an advanced AI solution to predict and prevent problems in the digital business. Loom stands alone in the industry as an AI analysis platform requiring no prior math knowledge from operators, leveraging the existing staff to succeed in the digital era. With offices in S...
Mar. 29, 2017 01:30 PM EDT Reads: 1,757
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 peeled 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 enviro...
Mar. 29, 2017 12:15 PM EDT Reads: 7,912
SYS-CON Events announced today that T-Mobile 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. As America's Un-carrier, T-Mobile US, Inc., is redefining the way consumers and businesses buy wireless services through leading product and service innovation. The Company's advanced nationwide 4G LTE network delivers outstanding wireless experiences to 67.4 million customers who are unwilling to compromise on ...
Mar. 29, 2017 11:45 AM EDT Reads: 2,584
SYS-CON Events announced today that Infranics 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. Since 2000, Infranics has developed SysMaster Suite, which is required for the stable and efficient management of ICT infrastructure. The ICT management solution developed and provided by Infranics continues to add intelligence to the ICT infrastructure through the IMC (Infra Management Cycle) based on mathemat...
Mar. 29, 2017 11:00 AM EDT Reads: 3,452
SYS-CON Events announced today that Interoute, owner-operator of one of Europe's largest networks and a global cloud services platform, has been named “Bronze Sponsor” of SYS-CON's 20th Cloud Expo, which will take place on June 6-8, 2017 at the Javits Center in New York, New York. Interoute is the owner-operator of one of Europe's largest networks and a global cloud services platform which encompasses 12 data centers, 14 virtual data centers and 31 colocation centers, with connections to 195 add...
Mar. 29, 2017 10:15 AM EDT Reads: 1,742
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 ...
Mar. 29, 2017 10:00 AM EDT Reads: 2,353
In his session at @ThingsExpo, Eric Lachapelle, CEO of the Professional Evaluation and Certification Board (PECB), will provide an overview of various initiatives to certifiy the security of connected devices and future trends in ensuring public trust of IoT. Eric Lachapelle is the Chief Executive Officer of the Professional Evaluation and Certification Board (PECB), an international certification body. His role is to help companies and individuals to achieve professional, accredited and worldw...
Mar. 29, 2017 08:45 AM EDT Reads: 954
In his General Session at 16th Cloud Expo, David Shacochis, host of The Hybrid IT Files podcast and Vice President at CenturyLink, investigated three key trends of the “gigabit economy" though the story of a Fortune 500 communications company in transformation. Narrating how multi-modal hybrid IT, service automation, and agile delivery all intersect, he will cover the role of storytelling and empathy in achieving strategic alignment between the enterprise and its information technology.
Mar. 29, 2017 08:00 AM EDT Reads: 7,568
Microservices are a very exciting architectural approach that many organizations are looking to as a way to accelerate innovation. Microservices promise to allow teams to move away from monolithic "ball of mud" systems, but the reality is that, in the vast majority of organizations, different projects and technologies will continue to be developed at different speeds. How to handle the dependencies between these disparate systems with different iteration cycles? Consider the "canoncial problem" ...
Mar. 29, 2017 06:00 AM EDT Reads: 9,081
The Internet of Things is clearly many things: data collection and analytics, wearables, Smart Grids and Smart Cities, the Industrial Internet, and more. Cool platforms like Arduino, Raspberry Pi, Intel's Galileo and Edison, and a diverse world of sensors are making the IoT a great toy box for developers in all these areas. In this Power Panel at @ThingsExpo, moderated by Conference Chair Roger Strukhoff, panelists discussed what things are the most important, which will have the most profound e...
Mar. 29, 2017 04:00 AM EDT Reads: 15,133
Keeping pace with advancements in software delivery processes and tooling is taxing even for the most proficient organizations. Point tools, platforms, open source and the increasing adoption of private and public cloud services requires strong engineering rigor - all in the face of developer demands to use the tools of choice. As Agile has settled in as a mainstream practice, now DevOps has emerged as the next wave to improve software delivery speed and output. To make DevOps work, organization...
Mar. 29, 2017 03:45 AM EDT Reads: 2,190
My team embarked on building a data lake for our sales and marketing data to better understand customer journeys. This required building a hybrid data pipeline to connect our cloud CRM with the new Hadoop Data Lake. One challenge is that IT was not in a position to provide support until we proved value and marketing did not have the experience, so we embarked on the journey ourselves within the product marketing team for our line of business within Progress. In his session at @BigDataExpo, Sum...
Mar. 29, 2017 03:30 AM EDT Reads: 3,273
Web Real-Time Communication APIs have quickly revolutionized what browsers are capable of. In addition to video and audio streams, we can now bi-directionally send arbitrary data over WebRTC's PeerConnection Data Channels. With the advent of Progressive Web Apps and new hardware APIs such as WebBluetooh and WebUSB, we can finally enable users to stitch together the Internet of Things directly from their browsers while communicating privately and securely in a decentralized way.
Mar. 29, 2017 03:00 AM EDT Reads: 6,110
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.
Mar. 29, 2017 01:15 AM EDT Reads: 2,550