Оглавление

• Ответ 1
• Ответ 2

Ответ 1

В стандарте SQL рекурсивные запросы реализуются через WITH RECURSIVE (Common Table Expression, CTE).

---

1. Пример рекурсивного запроса

Задача:

Выбрать всех подчинённых сотрудника (включая подчинённых подчинённых и т.д.) из таблицы employees:

id	name	manager_id
1	Иван	NULL
2	Мария	1
3	Петр	1
4	Анна	2
5	Алексей	3

Решение:

WITH RECURSIVE employee_hierarchy AS (
    -- Базовый случай: выбираем начального сотрудника (например, Иван, id=1)
    SELECT id, name, manager_id
    FROM employees
    WHERE id = 1
    
    UNION ALL
    
    -- Рекурсивный случай: находим всех подчинённых
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN employee_hierarchy eh ON e.manager_id = eh.id
)
SELECT * FROM employee_hierarchy;

Результат:

id	name	manager_id
1	Иван	NULL
2	Мария	1
3	Петр	1
4	Анна	2
5	Алексей	3

---

2. Как работает WITH RECURSIVE?

1. Базовый запрос — начальная точка рекурсии (например, сотрудник с id = 1).
2. Рекурсивная часть — объединяется с предыдущим результатом через UNION ALL.
3. Условие остановки — рекурсия прекращается, когда новые строки не находятся.

⚠️ Важно: Если рекурсия бесконечная (например, из-за циклических связей), СУБД прервёт выполнение (в PostgreSQL — по умолчанию 1000 итераций, но можно увеличить через SET max_recursive_iterations = 10000).

---

3. Практические применения

3.1. Деревья (категории товаров, комментарии)

-- Найти все подкатегории категории "Электроника"
WITH RECURSIVE category_tree AS (
    SELECT id, name, parent_id
    FROM categories
    WHERE name = 'Электроника'
    
    UNION ALL
    
    SELECT c.id, c.name, c.parent_id
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT * FROM category_tree;

3.2. Графы (маршруты, соцсети)

-- Найти всех друзей пользователя (в глубину)
WITH RECURSIVE friend_graph AS (
    SELECT user_id, friend_id
    FROM friendships
    WHERE user_id = 1
    
    UNION ALL
    
    SELECT f.user_id, f.friend_id
    FROM friendships f
    JOIN friend_graph fg ON f.user_id = fg.friend_id
)
SELECT * FROM friend_graph;

3.3. Генерация последовательностей

-- Создать последовательность чисел от 1 до 10
WITH RECURSIVE numbers AS (
    SELECT 1 AS n
    
    UNION ALL
    
    SELECT n + 1
    FROM numbers
    WHERE n < 10
)
SELECT * FROM numbers;

---

4. Поддержка в СУБД

• PostgreSQL, Oracle, SQLite, MS SQL — полная поддержка WITH RECURSIVE.
• MySQL — поддерживает, но с ограничениями (например, нет проверки на циклы).
• SQLite — поддерживает, но без контроля глубины рекурсии.

---

5. Ограничения и оптимизация

• Глубина рекурсии — может потребоваться настройка (например, в PostgreSQL max_recursive_iterations).
• Производительность — рекурсивные запросы могут быть медленными для больших графов. Альтернатива — предварительное материализованное представление.
• Циклические связи — нужно обрабатывать отдельно (например, через NOT IN в рекурсивной части).

---

Вывод

Рекурсивные запросы в SQL — мощный инструмент для работы с иерархическими данными. Они поддерживаются большинством современных СУБД и позволяют решать задачи, которые иначе потребовали бы множества JOIN или обработки на стороне приложения.

Пример для FastAPI:

from fastapi import FastAPI
from sqlalchemy import text

app = FastAPI()

@app.get("/employee/{employee_id}/hierarchy")
def get_hierarchy(employee_id: int):
    query = text("""
        WITH RECURSIVE employee_hierarchy AS (
            SELECT id, name, manager_id
            FROM employees
            WHERE id = :employee_id
            
            UNION ALL
            
            SELECT e.id, e.name, e.manager_id
            FROM employees e
            JOIN employee_hierarchy eh ON e.manager_id = eh.id
        )
        SELECT * FROM employee_hierarchy
    """)
    result = db.execute(query, {"employee_id": employee_id}).fetchall()
    return {"hierarchy": result}

Ответ 2

Рекурсивные запросы реализуются с помощью Common Table Expressions (CTE) с ключевым словом WITH RECURSIVE.

---

Как работает рекурсия в SQL?

Рекурсивный CTE состоит из двух частей:

1. Базовый случай (anchor member): Начальный запрос, который определяет начальную точку рекурсии.
2. Рекурсивный случай (recursive member): Запрос, который ссылается на сам CTE и продолжает выполнение до тех пор, пока не будет выполнено условие завершения.

Синтаксис выглядит так:

WITH RECURSIVE cte_name AS (
    -- Базовый случай
    SELECT ...
    FROM table
    WHERE condition

    UNION ALL

    -- Рекурсивный случай
    SELECT ...
    FROM table
    JOIN cte_name ON join_condition
)
SELECT * FROM cte_name;

---

Пример использования рекурсии

1. Иерархическая структура сотрудников

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

id	name	manager_id
1	Alice	NULL
2	Bob	1
3	Charlie	1
4	David	2
5	Eve	2

Мы хотим найти всех подчинённых для конкретного руководителя (например, Alice).

WITH RECURSIVE subordinates AS (
    -- Базовый случай: начнем с Alice
    SELECT id, name, manager_id
    FROM employees
    WHERE id = 1

    UNION ALL

    -- Рекурсивный случай: найдем подчинённых текущего уровня
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates;

Результат:

• Сначала выбирается Alice (id=1).
• Затем находятся её прямые подчинённые (Bob и Charlie).
• Далее находятся подчинённые Bob и Charlie (David и Eve).

Результат будет таким:

id	name	manager_id
1	Alice	NULL
2	Bob	1
3	Charlie	1
4	David	2
5	Eve	2

---

2. Генерация последовательности чисел

Рекурсивный CTE можно использовать для генерации последовательностей чисел. Например, создадим последовательность от 1 до 10:

WITH RECURSIVE numbers AS (
    -- Базовый случай: начнем с 1
    SELECT 1 AS n

    UNION ALL

    -- Рекурсивный случай: увеличиваем число на 1
    SELECT n + 1
    FROM numbers
    WHERE n < 10
)
SELECT * FROM numbers;

Результат:

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

---

3. Обход дерева категорий

Предположим, у нас есть таблица categories с иерархической структурой:

id	name	parent_id
1	Electronics	NULL
2	Computers	1
3	Laptops	2
4	Desktops	2
5	Accessories	1

Мы хотим найти все подкатегории для "Electronics".

WITH RECURSIVE category_tree AS (
    -- Базовый случай: начнем с Electronics
    SELECT id, name, parent_id
    FROM categories
    WHERE id = 1

    UNION ALL

    -- Рекурсивный случай: найдем дочерние категории
    SELECT c.id, c.name, c.parent_id
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT * FROM category_tree;

Результат:

id  | name         | parent_id
-----|--------------|-----------
1    | Electronics  | NULL
2    | Computers    | 1
3    | Laptops      | 2
4    | Desktops     | 2
5    | Accessories  | 1

---

Ограничения рекурсии

1. Максимальная глубина: В некоторых СУБД (например, PostgreSQL) есть ограничение на максимальную глубину рекурсии (по умолчанию 1000). Это можно изменить с помощью настроек.
2. Производительность: Рекурсивные запросы могут быть медленными для больших иерархий. Используйте индексы и оптимизируйте запросы.
3. Циклические ссылки: Если в данных есть циклы (например, запись ссылается сама на себя), рекурсия может зациклиться. Убедитесь, что данные корректны.

---

Поддержка рекурсии в разных СУБД

Рекурсивные CTE поддерживаются большинством современных СУБД:

• PostgreSQL: Полная поддержка рекурсивных CTE.
• MySQL: Поддерживается с версии 8.0.
• SQL Server: Поддерживается через WITH RECURSIVE.
• Oracle: Поддерживается через CONNECT BY или рекурсивные CTE.
• SQLite: Поддерживается с версии 3.8.3.

---

Заключение

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

Вверх