Блог

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

22 августа 2013 Рубрики: Программирование. Метки: closure table, laravel, php, базы данных и древовидные структуры.

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

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

Что такое Closure Table и с чем его едят

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

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

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

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

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

— О компании #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
Схема таблиц БД
Схема таблиц БД

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