Using the Nested Set Data Model for Breadcrumb Links
Retrieving the Data
To get the data returned in a way that's conducive to constructing the HTML needed for breadcrumb links, it's likely that you will want to find all the subordinate rows (starting from the top) that lead down to the row for the site area you're concerned with. To make the construction of the HTML as easy as possible, you'll also want the rows ordered in a top-down fashion, so that you can just loop through the result set. If you wanted to find all breadcrumb link information down to the level of Ping golf clubs, you could write a query like this:
SELECT C.* FROM BreadCrumbLinks AS B, BreadCrumbLinks AS C WHERE (B.Lft BETWEEN C.Lft AND C.Rgt) AND (B.SiteAreaName = 'Ping) ORDER BY C.Lft
And see these results:
SELECT C.* FROM BreadCrumbLinks AS B, BreadCrumbLinks AS C WHERE (B.Lft BETWEEN C.Lft AND C.Rgt) AND (B.SiteAreaName = 'Racquets) ORDER BY C.Lft
And the results:
Now, this data could easily be used to create a series of breadcrumb links that look something like this:
Home > Sporting Goods > Tennis > Racquets
It is also probably obvious to you at this point that you don't need to select the Lft and Rgt columns in your queries. I selected those columns in these examples only to demonstrate the structure of the data.
Managing the Data: Inserting, Updating, and Deleting Rows
Another benefit of the nested set model is that it is relatively easy to manage the data in the Lft and Rgt columns. Take a look at deleting an item from the hierarchy. This could entail deleting one of the lowest level items with no subordinates or a level with several items contained beneath it. You'll need to get and then hold onto the SiteAreaName, Lft, and Rgt values for the level (or node) being deleted to use those values throughout the SQL. Because I'm a bigger fan of tennis than golf, pretend I want to delete all the golfing equipment from your BreadCrumbLinks table.
--SELECT the values for the Deleted level into variables DECLARE DeletedAreaName CHAR(32); DECLARE DeletedLft INTEGER; DECLARE DeletedRgt INTEGER; SELECT SiteAreaName, Lft, Rgt INTO DeletedAreaName, DeletedLft, DeletedRgt FROM BreadCrumbLinks WHERE SiteAreaName = 'Golf; --Perform the deletion DELETE FROM BreadCrumbLinks WHERE Lft BETWEEN DeletedLft AND DeletedRgt; --UPDATE the table so that the gaps between Lft -- and Rgt values are removed UPDATE BreadCrumbLinks SET Lft = CASE WHEN Lft > DeletedLft THEN Lft - (DeletedRgt - DeletedLft + 1) ELSE Lft END, Rgt = CASE WHEN Rgt > DeletedLft THEN Rgt - (DeletedRgt - DeletedLft + 1) ELSE Rgt END WHERE Lft > DeletedLft OR Rgt > DeletedLft;
Now, look at what it takes to insert a new tennis racquet within the Home > SportingGoods > Tennis > Racquets level (node). This is basically the Delete process, but reversed. It requires identifying a specific level (node) that the new item (node) is going to be inserted beneath, and then incrementing the numbers of the Lft and Rgt columns of levels in the path up the hierarchy chain. Lastly, you'll need to number the Lft and Rgt columns of the newly inserted item(s) to fit within the hierarchy. So, the parent level will be Racquets, and you'll insert a new brand of racquet named Volkl.
-- Declare an int var to hold the ParentLevel Rgt value DECLARE ParentLevel INTEGER; -- Fill the ParentLevel var w/ the Rgt value SET ParentLevel = (SELECT Rgt FROM BreadCrumbLinks WHERE SiteAreaName = 'Racquets); --UPDATE the table in preparation for the INSERT statement UPDATE BreadCrumbLinks SET Lft = CASE WHEN Lft > ParentLevel THEN Lft + 2 ELSE Lft END, SET Rgt = CASE WHEN Rgt >= ParentLevel THEN Rgt + 2 ELSE Rgt END WHERE Rgt >= ParentLevel; --INSERT the new record w/ the values derived from the SQL above INSERT INTO BreadCrumbLinks (SiteAreaName, SiteAreaUrl, Lft, Rgt) VALUES ('Volkl, 'RacquetCategory.aspx?Brand=Volkl, ParentLevel, (ParentLevel + 1));
Not too difficult to manage, especially given the benefits the nested set model provides.
A Couple of Considerations
There are a couple of things worth mentioning about the table I've used in this article. Most experienced database designers will have noticed right away that it's far away from a perfect example of normalization. Also, there is no mention of how the pages themselves are related to the BreadCrumbLinks table. I've left these things out to try and focus on the point of the article (the nested set model) and didn't want to delve into topics that would probably just distract from that focus. If you spend a moment thinking about the relationship, though (between the page and the BreadCrumbLinks table), it's fair to assume that a something like a QueryString value in the Url of the page address or a piece of data associated with the page content would hold a key reference to one of the keys in your BreadCrumbLinks table, thus allowing you to retrieve the appropriate breadcrumb data. The reason I mention this is to remind you that this dependency should be modeled somewhere in your database and not left to be ignored until it causes trouble later on.
I hope I have achieved my goal with this article: providing you with a new way to think about modeling hierarchical data using the nested set model. Breadcrumb links were merely a means to show the benefits of this model. It has been my experience that the more you use the nested set model, the more you come to appreciate the power and inherent simplicity it provides. Organizational data, genealogy data, and many other types of data are perfect candidates for the nested set model. Choosing the right way to model this data is essential to providing a solid foundation to build applications on top of.
Page 2 of 2