Как работает рекурсия? Иерархические / рекурсивные SQL запросы в базах данных SQLite: WITH RECURSIVE

Помощь проекту:
WMR: R288272666982
WMZ: Z293550531456
Яндекс.Деньги: 410011531129223

Рубрика SQLite на сайте: http://zametkinapolyah.ru/zametki-o-mysql/sqlite/
Паблик блога в ВК: https://vk.com/zametkinapolyah
Тематическая группа в ВК: https://vk.com/zametki_bd

— Рекурсивные/иерархические SQL запросы в базах данных SQLite:
— WITH RECURSIVE clause.

/*
Не все любят рекурсивные или как еще говорят иерархические
SQL запросы. Потому что не всем и не всегда просто понять
рекурсию, поэтому, обычно, рекурсивные запросы применяют
либо те, кто рекурсию понимают, либо те, кто не ленится
эксперементировать и пробовать и в конце концов тоже начинает
понимать рекурсию.

Здесь мы попробуем разобраться и с рекурсией и с
иерархическими SQL-запросами. SQLite, как и многие другие
СУБД – реляционная: база данных состоит из таблиц, таблицы
в свою очередь состоят из строк и столбцов, другими словами:
данные представлены двумерно.

В нашей жизни, так уж получается, что не все объекты удобно
описывать двумерной моделью: крупная международная компания
с холдингами и филиалами в различных странах, файловая система
компьютера, карьерная лестница в компании – эти данные намного
удобнее описывать иерархической моделью.

Конечно, например, структуру крупной компании можно описать
несколькими таблицами, например, таблицы стран: Китай, Россия,
США, Англия, Япония. Далее спуститься на уровень ниже
и создать таблицы регионов для страны: Москва, Иваново,
Новосибирск, Омск. Но такой подход не всегда удобен, поскольку
не всегда известна глубина вложенности.

В 1999 году международное сообщество решило эту проблему
путем добавления в стандарт (SQL-1999) рекурсивных SQL-запросов,
хотя компания Oracle это сделала немного раньше (и по Ораклу
рекурсивные запросы называются иерархическими).

*/

http://sqlite.org/lang_with.html

/*
Общий синтаксис рекурсивных запросов в SQLite выглядит следующим
образом:

WITH [RECURSIVE] cte-table-name AS (select-stmt);

Но это не всё, рекурсивный SQL запрос состоит из двух запросов SELECT,
если эта фраза в данном случае уместна:

WITH RECURSIVE
cte-table-name AS (initial-select UNION [ALL] recursive-select)
cte-select;

2 1 cte-table-name 1 2

initial-select (не должен в себя включать ORDER BY, LIMIT, OFFSET) –
точка, откуда начинается рекурсия.

recursive-select – рекурсивный запрос, который будет вполняться
до тех пор, пока условие не будет выполнено, два верхних запроса
позволяют создать наполнить нашу импровизированную таблицу данными
cte-select – позволяет работать с данными таблицы

1-1000

WITH RECURSIVE
table1(col1) AS (
VALUES(1)
UNION ALL
SELECT col1+1 FROM table1
WHERE col1(знак меньше)1000)
SELECT col1 FROM table1;

WITH RECURSIVE
table1(col1) AS (
SELECT 1
UNION ALL
SELECT col1+1 FROM table1
LIMIT 1000
)
SELECT col1 FROM table1;
table1
col1
2

3 2 1 table1 1 2 3

— Создадим таблицу
CREATE TABLE org(
name TEXT PRIMARY KEY,
boss TEXT REFERENCES org
);

— наполним ее данными
INSERT INTO org VALUES(‘Alice’,NULL);
INSERT INTO org VALUES(‘Bob’,’Alice’);
INSERT INTO org VALUES(‘Cindy’,’Alice’);
INSERT INTO org VALUES(‘Dave’,’Bob’);
INSERT INTO org VALUES(‘Emma’,’Bob’);
INSERT INTO org VALUES(‘Fred’,’Cindy’);
INSERT INTO org VALUES(‘Gail’,’Cindy’);

SELECT * FROM org;

— Для лучшего понимания работы рекурсии и поиска значений
— рекомендую вам погуглить:
— FIFO, поиск в глубину и поиск в ширину

0|Alice
1|Bob
1|Cindy
2|Dave
2|Emma
2|Fred
2|Gail

— поиск в глубину
WITH RECURSIVE
under_alice(name,level) AS (
VALUES(‘Alice’,0)
UNION ALL
SELECT org.name, under_alice.level+1
FROM org JOIN under_alice ON org.boss=under_alice.name
ORDER BY 2 DESC
)
SELECT level, name FROM under_alice;

Alice
…Bob
…Cindy
……Dave
……Emma
……Fred
……Gail

WITH RECURSIVE
under_alice(name,level) AS (
VALUES(‘Alice’,0)
UNION ALL
SELECT org.name, under_alice.level+1
FROM org JOIN under_alice ON org.boss=under_alice.name
ORDER BY 2 DESC
)
SELECT substr(‘……….’,1,level*3) || name FROM under_alice;