Использование Common Table Expressions (CTE) для поиска в деревьях

Начиная с версии Firebird 2.1 появилась возможность использовать Common Table Expressions (CTE) в запросах, в том числе и для организации рекурсивной обработки информации. Рассмотрим такую задачу: в таблице GD_GOODGROUP находится древовидная иерархия товарных групп. Необходимо построить выборку, которая будет включать:

1. все группы с наименованиями, содержащими заданную подстроку;
2. для каждой найденной группы из п. 1. все группы из родительской цепочки.

Организация древовидной иерархии в таблице GD_GOODGROUP осуществляется как через ссылку (parent) на идентификатор (id) родительской записи, так и через вложенные интервалы (поля lb и rb).

Знакомство с CTE. Вывод древовидной иерархии на экран

Использование CTE для рекурсивного обхода иерархических структур легче всего понять рассмотрев пример:

WITH RECURSIVE
  group_tree AS (
    SELECT id, parent, name, CAST('' AS VARCHAR(255)) AS indent
    FROM gd_goodgroup
    WHERE parent IS NULL
 
    UNION ALL
 
    SELECT g.id, g.parent, g.name, h.indent || rpad('', 2)
    FROM gd_goodgroup g JOIN group_tree h
      ON g.parent = h.id
  )
SELECT
  gt.indent || gt.name
FROM
  group_tree gt

Этот запрос выводит древовидный список, используя отступы для выделения вложенных уровней:

 Все ТМЦ
   ТМЦ счет 10.01
     ЗЕРНОВЫЕ ОЗИМЫЕ
     КАРТОФЕЛЬ
     КОРМА ПОКУПНЫЕ
       ЗЦМ
     РАПС ОЗИМЫЙ
     РАПС ЯРОВОЙ
   Спецодежда
   Драгметаллы
   Основные средства
     01. Здания и сооружения
     02. Передаточные устр-ва, измерительные приборы 
   ТМЦ счет 10.042

Данное рекурсивное CTE состоит из двух частей. Нерекурсивной, которая создает список корневых элементов:

    SELECT id, parent, name, CAST('' AS VARCHAR(255)) AS indent
    FROM gd_goodgroup
    WHERE parent IS NULL

и рекурсивной, которая для каждого элемента возвращает список его детей:

    SELECT g.id, g.parent, g.name, h.indent || rpad('', 2)
    FROM gd_goodgroup g JOIN group_tree h
      ON g.parent = h.id

В общем случае для рекурсивного CTE действуют следующие правила:

1. Рекурсивное CTE содержит ссылку на само себя
2. Рекурсивное CTE является объединением (UNION) из рекурсивных и нерекурсивных запросов
3. Как минимум один нерекурсивный запрос (anchor) должен присутствовать в CTE
4. Нерекурсивные запросы располагаются первыми в объединении
5. Рекурсивные запросы присоединяются с помощью оператора UNION ALL
6. Циклические ссылки не допускаются
7. Секции (DISTINCT, GROUP BY, HAVING) и агрегатные функции (SUM, COUNT, MAX etc) не могут присутствовать в рекурсивных запросах
8. Рекурсивный запрос может содержать только одну ссылку на себя и только в секции FROM
9. Рекурсивные CTE не могут использоваться в OUTER JOIN.

Применение CTE для решения поставленной задачи

В качестве нерекурсивной части CTE мы создадим запрос, который вернет все элементы дерева, удовлетворяющие заданному условию:

    SELECT id, parent, name
    FROM gd_goodgroup
    WHERE name CONTAINING :S

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

    SELECT g.id, g.parent, g.name
    FROM gd_goodgroup g JOIN group_tree h
      ON g.id = h.parent

Итоговый запрос:

  WITH RECURSIVE
    group_tree AS (
      SELECT id, parent, name
      FROM gd_goodgroup
      WHERE name CONTAINING :S
 
      UNION ALL
 
      SELECT g.id, g.parent, g.name
      FROM gd_goodgroup g JOIN group_tree h
        ON g.id = h.parent
    )
  SELECT DISTINCT
    id, parent, name
  FROM
    group_tree

Обратите внимание на использование DISTINCT для исключения из выборки элементов дерева, которые могут повторяться при переборе цепочки от каждого найденного элемента к корню.