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

Цю статтю написано занадто професійним стилем зі специфічною термінологією, що може бути незрозумілим для більшості читачів. Ви можете допомогти вдосконалити цю статтю, зробивши її зрозумілою для неспеціалістів без втрат змісту. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (квітень 2018)

Ієрархічний запит — тип запиту 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; її було впроваджено 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]
• Ієрархічна модель даних
• Транзитивне замикання

• Date, C. J. (2011). SQL and Relational Theory: How to Write Accurate SQL Code (англійською) (вид. 2-е). O'Reilly Media. с. 159—163. ISBN 978-1-4493-1640-2.

Академічні підручники. Зверніть увагу, що вони покривають тільки SQL:1999 (та Datalog), але не розширення Oracle.

• Silberschatz, Abraham; Korth, Henry; Sudarshan, S. (2010). Database System Concepts (англійською) (вид. 6-е). McGraw-Hill. с. 187—192. ISBN 978-0-07-352332-3.
• Ramakrishnan, Raghu; Gehrke, Johannes (2003). Chapter 24. Database management systems (англійською) (вид. 3-є). McGraw-Hill. ISBN 978-0-07-246563-1.
• Garcia-Molina, Hector; Ullman, Jeffrey D.; Widom, Jennifer (2009). Database systems: the complete book (англійською) (вид. 2-е). Pearson Prentice Hall. с. 437—445. ISBN 978-0-13-187325-4.

• https://stackoverflow.com/questions/1731889/cycle-detection-with-recursive-subquery-factoring [Архівовано 14 квітня 2020 у Wayback Machine.]
• http://explainextended.com/2009/11/18/sql-server-are-the-recursive-ctes-really-set-based/ [Архівовано 1 серпня 2020 у Wayback Machine.]
• https://web.archive.org/web/20131114094211/http://gennick.com/with.html
• http://www.cs.duke.edu/courses/fall04/cps116/lectures/11-recursion.pdf [Архівовано 1 серпня 2020 у Wayback Machine.]
• http://www.blacktdn.com.br/2015/06/blacktdn-mssql-usando-consulta-cte.html [Архівовано 28 липня 2020 у Wayback Machine.]