PHPRO.ORG

Managing Hierarchical Data with PHP and MySQL

Managing Hierarchical Data with PHP and MySQL

by Kevin Waterson

Contents

  1. What is Hierarchical Data?
  2. Getting Started
  3. Finding all the Leaf Nodes
  4. Retrieving a Single Path
  5. Finding the Depth of the Nodes
  6. Depth of a Sub-Tree
  7. Get Local Sub-Tree Depth
  8. Product Count
  9. Adding New Nodes
  10. Adding a Child Node
  11. Deleting a Node
  12. Delete Node Recursive
  13. Putting it all together
  14. Connection Class
  15. 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".

CREATE TABLE categories (
category_id int(11) NOT NULL auto_increment,
name varchar(20) NOT NULL,
left_node int(11) NOT NULL,
right_node int(11) NOT NULL,
PRIMARY KEY (category_id)
);

INSERT INTO categories (category_id, name, left_node, right_node) VALUES
(1, 'electronics', 1, 20),
(2, 'televisions', 2, 9),
(3, 'tube', 3, 4),
(4, 'lcd', 5, 6),
(5, 'plasma', 7, 8),
(6, 'portable electronics', 10, 19),
(7, 'mp3 players', 11, 14),
(8, 'flash', 12, 13),
(9, 'cd players', 15, 16),
(10, '2 way radios', 17, 18);

CREATE TABLE products (
product_id int(11) NOT NULL auto_increment,
name varchar(40) default NULL,
category_id int(11) NOT NULL,
PRIMARY KEY (product_id)
);

INSERT INTO products (product_id, name, category_id) VALUES
(1, '20" TV', 3),
(2, '36" TV', 3),
(3, 'Super-LCD 42"', 4),
(4, 'Ultra-Plasma 62"', 5),
(5, 'Value Plasma 38"', 5),
(6, 'Power-MP3 5gb', 7),
(7, 'Ipod 4gb', 8),
(8, 'Porta CD', 9),
(9, 'Walkman', 9),
(10,'Family Talk 360', 10);

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..

<?php
class hierachy{

/***
 *
 * @fetch the full tree
 *
 * @param string $parent
 *
 * @return array
 *
 */
public function fullTree($parent){
$stmt conn::getInstance()->prepare("SELECT node.name FROM categories AS node, categories AS parent
WHERE node.left_node BETWEEN parent.left_node AND parent.right_node
AND parent.name = :parent ORDER BY node.left_node"
);
$stmt->bindParam('parent'$parent);
$stmt->execute();
$res $stmt->fetchALL(PDO::FETCH_ASSOC);
return 
$res;
}

/*** end of class ***/
?>

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

<?php
/*** a new hierachy instance ***/
$hierachy = new hierachy;
$iterator = new RecursiveIteratorIterator(new recursiveArrayIterator($hierachy->fullTree('electronics')));
try {
    foreach(
$iterator as $key=>$value)
        {
        echo 
$value.'<br />';
        }
    }
catch(
Exception $e)
    {
    echo 
$e->getMessage();
    }

?>

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


electronics<br />
televisions<br />
tube<br />lcd<br />
plasma<br />
portable electronics<br />
mp3 players<br />
flash<br />
cd players<br />
2 way radios<br />

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

televisions
tube
lcd
plasma

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:

<?php
/**
 *
 * Find all leaf nodes
 *
 * @access public
 *
 * @return array
 *
 */
public function leafNodes(){
$stmt conn::getInstance()->prepare("SELECT name FROM categories WHERE right_node = left_node + 1");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}
?>

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.

<?php
$iterator 
= new RecursiveIteratorIterator(new recursiveArrayIterator($hierachy->leafNodes()));
try {
    foreach(
$iterator as $key=>$value)
        {
        echo 
$value.'<br />';
        }
    }
catch(
Exception $e)
    {
    echo 
$e->getMessage();
    }
?>

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.

<?php
/**
 *
 * Retrieve a single path
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function singlePath($node_name){
$stmt conn::getInstance()->prepare("SELECT parent.name FROM categories AS node, categories AS parent WHERE node.left_node BETWEEN parent.left_node AND parent.right_node AND node.name = '{$node_name}' ORDER BY parent.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}
?>

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.

<?php
/**
 *
 * Retrieve a depth of nodes
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function getNodeDepth(){
$stmt conn::getInstance()->prepare("SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM categories AS node, categories AS parent WHERE node.left_node BETWEEN parent.left_node AND parent.right_node GROUP BY node.name ORDER BY node.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}
?>

And to see the nodes it is simply a matter of crunching through the array...

<?php
$iterator 
= new RecursiveIteratorIterator(new recursiveArrayIterator($hierachy->getNodeDepth()));
try {
    foreach(
$iterator as $key=>$value)
        {
        echo 
$key.' -- '.$value.'<br />';
        }
    }
catch(
Exception $e)
    {
    echo 
$e->getMessage();
    }
?>

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.

<?php
/**
 *
 * Retrieve a subTree depth
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function subTreeDepth($node_name){
$stmt conn::getInstance()->prepare("SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM categories AS node, categories AS parent WHERE node.left_node BETWEEN parent.left_node AND parent.right_node AND node.name = '{$node_name}' GROUP BY node.name ORDER BY node.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}
?>

To fetch the sub tree depth is the same as previous...

<?php
$iterator 
= new RecursiveIteratorIterator(new recursiveArrayIterator($hierachy->subTreeDepth('portable electronics')));
try {
    foreach(
$iterator as $key=>$value)
        {
        echo 
$key.' -- '.$value.'<br />';
        }
    }
catch(
Exception $e)
    {
    echo 
$e->getMessage();
    }
?>

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:

<?php
/**
 *
 * @fetch local sub nodes only
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function getLocalSubNodes($node_name){
$stmt conn::getInstance()->prepare(" SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth FROM categories AS node, categories AS parent, categories AS sub_parent,
        (
        SELECT node.name, (COUNT(parent.name) - 1) AS depth
        FROM categories AS node,
        categories AS parent
        WHERE node.left_node BETWEEN parent.left_node AND parent.right_node
        AND node.name = :node_name
        GROUP BY node.name
        ORDER BY node.left_node
        )AS sub_tree
WHERE node.left_node BETWEEN parent.left_node AND parent.right_node
AND node.left_node BETWEEN sub_parent.left_node AND sub_parent.right_node
AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.left_node"
);
$stmt->bindParam(':node_name'$node_namePDO::PARAM_STR);
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}
?>

And once again, to access the returned array, we simply iterate over the object..

<?php
$iterator 
= new RecursiveIteratorIterator(new recursiveArrayIterator($hierachy->getLocalSubNodes('portable electronics')));
try {
    foreach(
$iterator as $key=>$value)
        {
        echo 
$key.' -- '.$value.'<br />';
        }
    }
catch(
Exception $e)
    {
    echo 
$e->getMessage();
    }
?>

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.

<?php
/**
 *
 * @list categories and product count
 *
 * @access public
 *
 * @return array
 *
 */
public function productCount(){
$stmt conn::getInstance()->prepare("SELECT parent.name, COUNT(products.name) AS product_count FROM categories AS node ,categories AS parent, products  WHERE node.left_node BETWEEN parent.left_node AND parent.right_node AND node.category_id = products.category_id GROUP BY parent.name ORDER BY node.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}
?>

Once more we access with an SPL iterator...

<?php
$iterator 
= new RecursiveIteratorIterator(new recursiveArrayIterator($hierachy->productCount()));
try {
    foreach(
$iterator as $key=>$value)
        {
        echo 
$key.' -- '.$value.'<br />';
        }
    }
catch(
Exception $e)
    {
    echo 
$e->getMessage();
    }
?>

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.

<?php
/**
 *
 * @add a node
 *
 * @access public
 *
 * @param string $left_node
 *
 * @param string $new_node
 *
 */
public function addNode($left_node$new_node){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myRight := right_node FROM categories WHERE name = :left_node");
    
$stmt->bindParam(':left_node'$left_node);
    
$stmt->execute();
    
/*** increment the nodes by two ***/
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node + 2 WHERE right_node > @myRight");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node + 2 WHERE left_node > @myRight");
    
/*** insert the new node ***/
    
$stmt conn::getInstance()->prepare("INSERT INTO categories(name, left_node, right_node) VALUES(:new_node, @myRight + 1, @myRight + 2)");
    
$stmt->bindParam(':new_node'$new_node);
    
$stmt->execute();
    
/*** commit the transaction ***/
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}

?>

To make the addNode() method work..

<?php
 $hierachy
->addNode('televisions''game consoles');
 echo 
'new node added';
?>

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.

<?php
/**
 *
 * @Add child node
 * @ adds a child to a node that has no children
 *
 * @access public
 *
 * @param string $node_name The node to add to
 *
 * @param string $new_node The name of the new child node
 *
 * @return array
 *
 */
public function addChildNode($node_name$new_node){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myLeft := left_node FROM categories WHERE name=:node_name");
    
$stmt->bindParam(':node_name'$node_name);
    
$stmt->execute();
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node + 2 WHERE right_node > @myLeft");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node + 2 WHERE left_node > @myLeft");
    
$stmt conn::getInstance()->prepare("INSERT INTO categories(name, left_node, right_node) VALUES(:new_node, @myLeft + 1, @myLeft + 2)");
    
$stmt->bindParam(':new_node'$new_node);
    
$stmt->execute();
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}

?>

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

<?php
$hierachy
->addChildNode('2 way radios''uhf');
echo 
'New Child Node Added';
?>

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:

<?php
/**
 *
 * @Delete a leaf node
 *
 * @param string $node_name
 *
 * @access public
 *
 */
public function deleteLeafNode($node_name){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myLeft := left_node, @myRight := right_node, @myWidth := right_node - left_node + 1 FROM categories WHERE name = :node_name");
    
$stmt->bindParam(':node_name'$node_name);
    
$stmt->execute();
    
conn::getInstance()->exec("DELETE FROM categories WHERE left_node BETWEEN @myLeft AND @myRight;");
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node - @myWidth WHERE right_node > @myRight");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node - @myWidth WHERE left_node > @myRight");
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}
?>

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

<?php
 $hierachy
->deleteLeafNode('game consoles');
?>

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.

<?php
/**
 *
 * @Delete a node and all its children
 *
 * @access public
 *
 * @param string $node_name
 *
 */
public function deleteNodeRecursive($node_name){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myLeft := left_node, @myRight := right_node, @myWidth := right_node - left_node + 1 FROM categories WHERE name = :node_name");
    
$stmt->bindParam(':node_name'$node_name);
    
$stmt->execute();
    
conn::getInstance()->exec("DELETE FROM categories WHERE left_node BETWEEN @myLeft AND @myRight");
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node - @myWidth WHERE right_node > @myRight");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node - @myWidth WHERE left_node > @myRight");
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}
?>

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.

<?php
 $hierachy
->deleteNodeRecursive('mp3 players');
?>

Putting it all together

Here we present the entire class for managing the hierarchical data.

<?php
class hierachy{

/***
 *
 * @fetch the full tree
 *
 * @param string $parent
 *
 * @return array
 *
 */
public function fullTree($parent){
$stmt conn::getInstance()->prepare("SELECT node.name FROM categories AS node, categories AS parent
WHERE node.left_node BETWEEN parent.left_node AND parent.right_node
AND parent.name = :parent ORDER BY node.left_node"
);
$stmt->bindParam('parent'$parent);
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}

/**
 *
 * Find all leaf nodes
 *
 * @access public
 *
 * @return array
 *
 */
public function leafNodes(){
$stmt conn::getInstance()->prepare("SELECT name FROM categories WHERE right_node = left_node + 1");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}

/**
 *
 * Retrieve a single path
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function singlePath($node_name){
$stmt conn::getInstance()->prepare("SELECT parent.name FROM categories AS node, categories AS parent WHERE node.left_node BETWEEN parent.left_node AND parent.right_node AND node.name = '{$node_name}' ORDER BY node.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}


/**
 *
 * Retrieve a depth of nodes
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function getNodeDepth(){
$stmt conn::getInstance()->prepare("SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM categories AS node, categories AS parent WHERE node.left_node BETWEEN parent.left_node AND parent.right_node GROUP BY node.name ORDER BY node.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}

/**
 *
 * Retrieve a subTree depth
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function subTreeDepth($node_name){
$stmt conn::getInstance()->prepare("SELECT node.name, (COUNT(parent.name) - 1) AS depth FROM categories AS node, categories AS parent WHERE node.left_node BETWEEN parent.left_node AND parent.right_node AND node.name = :node_name GROUP BY node.name ORDER BY node.left_node");
$stmt->bindParam(':node_name'$node_namePDO::PARAM_STR);
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}

/**
 *
 * @fetch local sub nodes only
 *
 * @access public
 *
 * @param $node_name
 *
 * @return array
 *
 */
public function getLocalSubNodes($node_name){
$stmt conn::getInstance()->prepare(" SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth FROM categories AS node, categories AS parent, categories AS sub_parent,
    (
    SELECT node.name, (COUNT(parent.name) - 1) AS depth
    FROM categories AS node,
    categories AS parent
    WHERE node.left_node BETWEEN parent.left_node AND parent.right_node
    AND node.name = :node_name
    GROUP BY node.name
    ORDER BY node.left_node
    )AS sub_tree
WHERE node.left_node BETWEEN parent.left_node AND parent.right_node
    AND node.left_node BETWEEN sub_parent.left_node AND sub_parent.right_node
    AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth <= 1
ORDER BY node.left_node"
);
$stmt->bindParam(':node_name'$node_namePDO::PARAM_STR);
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}

/**
 *
 * @list categories and product count
 *
 * @access public
 *
 * @return array
 *
 */
public function productCount(){
$stmt conn::getInstance()->prepare("SELECT parent.name, COUNT(products.name) AS product_count FROM categories AS node ,categories AS parent, products  WHERE node.left_node BETWEEN parent.left_node AND parent.right_node AND node.category_id = products.category_id GROUP BY parent.name ORDER BY node.left_node");
$stmt->execute();
return 
$stmt->fetchALL(PDO::FETCH_ASSOC);
}


/**
 *
 * @add a node
 *
 * @access public
 *
 * @param string $left_node
 * 
 * @param string $new_node
 *
 */
public function addNode($left_node$new_node){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myRight := right_node FROM categories WHERE name = :left_node");
    
$stmt->bindParam(':left_node'$left_node);
    
$stmt->execute();
    
/*** increment the nodes by two ***/
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node + 2 WHERE right_node > @myRight");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node + 2 WHERE left_node > @myRight");
    
/*** insert the new node ***/
    
$stmt conn::getInstance()->prepare("INSERT INTO categories(name, left_node, right_node) VALUES(:new_node, @myRight + 1, @myRight + 2)");
    
$stmt->bindParam(':new_node'$new_node);
    
$stmt->execute();
    
/*** commit the transaction ***/
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}


/**
 *
 * @Add child node
 * @ adds a child to a node that has no children
 *
 * @access public
 *
 * @param string $node_name The node to add to
 *
 * @param string $new_node The name of the new child node
 *
 * @return array
 *
 */
public function addChildNode($node_name$new_node){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myLeft := left_node FROM categories WHERE name=:node_name");
    
$stmt->bindParam(':node_name'$node_name);
    
$stmt->execute();
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node + 2 WHERE right_node > @myLeft");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node + 2 WHERE left_node > @myLeft");
    
$stmt conn::getInstance()->prepare("INSERT INTO categories(name, left_node, right_node) VALUES(:new_node, @myLeft + 1, @myLeft + 2)");
    
$stmt->bindParam(':new_node'$new_node);
    
$stmt->execute();
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}

/**
 *
 * @Delete a leaf node
 *
 * @param string $node_name
 *
 * @access public
 *
 */
public function deleteLeafNode($node_name){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myLeft := left_node, @myRight := right_node, @myWidth := right_node - left_node + 1 FROM categories WHERE name = :node_name");
    
$stmt->bindParam(':node_name'$node_name);
    
$stmt->execute();
    
conn::getInstance()->exec("DELETE FROM categories WHERE left_node BETWEEN @myLeft AND @myRight");
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node - @myWidth WHERE right_node > @myRight");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node - @myWidth WHERE left_node > @myRight");
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}

/**
 *
 * @Delete a node and all its children
 *
 * @access public
 *
 * @param string $node_name
 *
 */
public function deleteNodeRecursive($node_name){
try {
    
conn::getInstance()->beginTransaction();
    
$stmt conn::getInstance()->prepare("SELECT @myLeft := left_node, @myRight := right_node, @myWidth := right_node - left_node + 1 FROM categories WHERE name = :node_name");
    
$stmt->bindParam(':node_name'$node_name);
    
$stmt->execute();
    
conn::getInstance()->exec("DELETE FROM categories WHERE left_node BETWEEN @myLeft AND @myRight");
    
conn::getInstance()->exec("UPDATE categories SET right_node = right_node - @myWidth WHERE right_node > @myRight");
    
conn::getInstance()->exec("UPDATE categories SET left_node = left_node - @myWidth WHERE left_node > @myRight");
    
conn::getInstance()->commit();
    }
catch(
Exception $e)
    {
    
conn::getInstance()->rollBack();
    throw new 
Exception($e);
    }
}


/*** end of class ***/
?>

Connection Class

<?php

class conn{

/*** Declare instance ***/
private static $instance NULL;

/**
*
* the constructor is set to private so
* so nobody can create a new instance using new
*
*/
private function __construct() {
  
/*** maybe set the db name here later ***/
}

/**
*
* Return DB instance or create intitial connection
*
* @return object (PDO)
*
* @access public
*
*/
public static function getInstance() {

if (!
self::$instance)
    {
    
self::$instance = new PDO("mysql:host=localhost;dbname=hierachy"'username''password');
    
self::$instance-> setAttribute(PDO::ATTR_ERRMODEPDO::ERRMODE_EXCEPTION);
    }
return 
self::$instance;
}

/**
*
* Like the constructor, we make __clone private
* so nobody can clone the instance
*
*/
private function __clone(){
}

/*** end of 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