Tabella gerarchica - come ottenere i percorsi degli elementi [liste collegate in MySQL]

Question

Ho una tabella gerarchica in MySQL: il campo parent di ciascun elemento punta al campo id dell'elemento principale. Per ogni articolo posso ottenere l'elenco di tutti i suoi genitori [indipendentemente dalla profondità] usando lo query described here. Con GROUP_CONCAT ottengo il percorso completo come una singola stringa:

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 

posso fare questo lavoro solo se la id della voce è fissa [è 200 in questo caso].

Voglio fare lo stesso per tutte le righe: recuperare l'intera tabella con un campo aggiuntivo (path) che visualizzerà il percorso completo. L'unica soluzione che mi viene in mente è racchiudere questa query in un'altra selezione, impostare una variabile temporanea @id e utilizzarla all'interno della sottoquery. Ma non funziona. Ottengo NULL s nel 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. So che posso memorizzare i percorsi in un campo separato e aggiornarli durante l'inserimento/l'aggiornamento, ma ho bisogno di una soluzione basata sulla tecnica dell'elenco .

UPDATE: Vorrei vedere una soluzione che non utilizzerà la ricorsione o costrutti come for e while. Il metodo sopra riportato per trovare i percorsi non utilizza loop o funzioni. Voglio trovare una soluzione nella stessa logica. Oppure, se è impossibile, prova a spiegare perché!

Answer 1

Definire la funzione getPath ed eseguire la seguente query:

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

Definire la funzione 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

considerare la differenza tra le seguenti due domande:

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; 

Essi sembrano quasi identici, ma danno risultati drammaticamente differenti. Nella mia versione di MySQL, _id nella seconda query è uguale per ogni riga nel suo set di risultati e uguale a id dell'ultima riga. Tuttavia, quell'ultimo bit è vero solo perché ho eseguito le due query nell'ordine dato; ad esempio, dopo SET @id := 1, posso vedere che _id è sempre uguale al valore nell'istruzione SET.

Quindi cosa sta succedendo qui? Un EXPLAIN cede un indizio:

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) 

Tale terza riga, la tabella DERIVED senza tabelle utilizzate, segnala MySQL che può essere calcolato una sola volta, in qualsiasi momento. Il server non si accorge che la tabella derivata utilizza una variabile definita altrove nella query e non ha idea che si desideri eseguirla una volta per riga. Sei stato morso da un comportamento menzionato nella documentazione di MySQL su 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.

Nel mio caso, si sceglie di fare il calcolo quel tavolo, prima @id è (ri) definita dalla esterno SELECT.In effetti, questo è esattamente il motivo per cui la query originale sui dati gerarchici funziona; la definizione di @r viene calcolata da MySQL prima di qualsiasi altra cosa nella query, proprio perché è quel tipo di tabella derivata. Tuttavia, abbiamo bisogno di un modo per ripristinare @r una volta per riga della tabella, non solo una volta per l'intera query. Per fare ciò, abbiamo bisogno di una query che assomigli a quella originale, ripristinando a mano @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 

Questa query utilizza la seconda t_hierarchy allo stesso modo in cui la query originale fa, al fine di garantire ci sono abbastanza righe nel risultato del sottoquery genitore di un ciclo su. Aggiunge anche una riga per ogni _id che include se stesso come genitore; senza di esso, gli oggetti radice (con NULL nel campo padre) non apparirebbero affatto nei risultati.

Stranamente, il risultato tramite GROUP_CONCAT sembra interrompere l'ordine. Per fortuna, che la funzione ha la propria ORDER BY clausola:

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; 

Fair Warning: Queste query implicitamente si basano sui @r e @l aggiornamenti che accadono prima dell'aggiornamento @c. Tale ordine non è garantito da MySQL e può cambiare con qualsiasi versione del server.