tiempo - ¿Cómo convertir una tabla padre-hijo(adyacencia) a un conjunto anidado usando PHP y MySQL?

insertar datos en tablas relacionadas mysql desde php

Question

He pasado las últimas horas tratando de encontrar la solución a esta pregunta en línea. He encontrado muchos ejemplos sobre cómo convertir de un conjunto anidado a una adyacencia ... pero pocos que van al revés. Los ejemplos que encontré no funcionan o usan procedimientos MySQL. Desafortunadamente, no puedo usar procedimientos para este proyecto. Necesito una solución PHP pura.

Tengo una tabla que utiliza el modelo de adyacencia a continuación:

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

Y me gustaría convertirlo en una tabla de conjunto anidado a continuación:

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

Aquí hay una imagen de lo que necesito:

Tengo una función, basada en el pseudo código de esta publicación del foro ( http://www.sitepoint.com/forums/showthread.php?t=320444 ) pero no funciona. Obtengo varias filas que tienen el mismo valor para la izquierda. Esto no debería suceder.

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

?>

Esta es la salida del script anterior.

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'', ''Formato grande'')

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

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'', ''Revistas'')

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

Como puede ver, hay varias filas que comparten el valor de lft de "1". Lo mismo ocurre con "2". En un conjunto anidado, los valores de izquierda y derecha deben ser únicos. Este es un ejemplo de cómo numerar manualmente los identificadores izquierdo y derecho en un conjunto anidado:

Crédito de la imagen: Gijs Van Tulder, artículo ref.

Answer 1

Conversión de 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*)"

Answer 2

Encontré una respuesta en línea y actualicé la pregunta en esta página para mostrar a otros cómo se hace.

ACTUALIZACIÓN - PROBLEMA RESUELTO

En primer lugar, creí erróneamente que la tabla de origen (la que está en formato de listas adyacentes) debía modificarse para incluir un nodo de origen. Este no es el caso. En segundo lugar, encontré una clase a través de BING que hace el truco. Lo he modificado para PHP5 y he convertido los bits relacionados con mysql del autor original a PHP básico. Estaba usando alguna clase de DB. Puede convertirlos a su propia clase de abstracción de base de datos más tarde si lo desea.

Obviamente, si su "tabla de origen" tiene otras columnas que desea mover a la tabla de conjunto anidada, tendrá que ajustar el método de escritura en la clase a continuación.

Con suerte, esto salvará a otra persona de los mismos problemas en el futuro.

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

?> 

Aquí está la salida:

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

INSERT INTO en nested_table ( id , lft , rgt , category ) VALUES (''5'', ''5'', ''6'', ''Formato grande'')

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

INSERT INTO en 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'', ''Revistas'')

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