Tabla jerárquica: cómo obtener las rutas de los elementos [listas vinculadas en MySQL]

Question

Tengo una tabla jerárquica en MySQL: parent campo de cada elemento apunta al campo id de su elemento principal. Para cada elemento, puedo obtener la lista de todos sus padres [independientemente de la profundidad] usando el query described here. Con GROUP_CONCAT consigo la ruta completa como una única cadena:

SELECT GROUP_CONCAT(_id SEPARATOR ' > ') FROM (
SELECT @r AS _id, 
     (
     SELECT @r := parent 
     FROM t_hierarchy 
     WHERE id = _id 
     ) AS parent, 
     @l := @l + 1 AS lvl 
FROM (
     SELECT @r := 200, 
       @l := 0 
     ) vars, 
     t_hierarchy h 
WHERE @r <> 0 
ORDER BY lvl DESC 
) x 

puedo hacer este trabajo sólo si el id del artículo es fijo [es 200 en este caso].

Quiero hacer lo mismo para todas las filas: recuperar toda la tabla con un campo adicional (path) que mostrará la ruta completa. La única solución que me viene a la mente es ajustar esta consulta en otra selección, establecer una variable temporal @id y usarla dentro de la subconsulta. Pero no funciona. Obtengo NULL s en el campo path.

SELECT @id := id, parent, (
    SELECT GROUP_CONCAT(_id SEPARATOR ' > ') FROM (
    SELECT @r AS _id, 
      (
      SELECT @r := parent 
      FROM t_hierarchy 
      WHERE id = _id 
      ) AS parent, 
      @l := @l + 1 AS lvl 
    FROM (
      SELECT @r := @id, 
        @l := 0 
      ) vars, 
      t_hierarchy h 
    WHERE @r <> 0 
    ORDER BY lvl DESC 
    ) x 
) as path 
FROM t_hierarchy 

P.S. Sé que puedo almacenar las rutas en un campo separado y actualizarlas al insertar/actualizar, pero necesito una solución basada en la técnica de lista vinculada .

ACTUALIZACIÓN: me gustaría ver una solución que no va a usar la recursividad o construcciones como for y while. El método anterior para encontrar rutas no utiliza ningún bucle o función. Quiero encontrar una solución en la misma lógica. O, si es imposible, intente explicar por qué.

Answer 1

Definir la función getPath y ejecutar la siguiente consulta:

select id, parent, dbo.getPath(id) as path from t_hierarchy 

Definición de la función getPath:

create function dbo.getPath(@id int) 
returns varchar(400) 
as 
begin 
declare @path varchar(400) 
declare @term int 
declare @parent varchar(100) 
set @path = '' 
set @term = 0 
while (@term <> 1) 
begin 
    select @parent = parent from t_hierarchy where id = @id 
    if (@parent is null or @parent = '' or @parent = @id) 
     set @term = 1 
    else 
     set @path = @path + @parent 
    set @id = @parent  
end 
return @path 
end 

Answer 2

considerar la diferencia entre las dos consultas siguientes:

SELECT @id := id as id, parent, (
    SELECT concat(id, ': ', @id) 
) as path 
FROM t_hierarchy; 

SELECT @id := id as id, parent, (
    SELECT concat(id, ': ', _id) 
    FROM (SELECT @id as _id) as x 
) as path 
FROM t_hierarchy; 

Ellos se ven casi idénticos, pero dan resultados dramáticamente diferentes. En mi versión de MySQL, _id en la segunda consulta es el mismo para cada fila en su conjunto de resultados, e igual a id de la última fila. Sin embargo, ese último bit solo es cierto porque ejecuté las dos consultas en el orden dado; después de SET @id := 1, por ejemplo, puedo ver que _id siempre es igual al valor en la instrucción SET.

¿Qué está pasando aquí? Un EXPLAIN produce una pista:

mysql>  explain SELECT @id := id as id, parent, (
    ->   SELECT concat(id, ': ', _id) 
    ->   FROM (SELECT @id as _id) as x 
    -> ) as path 
    ->  FROM t_hierarchy; 
+----+--------------------+-------------+--------+---------------+------------------+---------+------+------+----------------+ 
| id | select_type  | table  | type | possible_keys | key    | key_len | ref | rows | Extra   | 
+----+--------------------+-------------+--------+---------------+------------------+---------+------+------+----------------+ 
| 1 | PRIMARY   | t_hierarchy | index | NULL   | hierarchy_parent | 9  | NULL | 1398 | Using index | 
| 2 | DEPENDENT SUBQUERY | <derived3> | system | NULL   | NULL    | NULL | NULL | 1 |    | 
| 3 | DERIVED   | NULL  | NULL | NULL   | NULL    | NULL | NULL | NULL | No tables used | 
+----+--------------------+-------------+--------+---------------+------------------+---------+------+------+----------------+ 
3 rows in set (0.00 sec) 

Esa tercera fila, la tabla DERIVED sin mesas utilizadas, indica a MySQL que se puede calcular exactamente una vez, en cualquier momento. El servidor no se da cuenta de que la tabla derivada usa una variable definida en otra parte de la consulta, y no tiene ni idea de que desee que se ejecute una vez por fila. Usted está siendo mordido por un comportamiento mencionado en la documentación de MySQL en user-defined variables:

As a general rule, you should never assign a value to a user variable and read the value within the same statement. You might get the results you expect, but this is not guaranteed. The order of evaluation for expressions involving user variables is undefined and may change based on the elements contained within a given statement; in addition, this order is not guaranteed to be the same between releases of the MySQL Server.

En mi caso, se opta por hacer el cálculo de la mesa primero, antes de @id es (re) definido por el exterior SELECT.De hecho, es exactamente por eso que funciona la consulta de datos jerárquica original; la definición de @r es calculada por MySQL antes que nada en la consulta, precisamente porque es ese tipo de tabla derivada. Sin embargo, necesitamos aquí una forma de restablecer @r una vez por fila de la tabla, no solo una vez para toda la consulta. Para hacer eso, necesitamos una consulta que se parezca a la original, reiniciando a mano el @r.

SELECT @r := if(
      @c = th1.id, 
      if(
      @r is null, 
      null, 
      (
       SELECT parent 
       FROM t_hierarchy 
       WHERE id = @r 
      ) 
     ), 
      th1.id 
     ) AS parent, 
     @l := if(@c = th1.id, @l + 1, 0) AS lvl, 
     @c := th1.id as _id 
FROM (
     SELECT @c := 0, 
       @r := 0, 
       @l := 0 
     ) vars 
     left join t_hierarchy as th1 on 1 
     left join t_hierarchy as th2 on 1 
HAVING parent is not null 

Esta consulta utiliza la segunda t_hierarchy la misma forma en que la búsqueda original hace, para asegurarse de que hay suficientes filas en el resultado de la subconsulta padres para recorrer. También agrega una fila para cada _id que se incluye como padre; sin eso, ningún objeto raíz (con NULL en el campo principal) no aparecería en absoluto en los resultados.

Curiosamente, ejecutar el resultado a través de GROUP_CONCAT parece interrumpir el pedido. Afortunadamente, esa función tiene su propia ORDER BY cláusula:

SELECT _id, 
     GROUP_CONCAT(parent ORDER BY lvl desc SEPARATOR ' > ') as path, 
     max(lvl) as depth 
FROM (
    SELECT @r := if(
      @c = th1.id, 
      if(
       @r is null, 
       null, 
       (
       SELECT parent 
       FROM t_hierarchy 
       WHERE id = @r 
      ) 
      ), 
      th1.id 
     ) AS parent, 
      @l := if(@c = th1.id, @l + 1, 0) AS lvl, 
      @c := th1.id as _id 
    FROM (
      SELECT @c := 0, 
        @r := 0, 
        @l := 0 
     ) vars 
      left join t_hierarchy as th1 on 1 
      left join t_hierarchy as th2 on 1 
    HAVING parent is not null 
    ORDER BY th1.id 
) as x 
GROUP BY _id; 

Feria advertencia: Estas consultas implícitamente se basan en los @r y @l cambios que ocurren antes de la actualización @c. Ese orden no está garantizado por MySQL, y puede cambiar con cualquier versión del servidor.