Изменение задачи - отображаем часть иерархии

Предположим, требуется вывести только часть иерархии, начиная с конкретных узлов, не обязательно корневых. Например, если иерархия объемная, это позволит сократить объем вывода, либо просто отбросить ненужные уровни.

В целом формулировка задачи не изменится, но добавится одно условие:

• Запрос должен выводить всю иерархию, либо может быть задан начальный узел (или список узлов) иерархии, для визуализации ее части, начинающейся с заданного узла

Подход к решению в целом сохранится, но добавится еще одно CTE, и в три будут внесены изменения:

1. Mapping: без изменений

2. RootNodes: новое CTE для извлечения всех начальных узлов. Имеет 2 варианта - базовый, в котором извлекаются все корневые узлы, не имеющие "родителя", и альтернативный, в котором задается список конкретных узлов. Только один из вариантов должен быть в запросе (второй нужно закомментировать)

3. Levels: измененное рекурсивное CTE, соединяющее на первом уровне Mapping и RootNodes (через внутреннее соединение), и рекурсивно собирающее последовательность ИД «родителей» каждого узла parents, полное имя узла full_path и уровень иерархии node_level

4. Branches: измененное CTE, в котором для всех узлов, не являющихся корневыми/начальными, определяется вид «ветви», а так же определяются «сквозные» ветви родительских узлов для использования их «потомками». В CTE используется окно WindowByParents с партицированием по полю Levels.parents, и с помощью функции LAST_VALUE(id) OVER WindowByParents определяется особый вид «ветви» для «конечных» узлов уровня. Для определения корневых/начальных узлов используется левое внешнее соединение Levels и RootNodes

5. Tree: рекурсивное CTE, соединяющее на первом уровне Mapping и RootNodes (через внутреннее соединение), и рекурсивно собирающее все сквозные «ветки» родителей узла в поле all_through

6. FineTree: без изменений

Измененный запрос (включает все CTE)

with recursive 
Mapping as (
	select 
		id 					as node_id, 
		parent_directory_id as parent_node_id,
		name 				as node_name
	from Files
),

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 						-- Exactly one line below should be uncommented
		parent_node_id is null	-- Uncomment to build from root(s)
		-- node_id in (1)	-- Uncomment to add node_id(s) into the brackets
),

Levels as (
	select
		node_id,
		parent_node_id,
		node_name,
		cast(parent_node_id as char(2000)) as parents,
		cast(node_name as char(2000)) as full_path,
		0 as node_level
	from
		Mapping
		inner join RootNodes on node_id = root_node_id
		
	union
	
	select 
		Mapping.node_id, 
		Mapping.parent_node_id,
		Mapping.node_name,
		concat(coalesce(concat(prev.parents, '-'), ''), cast(Mapping.parent_node_id as char)),
		concat_ws(' ', prev.full_path, Mapping.node_name),
		prev.node_level + 1
	from 
		Levels as prev
		inner join Mapping on Mapping.parent_node_id = prev.node_id
),

Branches as (
	select
		node_id,
		parent_node_id,
		node_name,
		parents,
		full_path,
		node_level,
		case
			when root_node_id is null then
				case
					when node_id = last_value(node_id) over WindowByParents then '└── '
					else '├── '
				end
			else ''
		end as node_branch,
		case
			when root_node_id is null then
				case
					when node_id = last_value(node_id) over WindowByParents then '    '
					else '│   '
				end
			else ''
		end as branch_through
	from
		Levels
		left join RootNodes on node_id = root_node_id
	window WindowByParents as (
		partition by parents
		order by node_name
		rows between current row and unbounded following
		)
	order by full_path
),

Tree as (
	select
		node_id,
		parent_node_id,
		node_name,
		parents,
		full_path,
		node_level,
		node_branch,
		cast(branch_through as char(2000)) as all_through
	from
		Branches
		inner join RootNodes on node_id = root_node_id
		
	union
	
	select 
		Branches.node_id,
		Branches.parent_node_id,
		Branches.node_name,
		Branches.parents,
		Branches.full_path,
		Branches.node_level,
		Branches.node_branch,
		concat(prev.all_through, Branches.branch_through)
	from 
		Tree as prev
		inner join Branches on Branches.parent_node_id = prev.node_id
),

FineTree as (
	select
		tr.node_id,
		tr.parent_node_id,
		tr.node_name,
		tr.parents,
		tr.full_path,
		tr.node_level,
		concat(coalesce(parent.all_through, ''), tr.node_branch, tr.node_name) as fine_tree
	from
		Tree as tr
		left join Tree as parent on
			parent.node_id = tr.parent_node_id
	order by tr.full_path
)

select fine_tree, node_id from FineTree
;

Пришлось отступить от принципа изолированности CTE по "уровням" - RootNodes используется трижды в соединениях в разных CTE. Но, так как он не извлекает данные иерархии для визуализации, а служит только для параметризации запроса, буду считать, что это не считается )

С базовым вариантом RootNodes...

... запрос отрабатывает так же, как в предыдущей части статьи, и в MySQL 8.2, и в SQLite 3.44.1

Теперь проверю отображение части иерархии, подставив ИД 3 и 11 в альтернативный RootNodes:

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 							-- Keep uncommented exactly one line below 
		-- parent_node_id is null	-- Uncomment to build from root(s)
		node_id in (3, 11)	-- Uncomment to add node_id(s) into the brackets
),

Результат запроса полностью соответствует с ожиданиям: выведена часть иерархии, начиная с узлов с заданными в RootNodes ИД

Ещё одна файловая структура

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

DROP TABLE IF EXISTS Files;
CREATE TABLE Files
(
    id                  INT,
    name                VARCHAR(40),
    parent_directory_id INT
);

INSERT INTO Files (id, name, parent_directory_id)
VALUES  (1, 'desktop', null),
        (2, 'another_folder', 1),
        (3, 'FOLDER', 2),
        (4, 'code.jpeg', 3),
        (5, 'player10.json', 3),
        (6, 'player11.json', 3),
        (7, 'player5.json', 3),
        (8, 'player6.json', 3),
        (9, 'stepik.png', 3),
        (10, 'FOLDER_HERE', 2),
        (11, 'Crying All the Time.mp3', 10),
        (12, 'player1.json', 10),
        (13, 'player14.json', 10),
        (14, 'player39.json', 2),
        (15, 'player45.json', 2),
        (16, 'player46.json', 2),
        (17, 'python.pdf', 2),
        (18, 'shopping_list.txt', 2),
        (19, 'folder', 1),
        (20, 'player19.json', 19),
        (21, 'player20.json', 19),
        (22, 'player21.json', 19),
        (23, 'player42.json', 19),
        (24, 'player47.json', 19),
        (25, 'player48.json', 19),
        (26, 'player49.json', 19);

Иерархия в базовом варианте RootNodes соответствует ожиданиям (MySQL):

fine_tree                          |node_id|
-----------------------------------+-------+
desktop                            |      1|
├── another_folder                 |      2|
│   ├── FOLDER                     |      3|
│   │   ├── code.jpeg              |      4|
│   │   ├── player10.json          |      5|
│   │   ├── player11.json          |      6|
│   │   ├── player5.json           |      7|
│   │   ├── player6.json           |      8|
│   │   └── stepik.png             |      9|
│   ├── FOLDER_HERE                |     10|
│   │   ├── Crying All the Time.mp3|     11|
│   │   ├── player1.json           |     12|
│   │   └── player14.json          |     13|
│   ├── player39.json              |     14|
│   ├── player45.json              |     15|
│   ├── player46.json              |     16|
│   ├── python.pdf                 |     17|
│   └── shopping_list.txt          |     18|
└── folder                         |     19|
    ├── player19.json              |     20|
    ├── player20.json              |     21|
    ├── player21.json              |     22|
    ├── player42.json              |     23|
    ├── player47.json              |     24|
    ├── player48.json              |     25|
    └── player49.json              |     26|

Так же часть иерархии:

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 							-- Keep uncommented exactly one line below 
		-- parent_node_id is null	-- Uncomment to build from root(s)
		node_id in (3, 10, 17)	-- Uncomment to add node_id(s) into the brackets
),

Есть нюанс - в этой иерархии на одном уровне находятся "папки" с похожими именами "FOLDER" и "FOLDER_HERE". Если отсортировать их имена в списке потомков узла "another_folder", они расположатся в правильном порядке, но если будет выполняться сортировка всех узлов по полным путям, как в CTE FineTree для финального отображения, результат сортировки будет зависеть от символа-разделителя, через который собрана строка full_path. Если заменить пробел " " косой чертой "/", привычной для отображения путей в файловой структуре, результат будет некорректным:

Другая таблица - категории товаров

Приведу еще один небольшой пример со схожей структурой таблицы, но измененными именами,

кому это интересно

DROP TABLE IF EXISTS Categories;
CREATE TABLE Categories
(
    category_id         INT,
    parent_category_id 	INT,
    name                VARCHAR(40)
);

INSERT INTO Categories (category_id, parent_category_id, name)
VALUES 	(1, NULL, 'Товары для дома'),
		(2, NULL, 'Цифровая техника'),
		(3, 1, 'Бытовая техника'),
		(4, 2, 'Ноутбуки и аксессуары'),
		(5, 2, 'Фотоаппараты'),
		(6, 2, 'Игровые консоли'),
		(7, 2, 'Аудиотехника'),
		(8, 2, 'Сотовые телефоны'),
		(9, 4, 'Ноутбуки'),
		(10, 4, 'Рюкзаки');

Для настройки запроса на новый источник нужно изменить Mapping:

with recursive 
Mapping as (
	select 
		category_id			as node_id, 
		parent_category_id	as parent_node_id,
		name 				as node_name
	from Categories
),

Запрос в базовом варианте отрабатывает корректно, хотя это уже перестало быть сюрпризом ))

Возможные ошибки

Так как в запрос можно передать ИД нескольких начальных узлов, некоторые их сочетания спровоцируют ошибки. Для примеров буду использовать последнюю "короткую" иерархию

Передача родителя и потомка как начальных узлов

Такой вариант спровоцирует дублирование узлов и искажение отображения иерархии

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 							-- Keep uncommented exactly one line below 
		-- parent_node_id is null	-- Uncomment to build from root(s)
		node_id in (2, 4)	-- Uncomment to add node_id(s) into the brackets
),

Специфика "Списка смежности" не позволяет простым способом обнаружить такую коллизию в параметрах, если только переданные узлы не являются прямыми родителем и потомком, что не подойдет в общем случае.
И distinct ситуацию так же исправит лишь отчасти, предлагаю убедиться в этом самостоятельно

Циклическая иерархия, ошибка при попытке отображения

Можно создать "зацикленную" иерархию, например, так:

DROP TABLE IF EXISTS Categories;
CREATE TABLE Categories
(
    category_id         INT,
    parent_category_id 	INT,
    name                VARCHAR(40)
);

INSERT INTO Categories (category_id, parent_category_id, name)
VALUES 	(1, NULL, 'Товары для дома'),
  		(2, 9, 'Цифровая техника'),    -- Ссылка на потомок "Ноутбуки"
		(3, 1, 'Бытовая техника'),
		(4, 2, 'Ноутбуки и аксессуары'),
		(5, 2, 'Фотоаппараты'),
		(6, 2, 'Игровые консоли'),
		(7, 2, 'Аудиотехника'),
		(8, 2, 'Сотовые телефоны'),
		(9, 4, 'Ноутбуки'),
		(10, 4, 'Рюкзаки');

При попытке построения такой иерархии от узла с ИД = 2 произойдет либо переполнение поля full_path:, либо переполнение вложенности рекурсии, в зависимости от конкретной СУБД и ее настроек

RootNodes as (
	select node_id as root_node_id
	from Mapping
	where 				-- Keep uncommented exactly one line below 
		-- parent_node_id is null	-- Uncomment to build from root(s)
  		node_id in (2)	-- Uncomment to add node_id(s) into the brackets
),

В MySQL 8.2:

SQL Error [3636] [HY000]: Recursive query aborted after 1001 iterations. Try increasing @cte_max_recursion_depth to a larger value.

SQLite просто зависает

При базовом отображении "от корня" это "кольцо узлов" просто не попадет в выборку, поэтому бороться с этой ошибкой я не вижу особого смысла - ее можно воспроизвести, сознательно "закольцевав" часть иерархии и передав один или несколько узлов кольца как параметр в RootNodes

Продолжение следует - рассмотрю "большие" иерархии и реализацию запроса в PostrgreSQL