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

Ответ 1

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

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

Во-первых, я ошибочно полагал, что исходную таблицу (формат в смежных списках) необходимо изменить, чтобы включить источник node. Это не тот случай. Во-вторых, я нашел класс через 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, lft, rgt, category) ЦЕННОСТИ ( '4', '3', '4', 'Hard Cover')

INSERT INTO nested_table(id, lft, rgt, category) ЦЕННОСТИ ( '5', '5', '6', 'Large Format')

INSERT INTO nested_table(id, lft, rgt, category) ЦЕННОСТИ ( '1', '2', '7', 'Books')

INSERT INTO nested_table(id, lft, rgt, category) ЦЕННОСТИ ( '2', '8', '9', 'CD \' s ')

INSERT INTO nested_table(id, lft, rgt, category) ЦЕННОСТИ ( '6', '11', '12', 'Vintage')

INSERT INTO nested_table(id, lft, rgt, category) ЦЕННОСТИ ( '3', '10', '13', 'Журналы')

INSERT INTO nested_table(id, lft, rgt, category) ЦЕННОСТИ ( '0', '1', '14', 'ROOT')

Ответ 2

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 i p o
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 i l o
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 [ -s i$n ]
do
  while IFS="|" read i l nil left nil
  do
    grep "|$i,$l|" listpar |
    while IFS="|" read i l o
    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*)"