Hierarchical Data with PHP and MySQL

What is Hierarchical Data?
Getting Started
Finding all the Leaf Nodes
Retrieving a Single Path
Finding the Depth of the Nodes
Depth of a Sub-Tree
Get Local Sub-Tree Depth
Product Count
Adding New Nodes
Adding a Child Node
Deleting a Node
Delete Node Recursive
Putting it all together
Connection Class
Credits

What is Hierarchical Data?

Traditionally, hierachical data is the realm of XML as a relational database is not hierarchical. Managing hierarchical data with a database poses several issues in establishing a parent/child relationship that is dynamic. There are several ways of approaching this issue, and here we explore the Nested Set Model, which allows us to contain each child within the parent. Each node has a single parent (except for the root node) and may have zero or more child nodes. To demonstrate how this works see the diagram below.
hierachy
Getting Started

To help guide us through this tutorial we will be using a MySQL database with two tables, categories and products. The SQL dump is provided here. The name of the database is “hierachy”.

Getting Started
To begin with we will create a class to carry out the work of retrieving result sets from the database. A helper class will also be included to connect to the database. It is a singleton pattern and is shown below. The connection class will not be included in any of the scripts here for sanity reasons. You may either include the database class or simply add it to the bottom of any of the scripts you see here. Savvie?

The first method to go in the class should be something to retrieving the full tree. Lets begin..

The fullTree method returns an arry of arrays. We can use an SPL iterator to “flatten” the array and print out our tree.

This method will work regardless of the depth of the tree and simple display can be seen of the entire tree like this:

You could of course change the parent to televisions and you would get an array like this:

Finding all the Leaf Nodes

Because the left and right leaf nodes are consicutive numbers we can simply look for nodes where right_node = left_node + 1. The class method will look like this:

To access the leaf nodes is a simple task as shown here. Once again, the class method returns an array of arrays and we can use SPL goodness to simplify the iteration.

The above code will produce of leaf nodes like this:
tube
lcd
plasma
flash
cd players
2 way radios
Retrieving a Single Path

Using the nested set model allows us to retrieve a single path without messy multiple self-joins. Here we show how to fetch the flash node path.

The single path result will look like this:
electronics
portable electronics
mp3 players
flash

This shows that “flash” is in the mp3 players category, which in turn, is in the portable electronics category which is within the root electronics category. As a path it may be expressed as
/electronics/portable electronics/mp3 players/flash
Finding the Depth of the Nodes

The full tree method can be altered a little to produce a listing of each node with its depth. This may be used as a menu hierachy and the depth could be used for placing node names within the menu.

The list of names and depth is presented like this:
name — electronics
depth — 0
name — televisions
depth — 1
name — tube
depth — 2
name — lcd
depth — 2
name — plasma
depth — 2
name — portable electronics
depth — 1
name — mp3 players
depth — 2
name — flash
depth — 3
name — cd players
depth — 2
name — 2 way radios
depth — 2
Depth of a Sub-Tree

Retrieving the depth of an indivdual sub tree is a little more complex and requires the addition of another self join and a sub-query.

This will give the name and depth as follows.
name — portable electronics
depth — 1
Get Local Sub-Tree Depth

Suppose now you wish to get all the local, or subordinate, nodes of a category. These are the nodes, or categories, immediately below the specified category, but no deeper within the tree. So if we were to show the Portable Electronics category, we would want to see Mp3 Players, CD Players and 2 Way Radio’s, but not the Flash category. So we need to limit our query to those categories HAVING depth less than or equal to one. (HAVING depth < = 1). Our class method will look like this:

And the resulting output will look like this.. name -- portable electronics depth -- 0 name -- mp3 players depth -- 1 name -- cd players depth -- 1 name -- 2 way radios depth -- 1 Product Count So far we have dealt with the categories and sub categories within our hierachy. Now lets introduce the products from the products table. To begin with a simple category tree with a count for each category. Basically what we need is the same as our earlier full tree view, with a count of each product, related to the category.

Once more we access with an SPL iterator...

From the above snippet we can see the name of each category and the product count of each sub-category within as shown here: name -- electronics product_count -- 10 name -- televisions product_count -- 5 name -- tube product_count -- 2 name -- lcd product_count -- 1 name -- plasma product_count -- 2 name -- mp3 players product_count -- 2 name -- portable electronics product_count -- 5 name -- flash product_count -- 1 name -- cd players product_count -- 2 name -- 2 way radios product_count -- 1 Adding New Nodes Now that we can query the tree and get sub-trees and product counts, lets see about adding a new Node. Lets look back at our original container diagram. hierachy To add a new node between Televisions and Portable Electronics then the new node would have left_node = 10 and right_node = 11. All nodes to the right would have to have thier left_node and right_node values incremented by two to adjust for the extra node. To expediate this process we can use a transaction.

To make the addNode() method work..

Adding a Child Node Adding a node as above gives us a parent, but what if we wish to add a child of a node that has no children? Here we will add "uhf" as a child node of "2 way radios". This entails expending everything to the right of the left_node of the new parent and placing the node to the right of the left_node value. Here is the class method to do it.

With the class method in place it is a simple matter to execute from your user space code.

Deleting a node Now that we can add nodes we need to be able to delete them. Deleting leaf nodes is easier than deleting parent nodes with children as the orphaned nodes need to be handled. To delete a leaf node is the opposite of adding a new node. We delete the node and its width from every node to its right:

To delete the node "game consoles" it is now a simple matter of passing the correct node name to the method.

Delete Node Recursive With a little revision, we can us this same approach as above to delete a whole parent node and all its children.

To delete the "mp3 players" node and all its child nodes, we simply call the above method in our code, passing the node name as its single arguement.

Putting it all together Here we present the entire class for managing the hierarchical data.

Connection Class

Credits This tutorial follows on from the work of Mike Hillyer of MySQL AB. His original tutorial can be found at http://dev.mysql.com/tech-resources/articles/hierarchical-data.html