|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.
How do APIs and IoT relate? The answer is not as simple as merely adding an API on top of a dumb device, but rather about understanding the architectural patterns for implementing an IoT fabric. There are typically two or three trends: Exposing the device to a management framework Exposing that management framework to a business centric logic Exposing that business layer and data to end users. This last trend is the IoT stack, which involves a new shift in the separation of what stuff happens, where data lives and where the interface lies. For instance, it's a mix of architectural styles ...
Nov. 26, 2014 04:15 PM EST Reads: 577
"Matrix is an ambitious open standard and implementation that's set up to break down the fragmentation problems that exist in IP messaging and VoIP communication," explained John Woolf, Technical Evangelist at Matrix, in this SYS-CON.tv interview at @ThingsExpo, held Nov 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
Nov. 26, 2014 04:15 PM EST Reads: 1,057
Cultural, regulatory, environmental, political and economic (CREPE) conditions over the past decade are creating cross-industry solution spaces that require processes and technologies from both the Internet of Things (IoT), and Data Management and Analytics (DMA). These solution spaces are evolving into Sensor Analytics Ecosystems (SAE) that represent significant new opportunities for organizations of all types. Public Utilities throughout the world, providing electricity, natural gas and water, are pursuing SmartGrid initiatives that represent one of the more mature examples of SAE. We have s...
Nov. 26, 2014 04:00 PM EST Reads: 1,154
We are reaching the end of the beginning with WebRTC, and real systems using this technology have begun to appear. One challenge that faces every WebRTC deployment (in some form or another) is identity management. For example, if you have an existing service – possibly built on a variety of different PaaS/SaaS offerings – and you want to add real-time communications you are faced with a challenge relating to user management, authentication, authorization, and validation. Service providers will want to use their existing identities, but these will have credentials already that are (hopefully) i...
Nov. 26, 2014 04:00 PM EST Reads: 1,162
The Internet of Things will greatly expand the opportunities for data collection and new business models driven off of that data. In her session at @ThingsExpo, Esmeralda Swartz, CMO of MetraTech, discussed how for this to be effective you not only need to have infrastructure and operational models capable of utilizing this new phenomenon, but increasingly service providers will need to convince a skeptical public to participate. Get ready to show them the money!
Nov. 26, 2014 04:00 PM EST Reads: 1,289
The Internet of Things will put IT to its ultimate test by creating infinite new opportunities to digitize products and services, generate and analyze new data to improve customer satisfaction, and discover new ways to gain a competitive advantage across nearly every industry. In order to help corporate business units to capitalize on the rapidly evolving IoT opportunities, IT must stand up to a new set of challenges. In his session at @ThingsExpo, Jeff Kaplan, Managing Director of THINKstrategies, will examine why IT must finally fulfill its role in support of its SBUs or face a new round of...
Nov. 26, 2014 04:00 PM EST Reads: 1,078
One of the biggest challenges when developing connected devices is identifying user value and delivering it through successful user experiences. In his session at Internet of @ThingsExpo, Mike Kuniavsky, Principal Scientist, Innovation Services at PARC, described an IoT-specific approach to user experience design that combines approaches from interaction design, industrial design and service design to create experiences that go beyond simple connected gadgets to create lasting, multi-device experiences grounded in people's real needs and desires.
Nov. 26, 2014 03:45 PM EST Reads: 1,292
Connected devices and the Internet of Things are getting significant momentum in 2014. In his session at Internet of @ThingsExpo, Jim Hunter, Chief Scientist & Technology Evangelist at Greenwave Systems, examined three key elements that together will drive mass adoption of the IoT before the end of 2015. The first element is the recent advent of robust open source protocols (like AllJoyn and WebRTC) that facilitate M2M communication. The second is broad availability of flexible, cost-effective storage designed to handle the massive surge in back-end data in a world where timely analytics is e...
Nov. 26, 2014 03:15 PM EST Reads: 991
P2P RTC will impact the landscape of communications, shifting from traditional telephony style communications models to OTT (Over-The-Top) cloud assisted & PaaS (Platform as a Service) communication services. The P2P shift will impact many areas of our lives, from mobile communication, human interactive web services, RTC and telephony infrastructure, user federation, security and privacy implications, business costs, and scalability. In his session at @ThingsExpo, Robin Raymond, Chief Architect at Hookflash, will walk through the shifting landscape of traditional telephone and voice services ...
Nov. 26, 2014 02:00 PM EST Reads: 1,782
Scott Jenson leads a project called The Physical Web within the Chrome team at Google. Project members are working to take the scalability and openness of the web and use it to talk to the exponentially exploding range of smart devices. Nearly every company today working on the IoT comes up with the same basic solution: use my server and you'll be fine. But if we really believe there will be trillions of these devices, that just can't scale. We need a system that is open a scalable and by using the URL as a basic building block, we open this up and get the same resilience that the web enjoys.
Nov. 25, 2014 09:30 PM EST Reads: 1,800
The Internet of Things is tied together with a thin strand that is known as time. Coincidentally, at the core of nearly all data analytics is a timestamp. When working with time series data there are a few core principles that everyone should consider, especially across datasets where time is the common boundary. In his session at Internet of @ThingsExpo, Jim Scott, Director of Enterprise Strategy & Architecture at MapR Technologies, discussed single-value, geo-spatial, and log time series data. By focusing on enterprise applications and the data center, he will use OpenTSDB as an example t...
Nov. 25, 2014 09:30 PM EST Reads: 1,853
The Domain Name Service (DNS) is one of the most important components in networking infrastructure, enabling users and services to access applications by translating URLs (names) into IP addresses (numbers). Because every icon and URL and all embedded content on a website requires a DNS lookup loading complex sites necessitates hundreds of DNS queries. In addition, as more internet-enabled ‘Things' get connected, people will rely on DNS to name and find their fridges, toasters and toilets. According to a recent IDG Research Services Survey this rate of traffic will only grow. What's driving t...
Nov. 25, 2014 07:00 PM EST Reads: 1,749
Enthusiasm for the Internet of Things has reached an all-time high. In 2013 alone, venture capitalists spent more than $1 billion dollars investing in the IoT space. With "smart" appliances and devices, IoT covers wearable smart devices, cloud services to hardware companies. Nest, a Google company, detects temperatures inside homes and automatically adjusts it by tracking its user's habit. These technologies are quickly developing and with it come challenges such as bridging infrastructure gaps, abiding by privacy concerns and making the concept a reality. These challenges can't be addressed w...
Nov. 25, 2014 04:30 PM EST Reads: 1,700
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...
Nov. 24, 2014 07:00 PM EST Reads: 2,066
Bit6 today issued a challenge to the technology community implementing Web Real Time Communication (WebRTC). To leap beyond WebRTC’s significant limitations and fully leverage its underlying value to accelerate innovation, application developers need to consider the entire communications ecosystem.
Nov. 24, 2014 12:00 PM EST Reads: 1,803
The definition of IoT is not new, in fact it’s been around for over a decade. What has changed is the public's awareness that the technology we use on a daily basis has caught up on the vision of an always on, always connected world. If you look into the details of what comprises the IoT, you’ll see that it includes everything from cloud computing, Big Data analytics, “Things,” Web communication, applications, network, storage, etc. It is essentially including everything connected online from hardware to software, or as we like to say, it’s an Internet of many different things. The difference ...
Nov. 24, 2014 11:00 AM EST Reads: 2,164
Cloud Expo 2014 TV commercials will feature @ThingsExpo, which was launched in June, 2014 at New York City's Javits Center as the largest 'Internet of Things' event in the world.
Nov. 24, 2014 09:00 AM EST Reads: 2,017
SYS-CON Events announced today that Windstream, a leading provider of advanced network and cloud communications, 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. Windstream (Nasdaq: WIN), a FORTUNE 500 and S&P 500 company, is a leading provider of advanced network communications, including cloud computing and managed services, to businesses nationwide. The company also offers broadband, phone and digital TV services to consumers primarily in rural areas.
Nov. 23, 2014 07:30 PM EST Reads: 2,182
"There is a natural synchronization between the business models, the IoT is there to support ,” explained Brendan O'Brien, Co-founder and Chief Architect of Aria Systems, in this SYS-CON.tv interview at the 15th International Cloud Expo®, held Nov 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
Nov. 23, 2014 12:00 PM EST Reads: 2,119
The major cloud platforms defy a simple, side-by-side analysis. Each of the major IaaS public-cloud platforms offers their own unique strengths and functionality. Options for on-site private cloud are diverse as well, and must be designed and deployed while taking existing legacy architecture and infrastructure into account. Then the reality is that most enterprises are embarking on a hybrid cloud strategy and programs. In this Power Panel at 15th Cloud Expo (http://www.CloudComputingExpo.com), moderated by Ashar Baig, Research Director, Cloud, at Gigaom Research, Nate Gordon, Director of T...
Nov. 23, 2014 07:45 AM EST Reads: 2,196