Как преобразовать таблицу parent-child (смежность) в вложенный набор с использованием PHP и MySQL?

Последние несколько часов я пытался найти решение этого вопроса в Интернете. Я нашел множество примеров того, как конвертировать из вложенного набора в смежность … но мало что происходит наоборот. Примеры, которые я нашел, либо не работают, либо используют процедуры MySQL. К сожалению, я не могу использовать процедуры для этого проекта. Мне нужно чистое PHP-решение.

У меня есть таблица, которая использует приведенную ниже модель смежности:

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

И я хотел бы преобразовать его в таблицу вложенных наборов ниже:

 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

Вот образ того, что мне нужно:

Вложенная диаграмма дерева

У меня есть функция, основанная на псевдокоде на этом форуме ( http://www.sitepoint.com/forums/showthread.php?t=320444 ), но это не работает. Я получаю несколько строк, имеющих одинаковое значение слева. Этого не должно быть.

 <?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; } ?>

Это результат вышеприведенного скрипта.

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '2', '5', 'Hard Cover')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '2', '7', 'Large Format')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '1', '8', 'Books')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '1', '10', 'CD \' s ')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '10', '13', 'Vintage')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '1', '14', 'Magazines')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES (NULL, '0', '15', 'ROOT')

Как вы можете видеть, существует несколько строк, в которых значение lft равно «1», то же самое относится к «2». В вложенном наборе значения для левого и правого должны быть уникальными. Ниже приведен пример того, как вручную указывать левый и правый идентификаторы во вложенном наборе:

Как набрать вложенные наборы

Кредит изображения: Gijs Van Tulder, ссылка

Я нашел ответ онлайн и обновил вопрос на этой странице, чтобы показать другим, как это делается.

ОБНОВЛЕНИЕ – РЕШЕНИЕ ПРОБЛЕМЫ

Во-первых, я ошибочно полагал, что исходную таблицу (формат в смежных списках) необходимо изменить, чтобы включить исходный узел. Это не тот случай. Во-вторых, я нашел класс через BING, который делает трюк. Я изменил его для PHP5 и преобразовал связанные с MySQL биты исходного кода в базовый PHP. Он использовал некоторый класс DB. Вы можете преобразовать их в свой собственный класс абстракции базы данных позже, если хотите.

Очевидно, что если ваша «исходная таблица» содержит другие столбцы, которые вы хотите переместить во вложенную таблицу наборов, вам придется настроить метод записи в классе ниже.

Надеюсь, это спасет кого-то еще от тех же проблем в будущем.

 <?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); ?>

Вот результат:

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('4', '3', '4', 'Hard Cover')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('5', '5', '6', 'Large Format')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('1', '2', '7', 'Books')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('2', '8', '9', 'CD \' s ')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('6', '11', '12', 'Vintage')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('3', '10', '13', 'Magazines')

INSERT INTO nested_table ( id , rgt , rgt , category ) VALUES ('0', '1', '14', 'ROOT')

Преобразование Bash:

 # SQL command to fetch necessary fields, output it to text archive "tree" SELECT id, parent_id, name FROM projects; # Make a list "id|parentid|name" and sort by name cat tree | cut -d "|" -f 2-4 | sed 's/^ *//;s/ *| */|/g' | sort -t "|" -k 3,3 > list # Creates the parenthood chain on second field while IFS="|" read ipo do l=$p while [[ "$p" != "NULL" ]] do p=$(grep -w "^$p" list | cut -d "|" -f 2) l="$l,$p" done echo "$i|$l|$o" done < list > listpar # Creates left and right on 4th and 5th fields for interaction 0 let left=0 while IFS="|" read ilo do let dif=$(grep "\b$i,NULL|" listpar | wc -l)*2+1 let right=++left+dif echo "$i|$l|$o|$left|$right" let left=right done <<< "$(grep "|NULL|" listpar)" > i0 # The same for following interactions n=0 while [ -si$n ] do while IFS="|" read il nil left nil do grep "|$i,$l|" listpar | while IFS="|" read ilo do let dif=$(grep "\b$i,$l|" listpar | wc -l)*2+1 let right=++left+dif echo "$i|$l|$o|$left|$right" let left=right done done < i$n > i$((++n)) done # Show concatenated cat i*|sort -t"|" -k 4n # SQL commands while IFS="|" read id nil nil left right do echo "UPDATE projects SET lft=$left, rgt=$right WHERE id=$id;" done <<< "$(cat i*)"