FuelPHP, a PHP 5.3 Framework Documentation

Introduction

This introduction is based on this article, (c) James Simpson.

The nested set model is a particular technique for representing nested sets (also known as trees or hierarchies) in relational databases. The term was apparently introduced by Joe Celko; others describe the same technique without naming it or using different terms. (Source: Wikipedia)

A typical example of a tree structure is an organigram of an organisation. We'll be using this to explain how nested sets work.

The above diagram is indicating that each node is aware of all its descendants, and vice versa. For example, we can see easily enough from the diagram that Ben and Angela are "children" of Bill. We can also see that Tim and James are "children" of Ben. This ultimately gives us a link between each member of the hierarchy.

For us to represent this we need to store two more values per node, that define the relationship between the nodes of the tree structure. These are shown on the diagram in blue and red. We call these Left (red values) and Right (blue values) pointers. These values are stored on the table, this is all we need to fully represent a nested sets hierarchy.

Those who are into Mathematics know that you can use a different diagram to represent tree structures:

Although this might look confusing at first, and certainly more difficult to read, it is immediately clear why this is called nested sets, and why this way of storing hierarchical data in a flat table is efficient: you can directly see the relation between parent and children (all children are contained within their parent), and every node is aware of its parent, and all its descendants. Using this representation you can clearly see that all pointers line up beautifully. This will come in very handy when we need to access the tree.

Storing multiple tree structures in a single table

You can store multiple tree structures into a single database table. To make this possible, you can add a tree-id column to the table. The tree-id identifies the tree the node belongs to.

A tree-id may either be an integer or a string, and it can be auto-generated for you when you create a new tree, in case integers are used. Integers also make it easier to use the tree-id as a foreign key in a one-to-many relation, and their index lookup in the database is faster. It's strongly suggested you don't use a string value as a tree-id.

Table structure

You can add as many columns to the table as you want, but to be able to work, the Nestedset Model requires certain columns to be present:

• Left node pointer, default column name is 'left_id'
• Right node pointer, default column name is 'right_id'
• Tree id, a required column only if the table contains multiple trees (no default)

The actual names of the columns used for these functions can be configured in the model. Altough not strictly needed, several methods require a "title" or "name" field. The name of this column can be configured in the model as well. If you use a method that requires it to be present, but you haven't defined it, an exception will be thrown.

This is a minumal stucture for a nested sets table:

CREATE TABLE `tree` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `left_id` int(11) unsigned NOT NULL,
  `right_id` int(11) unsigned NOT NULL,
  `tree_id` int(11) unsigned NOT NULL,
  `name` varchar(50),
  PRIMARY KEY (`id`),
  KEY `left_id` (`left_id`),        // optional, might speed up certain lookups
  KEY `right_id` (`right_id`),      // optional, might speed up certain lookups
)

Configuration

The Nestedset Model adds an additional property, $_tree, to the model, with which you can configure the model:

• left_field defines the name of the table column that is used to store the tree's left pointer. The column name defaults to "left_id".
• right_field defines the name of the table column that is used to store the tree's right pointer. The column name defaults to "right_id".
• tree_field defines the name of the table column that is used to store the tree's id, a value that uniquely identifies a tree in case you want to store multiple trees in a single table. If you use a numeric value as tree-id, the model can automatically assign it when you create new tree root nodes. If it is not numeric, you have to supply the value before you call save(). There is no default value.
• title_field defines the name of the table column that is used to store the tree node's title or name. It is optional, the Model works well without it, but it is required for some of the models methods. Where applicable this is mentioned in the documentation of the method. There is no default value.

The next section show you what a basic Nestedset model looks like, and how you configure it.

Defining the model

Using the nested sets model is as easy as extending \Orm\Model_Nestedset instead of \Orm\Model. This marks your model as being a nested sets model, adds a lot of methods to manipulate trees and nodes, and changes the default behaviour of the delete() and save() methods to make sure the tree stays consistent.

<?php
class Model_Tree extends \Orm\Model_Nestedset
{
	/**
	* @var  string  name of the table to be used by this model
	*/
    protected static $_table_name = 'tree';

	/**
	 * @var  array  array of object properties
	 */
    protected static $_properties = array(
		'id',
		'left_id',
		'right_id',
		'tree_id',
		'name',
    );

	/**
	 * @var  array  array with the tree configuration
	 */
    protected static $_tree = array(
		'left_field'     => 'left_id',		// name of the tree node left index field
		'right_field'    => 'right_id',		// name of the tree node right index field
		'tree_field'     => 'tree_id',		// name of the tree node tree index field
		'title_field'    => 'name',		//  name of the tree node title field
    );

}
?>

As you can see, a pretty standard ORM model configuration. The only additional class property is $_tree, which defines the tree configuration. The model is then set up like a normal ORM model, including any relations or other properties that you wish to use.

Using the model

Based on the example in the introduction and the model defined above, let's start by creating this tree.

<?php
// Bill, our MD, is the root of the tree
$bill = Model_Tree::forge(array('name' => 'Bill'));

// if you save a new node, it will automatically become a tree root node
$bill->save();

// give our MD some subordinates
$angela = Model_Tree::forge(array('name' => 'Angela'));
$ben = Model_Tree::forge(array('name' => 'Ben'));

// they are children of Bill in the tree
$angela->child($bill)->save();
$ben->child($bill)->save();

// add the rest of Customer service
$henry = Model_Tree::forge(array('name' => 'Henry'));
$henry->child($angela)->save();
$nicola = Model_Tree::forge(array('name' => 'Nicola'));
$nicola->child($angela)->save();

// and the development team
$kerry = Model_Tree::forge(array('name' => 'Kerry'));
$kerry->child($ben)->save();
// a sibling of Kerry is a child of Ben too...
$james = Model_Tree::forge(array('name' => 'James'));
$james->sibling($kerry)->save();

// assign the teams benjamin to Kerry
$tim = Model_Tree::forge(array('name' => 'Tim'));
$tim->child($kerry)->save();
?>

As you can see, creating a tree and adding tree nodes is pretty straitforward. One of the main differences between the Nestedset model and other ORM models, it that is has methods that operate on other model objects. You don't just query the model, or save an object, you do it in relation to another object in the tree. That doesn't mean you can't use the traditional methods, Model::find() and Model::query() still work like for any other ORM model.

Let's move on to describing the methods that are available for getting information out of our tree and manupulating the tree structure.

Behavioral changes

In addition to the primary key, which is read-only in every ORM model object once set, a Nestedset model doesn't allow you to make changes to the left- and right pointers of the node, and to the tree-id if defined. Attempting to do so, either via assigment, using a call to set() or by using unset(), will result in a InvalidArgumentException.

Collection methods

Collection methods are methods that allow you to perform an operation, either a get() or a save(), on a part of a nestedset tree. Some methods are available for both, some are only relevant for one. For clarity, they are documented seperately. Using a collection method on an operation that doesn't support it will cause an OutOfBoundsException to be thrown.

Collection methods for getting nodes

Like with standard ORM models, you can use the get() method to return an array of objects, and the get_one() method to return a single object. If a collection method is supposed to return a single result, like for example root(), get() will return an array with that single object. If a collection method returns multiple objects, like for example children(), get_one() will return the first object from the result set. It is undetermined which one that will be.
get() and get_one() return null if no result was found.

// get the root of the tree $henry belongs to
$root = $henry->root()->get_one();

// echos 'true'
echo $root == $bill ? 'true' : 'false';

// get the root of a specific tree
$root = Model_Tree::forge()->set_tree_id($mytreeid)->root()->get_one();

// get all roots in the tree
$roots = $henry->roots()->get();

// echos 'true' (there's only one root in the tree)
echo reset($roots) == $bill ? 'true' : 'false';

// get alls root without having an existing object
$roots = Model_Tree::forge()->roots()->get();

// get the parent of $nicola
$parent = $nicola->parent()->get_one();

// echos 'true'
echo $parent == $angela ? 'true' : 'false';

// returns null, it won't work without a node tree context
$parent = Model_Tree::forge()->parent()->get_one();

// get the children of $angela
$children = $angela->children()->get();

// echos 'true'
echo $children == array($henry->id => $henry, $nicola->id => $nicola) ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->children()->get();

// get the ancestors of $henry
$ancestors = $henry->children()->get();

// echos 'true'
echo $ancestors == array($bill->id => $bill, $angela->id => $angela) ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->ancestors()->get();

// get the descendants of $ben
$descendants = $ben->descendants()->get();

// echos 'true'
echo $descendants == array($kerry->id => $kerry, $tim->id => $tim, $james->id => $james) ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->descendants()->get();

// get the leaf descendants of $ben
$descendants = $ben->leaf_descendants()->get();

// echos 'true'. Note that $kerry is not returned now, as that has a child object
echo $descendants == array($tim->id => $tim, $james->id => $james) ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->leaf_descendants()->get();

// get the siblings of $kerry
$siblings = $kerry->siblings()->get();

// echos 'true'
echo $siblings == array($kerry->id => $kerry, $james->id => $james) ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->siblings()->get();

// get the first child of $bill
$child = $bill->first_child()->get_one();

// echos 'true'
echo $child == $angela ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->first_child()->get_one();

// get the last child of $bill
$child = $bill->last_child()->get_one();

// echos 'true'
echo $child == $ben ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->last_child()->get_one();

// get the previous sibling of $nicola
$sibling = $nicola->previous_silbing()->get_one();

// echos 'true'
echo $sibling == $henry ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->previous_sibling()->get_one();

// will return null too, $henry has no previous sibling
$sibling = $henry->previous_silbing()->get_one();

// get the next sibling of $henry
$sibling = $henry->next_silbing()->get_one();

// echos 'true'
echo $sibling == $nicola ? 'true' : 'false';

// returns null, it won't work without a current node context
$parent = Model_Tree::forge()->previous_sibling()->get_one();

// will return null too, $nicola has no previous sibling
$sibling = $nicola->next_silbing()->get_one();

// get the path to Tim, returns "Bill/Ben/Kerry/Tim"
$path = $tim->path();

// get the path to Nicola, returns "Bill/Angela/Nicola"
$path = $nicola->path();

Collection methods for saving nodes

Like with a standard ORM model, save() will either insert the object as a new record in the table, or it updates an existing record in case the object was retrieved from the database.

However, unlike a standard ORM model in a nestedset tree is is very relevant where exactly in the tree an object is saved. If you don't specify a collection method before save, saving an existing object will just do that, identical to normal ORM model behaviour. If you did specify a collection method, the object will be relocated in the tree when you save. If your saving a new object, not specifing a collection method will create a new root node. If you did specify one, it will determine where in the tree the new node will be inserted.

null

// give bill a new subordinate, before Angela in the tree
$john = Model_Tree::forge(array('name' => 'John'))->first_child($bill)->save();

// promote Kerry to a subordinate of Bill
$kerry->first_child($bill)->save();

null

// give bill a new subordinate, after Ben in the tree
$john = Model_Tree::forge(array('name' => 'John'))->last_child($bill)->save();

// promote Kerry to a subordinate of Bill
$kerry->last_child($bill)->save();

From a hierarchy perspective, first_child and last_child do the same. Only the exact position in the tree, the relation to it's siblings after the insert or relocation of the node, is different.

null

// give bill a new subordinate, before Angela in the tree
$john = Model_Tree::forge(array('name' => 'John'))->previous_sibling($angela)->save();

// demote James to be a subordinate of Ben, besides Tim
$james->previous_sibling($tim)->save();

null

// give bill a new subordinate, after Angela in the tree
$john = Model_Tree::forge(array('name' => 'John'))->next_sibling($angela)->save();

// demote James to be a subordinate of Ben, besides Tim
$james->next_sibling($tim)->save();

Test methods

Test methods are used to query a particular state of the object with regards to their position in the tree.

// is Bill a root node? echo's 'true'
echo $bill->is_root() ? 'true' : 'false';

// is Tim a root node? echo's 'false'
echo $tim->is_root() ? 'true' : 'false';

// is Tim a leaf node? echo's 'true'
echo $tim->is_leaf() ? 'true' : 'false';

// is Angela a leaf node? echo's 'false'
echo $angela->is_leaf() ? 'true' : 'false';

// is Henry a root node? echo's 'true'
echo $henry->is_child() ? 'true' : 'false';

// is Bill a root node? echo's 'false'
echo $bill->is_child() ? 'true' : 'false';

null

// is Ben a child node of Bill? echo's 'true'
echo $ben->is_child_of($bill) ? 'true' : 'false';

// is James a child node of Bill? echo's 'false', as it's a grandchild
echo $james->is_child_of($bill) ? 'true' : 'false';

// is Nicola a child node of Ben? echo's 'false', different part of the tree
echo $nicola->is_child_of($ben) ? 'true' : 'false';

null

// is Ben a descendant node of Bill? echo's 'true'
echo $ben->is_descendant_of($bill) ? 'true' : 'false';

// is James a descendant node of Bill? echo's 'true', as it's a grandchild
echo $james->is_descendant_of($bill) ? 'true' : 'false';

// is Nicola a descendant node of Ben? echo's 'false', different part of the tree
echo $nicola->is_descendant_of($ben) ? 'true' : 'false';

null

// is Bill the parent of Ben? echo's 'true'
echo $bill->is_parent_of($ben) ? 'true' : 'false';

// is Bill the parent of James? echo's 'false', as it's a grandparent
echo $bill->is_parent_of($james) ? 'true' : 'false';

null

// is Bill an ancestor of Ben? echo's 'true'
echo $bill->is_ancestor_of($ben) ? 'true' : 'false';

// is Bill an ancestor of James? echo's 'true', as it's a grandparent
echo $bill->is_ancestor_of($james) ? 'true' : 'false';

// Does James have a previous sibling? echo's 'true'
echo $james->has_previous_sibling() ? 'true' : 'false';

// Does Tim have a previous sibling? echo's 'false'
echo $tim->has_previous_sibling() ? 'true' : 'false';

// Does Henry have a next sibling? echo's 'true'
echo $henry->has_next_sibling() ? 'true' : 'false';

// Does Ben have a next sibling? echo's 'false'
echo $ben->has_next_sibling() ? 'true' : 'false';

Miscellaneous methods

null

// get the name of the tree-id column
$tree_id = Model_Tree::tree_config('tree_id');

// get the tree_id (returns 1)
$current_tree = $bill->get_tree_id();

null

// get the root of a tree without having a previous node to work with
$root = Model_Tree::forge()->set_tree_id($mytreeid)->get_one();

// get all nodes in the current tree with an enabled status set
$enabled = Model_Tree::forge()
	->set_tree_id($mytreeid)
	->build_query()
	->where('enabled', '=', 1)
	->get();

// using an existing object, this will use the tree-id of the $bill object
$enabled = $bill
	->build_query()
	->where('enabled', '=', 1)
	->get();

// get all child nodes of Bill with an enabled status set
$enabled = $bill
	->children()
	->get_query()
	->where('enabled', '=', 1)
	->get();

// Get the number of Bill's children, echo's 2
echo $bill->count_children();

// Get the number of Kerry's children, echo's 1
echo $kerry->count_children();

// Get the number of Tim's children, echo's 0
echo $tim->count_children();

// echo's 0 too, a new object can't have children
echo Model_Tree::forge()->count_children();

// Get the number of Bill's descendants, echo's 7
echo $bill->count_descendants();

// Get the number of Ben's children, echo's 3
echo $ben->count_descendants();

// echo's 0, a new object can't have descendants
echo Model_Tree::forge()->count_descendants();

// Get the level of Bill in the organisation
echo $bill->depth(); // echo's 0, he's top dog!

// Get the level of Angela in the organisation
echo $angela->depth(); // echo's 1, as she's an N+1

// Get the level of Tim in the organisation
echo $tim->depth(); // echo's 3, as low as you can go...

// returns false, you can't get the depth of a new node
$result = Model_Tree::forge()->depth();

false

'children'

// returns a multi-dimensional array. $tree['children'] will contain the children of Bill
$tree = $bill->dump_tree();

// returns the 'bill' object with a property 'children' containing the children of Bill
$tree = $bill->dump_tree(true);

// using $tree, this returns array($angela, $ben)
$children = $tree->children;

// and this returns array($henry, $nicola), the children of $angela
$grandchildren = reset($children)->children;

// ORM objects are always used by reference!
$bill->dump_tree(true);

// so this works fine too...
$children = $bill->children;