Ієрархічні та рекурсивні запити в SQL

Ієрархічний запит — тип запиту SQL, що обробляє ієрархічну модель даних. Вони є особливим випадком загальніших рекурсивних нерухомих запитів, які обчислюють транзитивні замикання.

У стандарті SQL:1999 ієрархічні запити реалізовані шляхом рекурсивних загальних табличних виразів (ЗТВ). На відміну від більш ранніх умов connect-by в Oracle, рекурсивні ЗТВ було розроблено з нерухомою семантикою від початку^[1]. Рекурсивні ЗТВ зі стандарту були відносно близькі до наявної реалізації в IBM DB2 версії 2^[1]. Рекурсивні ЗТВ також підтримуються Microsoft SQL Server (починаючи з SQL Server 2008 R2)^[2], Firebird 2.1^[3], PostgreSQL 8.4+^[4], SQLite 3.8.3+^[5], IBM Informix версії 11.50+, CUBRID^[en], MariaDB 10.2+ і MySQL 8.0.1+^[6]. Tableau має документацію^[7], що описує, як ЗТВ можуть використовуватися. TIBCO Spotfire не підтримує ЗТВ, тоді як реалізації Oracle 11g Release 2 бракує нерухомої семантики.

Без загальних табличних виразів або умов connected-by можливо досягти ієрархічних запитів за допомогою користувацьких рекурсивних функцій^[8].

Загальний табличний вираз

Загальний табличний вираз, або ЗТВ (в SQL) — тимчасовий іменований результатний набір, що походить із простого запиту та визначений усередині області виконання інструкції SELECT, INSERT, UPDATE чи DELETE.

ЗТВ можна вважати альтернативами похідним таблицям (підзапитам), розрізам і вбудованим користувацьким функціям.

Загальні табличні вирази підтримуються Teradata, DB2, Firebird^[9], Microsoft SQL Server, Oracle (з рекурсією, починаючи з 11g release 2), PostgreSQL (починаючи з 8.4), MariaDB (починаючи з 10.2), MySQL (починаючи з 8.0), SQLite (починаючи з 3.8.3), HyperSQL і H2^[en] (експериментально)^[10]. Oracle називає ЗТВ «підзапитним факторингом» (англ. subquery factoring)^[11].

Синтаксис для рекурсивного ЗТВ виглядає наступним чином:

WITH [RECURSIVE] запит_with [, …]
SELECT …

де синтаксисом запит_with є:

назва_запиту [ (назва_колонки [, …]) ] AS (SELECT …)

Рекурсивні ЗТВ (або «рекурсивний підзапитний факторинг»^[12] у жаргоні Oracle) можуть використовуватися для обходу відношень (як графів або дерев), хоча синтаксис набагато більше залучений через відсутність створених автоматичних псевдо-колонок (як LEVEL нижче); якщо вони є бажаними, то їх слід створити в коді. Навчальні приклади див. у документації MSDN^[2] або IBM^[13][14].

Ключове слово RECURSIVE зазвичай не є необхідним після WITH у системах, крім PostgreSQL^[15].

В SQL:1999 рекурсивний (ЗТВ) запит може з'являтися будь-де, де дозволено запит. Можливо, наприклад, назвати результат за допомогою CREATE [RECURSIVE] VIEW^[1]. За допомогою ЗТВ усередині INSERT INTO можна наповнити таблицю даними, згенерованими з рекурсивного запиту; генерація випадкових даних можлива з використанням цієї техніки без використання жодних процедурних інструкцій^[16].

Деякі бази даних на кшталт PostgreSQL підтримують скорочений формат CREATE RECURSIVE VIEW, який внутрішньо перекладається в кодування WITH RECURSIVE^[17].

Прикладом рекурсивного запиту, що обчислює факторіал чисел від 0 до 9, є наступне:

WITH RECURSIVE temp (n, fact) AS
(SELECT 0, 1 -- Початковий підзапит
  UNION ALL
 SELECT n + 1, (n + 1) * fact -- Рекурсивний підзапит
  FROM temp
 WHERE n < 9)
SELECT * FROM temp;

CONNECT BY

Альтернативним синтаксисом є нестандартна конструкція CONNECT BY; її було впроваджено Oracle у 1980-х^[18]. До Oracle 10g конструкція була корисною тільки для обходу ациклічних графів, оскільки вона повертала помилку при виявленні будь-яких циклів; у версії 10g Oracle впровадила можливість NOCYCLE (та ключове слово), уможливлюючи роботу з обходу і за наявності циклів^[19].

CONNECT BY підтримується EnterpriseDB^[20], Oracle Database^[21], CUBRID^[en][22], IBM Informix^[23] і DB2, хоча тільки, якщо його увімкнено як режим сумісності^[24]. Синтаксис виглядає наступним чином:

SELECT список_вибірки
FROM табличний_вираз
[ WHERE … ]
[ START WITH початковий_вираз ]
CONNECT BY [NOCYCLE] { PRIOR дочірній_вираз = батьківський_вираз | батьківський_вираз = PRIOR дочірній_вираз }
[ ORDER SIBLINGS BY колонка1 [ ASC | DESC ] [, колонка2 [ ASC | DESC ] ] …
[ GROUP BY … ]
[ HAVING … ]
…

Наприклад,

Виведення з вищенаведеного запиту виглядатиме як:

 level |  працівник  | empno | менеджер
-------+-------------+-------+----------
     1 | KING        |  7839 |
     2 |   JONES     |  7566 |    7839
     3 |     SCOTT   |  7788 |    7566
     4 |       ADAMS |  7876 |    7788
     3 |     FORD    |  7902 |    7566
     4 |       SMITH |  7369 |    7902
     2 |   BLAKE     |  7698 |    7839
     3 |     ALLEN   |  7499 |    7698
     3 |     WARD    |  7521 |    7698
     3 |     MARTIN  |  7654 |    7698
     3 |     TURNER  |  7844 |    7698
     3 |     JAMES   |  7900 |    7698
     2 |   CLARK     |  7782 |    7839
     3 |     MILLER  |  7934 |    7782
(14 рядків)

Псевдо-колонки

• LEVEL
• CONNECT_BY_ISLEAF
• CONNECT_BY_ISCYCLE
• CONNECT_BY_ROOT

Унарні оператори

Наступний приклад повертає прізвище кожного працівника у відділі 10, кожного менеджера над цим працівником в ієрархії, кількість рівнів між менеджером і працівником і шлях між ними:

SELECT ename "Працівник", CONNECT_BY_ROOT ename "Менеджер",
       LEVEL - 1 "Довжина шляху", SYS_CONNECT_BY_PATH(ename, '/') "Шлях"
FROM emp
WHERE LEVEL > 1 and deptno = 10
CONNECT BY PRIOR empno = mgr
ORDER BY "Працівник", "Менеджер", "Довжина шляху", "Шлях";

Функції

• SYS_CONNECT_BY_PATH

Див. також

• Datalog також реалізує нерухомі запити
• Дедуктивні бази даних
• Деревоподібна структура
• Досяжність^[en]
• Ієрархічна модель даних
• Транзитивне замикання