Hierarchiczna tabela - jak uzyskać ścieżki elementów [połączonych list w MySQL]

Question

Mam tabelę hierarchiczną w MySQL: parent pole każdej pozycji wskazuje na pole id elementu nadrzędnego. Dla każdej pozycji mogę uzyskać listę wszystkich jej rodziców [niezależnie od głębokości] przy użyciu query described here. Z GROUP_CONCAT uzyskać pełną ścieżkę jako jeden ciąg znaków:

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 

mogę dokonać tej pracy tylko wtedy, gdy id elementu jest przymocowany [to 200 w tym przypadku].

Chcę zrobić to samo dla wszystkich wierszy: pobrać całą tabelę z jednym dodatkowym polem (path), który wyświetli pełną ścieżkę. Jedynym rozwiązaniem, które przychodzi mi do głowy, jest zawarcie tego zapytania w innym wyborze, ustawienie tymczasowej zmiennej @id i użycie jej wewnątrz podzapytania. Ale to nie działa. Otrzymuję NULL s w polu 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. Wiem, że mogę przechowywać ścieżki w osobnym polu i aktualizować je podczas wstawiania/aktualizowania, ale potrzebuję rozwiązania opartego na technice z listą powiązanej .

UPDATE: Chciałbym zobaczyć rozwiązanie, które nie będzie używał rekursji lub konstrukty jak for i while. Powyższa metoda wyszukiwania ścieżek nie używa żadnych pętli ani funkcji. Chcę znaleźć rozwiązanie w tej samej logice. Lub, jeśli to niemożliwe, spróbuj wyjaśnić, dlaczego!

Answer 1

Zdefiniuj funkcję getPath i wykonaj następujące zapytanie:

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

Definiowanie funkcji 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

uznała różnicę pomiędzy dwóch następujących zapytań:

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; 

one wyglądają niemal identycznie, ale dają radykalnie różne wyniki. W mojej wersji MySQL, _id w drugim zapytaniu jest takie samo dla każdego wiersza w jego zestawie wyników i jest równe id z ostatniego wiersza. Jednak ten ostatni bit jest prawdziwy, ponieważ wykonałem dwa zapytania w podanej kolejności; po SET @id := 1, na przykład, widzę, że _id jest zawsze równa wartości w instrukcji SET.

Co tu się dzieje? EXPLAIN daje wskazówkę:

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) 

To trzeci rząd, tabela DERIVED bez stosowanych tabelach MySQL wskazuje, że może być obliczona tylko raz, w dowolnym momencie. Serwer nie zauważa, że ​​wyprowadzona tabela używa zmiennej zdefiniowanej gdzie indziej w zapytaniu i nie ma żadnej wskazówki, że chcesz, aby była uruchamiana raz na wiersz. Jesteś ugryzieniu przez zachowanie wymienionego w dokumentacji MySQL na 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.

W moim przypadku, to zdecyduje się wykonać obliczenia pierwszy stół, zanim @id jest (re) zdefiniowany przez zewnętrzną SELECT.W rzeczywistości właśnie dlatego działa oryginalne hierarchiczne zapytanie danych; Definicja @r jest obliczana przez MySQL przed czymkolwiek innym w zapytaniu, właśnie dlatego, że jest to rodzaj pochodnej tabeli. Jednak potrzebujemy tutaj sposobu na zresetowanie @r raz na wiersz tabeli, a nie tylko raz dla całego zapytania. Aby to zrobić, potrzebujemy zapytania, które wygląda jak oryginalne, ręcznie resetując @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 

Zapytanie wykorzystuje drugi t_hierarchy w ten sam sposób, przy zapytania nie, w celu zapewnienia, że ​​to w wyniku, dla podkwerendzie macierzystego pętli na wystarczająco wierszy. Dodaje także wiersz dla każdego _id, który zawiera się jako rodzic; bez tego żadne obiekty root (z NULL w polu nadrzędnym) w ogóle nie pojawią się w wynikach.

Co dziwne, uruchomienie wyniku przez GROUP_CONCAT wydaje się zakłócać porządkowanie. Całe szczęście, że funkcja ma swój własny ORDER BY klauzuli:

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 ostrzeżenie: Te kwerendy niejawnie polegać na @r i @l aktualizacjach dzieje przed aktualizacją @c. Ta kolejność nie jest gwarantowana przez MySQL i może ulec zmianie w dowolnej wersji serwera.