Рекурсивные запросы sql: Рекурсивные SQL запросы / Хабр

Содержание

Рекурсивные SQL запросы / Хабр

Anthony

17 июня 2008 в 00:33

SQL *

Рекурсивны SQL запросы являются одним из способов решения проблемы дерева и других проблем, требующих рекурсивную обработку. Они были добавлены в стандарт SQL 99. До этого они уже существовали в Oracle. Несмотря на то, что стандарт вышел так давно, реализации запоздали. Например, в MS SQL они появились только в 2005-ом сервере.

Рекурсивные запросы используют довольно редко, прежде всего, из-за их сложного и непонятного синтаксиса:

with [recursive] <имя_алиаса_запроса> [ (<список столбцов>) ]
as (<запрос>)
<основной запрос>

В MS SQL нет ключевого слова recursive, а в остальном все тоже самое. Такой синтаксис поддерживается в DB2, Sybase iAnywhere, MS SQL и во всех базах данных, которые поддерживают стандарт SQL 99.

Проще разобрать на примере. Предположим, есть таблица:

create table tree_sample (
id integer not null primary key,
id_parent integer foreign key references tree_sample (id),
nm varchar(31) )

id – идентификатор
id_parent – ссылка на родитель
nm – название.

Для вывода дерева:

with recursive tree (nm, id, level, pathstr)
as (select nm, id, 0, cast(» as text)
   from tree_sample
   where id_parent is null
union all
   select tree_sample.nm, tree_sample.id, t.level + 1, tree.pathstr + tree_sample.nm
   from tree_sample
     inner join tree on tree.id = tree_sample.id_parent)
select id, space( level ) + nm as nm
from tree
order by pathstr

Этот пример выведет дерево по таблице с отступами. Первый запрос из tree_sample этот запрос выдаст все корни дерева. Второй запрос соединяет между собой таблицу tree_sample и tree, которая определяется этим же запросом.

Этот запрос дополняет таблицу узлами дерева.

Сначала выполняется первый запрос. Потом к его результатам добавляются результаты второго запроса, где данные таблица tree – это результат первого запроса. Затем снова выполняется второй запрос, но данные таблицы tree – это уже результат предыдущего выполнения второго запроса. И так далее. На самом деле база данных работает не совсем так, но результат будет таким же, как результат работы описанного алгоритма.

После этого данные этой таблицы можно использовать в основном запросе как обычно.

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

Теги:

SQL
рекурсия

Хабы:

Всего голосов 37: ↑35 и ↓2 +33

Просмотры

135K

Комментарии 51

Антон Жердев @Anthony

Пользователь

Комментарии Комментарии 51

sql — Как написать рекурсивный запрос?

Кратко опишу алгоритм.

Если я правильно понял, задача состоит из трёх частей:

От переданного ИДа идём вверх по дереву, пока не найдём департамент.
от департамента находим всех его детей, выбираем из них только с типом employee
выбираем тех, кто есть в таблице cache_extensions

пункты 1. и 2. первая и вторая рекурсивная часть рекурсивного СТЕ:

—таблички

USE tempdb;
IF OBJECT_ID('dept_employees')IS NOT NULL DROP TABLE dept_employees
IF OBJECT_ID('employees')IS NOT NULL DROP TABLE employees
IF OBJECT_ID('ogpo_dept')IS NOT NULL DROP TABLE ogpo_dept
IF OBJECT_ID('cash_extensions')IS NOT NULL DROP TABLE cash_extensions
CREATE TABLE dept_employees(
  ID INT NOT NULL,
  parent_id INT NULL,
  obj_id INT NOT NULL,
  obj_type VARCHAR(4) NOT NULL
)
CREATE TABLE employees(
  ID INT NOT NULL,
  FIO VARCHAR(255) NOT NULL,
  dept_id INT NOT NULL
)
/*CREATE TABLE ogpo_dept(
  ID INT NOT NULL,
  Name VARCHAR(255) NOT NULL
)*/
CREATE TABLE cash_extensions(
  ID INT NOT NULL,
  FIO VARCHAR(255) NOT NULL
)

—данные

INSERT dept_employees VALUES
--depts
(10, NULL, 1, 'dept'),
(20, 10,    2, 'dept'),
(30, NULL, 3, 'dept'),
(40, 30,    4, 'dept'),
--emps
(50, 20, 1, 'emp'),
(60, 50, 2, 'emp'),
(70, 50, 3, 'emp'),
(80, 40, 4, 'emp'),
(90, 80, 5, 'emp'),
(100,30, 6, 'emp')
INSERT employees VALUES
(1, 'd1->d2->p1', 2),
(2, 'd1->d2->p1->p2', 2),
(3, 'd1->d2->p1->p3', 2),
(4, 'd3->d4->p4', 4),
(5, 'd3->d4->p4->p5', 4),
(6, 'd3->p6', 3)
INSERT cash_extensions VALUES
(1, 'd1->d2->p1'),
(2, 'd1->d2->p1->p2'),
(3, 'd1->d2->p1->p3'),
(4, 'd3->d4->p4'),
(5, 'd3->d4->p4->p5'),
(6, 'd3->p6')

—процедура

IF OBJECT_ID('FindAllCasheExtemsionsFromDeptByEmployee') IS NOT NULL DROP PROC FindAllCasheExtemsionsFromDeptByEmployee
GO
CREATE PROC FindAllCasheExtemsionsFromDeptByEmployee 
  @EmployeeId INT
AS
WITH CTE AS(
  SELECT 
    CASE obj_type 
      WHEN 'emp' THEN 'find_depart' 
      WHEN 'dept' THEN 'find_childs'
    END what, id AS child_Id, parent_id AS parend_id, obj_id, E. obj_type
  FROM dept_employees E
  WHERE id = @EmployeeId
  UNION ALL
  --идём вверх по дереву до первого департамента
  SELECT 
    CASE E.obj_type 
      WHEN 'emp' THEN 'find_depart' 
      WHEN 'dept' THEN 'find_childs'
    END what, id AS child_Id, parent_id AS parend_id, E.obj_id, E.obj_type
  FROM CTE
    JOIN dept_employees E ON CTE.parend_id = E.ID
  WHERE what = 'find_depart'
  UNION ALL
  --теперь идём вниз по дереву, находим всех потомков
  SELECT 'find_childs' what, id AS child_Id, parent_id AS parend_id, E.obj_id, E.obj_type
  FROM CTE
    JOIN dept_employees E ON CTE.child_id = E.parent_id
  WHERE what = 'find_childs'
)
SELECT E.*
FROM CTE
  JOIN employees E ON CTE.obj_id = E.ID
  JOIN cash_extensions C ON E.FIO = C.FIO
WHERE CTE.obj_type = 'emp' AND CTE.what = 'find_childs'
OPTION (MAXRECURSION 0) 
GO

—тесты и результаты

EXEC FindAllCasheExtemsionsFromDeptByEmployee 10 -- d1
/*
ID     FIO    dept_id
1      d1->d2->p1   2
2      d1->d2->p1->p2      2
3      d1->d2->p1->p3      2
*/
EXEC FindAllCasheExtemsionsFromDeptByEmployee 50 -- p1
/*
ID     FIO    dept_id
1      d1->d2->p1   2
2      d1->d2->p1->p2      2
3      d1->d2->p1->p3      2
*/
EXEC FindAllCasheExtemsionsFromDeptByEmployee 70 -- p3
/*
ID     FIO    dept_id
1      d1->d2->p1   2
2      d1->d2->p1->p2      2
3      d1->d2->p1->p3      2
*/
EXEC FindAllCasheExtemsionsFromDeptByEmployee 40 -- d4
/*
ID     FIO    dept_id
4      d3->d4->p4   4
5      d3->d4->p4->p5      4
*/
EXEC FindAllCasheExtemsionsFromDeptByEmployee 90 -- p5
/*
ID     FIO    dept_id
4      d3->d4->p4   4
5      d3->d4->p4->p5      4
*/
EXEC FindAllCasheExtemsionsFromDeptByEmployee 100 -- p6
/*
ID     FIO    dept_id
4      d3->d4->p4   4
5      d3->d4->p4->p5      4
6      d3->p6 3
*/

пс: задача очень плохо описана.

Рекурсивное выражение SQL с визуальным объяснением

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

Что такое рекурсивное выражение общей таблицы SQL (CTE)?

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

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

Рекурсивный SQL: что это значит и как это работает?

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

Визуальное представление того, как рекурсивный запрос работает в SQL. | Изображение: Денис Лукичев

Пример SQL: ВЫБЕРИТЕ ИЗ R1, R2, R3, ГДЕ .

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

Визуальное представление запроса, который принимает что-то и ничего не производит. | Изображение: Денис Лукичев

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

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

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

| Изображение: Денис Лукичев

Пример SQL: SELECT 1 .

Или он ничего не может взять и ничего не произвести.

Визуальное представление запроса, ничего не принимающего и ничего не производящего. | Изображение: Денис Лукичев

SELECT 1 WHERE 1 = 2

Подробнее о блок-диаграммах DataUnderstanding

На жаргоне SQL это называется общим табличным выражением (CTE). Это позволяет вам назвать результат и позже ссылаться на него в других запросах.

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

Вот пример.

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

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

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

Использование рекурсивного общего табличного выражения. | Скриншот: Денис Лукичев

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

Рекурсивный оператор with в SQL. | Изображение: Денис Лукичев

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

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

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

Блок-схема алгоритма выполнения рекурсивного запроса. | Изображение: Денис ЛукичевПоследовательность выполнения рекурсивного запроса. | Изображение: Денис Лукичев

Примеры рекурсивного SQL

Если это слишком абстрактно, давайте рассмотрим пару конкретных примеров.

Пример 1. Считаем до трех

Первый пример, который мы рассмотрим, — это счет до трех.

Запуск рекурсивного оператора с оператором для выполнения подсчета до трех команд. | Скриншот: Денис Лукичев

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

Иллюстрация результатов вызова, сложенных вместе. | Изображение: Денис Лукичев

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

Подробнее о руководстве SQLA по разрешению расхождений данных в SQL

Пример 2. Поиск предков

Давайте рассмотрим другой пример, поиск предков человека.

Использование рекурсии для поиска предков человека. | Изображение: Денис Лукичев Рекурсивная общая таблица для поиска предков человека. | Скриншот: Денис Лукичев

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

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

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

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

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

Рекурсивный запрос SQL Server с рекурсивным CTE (выражение общей таблицы)

Структура SQL Server Recursive Query впервые представлена с улучшением SQL Server 2005 Common Table Expression . CTE (Common Table Expression) имеет широкую область применения в программировании T-SQL. Но что делает CTE незаменимым при разработке SQL, так это его функции создания рекурсивных запросов.

Рекурсивный запрос SQL Server состоит из трех разделов.

WITH RecursiveCTEQuery AS ( {Якорный запрос} UNION ALL {Запрос присоединен к RecursiveCTEQuery} ) SELECT * FROM RecursiveCTEQuery

Код

Якорный запрос в рекурсивном CTE-запросе — это первый раздел. Якорный запрос — это стартовая строка для рекурсии. Например, в якорном запросе вы выбираете элемент верхнего уровня. Или вы выбираете конкретную строку, используя предложение WHERE в якорном запросе.

Якорный запрос — это первая строка в первой рекурсии выражения CTE.

Вторая часть рекурсивного выражения CTE SQL — это оператор SELECT из целевой таблицы. Обычно это та же таблица, которая используется в якоре SELECT. Но на этот раз это INNER JOIN с рекурсивным CTE. Условие INNER JOIN определяет, переходите ли вы к более высоким уровням или запрашиваете более низкие уровни. Это выражение INNER JOIN устанавливает отношение родитель/потомок между строками в основной таблице sql.

Результирующие наборы внутренних разделов CTE объединяются в один возвращаемый набор с использованием выражения UNION ALL

Последний раздел — это инструкция SELECT, которая запрашивает само CTE.

Предположим, что компания, которую мы собираемся использовать в примерах рекурсивных запросов SQL Server, называется Adventure Works Cycle. И предположим, что иерархическая организационная структура компании Adventure Works Cycle выглядит следующим образом.

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

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

Сразу после команды SQL CREATE TABLE образец данных для приведенной выше организационной схемы заполняется с помощью команды SQL INSERT INTO. Мы будем использовать эту таблицу sql и данные в ней для примеров рекурсивных запросов SQL Server в этом руководстве по T-SQL.

Создание организационных структур таблицы ( BusinessUnitID smallint identity(1,1), BusinessUnit varchar(100) Not Null, ParentUnitID smallint ) вставить в OrganizationalStructures значения ("Adventure Works Cycle", NULL), ("Customer Care", 1), («Сервис», 1), («Продажи и маркетинг», 1), («Поддержка клиентов», 2), («Поддержка OEM», 2), («Центральный регион», 3) , («Восточный регион», 3), («Западный регион», 3), («OEM», 4), («Сбытовой маркетинг», 4), («Национальные счета», 4), («Продажи на местах», 4), («Маркетинг в национальном канале», 11), («Маркетинг в розничных каналах», 11), («Центральный регион», 13), («Восточный регион», 13), («Западный регион», 13), («Велосипеды», 15), («Велозапчасти», 15)

Код

Давайте посмотрим, как выглядят данные нашего примера, используя команду SQL SELECT.

выберите * из организационных структур

Код

В этом руководстве по SQL с использованием рекурсивного CTE (Common Table Expression) программисты SQL вскоре смогут запрашивать иерархические данные SQL и возвращать список бизнес-единиц, связанных друг с другом с родительскими/дочерними свойствами

Следующее CTE — Common Table Expression является образцом рекурсивного запроса SQL Server .
Приведенный ниже рекурсивный запрос SQL возвращает список строк из OrganizationalStructures, для которых BusinessUnitID равен 1, и подэлементы этой строки привязки.

WITH Recursive_CTE AS ( SELECT child.BusinessUnitID, child.BusinessUnit, CAST(child.ParentUnitID as SmallInt) ParentUnitID, CAST(NULL as varchar(100)) ParentUnit Из организационных структур Child , где бизнесментид = 1

Союз All

SELECT Child. BusinessUnitid, Child.BusinessUnit, Child.parentUnitid, Parent.BusinessNit ParentUnit от Recurive_Cte ParentSture. .BusinessUnitID ) SELECT * FROM Recursive_CTE

Код

Наш первый рекурсивный CTE-запрос SQL Server возвращает все записи в таблице, поскольку выбор привязки возвращает элемент верхнего уровня в иерархии организационной диаграммы.

Конечно, важно создавать повторно используемый код на SQL, как и на других языках программирования. Разработчики TSQL могут сохранить приведенный выше рекурсивный запрос SQL Server в хранимой процедуре, внеся простые изменения в выражение CTE, чтобы сделать его параметрическим.

Мы можем изменить привязку SELECT во внутреннем выражении CTE, чтобы изменить рекурсивный запрос. Как видно из следующего кода t-sql, запрос привязки возвращает строки с BusinessUnitID, равным значению параметра хранимой процедуры @BusinessUnitID. Собственно, это все изменения, необходимые для создания параметрических рекурсивных запросов.

Создать процедуру sp_listorganizationalStructureSof ( @businessUnitid smallint ) as с рекурсивным_кте ( Select Child.BusinessUnitid, Child. ParentUnit FROM OrganizationalStructures дочерний WHERE BusinessUnitID = @BusinessUnitID

UNION ALL

SELECT child.BusinessUnitID, child.BusinessUnit, Child.ParentUnitid, Parent.BusinessUnit ParentUnit от recursive_cte Parent Внутреннее объединение организационных структур на ребенка. PparentUnitid = Parent.BusinessUnitid ) SELECT * из recurisive_cte Go ExeclageStorizationalStractorsOf 110032 Go ExeclarganizationafationOf 110032 Go .

Код

Сразу после создания хранимой процедуры я выполнил SP для возврата бизнес-единиц, определенных ниже Channel Marketing (прямой или косвенный комбинированный)

Давайте изменим приведенный выше рекурсивный запрос SQL Server, чтобы добавить некоторую подробную информацию об иерархии и придать некоторые визуальные эффекты следующим образом:

WITH Recursive_CTE AS ( SELECT child. BusinessUnitID, CAST(child.BusinessUnit as varchar(100)) BusinessUnit, CAST(child.ParentUnitID as SmallInt) ParentUnitID, CAST(NULL as varChar(100)) 0 ParentUnitID, CAST(NULL as varChar(100)) 0 ParentUnitID ('>> ' as varchar(100)) LVL, CAST(child.BusinessUnitID as varchar(100)) Иерархия, 1 в качестве рекурсионного вещества из организационной структуры Child , где BusinessUnitid = 1

Union All

SELECT Child.BusinessUnitid, CAST (LVL + Child.BusinessUnit As varchar (100)) As BusinessUnit, ребенок. ProntUnitid, родитель. ParentUnit, CAST('>> ' + LVL as varchar(100)) AS LVL, CAST(Hierarchy + ':' + CAST(child.BusinessUnitID as varchar(100)) as varchar(100)) Hierarchy, RecursionLevel + 1 AS RecursionLevel FROM Recursive_CTE parent INNER JOIN OrganizationalStructures дочерний ON child.ParentUnitID = parent.BusinessUnitID ) SELECT * FROM Recursive_CTE ORDER BY Hierarchy

Код

Вывод приведенного выше запроса SQL Recursive CTE будет выглядеть следующим образом:

Я надеюсь, что разработчикам SQL так же, как и мне, понравится структура рекурсивных запросов SQL Server.