dcsimg
December 8, 2016
Hot Topics:

Using the Nested Set Data Model for Breadcrumb Links

  • July 5, 2005
  • By Jason Mauss
  • Send Email »
  • More Articles »

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:

SiteAreaName SiteAreaUrl Lft Rgt
Home Default.aspx 1 24
SportingGoods SportingGoods.aspx 2 23
Golf Golf.aspx 15 22
Drivers GolfClubs.aspx 16 21
Ping ClubCategory?Brand=Ping 17 18

The nice thing about the structure of this query is that it will work no matter how many levels deep the hierarchy is. Now, look at another query to get you the row set for Tennis Racquets:


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:

SiteAreaName SiteAreaUrl Lft Rgt
Home Default.aspx 1 24
SportingGoods SportingGoods.aspx 2 23
Tennis Tennis.aspx 3 14
Racquets TennisRacquets.aspx 4 13

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.

Conclusion

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



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date
Rocket Fuel