SQL код скопирован в буфер обмена

SQLtest.online

Практика

Уроки

Тест

EN PT FR

Урок 6.5: Рекурсивные CTE для Иерархических Данных

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

Что такое Рекурсивные CTE?

Рекурсивная CTE — это общее табличное выражение, которое ссылается на само себя, позволяя обходить иерархические структуры данных. В отличие от обычных CTE, которые выполняются один раз, рекурсивные CTE выполняются итеративно до тех пор, пока не будет выполнено условие завершения.

Распространенные случаи использования рекурсивных CTE:

  • Организационные иерархии: Отношения сотрудник-руководитель
  • Деревья категорий: Категории продуктов с подкатегориями
  • Спецификация материалов (BOM): Отношения деталей и поддеталей
  • Структуры файловых систем: Папки и подпапки
  • Социальные сети: Отношения друг-друга
  • Географические иерархии: Страна > Область > Город

Синтаксис Рекурсивной CTE

Общий синтаксис рекурсивной CTE:

WITH RECURSIVE имя_cte AS (
    -- Начальный член (базовый случай)
    SELECT ...
    FROM таблица
    WHERE условие
    
    UNION ALL
    
    -- Рекурсивный член (рекурсивный случай)
    SELECT ...
    FROM таблица
    JOIN имя_cte ON условие
)
SELECT * FROM имя_cte;

Компоненты:

  • WITH RECURSIVE: Ключевое слово, вводящее рекурсивную CTE
  • Начальный член: Начальный запрос, возвращающий начальные строки (базовый случай)
  • UNION ALL: Объединяет начальный и рекурсивный члены
  • Рекурсивный член: Запрос, который ссылается на саму CTE
  • Завершение: Рекурсия останавливается, когда рекурсивный член не возвращает строк

Как Работают Рекурсивные CTE

Процесс выполнения:

  1. Выполнить начальный член: Получить начальный набор строк
  2. Выполнить рекурсивный член: Использовать результаты шага 1
  3. Повторить шаг 2: Использовать результаты предыдущей итерации
  4. Продолжать до тех пор, пока: Рекурсивный член не вернет строк
  5. Вернуть все результаты: Объединенные результаты всех итераций

Базовый Пример: Последовательность Чисел

Начнем с простого примера, генерирующего последовательность чисел:

WITH RECURSIVE последовательность_чисел AS (
    -- Начальный член: начать с 1
    SELECT 1 AS n
    
    UNION ALL
    
    -- Рекурсивный член: добавить 1 к предыдущему значению
    SELECT n + 1
    FROM последовательность_чисел
    WHERE n < 10
)
SELECT n
FROM последовательность_чисел;

Результат:

n
--
1
2
3
4
5
6
7
8
9
10

Как это работает:

  1. Начало: Возвращает 1
  2. Итерация 1: 1 + 1 = 2
  3. Итерация 2: 2 + 1 = 3
  4. ... продолжается, пока n < 10 не станет ложным
  5. Последняя итерация: Возвращает 10, но 10 < 10 ложно, поэтому рекурсия останавливается

Пример Иерархии Сотрудников

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

-- Пример таблицы сотрудников
CREATE TABLE employee (
    employee_id INT PRIMARY KEY,
    employee_name VARCHAR(100),
    manager_id INT,
    title VARCHAR(100)
);

-- Пример данных
INSERT INTO employee VALUES
    (1, 'Алиса Джонсон', NULL, 'Генеральный директор'),
    (2, 'Боб Смит', 1, 'Вице-президент по разработке'),
    (3, 'Кэрол Уайт', 1, 'Вице-президент по продажам'),
    (4, 'Дэвид Браун', 2, 'Руководитель разработки'),
    (5, 'Ева Дэвис', 2, 'Руководитель разработки'),
    (6, 'Фрэнк Миллер', 3, 'Руководитель отдела продаж'),
    (7, 'Грейс Уилсон', 4, 'Старший разработчик'),
    (8, 'Генри Мур', 4, 'Разработчик'),
    (9, 'Айви Тейлор', 5, 'Разработчик'),
    (10, 'Джек Андерсон', 6, 'Торговый представитель');

Поиск Всех Подчиненных

Чтобы найти всех сотрудников, подчиняющихся конкретному руководителю (прямо или косвенно):

WITH RECURSIVE подчиненные AS (
    -- Начало: Начать с руководителя
    SELECT
        employee_id,
        employee_name,
        manager_id,
        title,
        0 AS уровень
    FROM
        employee
    WHERE
        employee_name = 'Боб Смит'
    
    UNION ALL
    
    -- Рекурсия: Найти прямых подчиненных
    SELECT
        e.employee_id,
        e.employee_name,
        e.manager_id,
        e.title,
        s.уровень + 1
    FROM
        employee e
    INNER JOIN
        подчиненные s ON e.manager_id = s.employee_id
)
SELECT
    employee_id,
    employee_name,
    title,
    уровень
FROM
    подчиненные
ORDER BY
    уровень, employee_name;

Результат:

employee_id | employee_name   | title                       | уровень
------------|-----------------|-----------------------------|---------
2           | Боб Смит        | Вице-президент по разработке| 0
4           | Дэвид Браун     | Руководитель разработки     | 1
5           | Ева Дэвис       | Руководитель разработки     | 1
7           | Грейс Уилсон    | Старший разработчик         | 2
8           | Генри Мур       | Разработчик                 | 2
9           | Айви Тейлор     | Разработчик                 | 2

Построение Полной Организационной Схемы

Чтобы отобразить полную иерархию от генерального директора вниз:

WITH RECURSIVE оргсхема AS (
    -- Начало: Начать с генерального директора (нет руководителя)
    SELECT
        employee_id,
        employee_name,
        manager_id,
        title,
        0 AS уровень,
        CAST(employee_name AS VARCHAR(1000)) AS путь
    FROM
        employee
    WHERE
        manager_id IS NULL
    
    UNION ALL
    
    -- Рекурсия: Добавить каждый уровень
    SELECT
        e.employee_id,
        e.employee_name,
        e.manager_id,
        e.title,
        oc.уровень + 1,
        CONCAT(oc.путь, ' > ', e.employee_name)
    FROM
        employee e
    INNER JOIN
        оргсхема oc ON e.manager_id = oc.employee_id
)
SELECT
    REPEAT('  ', уровень) || employee_name AS иерархия,
    title,
    уровень,
    путь
FROM
    оргсхема
ORDER BY
    путь;

Результат:

иерархия                       | title                        | уровень | путь
-------------------------------|------------------------------|---------|----------------------------------------
Алиса Джонсон                  | Генеральный директор         | 0       | Алиса Джонсон
  Боб Смит                     | Вице-президент по разработке | 1       | Алиса Джонсон > Боб Смит
    Дэвид Браун                | Руководитель разработки      | 2       | Алиса Джонсон > Боб Смит > Дэвид Браун
      Грейс Уилсон             | Старший разработчик          | 3       | Алиса Джонсон > Боб Смит > Дэвид Браун > Грейс Уилсон
      Генри Мур                | Разработчик                  | 3       | Алиса Джонсон > Боб Смит > Дэвид Браун > Генри Мур
    Ева Дэвис                  | Руководитель разработки      | 2       | Алиса Джонсон > Боб Смит > Ева Дэвис
      Айви Тейлор              | Разработчик                  | 3       | Алиса Джонсон > Боб Смит > Ева Дэвис > Айви Тейлор
  Кэрол Уайт                   | Вице-президент по продажам   | 1       | Алиса Джонсон > Кэрол Уайт
    Фрэнк Миллер               | Руководитель отдела продаж   | 2       | Алиса Джонсон > Кэрол Уайт > Фрэнк Миллер
      Джек Андерсон            | Торговый представитель       | 3       | Алиса Джонсон > Кэрол Уайт > Фрэнк Миллер > Джек Андерсон

Пример Дерева Категорий

Поработаем с иерархией категорий продуктов:

-- Пример таблицы категорий
CREATE TABLE category (
    category_id INT PRIMARY KEY,
    category_name VARCHAR(100),
    parent_category_id INT
);

-- Пример данных
INSERT INTO category VALUES
    (1, 'Электроника', NULL),
    (2, 'Компьютеры', 1),
    (3, 'Телефоны', 1),
    (4, 'Ноутбуки', 2),
    (5, 'Настольные ПК', 2),
    (6, 'Игровые ноутбуки', 4),
    (7, 'Бизнес-ноутбуки', 4),
    (8, 'Смартфоны', 3),
    (9, 'Обычные телефоны', 3);

Поиск Всех Подкатегорий

Чтобы найти все подкатегории под "Компьютеры":

WITH RECURSIVE дерево_категорий AS (
    -- Начало: Начать с Компьютеров
    SELECT
        category_id,
        category_name,
        parent_category_id,
        0 AS глубина,
        CAST(category_name AS VARCHAR(1000)) AS путь
    FROM
        category
    WHERE
        category_name = 'Компьютеры'
    
    UNION ALL
    
    -- Рекурсия: Получить все подкатегории
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        ct.глубина + 1,
        CONCAT(ct.путь, ' > ', c.category_name)
    FROM
        category c
    INNER JOIN
        дерево_категорий ct ON c.parent_category_id = ct.category_id
)
SELECT
    category_id,
    REPEAT('  ', глубина) || category_name AS иерархия_категорий,
    глубина,
    путь
FROM
    дерево_категорий
ORDER BY
    путь;

Результат:

category_id | иерархия_категорий  | глубина | путь
------------|---------------------|---------|--------------------------------------
2           | Компьютеры          | 0       | Компьютеры
4           |   Ноутбуки          | 1       | Компьютеры > Ноутбуки
6           |     Игровые ноутбуки| 2       | Компьютеры > Ноутбуки > Игровые ноутбуки
7           |     Бизнес-ноутбуки | 2       | Компьютеры > Ноутбуки > Бизнес-ноутбуки
5           |   Настольные ПК     | 1       | Компьютеры > Настольные ПК

Поиск Предков

Чтобы найти все родительские категории конкретной категории:

WITH RECURSIVE предки_категории AS (
    -- Начало: Начать с Игровых ноутбуков
    SELECT
        category_id,
        category_name,
        parent_category_id,
        0 AS уровень_выше
    FROM
        category
    WHERE
        category_name = 'Игровые ноутбуки'
    
    UNION ALL
    
    -- Рекурсия: Получить родительские категории
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        ca.уровень_выше + 1
    FROM
        category c
    INNER JOIN
        предки_категории ca ON c.category_id = ca.parent_category_id
)
SELECT
    category_id,
    category_name,
    уровень_выше
FROM
    предки_категории
ORDER BY
    уровень_выше;

Результат:

category_id | category_name    | уровень_выше
------------|------------------|--------------
6           | Игровые ноутбуки | 0
4           | Ноутбуки         | 1
2           | Компьютеры       | 2
1           | Электроника      | 3

Пример Спецификации Материалов (Bill of Materials)

Классический случай использования рекурсивных CTE — это изучение спецификаций материалов (деталей и поддеталей):

-- Пример таблицы деталей
CREATE TABLE parts (
    part_id INT PRIMARY KEY,
    part_name VARCHAR(100),
    quantity INT
);

-- Пример таблицы спецификации материалов
CREATE TABLE bom (
    parent_part_id INT,
    child_part_id INT,
    quantity_needed INT,
    PRIMARY KEY (parent_part_id, child_part_id)
);

-- Пример данных
INSERT INTO parts VALUES
    (1, 'Велосипед', 1),
    (2, 'Рама', 1),
    (3, 'Колесо', 2),
    (4, 'Шина', 1),
    (5, 'Обод', 1),
    (6, 'Спица', 36);

INSERT INTO bom VALUES
    (1, 2, 1),  -- Велосипеду нужна 1 Рама
    (1, 3, 2),  -- Велосипеду нужно 2 Колеса
    (3, 4, 1),  -- Колесу нужна 1 Шина
    (3, 5, 1),  -- Колесу нужен 1 Обод
    (5, 6, 36); -- Ободу нужно 36 Спиц

Подсчет Общего Количества Необходимых Деталей

Чтобы найти все детали, необходимые для сборки велосипеда:

WITH RECURSIVE разбор_деталей AS (
    -- Начало: Начать с продукта верхнего уровня
    SELECT
        p.part_id,
        p.part_name,
        1 AS количество,
        0 AS уровень,
        CAST(p.part_name AS VARCHAR(1000)) AS путь
    FROM
        parts p
    WHERE
        p.part_name = 'Велосипед'
    
    UNION ALL
    
    -- Рекурсия: Разобрать спецификацию
    SELECT
        p.part_id,
        p.part_name,
        pe.количество * b.quantity_needed,
        pe.уровень + 1,
        CONCAT(pe.путь, ' > ', p.part_name)
    FROM
        разбор_деталей pe
    INNER JOIN
        bom b ON pe.part_id = b.parent_part_id
    INNER JOIN
        parts p ON b.child_part_id = p.part_id
)
SELECT
    part_id,
    REPEAT('  ', уровень) || part_name AS иерархия_деталей,
    количество,
    уровень,
    путь
FROM
    разбор_деталей
ORDER BY
    путь;

Результат:

part_id | иерархия_деталей | количество | уровень | путь
--------|------------------|------------|---------|---------------------------
1       | Велосипед        | 1          | 0       | Велосипед
2       |   Рама           | 1          | 1       | Велосипед > Рама
3       |   Колесо         | 2          | 1       | Велосипед > Колесо
4       |     Шина         | 2          | 2       | Велосипед > Колесо > Шина
5       |     Обод         | 2          | 2       | Велосипед > Колесо > Обод
6       |       Спица      | 72         | 3       | Велосипед > Колесо > Обод > Спица

Обратите внимание, что нам нужно всего 72 спицы: 2 колеса × 1 обод на колесо × 36 спиц на обод = 72 спицы.

Предотвращение Бесконечных Циклов

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

1. Ограничение Максимальной Глубины

WITH RECURSIVE ограниченная_рекурсия AS (
    SELECT
        category_id,
        category_name,
        parent_category_id,
        0 AS глубина
    FROM
        category
    WHERE
        parent_category_id IS NULL
    
    UNION ALL
    
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        lr.глубина + 1
    FROM
        category c
    INNER JOIN
        ограниченная_рекурсия lr ON c.parent_category_id = lr.category_id
    WHERE
        lr.глубина < 10  -- Ограничение максимальной глубины
)
SELECT * FROM ограниченная_рекурсия;

2. Отслеживание Посещенных Узлов

WITH RECURSIVE безопасный_обход AS (
    SELECT
        category_id,
        category_name,
        parent_category_id,
        ARRAY[category_id] AS посещенные_id
    FROM
        category
    WHERE
        parent_category_id IS NULL
    
    UNION ALL
    
    SELECT
        c.category_id,
        c.category_name,
        c.parent_category_id,
        st.посещенные_id || c.category_id
    FROM
        category c
    INNER JOIN
        безопасный_обход st ON c.parent_category_id = st.category_id
    WHERE
        NOT (c.category_id = ANY(st.посещенные_id))  -- Предотвращение циклов
)
SELECT * FROM безопасный_обход;

Соображения Производительности

1. Индексирование Столбцов Родитель-Потомок

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

CREATE INDEX idx_employee_manager ON employee(manager_id);
CREATE INDEX idx_category_parent ON category(parent_category_id);

2. Ограничение Наборов Результатов

Используйте предложения WHERE для ограничения области рекурсии:

WITH RECURSIVE подчиненные AS (
    SELECT employee_id, employee_name, manager_id, 0 AS уровень
    FROM employee
    WHERE employee_name = 'Боб Смит'
    
    UNION ALL
    
    SELECT e.employee_id, e.employee_name, e.manager_id, s.уровень + 1
    FROM employee e
    INNER JOIN подчиненные s ON e.manager_id = s.employee_id
    WHERE s.уровень < 3  -- Только 3 уровня вглубь
)
SELECT * FROM подчиненные;

3. Использование Подходящих Типов Соединений

  • Используйте INNER JOIN, когда вам нужны только совпадающие строки
  • Используйте LEFT JOIN, когда хотите включить конечные узлы без потомков

Практический Случай Использования: Система Тредов/Комментариев

Распространенный паттерн веб-приложений — это вложенные комментарии или форумные треды:

CREATE TABLE comments (
    comment_id INT PRIMARY KEY,
    parent_comment_id INT,
    user_name VARCHAR(100),
    comment_text TEXT,
    created_at TIMESTAMP
);

WITH RECURSIVE тред_комментариев AS (
    -- Начало: Комментарии верхнего уровня
    SELECT
        comment_id,
        parent_comment_id,
        user_name,
        comment_text,
        0 AS глубина,
        CAST(comment_id AS VARCHAR(1000)) AS путь_сортировки
    FROM
        comments
    WHERE
        parent_comment_id IS NULL
    
    UNION ALL
    
    -- Рекурсия: Вложенные ответы
    SELECT
        c.comment_id,
        c.parent_comment_id,
        c.user_name,
        c.comment_text,
        ct.глубина + 1,
        CONCAT(ct.путь_сортировки, '-', LPAD(c.comment_id::TEXT, 10, '0'))
    FROM
        comments c
    INNER JOIN
        тред_комментариев ct ON c.parent_comment_id = ct.comment_id
)
SELECT
    REPEAT('  ', глубина) || user_name AS пользователь_с_отступом,
    comment_text,
    глубина
FROM
    тред_комментариев
ORDER BY
    путь_сортировки;

Основные Выводы

  • Рекурсивные CTE позволяют обходить иерархические данные с отношениями родитель-потомок
  • Синтаксис WITH RECURSIVE включает начальный член и рекурсивный член
  • Начальный член определяет начальную точку (базовый случай)
  • Рекурсивный член ссылается на саму CTE и обрабатывает каждую итерацию
  • Завершение происходит, когда рекурсивный член не возвращает строк
  • Распространенные случаи использования: Оргсхемы, деревья категорий, спецификации материалов, файловые системы
  • Отслеживание уровня: Включите столбец глубины/уровня для понимания позиции в иерархии
  • Построение пути: Объединяйте пути для отображения полной родословной
  • Предотвращение бесконечных циклов: Используйте ограничения глубины или отслеживание посещенных узлов
  • Производительность: Индексируйте родительские столбцы и ограничивайте глубину рекурсии, когда возможно
  • Универсальность: Работает с любой самоссылающейся табличной структурой

Рекурсивные CTE — это незаменимый инструмент для работы с древовидными и иерархическими данными в SQL. Они превращают сложные многозапросные операции в элегантные решения с одним запросом.

В следующем модуле мы изучим оконные функции для расширенного анализа данных.