Nested set model practical examples, part II.

In the second part I will demonstrate how to find and select required data from the tree and full tree structure.

Almost all reqests in the nested sets are based on the self JOIN query. So the very basic query can be like following:

SELECT n.node_id
  FROM tree_map AS n, tree_map AS p
 WHERE n.lft BETWEEN p.lft AND p.rgt
 GROUP BY node_id
 ORDER BY n.lft;

Retrieve a Tree

Suitable for
  • select boxes

In many situations you will need to get full tree structure. In the first part how to use r_tree_traversal() procedure I'm using another MySQL stored procedure r_return_tree() for this purpose.
To get a full tree call the procedure with NULL parameter. When you don't want to show a specific node in the tree, call procedure with node id you need to hide. (You may find this useful during moving or sorting process.)

mysql> call r_return_tree(NULL,'en');
+---------+---------------------+
| node_id | name                |
+---------+---------------------+
|       1 | Home                |
|       2 |  . . HTML&CSS       |
|       3 |  . . JS             |
|       4 |  . . PHP            |
|       6 |  . .  . . Debugging |
|       5 |  . .  . . Cloud     |
+---------+---------------------+

Another example is when you need to know the node depth. You can make some actions depending on that, like add css style or a new html list for example.

Suitable for
  • where node depth is required
  • menu structure
  • discussion comments
mysql> call r_return_tree_depth('en');
+---------+-------+-----------+
| node_id | depth | name      |
+---------+-------+-----------+
|       1 |     0 | Home      |
|       2 |     1 | HTML&CSS  |
|       3 |     1 | JS        |
|       4 |     1 | PHP       |
|       6 |     2 | Debugging |
|       5 |     2 | Cloud     |
+---------+-------+-----------+

Finding subtrees

Suitable for
  • where only node descendants are required
  • check if node is in the selected branch
  • navigation submenu

Any node in the tree is the root of a subtree. This is where tree traversal Rule 2 from first part may help. So all the descendants in a branch can be found by looking for nodes whose lft and rgt are between the lft and rgt values of their parent node. For this purposes you can use r_return_subtree() stored procedure.

Finding subtree where PHP (node_id = 4) is a parent.

mysql> call r_return_subtree(4,'en');
+---------+-------+-----------+
| node_id | depth | name      |
+---------+-------+-----------+
|       4 |     0 | PHP       |
|       6 |     1 | Debugging |
|       5 |     1 | Cloud     |
+---------+-------+-----------+

Return node path in a Tree

Suitable for
  • breadcrumbs
  • URL path compilation

For path mapping I'm using r_return_path() where SQL is similar to r_return_tree() stored procedure. It returns path from root to current node. Call the procedure with node_id as a parameter.

Let's display the path of node Cloud (node_id = 5):

mysql> call r_return_path(5,'en');
+---------+-------+
| node_id | name  |
+---------+-------+
|       1 | Home  |
|       4 | PHP   |
|       5 | Cloud |
+---------+-------+

 

Tree structure and Zend Framework navigation container

Now you can get easily full tree structure with one stored procedure call. If you are using nested set model for storing website navigation, it is all right to call stored procedure with every request on low traffic websites (in my opinion). But for performance boost it's better to put structure into XML file that we can store in a cache if needed.

I'm using Zend Framework in my projects and generating site structure into XML file is all that I need to have navigation, breadcrumbs and sitemap under control in the framework. Any changes in the navigation tree are updated into XML file from admin section. SQL requests related with navigation/breadcrumbs/sitemap are not needed then.

XML navigation structure we can put into Zend Framework 2 navigation container may look like following:

<?xml version="1.0" encoding="UTF-8"?>
<config>
<navigation>
<front>
<p0_1_1>
<label>Home</label>
<uri>/</uri>
</p0_1_1>
<p1_1_2>
<label>HTML CSS</label>
<uri>/html-css</uri>
</p1_1_2>
<p2_1_3>
<label>JS</label>
<uri>/js</uri>
</p2_1_3>
<p3_1_4>
<label>PHP</label>
<uri>/php</uri>
<class>dropdown</class>
<pages>
<p3_2_1>
<label>Cloud</label>
<uri>/php/cloud</uri>
</p3_2_1>
<p3_2_2>
<label>Debugging</label>
<uri>/php/debugging</uri>
</p3_2_2>
</pages>
</p3_1_4>
</front>
</navigation>
</config>

Just try it

I hope that both articles made it easier for you to understand the basic concept of Nested set model and will help you to save time on your project. You can find more in Joe Celko's book. I remember I spent over a week with the main procedure r_tree_traversal() to create and is tested over 6 years already.

Footnotes

  1. If you need more explanation about different types of data hierarchies and models I recommend Joe Celko's book Trees and hierarchies in SQL for Smarties.
  2. Managing Hierarchical Data in MySQL, Mike Hillyer's blog.
  3. I also recommend MySQL Stored Procedure Programming book by Guy Harrison with Steven Feuerstein to realize full potential of MySQL stored programs.