doc.prototypes.ru: Проекты: Деревья SQL: Materialized Path: ltree: Управление "чистым" алгоритмом

Управление "чистым" алгоритмом Materialized Path

Задача

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

Исходные данные

Создаем простую таблицу без излишеств:

SQL код (1)

CREATE TABLE "public"."mp_tree" (
  "id"          INTEGER             DEFAULT nextval('mpath_id_seq'::regclass) NOT NULL, 
  "name"        TEXT, 
  "mpath"       "public"."ltree"    NOT NULL, 
  CONSTRAINT "mpath_pkey" PRIMARY KEY("id")
) WITHOUT OIDS;

CREATE UNIQUE INDEX "mp_tree_idx" ON "public"."mp_tree"
  USING btree ("mpath" "public"."ltree_ops");

CREATE INDEX "mp_tree_idx1" ON "public"."mp_tree"
  USING gist ("mpath" "public"."gist_ltree_ops");

Правда, что плохо в ltree - приходится создавать 2 индекса на поле path, для того, что бы можно было осуществлять как по ltree типу так и по text:

В качестве элементов материализованного пути возьмем id.

Традиционно, для поддержания целостности данных я использую триггера. Соответсвенно их и буду описывать.

Триггер на вставку

Основной сложностью вставки материализованного пути на базе id является то, что id у нас не известен до момента вставки, поэтому собрать путь заранее не представляется возможным. Эту проблему можно решить создав триггер на вставку записи, в котором мы будем переопределять метериализованный путь вставляемого узла относительно входных данных. Входные данные у нас могут быть двух видов: ID родительского узла или материализованный путь родительского узла.

SQL код (2)

CREATE OR REPLACE FUNCTION "public"."_mpath_insert_before_trigger" (
)
RETURNS trigger AS
$body$
DECLARE
    new_mpath       ltree;
BEGIN
    IF NEW.mpath IS NOT NULL THEN
--- передан, какой-то материализованный путь
------- обрезаем в материализованном пути id вставляемого узла, если он есть
        new_mpath := CASE WHEN NEW.id::text = subpath(NEW.mpath, -1, 1)::text
                          THEN subpath(NEW.mpath, 0, -1)
                          ELSE NEW.mpath
                     END;
------- проверяем существование родителя
        SELECT mp.mpath INTO new_mpath 
            FROM mp_tree AS mp
            WHERE mp.mpath = new_mpath OR mp.id::text = new_mpath::text;
------- родителя не нашли
        IF new_mpath IS NULL OR new_mpath = '' THEN
            NEW.mpath := NEW.id::text;
        ELSE -- родителя нашли
            NEW.mpath := new_mpath || NEW.id::text;
        END IF;
    ELSE
        NEW.mpath := NEW.id::text;
    END IF;
    RETURN NEW;
END;
$body$
LANGUAGE 'plpgsql';

CREATE TRIGGER "mpath_insert_before" BEFORE INSERT 
ON "public"."mp_tree" FOR EACH ROW 
EXECUTE PROCEDURE "public"."_mpath_insert_before_trigger"();

Сразу бросается в глаза постоянное принудительное приведение значений переменных к определенному типу (::text). Это важно, так как ltree может работать только со своим типом данных и типом text.

Триггер на обновление

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

Так как нет прямой связи родитель-потомок, то FOREIGN KEY навесить не получится, но можно производить обновление рекурсивно, если применять изменения не на всех потомков, а только потомков следующего уровня вложенности:

SQL код (3)

CREATE OR REPLACE FUNCTION "public"."_mpath_update_after_trigger" (
)
RETURNS trigger AS
$body$
DECLARE
    tid         INTEGER;  
BEGIN
--- Принудительно запрещаем изменять ID
    NEW.id := OLD.id;
--- Приводим NULL значение материализованного пути к ID
    NEW.mpath := CASE WHEN NEW.mpath IS NULL 
                      THEN NEW.id::text
                      ELSE NEW.mpath::text 
                 END;
--- Есть ли у нас изменения материализованного пути
    IF NEW.mpath <> OLD.mpath THEN
------- Проверяем что новое значение материализованного пути
------- лежит не пределах подчинения и что на его конце ID
        IF 
            NEW.mpath ~ ('*.' || NEW.id::text || '.*{1,}')::lquery OR
            NEW.mpath ~ ('*.!' || NEW.id::text)::lquery
        THEN
            RAISE EXCEPTION 'Bad mpath!';
        END IF;
------- Если уровень больше 1 то стоит проверить родителя
        IF nlevel(NEW.mpath) > 1 THEN
            SELECT m.id INTO tid
                FROM mp_tree AS m
                WHERE m.mpath = subpath(NEW.mpath, 0, nlevel(NEW.mpath) - 1);
            IF tid IS NULL THEN
                RAISE EXCEPTION 'Bad parent!';
            END IF;
        END IF;
------- Обновляем детей узла следующего уровня
        UPDATE mp_tree
            SET mpath = NEW.mpath || id::text
            WHERE mpath ~ (OLD.mpath::text || '.*{1}')::lquery;
    END IF;
    RETURN NEW;
END;
$body$
LANGUAGE 'plpgsql';

CREATE TRIGGER "mpath_update_after" AFTER UPDATE
ON "public"."mp_tree" FOR EACH ROW 
EXECUTE PROCEDURE "public"."_mpath_update_after_trigger"();

Так же как и в триггере на вставку производится жесткая типизация данных.

Триггер на удаление

Тут вообще все просто: рекурсивное удаление всех детей:

SQL код (4)

CREATE OR REPLACE FUNCTION "public"."_mp_tree_delete_after_trigger" (
)
RETURNS trigger AS
$body$
BEGIN
    DELETE FROM mp_tree
        WHERE mpath ~ (OLD.mpath::text || '.*{1}')::lquery;
    RETURN OLD; 
END;
$body$
LANGUAGE 'plpgsql';

CREATE TRIGGER "mp_tree_delete_after" AFTER DELETE 
ON "public"."mp_tree" FOR EACH ROW 
EXECUTE PROCEDURE "public"."_mp_tree_delete_after_trigger"();

На этом все. Никаких сложностей, даже при отсутствии прямого наследования (Adjacency List).