Kevin Bradwick

Introduction to Doctrine’s Nested Set

A common problem requirement among developers is to store hierarchial data to a flat file database. You have probably come across the parent/child methodology whereby a table has a typical ‘parent’ column that references, you guessed it, its parent – this method is also known as adjacency list model. Querying in this way can often lead to a lot of transactions per single request (one transaction per row) and an application with many rows of hierarchial data will dent your transaction efficiency. There are benefits to this system (simpler SQL management for CRUD operation) but there is another way that is more efficient – the Nested Set model (also known as modified pre-order tree traversal algorithm – MPTT).

Doctrine has by far the best known method of Nested Set operation I have come across. My main reason for this is the ability for it to store multiple roots in a single table. For example, this could come in handy for an application that implements multiple blogs.

So, let’s dive in and take a look at how we use this system.

For this example, I am going to show how this would come in use for a web application that hosts multiple blogs. Our database schema looks like this.

CREATE TABLE `Blogs` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `blog_admin` int(11) unsigned NOT NULL,
  `blog_title` text,
  `blog_description` text,
  `status` enum('live','private','offline') NOT NULL DEFAULT 'live',
  PRIMARY KEY (`id`),
  KEY `FK_Blogs_users` (`blog_admin`),
  CONSTRAINT `FK_Blogs_users` FOREIGN KEY (`blog_admin`) REFERENCES `Users` (`id`) ON DELETE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=latin1 ROW_FORMAT=DYNAMIC;

CREATE TABLE `BlogCategories` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `blog_id` int(11) unsigned NOT NULL,
  `name` varchar(140) DEFAULT NULL,
  `description` text,
  `lft` int(11) unsigned NOT NULL,
  `rgt` int(11) unsigned NOT NULL,
  `level` int(10) unsigned NOT NULL DEFAULT '0',
  `root_id` int(11) unsigned NOT NULL,
  PRIMARY KEY (`id`),
  KEY `FK_BlogCategories_blogs` (`blog_id`),
  CONSTRAINT `FK_BlogCategories_blogs` FOREIGN KEY (`blog_id`) REFERENCES `Blogs` (`id`) ON DELETE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=latin1 ROW_FORMAT=DYNAMIC;

Simply, we have a blogs table that has a foreign key back to a user table and the BlogCategories table will hold our categories relating to all the blogs. Next we will create our models…

I’m not going to cover model creation but for reference, I prefer to design my database through MySQL Query Browser first, then let Doctrine to generate the models for me using the generateModelsFromDb method like this;

//...
Doctrine_Core::generateModelsFromDb('/path/to/where/i/want/to/output/my/models/', array('doctrine'), array('generateTableClasses' => true));

In my BlogsCategories model, I tell it to act as a nested set, tell it there are many roots and declare the root column name (by default it is root_id, so I don’t need to declare it here but this is to show you how you would declare it to be a name other than root_id)

//...
$this->actAs('NestedSet', array(
	'hasManyRoots' => TRUE,
	'rootColumnName' => 'root_id'
	));

Now we’re good to go. The first thing we want to do is create a new root category. This category will be the parent category for all other categories.

$root = new BlogCategories();
$root->blog_id = 1; // relates back to the Blogs table
$root->name = 'ROOT';
$root->description = 'DO NOT DELETE';
$root->save(); // saves the new root category

$treeObject = Doctrine_Core::getTable('BlogCategories')->getTree();
$treeObject->createRoot($root);

If you look in your database now, you notice this has inserted the row and set the left/right/level/root columns appropriately. You can do this a few times to create a few roots. Now let’s look at inserting nodes for a particular blog. We’ll work with blog_id 1.

$blogOneRoot = Doctrine_Core::getTable('BlogCategories')->find(1); // the primary key of the root node for blog_id 1

$child = new BlogCategories();
$child->blog_id = 1;
$child->name = 'Doctrine';
$child->description = 'Good Doctrine tutorials';
$child->getNode()->insertAsLastChildOf($blogOneRoot);

This has now inserteda new child category for blog_id 1.

The last step we’ll take now is rendering a category tree of a particular blog. For this example again, I’ll assume blog_id 1.

$categoryTree = Doctrine_Core::getTable('BlogCategories')->getTree();
foreach($categoryTree ->fetchTree(array('root_id' => 1)) as $cat)
{
     echo str_repeat(' ', $cat['level']) . $cat['name'] . "\n";

}

And that pretty much covers the basics. It’s really easy – once you know how. There are many more cool things that can be done with Doctrine’s nested set method that I may cover on another day. Have fun!