doc.prototypes.ru: Проекты: Деревья SQL: Adjacency List: Теория: Управление

Управление деревьями Adjacency List

Введение

Принципы управления я буду описывать только на уровне базы данных. База данных: PostgreSQL, потому что делать все тоже самое в MySQL, в некоторых случаях невозможно, а в некоторых гемморойно, но никогда не просто. Возможно позднее я рассмотрю более детально работу в MySQL.

Правила

На первый взгляд управление деревом Adjacency List довольно простое, но эта простота, зачастую природит к определенным проблемам, так очень просто, можно назначить подчинение первого узла второму, а второго первому, что может привести к бесконечному зацикливанию при выборе дерева, можно назначить родителем узла несуществующий ID и тогда ветка полностью исключится из дерева. Соответсвенно отсюда определим правила:

Узел может подчиняться только существующему узлу;
Узел не может подчиняться потомку, что очевидно;

Решения

С первым правилом, казалось бы просто, но, если при установке родителя мы можем проверить его существование, то при удалении родителького узла, нам потребуется провести обновление/удаление подчиненных узлов. Для этого рекомендуют использовать внешний ключ (FOREING KEY) на таблицу, но и это не решит всех проблем. Так, если нам потребуется не удалять каскадно потомков, то мы сможем с помощью FOREIGN KEY перевести потомков только в корень дерева, но не на уровень выше.

Впрочем, все решаем по ситуации, создаем внешний ключ:

SQL код (1)

-- 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 нет координат узла, максимум, что мы можем получить - это зависимость на уровень вверх и зависимость на уровень вниз, поэтому будем производить проверку выбрав родительскую ветку узла, в подчинение которому ставим текущий узел. Для этого создадим триггер на обновление:

SQL код (2)

-- 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"();

Для тех у кого PostgreSQL ниже 8.4 воспользуемся процедурой получения родительской ветки (ссылка):

SQL код (3)

-- 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
-- Пытаемся найти в родителькой ветки нового родителя текущий узел
        SELECT id INTO tmp_id FROM get_parents(NEW.pid) WHERE id = NEW.id 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 и создаем триггеры:

SQL код (4)

-- 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 только когда это действительно необходимо;

SQL код (5)

-- Триггер на обновление
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 добавляем раздел, если его еще нет:

Config (1)

# Список дополнительных пространств имен переменных
custom_variable_classes = 'user_vars'
# Переменная отвечающая за тип удаления
user_vars.tree_delete = cascade

По-умолчанию поставим cascade - каскадное удаление. Для остальных действий обозначим значения переменных как: root и levelup.

SQL код (6)

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 можно изменять локально в пределах транзакции, соответсвенно можно не переживать по поводу того, что изменение установок распространится на другие соответсвующие запросы:

SQL код (7)

BEGIN;
SELECT set_config('user_vars.tree_delete', 'levelup', TRUE);
DELETE FROM my_tree WHERE id = [item.id];
COMMIT;

Но можно сделать еще проще, без явного использования транзакции:

SQL код (8)

DELETE FROM my_tree
    USING (
        SELECT set_config('user_vars.tree_delete', 'root', TRUE)
        ) AS conf
    WHERE id = [item.id];

На этом все. Решение для MySQL я рассмотрю по возможности позднее, хотя желания, если четно нет.

Использование деревьев Adjacency List

Сергей Томулевич aka Phoinix (02.01.2010 г.)

DOC.PROTOTYPES.RU

Управление деревьями Adjacency List

Введение

Правила

Решения

Денормализация