It's Sunday - what a day to visit jfoobar!

Hierarchical data, nodes and nested sets in 1.6

Written by Wilco Jansen Wednesday, 14 October 2009 21:44

To understand nested data sets I will start with explaining the most logical way to represent data in an hierarchical way; a record holds a pointer to the parent record, this is referred to as the Adjacency List Model. Imagine the following representation of a tree holding the category data.

Since the Adjacency List Model and the Nested Set have been implemented we can re-use the current example data from Joomla 1.6. Let's take a look at the Adjacency List Model implementation within the categories table.

SELECT id, title, parent_id FROM jos_categories WHERE extension='com_content' OR extension='system'

+----+------------+-----------+
+ id + title      | parent_id |
+----+------------+-----------+
|  1 | ROOT       |         0 |
| 11 | News       |         1 |
| 12 | Countries  |         1 |
| 23 | Australia  |        12 |
| 24 | Queensland |        23 |
| 25 | Tasmania   |        23 |
+----+------------+-----------+

As you can see in this example each item contains a pointer to its parent. The top-level element is the root element and hold the title 'ROOT' and has a parent reference of 0. The benefit of this model is that is straight forward and very easy to understand. Retrieving data from an Adjacency List Model using SQL can be more problematic when the tree in the hierarchy has multiple levels. In the given data-set retrieving a full tree would require the following SQL statement:

SELECT t1.title AS cat1, t2.title AS cat2, t3.title AS cat3, t4.title AS cat4
FROM jos_categories as t1
LEFT JOIN jos_categories AS t2 ON t2.parent_id = t1.id
LEFT JOIN jos_categories AS t3 ON t3.parent_id = t2.id
LEFT JOIN jos_categories AS t4 ON t4.parent_id = t3.id
WHERE t1.title = 'ROOT'

+------+------------------------+------------------------+-----------------+
|cat1  | cat2                   | cat3                   | cat4            |
+------+------------------------+------------------------+-----------------+
| ROOT | News                   |                        |                 |
| ROOT | Countries              | Australia              | Queensland      |
| ROOT | Countries              | Australia              | Tasmania        |
| ROOT | Uncategorised Weblinks | Joomla! Specific Links | Other Resources |
+------+------------------------+------------------------+-----------------+

As you can see a hierarchy of only 3 levels requires a multi-level LEFT JOIN and every increment of the tree depth would require an additional LEFT JOIN. This makes working with Adjacency List Model difficult at best, but also performance would degrade quickly when the tree becomes really large. The beauty of the implementation within Joomla 1.6 is that the Adjacency List Model is implemented in combination with the Nested Set Model. That implicates that you can access the hierarchical data using the Adjacency List and Nested Set method.

In the Nested set model the hierarchy is organized in a new way, not as individual nodes but as nested containers. When we try to visualize this based upon the current available example data from Joomla 1.6 this would look like:

The hierarchy is still maintained as parent category envelop their children. For the Nested Set implementation the use of the left and right values have been added to represent the nesting of the individual nodes, lets take a look.

SELECT id, title, lft, rgt FROM jos_categories

+----+------------------------+-----+-----+
| id | title                  | lft | rgt |
+----|------------------------+-----+-----+
|  1 | ROOT                   |   0 |  17 |
| 11 | News                   |   1 |   2 |
| 12 | Countries              |   9 |  16 |
| 20 | Uncategorised Weblinks |   3 |   8 |
| 21 | Joomla! Specific Links |   4 |   7 |
| 22 | Other Resources        |   5 |   6 |
| 23 | Australia              |  10 |  15 |
| 24 | Queensland             |  11 |  12 |
| 25 | Tasmania               |  13 |  14 |
+----+------------------------+----+------+

The values for the left and right are determined by numbering the leftmost side of the outer node and continue to the right (see image above to get an idea how it is working). To get a full understanding of the way these data-sets are created and maintained I suggest you read up on the article of Mike Hillyer.

To get a full tree you need the following SQL statement:

SELECT node.title FROM jos_categories AS node, jos_categories AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND parent.title='ROOT' ORDER BY node.lft

+------------------------+
| title                  |
+------------------------+
| ROOT                   |
| News                   |
| Uncategorised Weblinks |
| Joomla! Specific Links |
| Other Resources        |
| Countries              |
| Australia              |
| Queensland             |
| Tasmania               |
+------------------------+

This statement always works regardless of the tree size and depth and also performance will be optimal since we do not have to join data here. The current implementation is targeted at a second alpha, or maybe a beta and can be used for some powerful application logic like a nested comment solution for content items. The current implementation though has limitations, for example when the tree is becoming big an insert of a node can take very long. Also when there are frequent tree insertions performance can drop dramatically (the table will be locked when a mutation is committed to the nested tree), this problem is solved most of the times by implementing a node spread (higher increments in the numbers so individual nodes can be inserted without renumbering the whole tree), as far as I can see this logic has not been implemented into the current code-base.

Another feature missing in the current implemented classes are Hardlinked Nested Sets as implemented in the Summer of Code work of 2007 by Enno Klassing. Hardlinked Nested Sets provide the possibility to clone whole branches of a tree, and keep them in sync afterwards. They are called hard-linked since one can think of them as hard-links in a *nix based file-system. Reading the tree is possible without any additional overhead - this distinguishes this data model from symlinks.

This article just gives a very brief overview of the new code that has gone into Joomla 1.6. To get a full and better understanding I suggest you read up on the article of Mike Hillyer describing the full theoretical background of this new piece of technology that has been put into 1.6.

Like it? Share it!

• bookmark.it
• del.icio.us
• digg
• furl
• blinkllist
• reddit
• feedmelinks
• technorati
• yahoo
• rawsugar
• netvouz
• rojo
• shadows
• gabbr
• dzone
• newsvine
• ma.gnolia
• stumbleupon
• google
• squidoo
• spurl
• blinkbits
• blogmarks
• bloglines
• co.mments
• scuttle
• ask
• slashdot