Хранение деревьев в базе данных. Часть первая, теоретическая

Полгода назад написал бандл ClosureTable для фреймворка Laravel 3. Поводом для написания стала вот эта замечательная презентация Билла Карвина о способах хранения и обработки иерархических данных в MySQL с использованием PHP.

Итак. Существует несколько шаблонов проектирования баз данных для хранения и обработки иерархических структур:

• Adjacency List («список смежности»)
• Materialized Path («материализованный путь»)
• Nested Sets («вложенные множества»)
• Closure Table («таблица связей»)

Что такое Closure Table

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

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

• ссылку на родительский элемент (ancestor)
• ссылку на дочерний элемент (descendant)

Пусть мы работаем над созданием очередной SuperPuper CMS и приступили к разработке модуля редактирования текстовых страниц. Нам понадобятся две таблицы:

• pages будет содержать данные о странице
• pages_treepath будет содержать данные об иерархии страниц

Схема таблиц БД

В качестве примера используем следующую иерархию страниц:

 — О компании #1   — Контакты #3   — Вакансии #4      — Менеджер по рекламе #5      — Веб-дизайнер #6   — Реквизиты — Цены #2    — Сайты #7      — Визитка #10      — Корпоративный #11    — Логотипы #8    — Знаки #9 

Выборка дочерних элементов

Вот такой SQL-запрос у нас получится, если мы захотим выбрать все страницы раздела «О компании».

SELECT * FROM pages p JOIN pages_treepath t ON (p.id = t.descendant) WHERE t.ancestor = 1 

«Descendant» означает «дочерний», а «ancestor» — родительский. Соответственно, чтобы получить все дочерние страницы, мы присоединяем таблицу связей pages_treepath при условии, что идентификатор страницы id имеет то же значение, что и ссылка на дочерний элемент descendant. При этом ссылка ancestor на родительскую страницу равняется 1, идентификатору страницы «О компании».

Выборка родительских элементов

А теперь снизу вверх: посмотрим всех «родителей» у страницы «Корпоративный».

SELECT * FROM pages p JOIN pages_treepath t ON (p.id = t.ancestor) WHERE t.descendant = 11 

В этом случае наоборот. Мы ищем родительские страницы, поэтому присоединяем таблицу связей с условием, что идентификатор страницы id должен равняться ссылке на родительскую страницу ancestor, а выборку осуществляем по ссылке на дочерний элемент descendant, в нашем случае равной 11.

Вставка нового элемента

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

INSERT INTO pages VALUES (12, 'Менеджер по продажам',         '',         'Требуется офигенный менеджер по продажам',         '0000-00-00 00:00:00',         '0000-00-00 00:00:00')   INSERT INTO pages_treepath (ancestor, descendant)     SELECT ancestor, 12 FROM pages_treepath     WHERE descendant = 4     UNION ALL     SELECT 12, 12 

С первым запросом все ясно — это простая вставка новых данных. А вот второй запрос стоит разобрать по порядку, так что давайте посмотрим, что тут происходит.

SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4 

Выполнив этот запрос, мы получим следующий список связей:

 ------------------------- | ancestor | descendant | ------------------------- |    4     |     12     | |    1     |     12     | ------------------------- 

Добавим к предыдущему запросу еще один путем объединения:

SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4 UNION ALL SELECT 12, 12 

В список связей добавится связь-ссылка страницы на саму себя:

 ------------------------- | ancestor | descendant | ------------------------- |    4     |     12     | |    1     |     12     | |   12     |     12     | ------------------------- 

Как видите, данный SELECT-запрос позволяет установить связи между новой страницей и всеми её «родителями». ancestor — всегда ссылка на родительский элемент, descendant — ссылка на дочерний элемент. INSERT-запрос, написанный вначале, вставляет полученный результат в таблицу pages_treepath.

Удаление элемента

А теперь закроем вакансию веб-дизайнера.

DELETE FROM pages_treepath WHERE descendant = 6   DELETE FROM pages WHERE id = 6 

Здесь всё просто. Сначала мы удаляем все связи, где ссылка на дочерний элемент равняется 6 (страница «Веб-дизайнер»), а затем удаляем и саму страницу.

Удаление вложенного дерева

Вдруг так случилось, что с некоторых пор компания ABC перестала разрабатывать сайты. Нам понадобится выполнить вот такой запрос, чтобы удалить соответствующий подраздел:

DELETE FROM pages WHERE id IN (     SELECT descendant FROM (         SELECT descendant FROM pages p         JOIN pages_treepath t ON p.id = t.descendant         WHERE t.ancestor = 7     ) AS tmptable )   DELETE FROM pages_treepath WHERE descendant IN (     SELECT descendant FROM (         SELECT descendant FROM pages_treepath         WHERE ancestor = 7     ) AS tmptable ) 

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

Сложность запросов отчасти объясняется тем, что MySQL не позволяет выполнять запрос на удаление записей с условием WHERE, в котором содержится выборка SELECT из той же таблицы. В случае с MySQL мы вынуждены поместить SELECT-запросы во временную таблицу. А в общем случае наши запросы выглядели бы так:

DELETE FROM pages WHERE id IN (     SELECT descendant FROM pages p     JOIN pages_treepath t ON p.id = t.descendant     WHERE t.ancestor = 7 )   DELETE FROM pages_treepath WHERE descendant IN (     SELECT descendant FROM pages_treepath     WHERE ancestor = 7 ) 

Если вы внимательно посмотрите на вложенный SELECT-запрос в DELETE-запросе из таблицы pages, то обнаружите, что мы уже рассматривали подобный запрос. Этот от предыдущего отличается только идентификатором страницы. В результате выборки мы получаем все дочерние страницы раздела «Сайты» (включая сам раздел), а затем удаляем все страницы с полученными идентификаторами.

После того, как страницы удалены, остаётся удалить связи между ними. Для этого находим все ссылки на дочерний элемент descendant, где ссылка на родительский элемент равняется идентификатору страницы «Сайты».

Уровень вложенности

Еще в таблицу связей можно добавить поле, контролирующее уровень вложенности элементов. Это поле позволит составлять более простые запросы на выборку непосредственных предков или непосредственных дочерних элементов. Например:

SELECT * FROM pages p JOIN pages_treepath t ON (p.id = t.descendant) WHERE t.ancestor = 4 AND t.level = 2 

Схема таблиц БД

Продолжение следует.