How do you convert a parent-child (adjacency) table to a nested set using PHP and MySQL?
I've spent the last few hours trying to find the solution to this question online. I've found plenty of examples on how to convert from nested set to adjacency... but few that go the other way around. The examples I have found either don't work or use MySQL procedures. Unfortunately, I can't use procedures for this project. I need a pure PHP solution.
I have a table that uses the adjacency model below:
id parent_id category
1 0 Books
2 0 CD's
3 0 Magazines
4 1 Books/Hardcover
5 1 Books/Large Format
6 3 Magazines/Vintage
And I would like to convert it to a Nested Set table below:
id left right category
0 1 14 Root Node
1 2 7 Books
4 3 4 Books/Hardcover
5 5 6 Books/Large Format
2 8 9 CD's
3 10 13 Magazines
6 11 12 Magazines/Vintage
Here is an image of what I need:
I have a function, based on the pseudo code from this forum post (http://www.sitepoint.com/forums/showthread.php?t=320444) but it doesn't work. I get multiple rows that have the same value for left. This should not happen.
<?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>\n";
throw new Exception(mysql_error());
}
echo "<p>$s_query</p>\n";
// 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>\n";
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;
}
?>
This is the output of the above script.
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' )
As you can see, there are multiple rows sharing the lft value of "1" same goes for "2" In a nested-set, the values for left and right must be unique. Here is an example of how to manually number the left and right ID's in a nested set:
Image Credit: Gijs Van Tulder, ref article
Answer
I found an answer online and updated the question on this page to show others how it is done.
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 some 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>\n";
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>\n";
throw new Exception(mysql_error());
}
else
{
// success: provide feedback
echo "<p>$s_query</p>\n";
}
}
}
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:
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' )