Using the Nested Set Data Model for Breadcrumb Links
It's likely that you have seen what I'm referring to as breadcrumb links before. For example, an online sporting goods store might display breadcrumb links (usually found around the top of the page) so you can see which area of their site you are currently browsing and how you got there:
Home > Sporting Equipment > Tennis > Racquets > Wilson
Adjacency List Model vs. Nested Set Model
Even if you've only been a database developer for short time, you've probably either read about or encountered a data model that required storing hierarchical data. The most common example of this kind of data is an organizational chart or "org chart." Most database designers and books on database design will show you how to model an org chart using the simple adjacency list model, like this:
CREATE TABLE OrgChart (EmpName VARCHAR(32) NOT NULL PRIMARY KEY, BossName VARCHAR(32), JobTitle VARCHAR(32));
You could add columns such as Salary, HireDate, and others to this table to make it more useful, but I'm sure you get the idea. This model produces a table like this:
|Steve||Dave||Sr. Vice President|
Even if you were to fix the obvious normalization problems this example has, it is fraught with weaknesses when it comes to managing the insertion, deletion, and update of records within the hierarchy. It is also limited when it comes to writing self-join queries to do tree traversals. Additionally, the more you try to extend this self-join pattern, the worse query performance becomes.
So what's the answer? The nested set model, of course.
The nested set model design uses two columns to model containment, which represents the subordination that was represented previously in the adjacency list model with the BossName column acting as a foreign key. These two columns can be called "Left" and "Right" or "Begin" and "End" or anything that widely appeals to most people's concept of containment. If you decide to go with "Left" and "Right," you'll need to abbreviate them somehow because they are reserved words in SQL. Something like "lft" and "rgt," for example. I'm going to use "Lft" and "Rgt" because of the left-to-right nature of the images included along with the text of this article.
Breadcrumb Links with the Nested Set Model
Here is what the DDL looks like for your BreadCrumbLinks table. I'll explain which columns hold which pieces of data if it's not clear to you from the column names and the table data.
CREATE TABLE BreadCrumbLinks( SiteAreaName CHAR(32) NOT NULL PRIMARY KEY, SiteAreaUrl CHAR(32) NOT NULL, Lft INTEGER NOT NULL, Rgt INTEGER NOT NULL);
Which, after some INSERT statements, gives you this:
As you can tell, I've once again used the Sporting Goods online store concept for the test data. If you're confused by the numbers in the Lft and Rgt columns, don't worry. I was also confused by them until I saw how they were used and managed. I'll discuss that shortly. First, I want to explain the columns and the data they hold.
The SiteAreaName column holds the text to be displayed for the link. This is what will go between your <a> and </a> tags. The SiteAreaUrl column holds the URL for the link. This is the href attribute value for the anchor tag. The Lft and Rgt columns hold the hierarchical information that you'll look at now.
If you look at the first row (Home), you will notice that the value in the Rgt column is (and will always be) double the number of rows in the table. Now, look at this data represented in a several different ways so that the relationships become more noticeable.
Listing 1: Data represented as XML
1 <Home> 2 <SportingGoods> 3 <Tennis> 4 <Racquets> 5 <Prince> 6 </Prince> 7 <Wilson> 8 </Wilson> 9 <Head> 10 </Head> 11 <Yonex> 12 </Yonex> 13 </Racquets> 14 </Tennis> 15 <Golf> 16 <Drivers> 17 <Ping> 18 </Ping> 19 <TaylorMade> 20 </TaylorMade> 21 </Drivers> 22 </Golf> 23 </SportingGoods> 24 </Home>
In this XML data, you can see the relationship between the Lft column values (the opening tags) and the Rgt column values (the closing tags). Now, look at some images.
Note: I've omitted one of the racquet types (Prince) so that things would fit nicely in the images; therefore, the numbers are slightly different but still correct.
Figure 1 shows the data as a nested circle diagram that looks similar to a ven diagram without intersecting areas.
Figure 2 shows the data as line intervals, similar to a horizontal bar (or Gantt) chart.
Both of these images help illustrate the relationship between the data in the Lft and Rgt columns. Hopefully, this has made you familiar with how the nested set model uses the Lft and Rgt columns to define the hierarchical structure of the data. Now, look at how you can write queries to retrieve the data you need to build breadcrumb links.
Page 1 of 2