Class for managing nested set data

February 27, 2010

Zend Framework

There are several ways of realizing demand of storing hierarchical data in database, and most popular methods today are Adjacency List and Nested Set models. Both of these two approaches have some advantages and disadvantages… In Adjacency List model, adding and updating of nodes is fairly simple, but retrieving the whole tree is a real challenge. It's a different story with Nested Set model. Whole tree can be retrieved with a single query, but there are lot of things that need to be done when you need to make some changes in hierarchy. From the title of this article, it’s obvious which model is my favorite. :)

The purpose of my class is managing nested sets of data stored in a database. I made two versions of this class, one is for general PHP projects, and the other is for Zend Framework based projects. That second one is the reason why I've published this article. Both of those can be downloaded from my personal site, and here are the links:

NP_Db_Table_NestedSet class (ZF version) extends Zend_Db_Table, to provide custom functionality for working with database tables that have hierarchical data. And yes, I’ve namespaced it with “NP”, which represents my initials. :)

This class can be used the same way as when working with Zend_Db_Table class, which means that developers will usually extend this class in order to create Table Gateway for some database table. Beside protected variable $_name, NP_Db_Table_NestedSet requires two more additional variables to be supplied. As in nested set model hierarchy is represented by beginning and ending node hierarchy number, or with so called left and right values, this class has two protected variables – $_left and $_right, which must be redefined in order to use this class. Those two must be the names of existing left and right table columns. So, here’s an example of how your extending class can look like:

class Foo extends NP_Db_Table_NestedSet
{
    protected $_name = 'foo';

    protected $_left = 'lft';
	
    protected $_right = 'rgt';
}

… where “foo” is the name of your database table, and “lft” and “rgt” are names of left and right columns in that table.

NP_Db_Table_NestedSet class overrides insert() method, to provide adding of new nodes in hierarchy tree, by accepting two additional optional parameters. First of those two is the id of an objective node, or in other words, node in respect to new node which is being added, and the second parameter describes position where new node will be inserted, regarding on objective node id. Possible values for that last parameter are defined through four class constants: FIRST_CHILD, LAST_CHILD, NEXT_SIBLING and PREV_SIBLING, which means that new node can be added as first child, last child, next sibling or previous sibling of some objective node. LAST_CHILD is used as a default placement. Here’s an example of how new node can be inserted as a next sibling of some node whose id is 2:

$foo = new Foo();

$data = array(
    'title' => 'Test',
    'text'  => 'Some text',
    'date'  => '2010-02-27'
);
$foo->insert($data, 2, NP_Db_Table_NestedSet::NEXT_SIBLING);

For updating some changes in tree hierarchy, there is updateNode() method. This method accepts four parameters. The first three are required and those are: array with data, id of a node that is being updated and id of an objective node. The fourth parameter is optional and it is for the same purpose as the last one in insert() method. If you don’t need to update hierarchy-related data, you should use inherited update() method. Here’s an example of updating some node whose id is 3, to be the first child of a node whose id is 1:

$foo = new Foo();

$data = array(
    'title' => 'Test',
    'text'  => 'Some text'
);
$foo->updateNode($data, 3, 1, NP_Db_Table_NestedSet::LAST_CHILD);

Both insert() and updateNode() methods simply merge data that is supplied through their first parameter, with calculated left and right values, and then call inherited insert()/update() methods to do the actual inserting/updating. In addition, updateNode() method also makes sure that those left and right values remain “tight”, which is done through reduceWidth() method of this class.

Deleting of nodes can be effectively done by using deleteNode() method. This method accepts two parameters. The first one is the id of a node that needs to be deleted, and the second one is optional, and it tells whether all child nodes should be deleted, too. Here’s an example of deleting node with id 4, and all its children:

$foo = new Foo();

$foo->deleteNode(3, true);

Of course, you can still delete you data using inherited delete() method.

Now, let’s see what features for fetching data NP_Db_Table_NestedSet class has… This class overrides fetchAll() and fetchRow() methods to provide some custom options for fetching data. fetchAll() method accepts two additional optional parameters, which are injected between $where and $order parameters. The first one is boolean which tells whether data should be retrieved as tree. If this parameter is passed with boolean true value, special getTree() method is automatically called, and that method is used for retrieving whole tree of nested data. Returning rows will contain additional depth column, which can help in cases when there’s need for rendering that nested data, in a way that a developer can easily loop through the tree, adding <li></li> and <ul></ul> tags as the depth number increases/decreases. getTree() is declared public, so it can be accessed through instance of NestedSetDbTable class. On the other hand, if this parameter ($getAsTree) is omitted, or its value is boolean false, fetchAll() method will utilize inherited fetchAll() method to retrieve data. The second of those additional parameters is string, and if it is supplied, additional column, named after value of this argument, will be returned, containing id of a parent node. This is done through protected getSelect() method, which is used for generating query with that additional column.
The same story is with fetchRow() method, except, of course, it doesn’t have $getAsTree parameter as it is retrieving only one row.
Here are examples of using those fetching methods:

$foo = new Foo();

foreach ($foo->fetchAll('status = \'published\'', false, null, 'date DESC') as $f) {
   echo $f['title'] . '
'; } foreach ($foo->getTree('status = \'published\'') as $f) { echo str_repeat('-', (int)$f['depth']*2) . ' ' . $f['title'] . '
'; } $f = $foo->fetchRow('id = 2'); echo '

' . $f['title'] . '

'; echo $f['text'];

I think that this class can be very useful for developers as it provides simple API for doing challenging tasks with nested data. And if someone thinks that it can be included in Zend Framework project, maybe as a part of Zend_Db_Table component, I’ll be honored to contribute it. :)

Download Zend Framework version of this class

10 Responses to “Class for managing nested set data”

  1. yentsun Says:

    Thats what I’ve been thinking about. It just seems not too trivial at the first glance:) Thanks, Nikola. I’ll post some solutions here if I succeed – I guess it’ll be of use to other people.

  2. alokin Says:

    getTree() accepts additional where clause parameter that can be injected in query which is used for retrieving whole tree, so perhaps you can reach your goal by specifying some additional WHERE condition.

  3. yentsun Says:

    Hi Nikola!

    Thanks for your class – I am using it in one of my current projects. I would like to know is there a way to get a part of the tree, like, say "child tree for node 3"?

  4. ivaniordanov Says:

    There is another Zend Framework nested set class. I’ve developed it for my needs about 2 years ago. It still misses move functions but so far I don’t need them. It can be found at http://dev.iordanov.net/archives/8

  5. andreaswarnaar Says:

    When adding a where statement to the getTree() / fetchAll(). The depth value is set to ’0′.
    The tree can’t be ordered based on the depth value.

  6. andreaswarnaar Says:

    When updating a node with sub nodes, the existing order of the sub nodes and parent_id are skipped. This mess up the entire tree structure.
    Here an FIX:
    public function updateNode($data, $id, $objectiveNodeId, $position = self::LAST_CHILD,$recursive = true)
    {
    // First get current tree;
    if($recursive){
    $tree = $this->getTree(‘parent.page_id = ‘.$id);
    }
    $id = (int)$id;
    $objectiveNodeId = (int)$objectiveNodeId;

    if (!$this->checkNodePosition($position)) {
    //include_once(‘NP/Db/Table/NestedSet/Exception.php’);
    throw new App_Model_DbTable_NestedSet_Exception(‘Invalid node position is supplied.’);
    }

    if ($objectiveNodeId !== $this->getCurrentObjectiveId($id, $position)) { //Objective node differs?
    $this->reduceWidth($id);

    $data = array_merge($data, $this->getLftRgt($objectiveNodeId, $position, $id));
    }

    $primary = $this->getAdapter()->quoteIdentifier($this->_primary[1]);
    $where = $this->getAdapter()->quoteInto($primary . ‘ = ?’, $id, Zend_Db::INT_TYPE);

    $this->update($data, $where);
    if($recursive){
    if(count($tree->toArray() ) > 0){
    foreach($tree->toArray()as $node){
    if($node['page_id'] == $id) continue;
    $this->updateNode(array(), $node['page_id'], $node['parent_id'],self::LAST_CHILD,false);
    }
    }
    }
    return true;

  7. altamash Says:

    I assume that u are using zf mvc(Model, View, Controller) pattern. And your model class is driven from zend_db_table_abstract.

    Then in the ‘IndexController’ action ‘indexAction’

    Write $your_tablename = new Application_Model_DbTable_Yourtablename();

    // then
    $this->view->data = $your_tablename->fetchAll(" ename=’smith’ AND id=520");

    I hope this help.

  8. venkatadry Says:

    SELECT * FROM emp WHERE ename=’smith’ AND id=520

    please tell me how to implement this qury in zend frame work

  9. alokin Says:

    For your information, that article inspired me to start creating my class. :)

    Nested set model is a powerful method, and I can’t believe I didn’t hear of it earlier.

  10. ldronkers Says:

    Thanks for sharing this. I am surely going to give it a try.

    I just recently red this article: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html and was amazed by the method, we just needed an implementation for php/zend. And you did.

    I will give feedback after using it.

    Cheers

    Leonard