Рекурсивный запрос sql: Изучение SQL: рекурсивные запросы

Простейший рекурсивный запрос

Простейший рекурсивный запрос

  • Оглавление
  • Рекурсивные подзапросы

Рекурсивные запросы используют в подзапросе данные самого себя.

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

Простейший пример

Потренируемся на цифрах. Сгенерируем числа от одного до трех:

WITH RECURSIVE lv_recursive (num) as (
  SELECT 1 AS num
    
    UNION ALL
  
  SELECT p.num + 1
    FROM lv_recursive p
   WHERE p.num < 3
)
SELECT *
  FROM lv_recursive

Обрати внимание, что lv_recursive используется как для названия подзапроса в WITH, так и как таблица в этом же подзапросе.

Чтобы в запросе ссылаться на самого себя, необходимо указать ключевое слово RECURSIVE. В противном случае будет ошибка:

WITH lv_recursive (num) as (
  SELECT 1 AS num
    
    UNION ALL
  
  SELECT p.num + 1
    FROM lv_recursive p
   WHERE p.num < 3
)
SELECT *
  FROM lv_recursive

error: relation "lv_recursive" does not exist

Рекурсивный подзапрос состоит из двух частей: нерекурсивной, определяющей первоначальный набор данных, и рекурсивной части, выполняющейся итерационно (несколько раз). Нерекурсивная и рекурсивная части разделяются UNION или UNION ALL.

WITH RECURSIVE lv_recursive (num) as (
  -- Нерекурсивная часть
  SELECT 1 AS num
    
    UNION ALL
  -- Рекурсивная часть
  SELECT p.num + 1
    FROM lv_recursive p
   WHERE p.num < 3
)

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

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

  2. Выполняется рекурсивная часть подзапроса. Вместо таблицы во фразе FROM с названием рекурсивного подзапроса (lv_recursive в нашем случае), используются строки из временной таблицы. Результат рекурсивной части добавляется в общий результат подзапроса и становится содержимым временной таблицы. Таким образом, на следующей итерации рекурсивный запрос выполняется для строк, полученных на текущей.

  3. Если во временной таблице есть записи, то переходим к шагу 2. Если нет — то рекурсивный подзапрос выполнен.

Разберем на нашем подзапросе

Шаг 1. Выполняется нерекурсивная часть подзапроса.

Общий результат подзапроса:

Временная таблица:

Шаг 2. Рекурсивная часть выполняется 1-й раз

lv_recursive равен

Т.к. 1 < 3, то запрос

SELECT p.num + 1
  FROM lv_recursive p
 WHERE p.num < 3

вернет одну строку с num = 2.

После первого выполнения рекурсивной части:

Общий результат подзапроса:

Временная таблица:

Шаг 3. Рекурсивная часть выполняется 2-й раз

lv_recursive равен

Т.к. 2 < 3, то будет возвращена одна строка с num = 3.

После второго выполнения рекурсивной части:

Общий результат подзапроса:

Временная таблица:

Шаг 4. Рекурсивная часть выполняется 3-й раз

lv_recursive равен

Т.к. 3 не меньше 3, то результат рекурсивной части не возвращает ни одной строки.

После третьего выполнения рекурсивной части:

Общий результат подзапроса:

Временная таблица пуста.

Т.к. временная таблица пуста, то выполнение рекурсивного подзапроса на этом завершается.

P.S.: Сгенерировать числа в PostgreSQL можно гораздо проще:

SELECT num
  FROM generate_series(1, 5) as num

  • Практика

    Простейший рекурсивный запрос

10.3 Несколько подзапросов в WITH

10. 5 Рекурсивный запрос посложнее

Несколько примеров рекурсивных SQL-запросов для системы DIRECTUM | Статья

Чтобы понять рекурсию, нужно сначала понять рекурсию.

Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

Пожалуй, одним определением и ограничусь, в сети масса информации на эту тему.

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

В стандартной поставке системы DIRECTUM есть ряд справочников, которые можно считать рекурсивными. Такие справочники содержат реквизит, сгенерированный по этому же справочнику (Подразделения, Поручения, РКК, Договоры и т.д.).

Косвенно рекурсивным можно считать справочники Работников (через Подразделения: в Работниках есть реквизит Подразделение, в Подразделении указан Руководитель — работник).

Кроме того, рекурсивной можно считать таблицу задач. Косвенно рекурсивной таблицу заданий (через задачи).

Построим несколько запросов на примере справочника Подразделения. Стандартный справочник Подразделения в DIRECTUM можно считать рекурсивным, так как в нем есть реквизит, который ссылается на сам справочник Подразделения: Головное подразделение. Фактически,
любой из примеров легко переделать для другого справочника или таблиц ЗЗУ.

Пример 1

В качестве первого примера хочу привести общий запрос, который строит иерархию всех подразделений компании. В качестве подразделения нулевого уровня берется то, у которого не указано головное, далее по уровню подчиненности.

-----------------------------------------------------------------
-- Иерархия подразделений
-----------------------------------------------------------------
with DipartmentHiererhcy (
  ID,
  HightID, 
  Level)
as
(
-- Подразделение верхнего уровня (N = 0)
  select
    department.Analit,
    department. Podr,
    0 as Level
  from
    MBAnalit department
  where
    department.Podr is null
    and department.vid = 
  union ALL
-- Подчиненное подразделение (N + 1)
  select
    department.Analit,
    department.Podr,
    Level + 1
  from
    MBAnalit as department
      inner join DipartmentHiererhcy as hightdepartment
        on department.Podr = hightdepartment.ID
  where
    department.vid = 
)
-- Иерархия подразделений
select
  hierarchy.ID as [ИД],
  department.NameAn as [Подразделение],
  IsNull(hightdepartment.NameAn, '') as [Ведущее подразделение],
  Level as [Уровень]
from
  DipartmentHiererhcy hierarchy
    left join MBAnalit department
      on department.Analit = hierarchy.ID
   left join MBAnalit hightdepartment
      on hightdepartment.Analit = hierarchy.HightID

Результат этого запроса на тестовой базе: список подразделений с указанием ведущего и уровня в иерархии.

Пример 2

Запрос можно модифицировать и под конкретные задачи. Например, при разработке отчетов по определенному подразделению необходимо учитывать не только указанное, но и все подчиненные подразделения. В этом случае можно получить все дерево таким запросом:

-----------------------------------------------------------------
-- Иерархия подразделений вниз от указанного
-----------------------------------------------------------------
with DipartmentHiererhcy (
  ID,
  HightID, 
  Level)
as
(
-- Подразделение верхнего уровня (N = 0)
  select
    department.Analit,
    department.Podr,
    0 as Level
  from
    MBAnalit department
  where
    department.Analit = 
    and department.vid = 
  union ALL
-- Подчиненное подразделение (N + 1)
  select
    department.Analit,
    department.Podr,
    Level + 1
  from
    MBAnalit as department
      inner join DipartmentHiererhcy as hightdepartment
        on department.Podr = hightdepartment.ID
  where
    department.vid = 
)
-- Иерархия подразделений вниз от указанного
select
  hierarchy.ID as [ИД],
  department.NameAn as [Подразделение],
  IsNull(hightdepartment.NameAn, '') as [Ведущее подразделение],
  Level as [Уровень]
from
  DipartmentHiererhcy hierarchy
    left join MBAnalit department
      on department. Analit = hierarchy.ID
   left join MBAnalit hightdepartment
      on hightdepartment.Analit = hierarchy.HightID

Пример 3

Также может возникнуть необходимость получить данные по всем подчиненным указанного работника:

-----------------------------------------------------------------
-- Список подчиненных указанного работника
-----------------------------------------------------------------
with DipartmentHiererhcy (
  ID,
  HightID, 
  Level)
as
(
-- Подразделение верхнего уровня (N = 0)
  select
    department.Analit,
    department.Podr,
    0 as Level
  from
    MBAnalit department
  where
    department.FIO = 
    and department.vid = 
  union ALL
-- Подчиненное подразделение (N + 1)
  select
    department.Analit,
    department.Podr,
    Level + 1
  from
    MBAnalit as department
      inner join DipartmentHiererhcy as hightdepartment
        on department.Podr = hightdepartment.ID
  where
    department.vid = 
)
-- Список подчиненных указанного работника
select distinct
  department. NameAn as [Подразделение],
  employee.NameAn as [Работник],
  IsNull(chiefemployee.NameAn, '') as [Руководитель],
  Level as [Уровень]
from
  DipartmentHiererhcy hierarchy
    left join MBAnalit department
      on department.Analit = hierarchy.ID
   left join MBAnalit hightdepartment
      on hightdepartment.Analit = hierarchy.HightID
   left join MBAnalit employee
     on department.Analit = employee.Podr and employee.Vid = 
   left join MBAnalit chiefemployee
     on department.FIO = chiefemployee.Analit and chiefemployee.Vid = 
where
  employee.Analit is not null

Пример 4

Обратный к примеру 3: цепочка руководителей указанного работника по иерархии вверх (например, может понадобиться для построения списка согласующих):

-----------------------------------------------------------------
-- Список руководителей указанного работника
-----------------------------------------------------------------
with DipartmentHiererhcy (
  ID,
  HightID, 
  Level)
as
(
-- Подразделение нижнего уровня (N = 0)
  select
    department. Analit,
    department.Podr,
    0 as Level
  from
    MBAnalit department
  where
    department.Analit = 
    and department.vid = 
  union ALL
-- Ведущее подразделение (N + 1)
  select
    department.Analit,
    department.Podr,
    Level + 1
  from
    MBAnalit as department
      inner join DipartmentHiererhcy as hightdepartment
        on department.Analit = hightdepartment.HightID
  where
    department.vid = 
)
-- Список руководителей указанного работника
select distinct
  department.NameAn as [Подразделение],
  IsNull(chiefemployee.NameAn, '') as [Руководитель],
  Level as [Уровень]
from
  DipartmentHiererhcy hierarchy
    left join MBAnalit department
      on department.Analit = hierarchy.ID
    left join MBAnalit chiefemployee
      on department.FIO = chiefemployee.Analit and chiefemployee.Vid =

В качестве P.S.

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

OPTION (MAXRECURSION )

 

Визуальное объяснение рекурсии в SQL | Денис Лукичев | The Startup

Опубликовано в

·

Чтение: 5 мин.

·

22 ноября 2020 г.

Рекурсия в SQL? Но почему? О, этому есть много применений. В SQL принято хранить иерархические данные, а рекурсивные запросы — удобный способ извлечения информации из таких графов. Организационная структура, структура меню приложения, набор задач с подзадачами в проекте, ссылки между веб-страницами, разбивка модуля оборудования на части и подчасти являются примерами иерархических данных. В этом посте не будут подробно рассказываться об этих многочисленных вариантах использования, а рассмотрим два игрушечных примера, чтобы понять концепцию — простейший возможный случай рекурсии чисел и запроса данных из генеалогического древа.

Давайте рассмотрим запросы как функцию. В том смысле, что функция принимает входные данные и производит выходные данные. Запросы оперируют отношениями или, можно сказать, таблицами. Мы будем обозначать их как Rn. Вот картинка запроса. Он принимает три отношения R1, R2, R3 и дает выход R. Достаточно просто.

Заголовок: Изображение того, как работает запрос.

Пример SQL: SELECT FROM R1, R2, R3 WHERE

Запрос может взять что-то и ничего не выдать:

Визуальное представление запроса, принимающего что-то и ничего не производящего.

Пример SQL: SELECT FROM R1 WHERE 1 = 2

Ничего не брать и что-то производить:

Визуальное представление запроса, который ничего не берет и что-то производит.

Пример SQL: SELECT 1

Или ничего не брать и ничего не производить

Визуальное представление запроса, ничего не принимающего и ничего не производящего.

ВЫБЕРИТЕ 1, ГДЕ 1 = 2

Рекурсия достигается оператором WITH , который на жаргоне SQL называется Common Table Expression (CTE). Это позволяет назвать результат и ссылаться на него в других запросах через некоторое время.

Именование результата и ссылка на него в других запросах.

Вот образец.

 С R AS (ВЫБРАТЬ 1 КАК n) 
 ВЫБРАТЬ n + 1 ИЗ R

Запрос (ВЫБРАТЬ 1 КАК n) теперь есть имя — R . Мы ссылаемся на это имя в SELECT n + 1 FROM R . Здесь Р — это таблица с одной строкой и одним столбцом, содержащая число 1. Результатом всего выражения является число 2.

Рекурсивная версия инструкции WITH ссылается на себя при вычислении выходных данных.

Использование рекурсивного оператора with.

Чтобы рекурсия работала, нам нужно с чего-то начать и решить, когда рекурсия должна остановиться. Для этого обычно рекурсивный оператор с оператором имеет следующую форму.

Результаты выполнения рекурсии.

Важно отметить, что базовый запрос не использует R, но рекурсивный запрос ссылается на R. На первый взгляд кажется, что это бесконечный цикл, для вычисления R нам нужно вычислить R. Но здесь есть одна загвоздка. R на самом деле не ссылается на себя, он просто ссылается на предыдущий результат, и когда предыдущий результат является пустой таблицей, рекурсия останавливается. На самом деле было бы полезно думать об этом как об итерации, а не о рекурсии!

Вот что происходит: сначала выполняется базовый запрос, который берет все необходимое для вычисления результата R0. Второй рекурсивный запрос выполняется с R0 в качестве входных данных, то есть R ссылается на R0 в рекурсивном запросе при первом выполнении. Рекурсивный запрос дает результат R1, и это то, на что R будет ссылаться при следующем вызове. И так до тех пор, пока рекурсивный запрос не вернет пустой результат. В этот момент все промежуточные результаты объединяются.

Блок-схема алгоритма выполнения рекурсивного запросаПоследовательность выполнения рекурсивного запроса

Довольно абстрактно. Возьмем конкретный пример, посчитаем до 3.

Запуск рекурсивного оператора со счетом до трех.

Базовый запрос возвращает число 1 , рекурсивный запрос принимает его под именем countUp и выдает число 2 , которое является входом для следующего рекурсивного вызова. Когда рекурсивный запрос возвращает пустую таблицу ( n >= 3 ), результаты вызовов складываются вместе.

Иллюстрация результатов вызова, сложенных вместе.

Осторожно, на таком счете далеко не уедешь. Есть предел рекурсии. По умолчанию он равен 100, но его можно расширить с помощью параметра MAXRECURSION (зависит от MS SQL Server). Практически, было бы плохой идеей увеличить лимит рекурсии. Графики могут иметь циклы, а ограниченная глубина рекурсии может быть хорошим защитным механизмом, позволяющим предотвратить плохое поведение запроса.

ОПЦИЯ (MAXRECURSION 200)

Вот еще один пример, поиск предков человека:

Использование рекурсии для поиска предков человека. Оператор кода для использования рекурсии для поиска предков человека.

Базовый запрос находит родителя Фрэнка — Мэри, рекурсивный запрос берет этот результат под именем Ancestor и находит родителей Мэри, которыми являются Дэйв и Ева, и это продолжается до тех пор, пока мы больше не сможем найти родителей.

Иллюстрация результатов рекурсии для поиска предков человека. Таблица, включающая год рождения для поиска родителей человека.

Теперь этот запрос обхода дерева может быть основой для дополнения запроса некоторой другой интересующей информацией. Например, имея в таблице год рождения, мы можем вычислить, сколько лет было родителю, когда родился ребенок. Следующий запрос делает именно это вместе с отображением родословных. Для этого он обходит дерево сверху вниз. parentAge равно нулю в первой строке, потому что по имеющимся у нас данным мы не знаем, когда родилась Алиса.

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

Убрать — рекурсивный запрос ссылается на результат базового запроса или предыдущего вызова рекурсивного запроса. Цепочка останавливается, когда рекурсивный запрос возвращает пустую таблицу.

В следующем посте мы рассмотрим рекурсию SQL с алгебраической точки зрения и рассмотрим рекурсивные хранимые процедуры.

[ОБНОВЛЕНИЕ] Сообщение дополнено комментариями пользователей Reddit kagato87 и GuybrushFourpwood.

[ПРИМЕЧАНИЕ] Примеры кода предназначены для MS-SQL. Другие СУБД могут иметь немного другой синтаксис.

Введение в рекурсивный SQL

Крейг С. Маллинз

Если вы программист SQL, изучение методов рекурсивного SQL может повысить вашу производительность. Рекурсивный запрос — это запрос, который ссылается сам на себя. Я думаю, что лучший способ быстро понять концепцию рекурсии — это подумать о зеркале, которое отражается в другом зеркале, и когда вы смотрите в него, вы видите бесконечные отражения себя. Это рекурсия в действии.

Различные продукты СУБД реализуют рекурсивный SQL по-разному. Рекурсия реализована в стандарте SQL-99 с использованием общих табличных выражений (CTE). DB2, Microsoft SQL Server, Oracle и PostgreSQL поддерживают рекурсивные запросы с использованием CTE. Обратите внимание, что Oracle также предлагает альтернативный синтаксис с использованием конструкции CONNECT BY, который мы здесь обсуждать не будем.

CTE можно рассматривать как именованную временную таблицу в операторе SQL, которая сохраняется на время выполнения этого оператора. В одном операторе SQL может быть много CTE, но каждое из них должно иметь уникальное имя. CTE определяется в начале запроса с использованием предложения WITH.

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

 

Рис. 1. Пример иерархии .

Таблицу, содержащую эти данные, можно настроить следующим образом:

    CREATE TABLE ORG_CHART

      (MGR_ID        SMALLINT,
       EMP_ID        SMALLINT, 9 0003

       EMP_NAME      CHAR(20))
    ;

Конечно, это простая реализация, и для производственной иерархии, вероятно, потребуется гораздо больше столбцов. Но простота этой таблицы подойдет для наших целей изучения рекурсии. Чтобы данные в этой таблице соответствовали нашей диаграмме, мы загрузим таблицу следующим образом:

MGR_ID             EMP_ID         EMP_NAME

  -1                 1            BIG BOSS

90 004   1                 2            ЛАКИ

  1                 3            LIL BOSS

  1                 4            BOOTLICKER

  2                  5             GRUNT

  3                  6            РУКОВОДИТЕЛЬ КОМАНДЫ

  6                  7            LOW MAN

  6                   8            SCRUB

Для MGR_ID самого верхнего узла задано некоторое значение, указывающее, что для этого узла нет родителя row, в данном случае используется –1. Теперь, когда мы загрузили данные, мы можем написать запрос для обхода иерархии с использованием рекурсивного SQL. Предположим, нам нужно отчитаться по всей организационной структуре под LIL BOSS. Следующий рекурсивный SQL с использованием CTE сделает свое дело:

     С EXPL (MGR_ID, EMP_ID, EMP_NAME) AS

     (

      SELECT ROOT. MGR_ID, ROOT.EMP_ID, ROOT.EMP_NAME

      FROM  ORG_CHART   ROOT

      WHERE  ROOT.MGR_ID = 3

 

      UNION ALL

      ВЫБРАТЬ CHILD.MGR_ID, CHILD.EMP_ID, CHILD.EMP_NAME

      FROM   EXPL PARENT, ORG_CHART CHILD

      WHERE  PARENT.EMP_ID = CHILD.MGR_ID

     )

 

     SELECT   DISTINCT MGR_ID, EMP_ID, EMP_NAME

     FROM     EXPL

     ORDER BY MGR_ID, EMP_ID;

Результатами выполнения этого запроса будут:

MGR_ID            EMP_ID         EMP_NAME

  1                          3            LIL BOSS

  3                 6           РУКОВОДИТЕЛЬ КОМАНДЫ

  6                  7                   8            SCRUB

Давайте разобьем этот довольно сложный запрос на его составные части, помогающие понять, что происходит. Во-первых, рекурсивный запрос реализуется с использованием предложения WITH (с использованием CTE). CTE называется EXPL. Первый SELECT запускает насос для инициализации «корня» поиска. В нашем случае начать с EMP_ID 3, то есть LIL BOSS.

Следующий SELECT представляет собой внутреннее соединение, объединяющее CTE с таблицей, на которой основано CTE. Вот где в дело вступает рекурсия. Часть определения CTE ссылается сама на себя. Наконец, мы ВЫБИРАЕМ из CTE. Подобные запросы могут быть написаны, чтобы полностью разрушить иерархию, чтобы получить всех потомков любого заданного узла.

Рекурсивный SQL может быть очень элегантным и эффективным. Однако из-за сложности понимания рекурсии разработчиками ее иногда считают «слишком неэффективной для частого использования». Но если у вас есть деловая потребность в обходе или взрыве иерархий в вашей базе данных, рекурсивный SQL, вероятно, будет вашим наиболее эффективным вариантом. Что еще ты собираешься делать? Вы можете создавать предварительно разобранные таблицы, но это требует денормализации и большой предварительной обработки, которая не будет эффективной.