Введение
Принципы управления я буду описывать только на уровне базы данных. База данных: PostgreSQL, потому что делать все тоже самое в MySQL, в некоторых случаях невозможно, а в некоторых геморойно, но никогда не просто. Возможно позднее я рассмотрю более детально работу в MySQL.
Правила
На первый взгляд управление деревом Adjacency List довольно простое, но эта простота, зачастую приводит к определенным проблемам, так очень просто, можно назначить подчинение первого узла второму, а второго первому, что может привести к бесконечному зацикливанию при выборе дерева, можно назначить родителем узла несуществующий ID и тогда ветка полностью выпадет из дерева. Соответственно отсюда определим правила:
- Узел может подчиняться только существующему узлу;
- Узел не может подчиняться потомку, что очевидно;
Решения
С первым правилом, казалось бы просто, но, если при установке родителя мы можем проверить его существование, то при удалении родительского узла, нам потребуется провести обновление/удаление подчиненных узлов. Для этого рекомендуют использовать внешний ключ (FOREING KEY) на таблицу, но и это не решит всех проблем. Так, если нам потребуется не удалять каскадно потомков, то мы сможем с помощью FOREIGN KEY перевести потомков только в корень дерева, но не на уровень выше.
Впрочем, все решаем по ситуации, создаем внешний ключ:
-- PostgreSQL
-- Внешний ключ на каскадное удаление
ALTER TABLE "public"."my_tree"
ADD CONSTRAINT "my_tree_fk" FOREIGN KEY ("pid")
REFERENCES "public"."my_tree"("id")
MATCH FULL
ON DELETE CASCADE
NOT DEFERRABLE;
-- Внешний ключ на перемещение потомков в корень дерева
ALTER TABLE "public"."my_tree"
ADD CONSTRAINT "my_tree_fk" FOREIGN KEY ("pid")
REFERENCES "public"."my_tree"("id")
MATCH FULL
ON DELETE SET NULL
NOT DEFERRABLE;С первым правилом более-менее разобрались. Правило второе: потомок узла не может быть его родителем.
Увы, в отличие от Nested Sets в Adjacency List нет координат узла, максимум, что мы можем получить — это зависимость на уровень вверх и зависимость на уровень вниз, поэтому будем производить проверку выбрав родительскую ветку узла, в подчинение которому ставим текущий узел. Для этого создадим триггер на обновление:
-- PostgreSQL >= 8.4.
CREATE OR REPLACE FUNCTION "public"."my_tree_update_trigger" ()
RETURNS TRIGGER AS
$body$
DECLARE
tmp_id INTEGER;
BEGIN
-- Если произошло изменение родителя узла
IF NEW.pid IS NOT NULL AND (NEW.pid <> OLD.pid OR OLD.pid IS NULL) THEN
-- Пытаемся найти в родителькой ветки нового родителя текущий узел
WITH RECURSIVE parents AS (
SELECT t.id, t.pid, ARRAY[t.id] AS exist, FALSE AS cycle
FROM my_tree AS t
WHERE id = NEW.pid
UNION ALL
SELECT t.id, t.pid, exist || t.id, t.id = ANY(exist)
FROM parents AS p, my_tree AS t
WHERE t.id = p.pid AND NOT p.cycle
)
SELECT id INTO tmp_id FROM parents WHERE id = NEW.id AND NOT cycle LIMIT 1;
-- Узел найден, следовательно родителя назначить не можем
IF tmp_id IS NOT NULL THEN
RAISE NOTICE 'Нельзя ставить потомком родителя!';
NEW.pid := OLD.pid;
END IF;
END IF;
RETURN NEW;
END;
$body$
LANGUAGE 'plpgsql';
CREATE TRIGGER "my_tree_update" BEFORE UPDATE
ON "public"."my_tree" FOR EACH ROW
EXECUTE PROCEDURE "public"."my_tree_update_trigger"();Вставку и удаление контролирует внешний ключ, так что можно насладится результатом проделанной работы.
Денормализация
Зачастую, определенные параметры узлов дерева требуются достаточно часто, а вычисление их достаточно ресурсоемко. Для этого потребуется ввести дополнительные денормализованные поля таблицы, которые зависят от внешних факторов. Так добавим поле уровень узла и количество подчиненных узлов.
Если со вторым полем (количество потомков) более менее все просто, то в первым (уровень узла) несколько сложнее: так, при смене уровня узла потребуется обновить уровни всех узлов-потомков, поэтому, если предполагается постоянное перемещение узлов по уровням и поле level не так актуально, то лучше от него отказаться.
Определение значений денормализованных полей на уровне приложения совершенно бессмысленно, так как это добавляет дополнительные точки отказа, отъедает достаточно много ресурсов, а так же выводит на более высокий уровень программирования логику связанную с низкоуровневыми неявными определениями.
Рассматриваем только уровень триггеров, собственно, по большей части, именно для этого они и предназначены. Итак, добавляем в таблице два дополнительных поля level и counter и создаем триггеры:
-- PostgreSQL
-- Триггер на вставку
CREATE OR REPLACE FUNCTION "public"."my_tree_insert_trigger" ()
RETURNS TRIGGER AS
$body$
DECLARE
parent my_tree;
BEGIN
-- Что денормализовано, то ставить вручную нельзя
NEW.counter := 0;
NEW.level := 0;
-- Если определен pid тогда обновляем счетчик родителя
IF NEW.pid IS NOT NULL OR NEW.pid > 0 THEN
-- Сразу вернем результат обновления родителя
-- Финт ушами с CASE при обновлении счетчика из-за того что NULL + 1 = NULL,
-- поэтому эти поля лучше сразу делать NOT NULL, а сейчас перестрахуемся
UPDATE my_tree
SET counter = CASE WHEN counter IS NULL
THEN 1
ELSE counter + 1
END
WHERE id = NEW.pid
RETURNING * INTO parent;
-- Проверим существование родителя, без отмены операции
IF parent.id IS NULL THEN
RAISE NOTICE 'ОШИБКА! Родителя с таким ID нет (%)', NEW;
NEW.pid := 0;
ELSE
-- Устанавливаем значение level для вставляемого узла
NEW.level := CASE WHEN parent.level IS NULL OR parent.level = 0
THEN 1
ELSE NEW.level + 1
END;
END IF;
END IF;
RETURN NEW;
END;
$body$
LANGUAGE 'plpgsql';
CREATE TRIGGER "my_tree_insert" BEFORE INSERT
ON "public"."my_tree" FOR EACH ROW
EXECUTE PROCEDURE "public"."my_tree_insert_trigger"();Как видно, все просто, если не считать «финты ушами» с NULL, именно по этому, я рекомендую использовать определение NULL только когда это действительно необходимо;
-- Триггер на обновление
CREATE OR REPLACE FUNCTION "public"."my_tree_update" ()
RETURNS TRIGGER AS
$body$
DECLARE
parent my_tree;
child my_tree;
level_skew INTEGER;
pids INTEGER[];
tmp_pids INTEGER[];
exist_update INTEGER[];
BEGIN
-- Опять же для предотвращения сравнения с NULL ставим 0
IF OLD.pid IS NULL THEN OLD.pid := 0; END IF;
IF NEW.pid IS NULL THEN NEW.pid := 0; END IF;
IF OLD.level IS NULL THEN OLD.level := 0; END IF;
-- Если произошла смена родителя
IF NEW.pid <> OLD.pid THEN
-- Уменьшаем счетчик старого родителя если он есть
IF OLD.pid > 0 THEN
UPDATE my_tree
SET counter = counter - 1
WHERE id = OLD.pid;
END IF;
-- Увеличиваем счетчик нового родителя если он есть
IF NEW.pid > 0 THEN
UPDATE my_tree
SET counter = CASE WHEN counter IS NULL
THEN 1
ELSE counter + 1
END
WHERE id = NEW.pid
RETURNING * INTO parent;
-- Проверяем существование родителя
IF parent.id IS NULL THEN
RAISE NOTICE 'ОШИБКА! Родителя с таким ID нет (%)', NEW;
NEW.level := 0;
NEW.pid := 0;
ELSE
-- Если родитель есть то устанавливаем новый уровень узла
NEW.level := CASE WHEN parent.level IS NULL
THEN 1
ELSE parent.level + 1
END;
END IF;
ELSE
NEW.level := 0;
END IF;
-- Данные по перемещаемому узлу обновили, теперь следует обновить
-- level потомков перемещаемого узла
level_skew := NEW.level - OLD.level;
-- Смещение уровня таки есть
IF level_skew <> 0 THEN
pids := ARRAY[NEW.id];
exist_update := ARRAY[NEW.id];
-- Пока есть узлы у которых есть потомки:
WHILE pids[1] IS NOT NULL LOOP
tmp_pids := ARRAY[NULL];
-- Обновляем всех потомков на уровне
FOR child IN UPDATE my_tree
SET level = level + level_skew
WHERE pid = ANY (pids) AND
id <> ALL (exist_update)
RETURNING *
LOOP
-- Поставим защиту для того, что бы невозможно было поставить узел в починение своему потомку
IF child.id = NEW.pid THEN
RAISE EXCEPTION 'Ошибка! Нельзя ставить узел в подчинение потомку! (%)', NEW;
RETURN NULL;
END IF;
-- Если у потомка еще есть потомки, то добавляем его id в список на обновление
-- следующего уровня
IF child.counter IS NOT NULL AND child.counter > 0 THEN
tmp_pids := array_prepend(child.id, tmp_pids);
END IF;
-- Защита от повторов
exist_update := array_append(exist_update, child.id);
END LOOP;
pids := tmp_pids;
END LOOP;
END IF;
END IF;
RETURN NEW;
END;
$body$
LANGUAGE 'plpgsql';
CREATE TRIGGER "my_tree_update" BEFORE UPDATE
ON "public"."my_tree" FOR EACH ROW
EXECUTE PROCEDURE "public"."my_tree_update"();Обновление сложнее, и изменение денормализованных полей мы не можем ограничить. Поле level обновляется практически рекурсивно, но, его использование помогает нам защитится от возможных зацикливаний;
Раз уж денормализировали таблицу, то можно сделать удаление узлов наиболее кошерным :-). Так, есть три варианта удаления узлов:
- Каскадное удаление, когда удаление узла удаляет его потомков;
- Перенос прямых потомков в корень дерева;
- Перенос прямых потомков на уровень выше;
Включать, выключать триггеры и внешние ключи перед каждым запросом, естественно не получится. Остается ввести дополнительные пользовательские переменные. Так в конфигурации PostgerSQL добавляем раздел, если его еще нет:
# Список дополнительных пространств имен переменных
custom_variable_classes = 'user_vars'
# Переменная отвечающая за тип удаления
user_vars.tree_delete = cascadeПо-умолчанию поставим cascade — каскадное удаление. Для остальных действий обозначим значения переменных как: root и levelup.
CREATE OR REPLACE FUNCTION "public"."my_tree_delete_trigger" ()
RETURNS TRIGGER AS
$body$
BEGIN
-- Если есть родитель, то обновляем его счетчик
IF OLD.pid IS NOT NULL AND OLD.pid > 0 THEN
UPDATE my_tree
SET counter = counter - 1
WHERE id = OLD.pid;
END IF;
IF current_setting('user_vars.tree_delete') = 'levelup' THEN
UPDATE my_tree
SET pid = OLD.pid
WHERE pid = OLD.id;
ELSIF current_setting('user_vars.tree_delete') = 'root' THEN
UPDATE my_tree
SET pid = 0
WHERE pid = OLD.id;
ELSE
IF OLD.counter IS NOT NULL AND OLD.counter > 0 THEN
DELETE FROM my_tree WHERE pid = OLD.id;
END IF;
END IF;
RETURN OLD;
END;
$body$
LANGUAGE 'plpgsql';
CREATE TRIGGER "my_tree_delete" AFTER DELETE
ON "public"."my_tree" FOR EACH ROW
EXECUTE PROCEDURE "public"."my_tree_delete_trigger"();Естественно, что при использовании этих триггеров, надобность во внешнем ключе отпадает, он будет только мешать. Остается уточнить как правильно производить удаление.
В PostgreSQL пользовательские установки, частности наши user_vars можно изменять локально в пределах транзакции, соответственно можно не переживать по поводу того, что изменение установок распространится на другие соответствующие запросы:
BEGIN;
SELECT set_config('user_vars.tree_delete', 'levelup', TRUE);
DELETE FROM my_tree WHERE id = [item.id];
COMMIT;Но можно сделать еще проще, без явного использования транзакции:
DELETE FROM my_tree
USING (
SELECT set_config('user_vars.tree_delete', 'root', TRUE)
) AS conf
WHERE id = [item.id];На этом все…