Предыстория

В процессе тестирования одного курса по SQL на stepik.org встретилась такая задача:

Вам доступна таблица Files, хранящая информацию о расположении файлов и папок внутри системы:

+----+--------------------------+---------------------+
| id | name                     | parent_directory_id |
+----+--------------------------+---------------------+
| 1  | deskop                   | NULL                |
| 2  | test                     | 1                   |
| 3  | Картинки                 | 2                   |
| 4  | 1.jpg                    | 3                   |
| 5  | avatar.png               | 3                   |
| 6  | certificate.png          | 3                   |
| 7  | py.png                   | 3                   |
| 8  | World_Time_Zones_Map.png | 3                   |
| 9  | Снимок экрана.png        | 3                   |
| 10 | Неравенства.djvu         | 2                   |
| 11 | Программы                | 2                   |
| 12 | image_util.py            | 11                  |
| 13 | sort.py                  | 11                  |
| 14 | Разные файлы             | 2                   |
| 15 | astros.json              | 14                  |
+----+--------------------------+---------------------+

Напишите запрос, извлекающий из данных идентификаторы всех файлов и папок, а также указывающий для каждого файла или папки путь до него в следующем формате:

.../<название родительской папки>/<название файла или папки>

Задача несложно решается рекурсивным обобщенным табличным выражением (Common Table Expression - далее CTE), но иллюстрация «зацепила» - захотел вывести такую "картинку" SQL запросом, а это уже не так просто. Поэтому появилась...

Задача

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

Поиск чего-то готового результата не дал, и я постарался сделать универсальное решение.

Итак, дана таблица, в которой определена иерархическая структура (классический Adjacency list - "Список смежности"). Каждый узел иерархии имеет как минимум (но не ограничиваясь только этим):

• Уникальный идентификатор (ИД)

• Имя (неуникальное), может содержать любые символы UTF-8

• Идентификатор родительского узла, равный NULL для узлов верхнего уровня

Необходимо с помощью одного составного (с использованием CTE) SQL запроса отобразить иерархию, в соответствии с иллюстрацией выше, соблюдая следующие требования:

• Каждый уровень иерархии имеет отступ в 4 символа

• Узлы одного уровня отсортированы по возрастанию имени

• Прямые "потомки" одного "родителя" располагаются на ветвях вида "├──", кроме последнего узла на "└──"

• Сквозные ветви имеют вид "│ "

• Ветви соседних уровней разделены одним пробелом

• Запрос должен быть работоспособен на распространенных СУБД: MySQL, SQLite, PostgreSQL (с возможной адаптацией под конкретную СУБД при необходимости).

Подход к решению

Я разделил задачу - оформил запрос в виде нескольких CTE, выполняющих определенную подзадачу каждый:

1. Mapping: приведение набора полей в источнике к универсальному. Позволит использовать запрос с любым источником, настроив в Mapping соответствие полей источника, не меняя остальные части

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

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

4. Tree: рекурсивное CTE, собирающее все сквозные «ветки» родителей узла в поле all_through

5. FineTree: финальное CTE, соединяющее сквозные ветки, собственные ветки и имена узлов в поле fine_tree. Его можно извлечь в собственно запросе из FineTree, как и любое из доступных в нем полей, определенных на каждом из предыдущих уровней, кроме фрагментов «ветвей», они не представляют ценности вне иерархии

Так же хотелось бы соблюсти «изолированность» CTE, чтобы каждое из них использовало только предыдущее, без необходимости соединений нескольких CTE в одном запросе.

Дисклеймер по оформлению: в реализованных SQL запросах не используется ALLCAPS. Актуальные среды прекрасно справляются с подсветкой синтаксиса, и следование Руководству по стилю SQL в этом аспекте с моей точки зрения не является необходимостью.

Иерархия в MySQL и SQLite

Выбрал для реализации запросов две СУБД:

• MySQL, весьма популярная СУБД, имеет ряд совместимых форков

• SQLite вообще чемпион по популярности. Несмотря на встраиваемость, чрезвычайно богата функционально, поддерживает и CTE, и оконные функции в необходимом для решения задачи объеме (и сверх того)

Запросы будут проверяться в обоих средах.

Создание таблицы с тестовыми данными

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

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, 'test', 1),
       (3, 'Картинки', 2),
       (4, '1.jpg', 3),
       (5, 'avatar.png', 3),
       (6, 'certificate.png', 3),
       (7, 'py.png', 3),
       (8, 'World_Time_Zones_Map.png', 3),
       (9, 'Снимок экрана.png', 3),
       (10, 'Неравенства.djvu', 2),
       (11, 'Программы', 2),
       (12, 'image_util.py', 11),
       (13, 'sort.py', 11),
       (14, 'Разные файлы', 2),
       (15, 'astros.json', 14);

Mapping

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

При использовании с другим источником, необходимо заменить имя таблицы Files и имена ее полей на актуальные

Levels

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
	where parent_node_id is null
	
	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
),

В рекурсивном CTE на верхнем уровне нужно определить типы полей. В MySQL для текстовых данных возможно использовать только тип CHAR, а VARCHAR или TEXT выдадут ошибку.
SQLite здесь гораздо менее требователен, в нем можно равноценно использовать любой из перечисленных выше типов, поэтому я использовал CHAR как универсальный

Поле full_path, содержащее имена всех родительских узлов на пути данному, и использующееся для корректной сортировки узлов иерархии при финальном выводе, в запросе ограничено 2000 символов, но можно выбрать и большее значение если необходимо - может пригодиться при длинных именах узлов.
Если запрос "упадет" с ошибкой вида Data truncation: Data too long for column 'full_path' - это сигнал, что нужно увеличить длину поля.

Для строкового представления соединения идентификаторов всех родительских узлов в parents используется "-", а для full_path - символ пробела CHAR(32), он должен быть "меньше" любого символа, который может встретиться в поле node_name, чтобы сортировка производилась корректно с учетом "родительских" узлов. В следующей части статьи будет соответствующий пример

Branches

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

Вместо вложенных CASE WHEN … END можно было бы использовать более компактный тернарный IF(), но совместимость его с другими СУБД ниже, как и "читабельность".

Tree

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
	where parent_node_id is null
	
	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
),

Использовано то же самое значение 2000 символов для ограничения длины поля со всеми «сквозными ветвями» all_through

Мы почти у цели!

FineTree

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 from FineTree
;

Длина поля fine_tree будет ограничена теми же 2000 символами, и это достаточно для отображения иерархии с более чем 450 уровнями (4 символа на уровень + до 200 символов имя узла), никто не будет визуализировать таких монстров.

Вуаля:

fine_tree                           |
------------------------------------+
desktop                             |
└── test                            |
    ├── Картинки                    |
    │   ├── 1.jpg                   |
    │   ├── avatar.png              |
    │   ├── certificate.png         |
    │   ├── py.png                  |
    │   ├── World_Time_Zones_Map.png|
    │   └── Снимок экрана.png       |
    ├── Неравенства.djvu            |
    ├── Программы                   |
    │   ├── image_util.py           |
    │   └── sort.py                 |
    └── Разные файлы                |
        └── astros.json             |

В MySQL и SQLite результат идентичен

All Together Now

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

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
	where parent_node_id is null
	
	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 parent_node_id is not null then 
				case 
					when node_id = last_value(node_id) over WindowByParents then '└── ' 
					else '├── ' 
				end 
			else '' 
		end as node_branch,
		case 
			when parent_node_id is not null then 
				case 
					when node_id = last_value(node_id) over WindowByParents then '    ' 
					else '│   ' 
				end 
			else '' 
		end as branch_through
	from Levels 
	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
	where parent_node_id is null
	
	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 from FineTree
;

Довольно длинно, если бы не самоограничение "изолированности" CTE можно было бы прилично сократить, но зато так более универсально.

Продолжение следует – в нем расширю функциональность запроса для отображения не всей, а части иерархии, и рассмотрю работу запроса на других примерах иерархий в MySQL и SQLite, включая возможные ошибки

Ссылки

Варианты реализации иерархических структур в SQL (En)