Рекурсивные запросы в SQLite
Рекурсивные запросы стандарта SQL-1999 хорошо описаны в блоге Postgres Professional на Хабре. В данной статье я покажу их на примере простой базы в SQLite3.
При проектировании БД иногда возникает необходимость хранить древовидные
структуры, а затем использовать в запросах эти деревья целиком.
Для этого в язык была добавлена конструкция WITH RECURSIVE, где каждая
итерация запроса ссылается на результат предыдущей итерации.
По сути, это хвостовая рекурсия — что-то вроде цикла.
WITH RECURSIVE переменная (колонки)
AS (
результат первой итерации
UNION ALL
результат каждой последующей итерации
)
SELECT * FROM переменная;
То, что я назвал здесь переменная на самом деле означает сразу две вещи:
внутри WITH это имя указывает на рабочую таблицу,
которая очищается и заполняется новым результатом после каждой итерации, а снаружи —
на результат рекурсивного запроса, т.е. объединение результатов всех итераций.
Например, следующий запрос выведет 10 случайных чисел.
Если убрать ссылку на себя (FROM x) в четвертой строчке,
запрос станет нерекурсивным и вернет только две строки.
WITH RECURSIVE x (rnd) AS (
VALUES(random())
UNION ALL
SELECT random() FROM x
)
SELECT * FROM x LIMIT 10;
Рекурсивный запрос состоит из двух подзапросов,
причем второй ведёт себя примерно как подзапросы
в обычных селектах — условие WHERE меняется для
каждой строки. Давайте освежим в памяти эту возможность языка.
Подзапросы
Обычно в SQL используют JOIN, а не подзапросы,
т.к. с помощью JOIN проще объединить сразу много таблиц.
Вот как подзапросы работают. Пусть есть две таблицы: машины и цвета. На один цвет приходится много машин, где этот цвет базовый — связь один-ко-многим.
Схема с тестовыми данными: car_colors.sql
Вывести названия цветов всех машин можно с помощью джойна:
SELECT cars.vin, colors.caption
FROM cars
LEFT JOIN colors
ON cars.base_color_id = colors.id
ORDER BY cars.vin;
Можно получить тот же результат с помощью подзапроса:
SELECT cars.vin, (
SELECT caption FROM colors
WHERE id = cars.base_color_id
) AS color
FROM cars
ORDER BY cars.vin;
Запрос получения названия цвета ссылается на значение в текущей строке родительского запроса, т.е. для каждого автомобиля как бы выполняется отдельный запрос получения цвета.
Рекурсивные запросы работают примерно так же.
Добавляем рекурсию
Жизненный пример: у нас есть работники организации, которые находятся
на некоторых позициях в отделах организации. Эти отделы
являются частями бо́льших подразделений, которые через несколько уровней
вложенности входят в подразделения верхнего уровня.
Колонка parent_id указывает на строчку подразделения,
в которое входит подразделение из текущей строки.
Тестовые данные: department_tree.sql
Теперь мы хотим получить таблицу сотрудников и названий отделов, в которых они работают.
Очевидный запрос
SELECT e.id, e.first_name, e.last_name, d.caption
FROM positions p
INNER JOIN employees e ON p.employee_id = e.id
INNER JOIN divisions d ON p.division_id = d.id
ORDER BY p.id;
выдаст что-то вроде
| id | first_name | last_name | caption |
|---|---|---|---|
| … | … | … | … |
| 43 | Юрий | Свиридов | Творческая группа 2 |
| 44 | Юлия | Быкова | Сборка |
| 45 | Янна | Смирнова | Сборка |
| 46 | Ярослав | Гальцев | Слесарный цех (ЧПУ) |
| 47 | Илья | Щербаков | Слесарный цех (ЧПУ) |
| 48 | Оксана | Петренко | Листогибочный цех |
| 49 | Полина | Леонова | Цех автоматической пайки |
| 50 | Павел | Абдулов | Снабжение |
| 51 | Руслан | Иванов | Внутренняя логистика |
| … | … | … | … |
Такая таблица мало что скажет большому начальнику, ведь с его перспективы компания состоит из следующих отделов.
SELECT * FROM divisions
WHERE parent_id IS NULL;
| id | parent_id | caption |
|---|---|---|
| 1 | NULL | Отдел фундаментальных исследований |
| 2 | NULL | Отдел стратегического планирования |
| 3 | NULL | IT-отдел |
| 4 | NULL | Маркетинговый отдел |
| 5 | NULL | Проектный отдел |
| 6 | NULL | Производственный отдел |
В отчёте следует показать названия отделов верхнего уровня. Сейчас у нас есть доступ к дочерним отделам, т.е. задача сводится к получению отдела верхнего уровня из любого дочернего отдела.
Вначале, найдём результат для одной строки отчета. На первой итерации берём отдел, непосредственно указанный в позиции:
SELECT id, parent_id, caption
FROM divisions
WHERE caption = 'Листогибочный цех';
Затем сошлёмся на эту строку из следующей итерации.
Здесь, во второй части объединения, r означает предыдущую итерацию.
То есть вторая часть рекурсивного выражения ссылается на строку,
возвращенную на предыдущей итерации, и для каждой такой строки
как бы выполняется отдельный запрос.
WITH RECURSIVE r (id, parent_id, caption)
AS (
SELECT id, parent_id, caption
FROM divisions
WHERE caption = 'Листогибочный цех'
UNION ALL
SELECT divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, r
WHERE (r.parent_id = divisions.id)
)
SELECT * FROM r;
Получаем следующее.
| id | parent_id | caption |
|---|---|---|
| 623 | 62 | Листогибочный цех |
| 62 | 6 | Изготовление деталей |
| 6 | NULL | Производственный отдел |
Наконец, отбрасываем все строки, кроме верхушки дерева, с помощью
проверки на NULL.
WITH RECURSIVE r (id, parent_id, caption)
AS (
SELECT id, parent_id, caption
FROM divisions
WHERE caption = 'Листогибочный цех'
UNION ALL
SELECT divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, r
WHERE (r.parent_id = divisions.id)
)
SELECT * FROM r
WHERE parent_id IS NULL;
| id | parent_id | caption |
|---|---|---|
| 6 | NULL | Производственный отдел |
Условие второго запроса меняется для каждой строки предыдущей итерации, аналогично тому, как работают подзапросы вообще, что было показано в первой половине статьи.
Будет нагляднее, если на первой итерации достать несколько строк.
WITH RECURSIVE r (id, parent_id, caption)
AS (
SELECT id, parent_id, caption
FROM divisions
WHERE (caption like '%цех%')
OR (caption = 'Творческая группа 2')
UNION ALL
SELECT divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, r
WHERE (r.parent_id = divisions.id)
)
SELECT * FROM r;
| id | parent_id | caption |
|---|---|---|
| 52 | 5 | Творческая группа 2 |
| 621 | 62 | Слесарный цех (ЧПУ) |
| 623 | 62 | Листогибочный цех |
| 624 | 62 | Покрасочный цех |
| 5 | NULL | Проектный отдел |
| 62 | 6 | Изготовление деталей |
| 62 | 6 | Изготовление деталей |
| 62 | 6 | Изготовление деталей |
| 6 | NULL | Производственный отдел |
| 6 | NULL | Производственный отдел |
| 6 | NULL | Производственный отдел |
Как видите, вторая итерация была выполнена с разными условиями для каждой строки, полученной в ходе первой итерации, и это справедливо для всех последующих итераций.
Встроим рекурсивный запрос как подзапрос туда, где раньше выводились названия подразделений.
SELECT e.id, e.first_name, e.last_name, (
WITH RECURSIVE r (id, parent_id, caption)
AS (
SELECT id, parent_id, caption
FROM divisions
WHERE id = d.id
UNION ALL
SELECT
divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, r
WHERE (r.parent_id = divisions.id)
)
SELECT caption FROM r
WHERE parent_id IS NULL
) AS top_caption
FROM positions p
INNER JOIN employees e ON p.employee_id = e.id
INNER JOIN divisions d ON p.division_id = d.id
ORDER BY p.id;
Проблема решена.
| id | first_name | last_name | top_caption |
|---|---|---|---|
| … | … | … | … |
| 43 | Юрий | Свиридов | Проектный отдел |
| 44 | Юлия | Быкова | Производственный отдел |
| 45 | Янна | Смирнова | Производственный отдел |
| 46 | Ярослав | Гальцев | Производственный отдел |
| 47 | Илья | Щербаков | Производственный отдел |
| 48 | Оксана | Петренко | Производственный отдел |
| 49 | Полина | Леонова | Производственный отдел |
| 50 | Павел | Абдулов | Производственный отдел |
| 51 | Руслан | Иванов | Производственный отдел |
| … | … | … | … |
То же можно сделать с помощью джойна с рекурсивным запросом. Вначале получим таблицу названий верхнего уровня для всех отделов.
WITH RECURSIVE r
(
initial_id,
id,
parent_id,
caption
)
AS (
SELECT id, id, parent_id, caption
FROM divisions
UNION ALL
SELECT
r.initial_id,
divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, r
WHERE (r.parent_id = divisions.id)
)
SELECT
initial_id AS id,
caption AS top_caption
FROM r
WHERE parent_id IS NULL;
| id | top_caption |
|---|---|
| 1 | Отдел фундаментальных исследований |
| 2 | Отдел стратегического планирования |
| 3 | IT-отдел |
| 4 | Маркетинговый отдел |
| 5 | Проектный отдел |
| 6 | Производственный отдел |
| 11 | Отдел фундаментальных исследований |
| 12 | Отдел фундаментальных исследований |
| 13 | Отдел фундаментальных исследований |
| 14 | Отдел фундаментальных исследований |
| 21 | Отдел стратегического планирования |
| 22 | Отдел стратегического планирования |
| 51 | Проектный отдел |
| 52 | Проектный отдел |
| … | … |
Присоединим, используя ON вместо WHERE.
SELECT e.id, e.first_name, e.last_name,
div_view.top_caption
FROM positions p
INNER JOIN employees e ON p.employee_id = e.id
INNER JOIN divisions d ON p.division_id = d.id
INNER JOIN (
WITH RECURSIVE r
(
initial_id,
id,
parent_id,
caption
)
AS (
SELECT id, id, parent_id, caption
FROM divisions
UNION ALL
SELECT
r.initial_id,
divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, r
WHERE (r.parent_id = divisions.id)
)
SELECT
initial_id AS id,
caption AS top_caption
FROM r
WHERE parent_id IS NULL
) AS div_view ON div_view.id = d.id
ORDER BY p.id;
Наконец, можно вынести WITH-выражение за пределы селекта.
WITH RECURSIVE div_view
(
initial_id,
id,
parent_id,
top_caption
)
AS (
SELECT id, id, parent_id, caption
FROM divisions
UNION ALL
SELECT
div_view.initial_id,
divisions.id,
divisions.parent_id,
divisions.caption
FROM divisions, div_view
WHERE (div_view.parent_id = divisions.id)
)
SELECT e.id, e.first_name, e.last_name,
div_view.top_caption
FROM positions p
INNER JOIN employees e ON p.employee_id = e.id
INNER JOIN divisions d ON p.division_id = d.id
INNER JOIN div_view
ON (div_view.parent_id is NULL)
AND (div_view.initial_id = d.id)
ORDER BY p.id;
Ключевое слово WITH определяет обобщенные табличные выражения
(Common Table Expressions, CTE),
которые конструируют вре́менные наборы данных —
что-то вроде виртуальных таблиц,
вынесеных из основной части запроса.
Они могут быть и не рекурсивными.
Документация по CTE: