Как выбрать, используя условие WITH RECURSIVE

Ответ 1

Прежде всего, попробуем упростить и уточнить описание алгоритма на странице . Чтобы упростить это, рассмотрим только union all в with recursive предложение (и union позже):

WITH RECURSIVE pseudo-entity-name(column-names) AS (
    Initial-SELECT
UNION ALL
    Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name

Чтобы прояснить это, давайте опишем процесс выполнения запроса в псевдокоде:

working-recordset = result of Initial-SELECT

append working-recordset to empty outer-recordset

while( working-recordset is not empty ) begin

    new working-recordset = result of Recursive-SELECT 
        taking previous working-recordset as pseudo-entity-name

    append working-recordset to outer-recordset

end

overall-result = result of Outer-SELECT 
    taking outer-recordset as pseudo-entity-name

Или даже короче - механизм базы данных выполняет начальный выбор, беря его результирующие строки в качестве рабочего набора. Затем он повторно выполняет рекурсивный выбор в рабочем наборе, каждый раз заменяя содержимое рабочего набора на полученный результат запроса. Этот процесс заканчивается, когда пустой набор возвращается рекурсивным выбором. И все строки результатов, заданные сначала путем первоначального выбора, а затем путем рекурсивного выбора, собираются и подаются на внешний выбор, результатом которого становится общий результат запроса.

Этот запрос вычисляет factorial из 3:

WITH RECURSIVE factorial(F,n) AS (
    SELECT 1 F, 3 n
UNION ALL
    SELECT F*n F, n-1 n from factorial where n>1
)
SELECT F from factorial where n=1

Первоначальный выбор SELECT 1 F, 3 n дает нам начальные значения: 3 для аргумента и 1 для значения функции.
Рекурсивный select SELECT F*n F, n-1 n from factorial where n>1 указывает, что каждый раз, когда нам нужно умножить последнее значение funcion на значение последнего аргумента и значение аргумента декремента.
Database engine выполняет это следующим образом:

Прежде всего, он выполняет initail select, который дает начальное состояние рабочего набора записей:

F | n
--+--
1 | 3

Затем он преобразует рабочий набор записей с рекурсивным запросом и получает его второе состояние:

F | n
--+--
3 | 2

Затем третье состояние:

F | n
--+--
6 | 1

В третьем состоянии нет строки, которая следует за условием n>1 в рекурсивном выборе, поэтому рабочий набор - это выходы цикла.

Внешний набор записей теперь содержит все строки, возвращенные начальным и рекурсивным выбором:

F | n
--+--
1 | 3
3 | 2
6 | 1

Внешний выбор отфильтровывает все промежуточные результаты из внешнего набора записей, показывая только конечное факторное значение, которое становится общим результатом запроса:

F 
--
6

А теперь рассмотрим таблицу forest(id,parent_id,name):

id | parent_id | name
---+-----------+-----------------
1  |           | item 1
2  | 1         | subitem 1.1
3  | 1         | subitem 1.2
4  | 1         | subitem 1.3
5  | 3         | subsubitem 1.2.1
6  |           | item 2
7  | 6         | subitem 2.1
8  |           | item 3

' Расширение полного дерева "означает сортировку элементов дерева в удобочитаемом глубинном порядке при вычислении их уровней и (возможно) путей. Обе задачи (правильного уровня сортировки и вычисления или пути) не разрешаются в одном (или даже любом постоянном числе) SELECT без использования предложения WITH RECURSIVE (или предложение Oracle CONNECT BY, которое не поддерживается PostgreSQL). Но этот рекурсивный запрос выполняет задание (ну, почти, см. Примечание ниже):

WITH RECURSIVE fulltree(id,parent_id,level,name,path) AS (
    SELECT id, parent_id, 1 as level, name, name||'' as path from forest where parent_id is null
UNION ALL
    SELECT t.id, t.parent_id, ft.level+1 as level, t.name, ft.path||' / '||t.name as path
    from forest t, fulltree ft where t.parent_id = ft.id
)
SELECT * from fulltree order by path

Механизм базы данных выполняет это следующим образом:

Во-первых, он выполняет выбор initail, который дает все элементы (корни) самого высокого уровня из таблицы forest:

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
1  |           | 1     | item 1           | item 1
8  |           | 1     | item 3           | item 3
6  |           | 1     | item 2           | item 2

Затем он выполняет рекурсивный выбор, который дает все элементы второго уровня из таблицы forest:

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
2  | 1         | 2     | subitem 1.1      | item 1 / subitem 1.1
3  | 1         | 2     | subitem 1.2      | item 1 / subitem 1.2
4  | 1         | 2     | subitem 1.3      | item 1 / subitem 1.3
7  | 6         | 2     | subitem 2.1      | item 2 / subitem 2.1

Затем он снова выполняет рекурсивный выбор, извлекая элементы уровня 3D:

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
5  | 3         | 3     | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1

И теперь он снова выполняет рекурсивный выбор, пытаясь извлечь элементы 4-го уровня, но их нет, поэтому цикл выходит.

Внешний SELECT устанавливает правильный порядок чтения строк в строке, сортируя по столбцу пути:

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
1  |           | 1     | item 1           | item 1
2  | 1         | 2     | subitem 1.1      | item 1 / subitem 1.1
3  | 1         | 2     | subitem 1.2      | item 1 / subitem 1.2
5  | 3         | 3     | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
4  | 1         | 2     | subitem 1.3      | item 1 / subitem 1.3
6  |           | 1     | item 2           | item 2
7  | 6         | 2     | subitem 2.1      | item 2 / subitem 2.1
8  |           | 1     | item 3           | item 3

ПРИМЕЧАНИЕ. Результирующий порядок строк останется верным только в том случае, если в именах элементов нет сопоставления знаков препинания, предшествующих /. Если мы переименуем Item 2 в Item 1 *, он сломает порядок строк, стоящий между Item 1 и его потомками.
Более стабильное решение использует символ табуляции (E'\t') как разделитель путей в запросе (который может быть заменен более читаемым разделителем путей позже: во внешнем выборе, перед перемещением на человека или т.д.). Разделенные на вкладки пути сохраняют правильный порядок, пока в именах элементов не будут указаны вкладки или контрольные символы, которые легко можно проверить и исключить без потери удобства использования.

Очень просто изменить последний запрос для расширения произвольного поддерева - вам нужно только заменить условие parent_id is null на perent_id=1 (например). Обратите внимание, что этот вариант запроса возвращает все уровни и пути относительно Item 1.

И теперь о типичных ошибках. Наиболее заметной типичной ошибкой, характерной для рекурсивных запросов, является определение условий плохой остановки в рекурсивном выборе, что приводит к бесконечному циклу.

Например, если мы опускаем условие where n>1 в факториальной выборке выше, выполнение рекурсивного выбора никогда не даст пустого набора (потому что у нас нет условия для фильтрации одной строки), и цикл будет продолжаться бесконечно.

Это наиболее вероятная причина, по которой некоторые из ваших запросов зависают (другая неспецифическая, но все же возможная причина - очень неэффективный выбор, который выполняется в конечном, но очень долгом времени).

Существует не так много запросов RECURSIVE guidlinesупомянуть, насколько я знаю. Но я хотел бы предложить (довольно очевидную) пошаговую процедуру рекурсивного построения запросов.

• Отдельно создавайте и отлаживайте свой первоначальный выбор.

• Оберните его лесками с конструкцией RECURSIVE
  и начните создавать и отлаживать рекурсивный выбор.

Рекомендуемая конструкция для защиты от сбоев выглядит следующим образом:

WITH RECURSIVE rec( <Your column names> ) AS (
    <Your ready and working initial SELECT>
UNION ALL
    <Recursive SELECT that you are debugging now>
)
SELECT * from rec limit 1000

Этот самый простой внешний выбор выведет весь внешний набор записей, который, как мы знаем, содержит все выходные строки от начального выбора и каждое выполнение recusrive select в цикле в их исходном порядке вывода - точно так же, как в примерах выше! Часть limit 1000 предотвратит зависание, заменив ее негабаритным выходом, в котором вы сможете увидеть пропущенную точку остановки.

• После отладки начальной и рекурсивной выберем сборку и отлаживаем внешний выбор.

И теперь последнее, что нужно упомянуть - разница в использовании union вместо union all в with recursive. Он вводит ограничение единственности строки, которое приводит к двум дополнительным строкам в нашем псевдокоде выполнения:

working-recordset = result of Initial-SELECT

discard duplicate rows from working-recordset /*union-specific*/

append working-recordset to empty outer-recordset

while( working-recordset is not empty ) begin

    new working-recordset = result of Recursive-SELECT 
        taking previous working-recordset as pseudo-entity-name

    discard duplicate rows and rows that have duplicates in outer-recordset 
        from working-recordset /*union-specific*/

    append working-recordset to outer-recordset

end

overall-result = result of Outer-SELECT 
    taking outer-recordset as pseudo-entity-name