четверг, 17 декабря 2009 г.

Рекурсивные (Иерархические) запросы

Дерево в БД можно представить достаточно просто:
ID | PID | NAME| VALUE
Куда сложней из такой таблицы вытаскивать данные. Можно это делать рекурсивно выполняя маленькие запросы, узнающие значение и родителя.
Оказывается эту задачу можно решить одним запросом используя лишь один T-SQL.
Рассмотрим на примере: необходимо выбрать все ветки/листья элемента, вывести значения элементов и построить полный путь до каждого.
Для этого можно использовать следующий запрос:
WITH tree ( data , id , pid , level , pathstr ) 
AS ( SELECT t.NAME, t.ID, t.PID, 0, CAST ( t.VALUE AS VARCHAR ( 4000 ) ) 
FROM table t
WHERE t.ID = 1 
UNION ALL 
SELECT t.NAME, t.ID, t.PID, t.level + 1 , CAST ( tr.pathstr + '\' + t.VALUE) AS VARCHAR ( 4000 ) ) 
FROM table t
INNER JOIN tree tr 
ON ( t.PID = tr.id ) 
) 
SELECT tr.* 
FROM tree tr 
ORDER BY tr.level, tr.pathstr 
Что делает каждая его часть:
WITH tree ( <список столбцов для выборки из дерева > ) 
AS ( 
<Начальное условие, откуда начнется рекурсия> 
Изначально путь = NAME корня, а уровень задан в 0
Строку с путем кастим к максимальному VARCHAR, т.к. путь может быть очень длинным.
UNION ALL 
<связка текущего запроса с деревом (родитель с идентификатором)>
Тут же мы увеличиваем уровень вложенности, и формируем следующий элемент пути
) 
<Тут мы работаем с полученными значениями, как с обычной таблицей>
Результат будет примерно такой:
id | pid | level | data                | pathstr
1  |  0  |   0   | Значение Корня      | Корень 
2  |  1  |   1   | Значение уровня 1   | Корень / Уровень 1
3  |  1  |   1   | Значение уровня 1.1 | Корень / Уровень 1.1
4  |  2  |   2   | Значение уровня 2   | Корень / Уровень 1 / Уровень 2

5 комментариев:

  1. Идея нормальная, ищу такую инфу.

    Но статья гавно полное. непонятно.
    Запрос вообще оформлен с избыточностью.
    Проще нельзя, товарищь?

    Можно бы и PHP реализацию подкинуть до кучи.

    ОтветитьУдалить
  2. Написан SQL запрос по стандарту Transact (В оракле это будет выглядеть немного подругому, через коннект: http://www.adp-gmbh.ch/ora/sql/connect_by.html), он будет одинакого выглядеть, что на php, что на с++.
    Избыточности в данном случае нет. Можно конечно сократить, если выкинуть из отбора некоторые данные.

    ОтветитьУдалить
  3. SELECT t.NAME, t.ID, t.PID, t.level + 1 , CAST ( tr.pathstr + '\' + t.VALUE) AS VARCHAR ( 4000 ) )
    FROM table t
    INNER JOIN tree tr
    ON ( t.PID = tr.id )
    Что за бред? Где в таблице с алиасом t есть level? C ошибками и криво всё написано...

    ОтветитьУдалить
  4. Здесь одна ошибка - "t." действительно не нужно.

    WITH tree ( data , id , pid , level , pathstr )
    AS ( SELECT t.NAME, t.ID, t.PID, 0, CAST ( t.VALUE AS VARCHAR (MAX) )
    FROM test t
    WHERE t.ID = 1
    UNION ALL
    SELECT t.NAME, t.ID, t.PID, level + 1 , CAST ( tr.pathstr + '\' + t.VALUE AS VARCHAR(MAX) )
    FROM test t
    INNER JOIN tree tr
    ON ( t.PID = tr.id )
    )
    SELECT tr.*
    FROM tree tr
    ORDER BY tr.level, tr.pathstr

    Это достаточно просто и можно самому догадаться.

    ОтветитьУдалить
  5. Спасибо. Помогло разобраться

    ОтветитьУдалить