Отображение иерархии в SQL запросе
Предыстория
В процессе тестирования одного курса по 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, выполняющих определенную подзадачу каждый:
Mapping: приведение набора полей в источнике к универсальному. Позволит использовать запрос с любым источником, настроив в Mapping соответствие полей источника, не меняя остальные части
Levels: рекурсивное CTE, собирающее последовательность ИД «родителей» каждого узла (parents), и полное имя узла, включающее имена всех его «родителей» (full_path).
Уровень иерархии node_level так же будет вычисляться, хотя для построения иерархии он и не требуетсяBranches: CTE, в котором определяется вид «ветки» каждого узла, а так же определяются «сквозные» ветки родительских узлов для использования их «потомками». Для этого в CTE используется окно
WindowByParentsс партицированием по полюLevels.parents, и с помощью функцииLAST_VALUE(id) OVER WindowByParentsопределяется особый вид «ветви» для «конечных» узлов уровняTree: рекурсивное CTE, собирающее все сквозные «ветки» родителей узла в поле
all_throughFineTree: финальное 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(char(9), 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(9), он должен быть «меньше» любого символа, который может встретиться в поле 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(char(9), 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)
