Say I have an table of categories as an adjacency list; there are three columns in the table: CategoryID (the primary key; an auto-incrementing field, the actual value is not important), CategoryName, and ParentID (which is NULL for top-level categories).
What would be the algorithm for creating a nested set table from this adjacency list table? (with the nested set table containing CategoryID, CategoryName, lft, and rgt columns)
In some pseudo PHP its …
function recursive($category, $left = 0)
{
$right = $left + 1;
$children = getCategoryChildren($category->categoryID);
foreach($children as $child)
$right = recursive($child, $right);
mysql_query('INSERT INTO Category VALUES($category->categoryID, $left, $right, $category->name)');
return $right + 1;
}
Also, once thats done, its a good idea to re-order the rows by left ascending order.
INSERT INTO RealCategory
SELECT * FROM Category ORDER BY left ASC
Because thats the order your mostly be needing.
Thank you very much, that was of great help to me.
Well, I’m using an index on ‘lft’ so hopefully this won’t be necessary.
Thanks 
Thanks for the pseudo code. I tried to implement it, however I keep getting a bunch of rows with the same value for “left” which I know shouldn’t be the case. I think we’re missing a step in the pseudo routine. Can someone provide a real-code example? I’m perplexed. Thanks in advance.
I tried to translate your pseudo code to real code and ran into a problem…
<?php
/**
--
-- Table structure for table `adjacent_table`
--
CREATE TABLE IF NOT EXISTS `adjacent_table` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`father_id` int(11) DEFAULT NULL,
`category` varchar(128) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;
--
-- Dumping data for table `adjacent_table`
--
INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
(1, 0, 'ROOT'),
(2, 1, 'Books'),
(3, 1, 'CD''s'),
(4, 1, 'Magazines'),
(5, 2, 'Hard Cover'),
(6, 2, 'Large Format'),
(7, 4, 'Vintage');
--
-- Table structure for table `nested_table`
--
CREATE TABLE IF NOT EXISTS `nested_table` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`lft` int(11) DEFAULT NULL,
`rgt` int(11) DEFAULT NULL,
`category` varchar(128) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;
*/
mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
mysql_select_db('DATABASE') or die(mysql_error());
adjacent_to_nested(0);
/**
* adjacent_to_nested
*
* Reads a "adjacent model" table and converts it to a "Nested Set" table.
* @param integer $i_id Should be the id of the "root node" in the adjacent table;
* @param integer $i_left Should only be used on recursive calls. Holds the current value for lft
*/
function adjacent_to_nested($i_id, $i_left = 0)
{
// the right value of this node is the left value + 1
$i_right = $i_left + 1;
// get all children of this node
$a_children = get_source_children($i_id);
foreach ($a_children as $a)
{
// recursive execution of this function for each child of this node
// $i_right is the current right value, which is incremented by the
// import_from_dc_link_category method
$i_right = adjacent_to_nested($a['id'], $i_right);
// insert stuff into the our new "Nested Sets" table
$s_query = "
INSERT INTO `nested_table` (`id`, `lft`, `rgt`, `category`)
VALUES(
NULL,
'".$i_left."',
'".$i_right."',
'".mysql_real_escape_string($a['category'])."'
)
";
if (!mysql_query($s_query))
{
echo "<pre>$s_query</pre>\
";
throw new Exception(mysql_error());
}
echo "<p>$s_query</p>\
";
// get the newly created row id
$i_new_nested_id = mysql_insert_id();
}
return $i_right + 1;
}
/**
* get_source_children
*
* Examines the "adjacent" table and finds all the immediate children of a node
* @param integer $i_id The unique id for a node in the adjacent_table table
* @return array Returns an array of results or an empty array if no results.
*/
function get_source_children($i_id)
{
$a_return = array();
$s_query = "SELECT * FROM `adjacent_table` WHERE `father_id` = '".$i_id."'";
if (!$i_result = mysql_query($s_query))
{
echo "<pre>$s_query</pre>\
";
throw new Exception(mysql_error());
}
if (mysql_num_rows($i_result) > 0)
{
while($a = mysql_fetch_assoc($i_result))
{
$a_return[] = $a;
}
}
return $a_return;
}
?>
I get the following output…
[INDENT]INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘2’, ‘5’, ‘Hard Cover’ )
INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘2’, ‘7’, ‘Large Format’ )
INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘1’, ‘8’, ‘Books’ )
INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘1’, ‘10’, 'CD\‘s’ )
INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘10’, ‘13’, ‘Vintage’ )
INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘1’, ‘14’, ‘Magazines’ )
INSERT INTO nested_table (id, lft, rgt, category) VALUES( NULL, ‘0’, ‘15’, ‘ROOT’ )[/INDENT]
As you can see there are multiple rows with the same value for lft. That should not be the case. It is as if the “left id” portion of the pseudo code is not being updated. I think a step was left out. Can anyone help?
UPDATE - PROBLEM SOLVED
First off, I had mistakenly believed that the source table (the one in adjacent-lists format) needed to be altered to include a source node. This is not the case. Secondly, I found a class via BING that does the trick. I’ve altered it for PHP5 and converted the original author’s mysql related bits to basic PHP. He was using a DB class. You can convert them to your own database abstraction class later if you want.
Obviously, if your “source table” has other columns that you want to move to the nested set table, you will have to adjust the write method in the class below.
Hopefully this will save someone else from the same problems in the future.
<?php
/**
--
-- Table structure for table `adjacent_table`
--
DROP TABLE IF EXISTS `adjacent_table`;
CREATE TABLE IF NOT EXISTS `adjacent_table` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`father_id` int(11) DEFAULT NULL,
`category` varchar(128) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=8 ;
--
-- Dumping data for table `adjacent_table`
--
INSERT INTO `adjacent_table` (`id`, `father_id`, `category`) VALUES
(1, 0, 'Books'),
(2, 0, 'CD''s'),
(3, 0, 'Magazines'),
(4, 1, 'Hard Cover'),
(5, 1, 'Large Format'),
(6, 3, 'Vintage');
--
-- Table structure for table `nested_table`
--
DROP TABLE IF EXISTS `nested_table`;
CREATE TABLE IF NOT EXISTS `nested_table` (
`lft` int(11) NOT NULL DEFAULT '0',
`rgt` int(11) DEFAULT NULL,
`id` int(11) DEFAULT NULL,
`category` varchar(128) DEFAULT NULL,
PRIMARY KEY (`lft`),
UNIQUE KEY `id` (`id`),
UNIQUE KEY `rgt` (`rgt`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;
*/
/**
* @class tree_transformer
* @author Paul Houle, Matthew Toledo
* @created 2008-11-04
* @url http://gen5.info/q/2008/11/04/nested-sets-php-verb-objects-and-noun-objects/
*/
class tree_transformer
{
private $i_count;
private $a_link;
public function __construct($a_link)
{
if(!is_array($a_link)) throw new Exception("First parameter should be an array. Instead, it was type '".gettype($a_link)."'");
$this->i_count = 1;
$this->a_link= $a_link;
}
public function traverse($i_id)
{
$i_lft = $this->i_count;
$this->i_count++;
$a_kid = $this->get_children($i_id);
if ($a_kid)
{
foreach($a_kid as $a_child)
{
$this->traverse($a_child);
}
}
$i_rgt=$this->i_count;
$this->i_count++;
$this->write($i_lft,$i_rgt,$i_id);
}
private function get_children($i_id)
{
return $this->a_link[$i_id];
}
private function write($i_lft,$i_rgt,$i_id)
{
// fetch the source column
$s_query = "SELECT * FROM `adjacent_table` WHERE `id` = '".$i_id."'";
if (!$i_result = mysql_query($s_query))
{
echo "<pre>$s_query</pre>\
";
throw new Exception(mysql_error());
}
$a_source = array();
if (mysql_num_rows($i_result))
{
$a_source = mysql_fetch_assoc($i_result);
}
// root node? label it unless already labeled in source table
if (1 == $i_lft && empty($a_source['category']))
{
$a_source['category'] = 'ROOT';
}
// insert into the new nested tree table
// use mysql_real_escape_string because one value "CD's" has a single '
$s_query = "
INSERT INTO `nested_table`
(`id`,`lft`,`rgt`,`category`)
VALUES (
'".$i_id."',
'".$i_lft."',
'".$i_rgt."',
'".mysql_real_escape_string($a_source['category'])."'
)
";
if (!$i_result = mysql_query($s_query))
{
echo "<pre>$s_query</pre>\
";
throw new Exception(mysql_error());
}
else
{
// success: provide feedback
echo "<p>$s_query</p>\
";
}
}
}
mysql_connect('localhost','USER','PASSWORD') or die(mysql_error());
mysql_select_db('DATABASE') or die(mysql_error());
// build a complete copy of the adjacency table in ram
$s_query = "SELECT `id`,`father_id` FROM `adjacent_table`";
$i_result = mysql_query($s_query);
$a_rows = array();
while ($a_rows[] = mysql_fetch_assoc($i_result));
$a_link = array();
foreach($a_rows as $a_row)
{
$i_father_id = $a_row['father_id'];
$i_child_id = $a_row['id'];
if (!array_key_exists($i_father_id,$a_link))
{
$a_link[$i_father_id]=array();
}
$a_link[$i_father_id][]=$i_child_id;
}
$o_tree_transformer = new tree_transformer($a_link);
$o_tree_transformer->traverse(0);
?>
Here is the output…
[INDENT] INSERT INTO nested_table (id,lft,rgt,category) VALUES ( ‘4’, ‘3’, ‘4’, ‘Hard Cover’ )
INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '5', '5', '6', 'Large Format' )
INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '1', '2', '7', 'Books' )
INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '2', '8', '9', 'CD\\'s' )
INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '6', '11', '12', 'Vintage' )
INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '3', '10', '13', 'Magazines' )
INSERT INTO nested_table (id,lft,rgt,category) VALUES ( '0', '1', '14', 'ROOT' )
[/INDENT]
or
function shapeshift($lft = 1,$father = 1)
{
//Your DB class here. Check JDatabase for functions
//(like $db->loadobject() etc);
$db = & JFactory::getDBO();
$tbl_from = 'temp_data.adjacent_table';
$tbl_to = 'temp_data.nested_table';
$rgt = $lft+1;
$query = "select * from $tbl_from where id = $father";
$db->setQuery($query);
$cat = $db->loadObject();
$query = "select * from $tbl_from where father_id = $father";
$db->setQuery($query);
$sibs = $db->loadObjectList();
foreach ($sibs as $sib)
{
$rgt = shapeshift($rgt,$sib->id);
}
$query = "insert into $tbl_to (id,lft,rgt,category) values ($cat->id,$lft,$rgt,'$cat->category')";
$db->setQuery($query);
$db->Query();
return $rgt+1;
}
Enjoy.
I’m pretty sure this is the same exact routine as the pseudo code. If that is the case, the left_id will not update correctly. Could you post a non-db-abstraction-class’ed version so I can check it out easily.
This one does works, does updates it all. It is checked, and even sold few times allready
I’m sorry but i don’t have time to translate it to straight mysql classes, so - you’ll have to do it by yourselve, sorry.
This is how it works in my particular case.
//Generates lft and rgt for
function shapeshift($lft = 1,$father = 0,$isroot=false)
{
$db = & JFactory::getDBO();
$tbl_from = '#__sct_category';
$tbl_to = '#__sct_category';
$query = "select * from $tbl_from where id = $father";
$db->setQuery($query);
$cat = $db->loadObject();
$rgt = $lft+1;
$query = "select * from $tbl_from where parent_id = $father";
$db->setQuery($query);
$sibs = $db->loadObjectList();
foreach ($sibs as $sib)
{
$rgt = $this->shapeshift($rgt,$sib->id);
}
$query = "update $tbl_to set lft = $lft,rgt = $rgt where id = $cat->id";
$db->setQuery($query);
$db->Query();
$rgt+=1;
return $rgt;
}
And in case of NOT SINGLE root category -
//And if you have a lot of roots - call proc sequently for each,
//updating lft
$left = 1;
foreach ($allroots as $root)
{
//$this->l->error("Sent $root->id to shapeshift");
$left = $this->shapeshift($left,$root->id,true);
}
.
And to end this article (^_^) i’ll put last useful piece that I’ve made
//this one moves rgt values, IF you have created some cats,
//that are started from some cat(not from root)
//This piece of code comes before upper one.
if($lim_cat)
{
$query = "select lft from $tbl_to where id = $lim_cat ";
$db->setQuery($query);
$oldleft = $db->loadResult() + 1;
//Important! You have to start with left = oldleft in such case...
$left = $oldleft;
}
//Calling the shapeshifter
if($lim_cat)
{
$query = "select max(rgt) from $tbl_from ";
$db->setQuery($query);
$right = $db->loadResult() + 1;
//Shift all existing cats by generated right value
$query = "update $tbl_to set lft = lft+$right, rgt = rgt+$right "
." where lft > $oldleft";
$db->setQuery($query);
$db->Query();
}
.
PS After spending some time analysing efficiency of nested approach, I’ve come to a conclusion, tht there is one thing, that would be verry useful in this schema. It is depth.
I’ve engineered schema with depth, and it gave me a lot of benefits in selecting.
It did make an insert\delete\update procedures a bit heavier, but in sites case - that is a lot less important than selecting abilities of approach .
Hope this will be useful.
PPS Once again - JDatabase, the db class used here can be easily translated to standard mysql. I just dont have the time, sorry guys 
I won’t be sleeping for today anyways As for all this week
Just google for “JDatabase api” and you will get all your answers there…
Enjoy.