Инфраструктура интервальных деревьев

Материал из GedeminWiki
(Различия между версиями)
Перейти к: навигация, поиск
(→‎Триггер на вставку записи)
(→‎Триггер на вставку записи)
Строка 78: Строка 78:
 
     EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, -1, -1)
 
     EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, -1, -1)
 
       RETURNING_VALUES NEW.lb, NEW.rb;
 
       RETURNING_VALUES NEW.lb, NEW.rb;
 +
  END
 +
END
 +
</syntaxhighlight>
 +
 +
=== Триггер на изменение записи ===
 +
 +
<syntaxhighlight lang="SQL">
 +
CREATE OR ALTER trigger gd_bu_contact10 for gd_contact
 +
active before update position 32000
 +
AS
 +
  DECLARE VARIABLE OldDelta  INTEGER;
 +
  DECLARE VARIABLE D        INTEGER;
 +
  DECLARE VARIABLE L        INTEGER;
 +
  DECLARE VARIABLE R        INTEGER;
 +
  DECLARE VARIABLE Prev      INTEGER;
 +
  DECLARE VARIABLE WasUnlock INTEGER;
 +
BEGIN
 +
  IF (NEW.parent IS DISTINCT FROM OLD.parent) THEN
 +
  BEGIN
 +
    /* Делаем проверку на зацикливание */
 +
    IF (EXISTS (SELECT * FROM GD_CONTACT
 +
          WHERE id = NEW.parent AND lb >= OLD.lb AND rb <= OLD.rb)) THEN
 +
      EXCEPTION tree_e_invalid_parent 'Attempt to cycle branch in table GD_CONTACT.';
 +
 +
    IF (NEW.parent IS NULL) THEN
 +
    BEGIN
 +
      D = OLD.rb - OLD.lb;
 +
      Prev = 1;
 +
      NEW.lb = NULL;
 +
 +
      FOR SELECT lb, rb FROM GD_CONTACT WHERE parent IS NULL ORDER BY lb ASC INTO :L, :R
 +
      DO BEGIN
 +
        IF ((:L - :Prev) > :D) THEN
 +
        BEGIN
 +
          NEW.lb = :Prev;
 +
          LEAVE;
 +
        END ELSE
 +
          Prev = :R + 1;
 +
      END
 +
 +
      NEW.lb = COALESCE(NEW.lb, :Prev);
 +
      NEW.rb = NEW.lb + :D;
 +
 +
      /* Определяем величину сдвига */
 +
      OldDelta = NEW.lb - OLD.lb;
 +
      /* Сдвигаем границы детей */
 +
      WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
 +
      IF (:WasUnlock IS NULL) THEN
 +
        RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
 +
      UPDATE GD_CONTACT SET lb = lb + :OldDelta, rb = rb + :OldDelta
 +
        WHERE lb > OLD.lb AND rb <= OLD.rb;
 +
      IF (:WasUnlock IS NULL) THEN
 +
        RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
 +
    END ELSE
 +
      EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, OLD.lb, OLD.rb)
 +
        RETURNING_VALUES NEW.lb, NEW.rb;
 +
  END ELSE
 +
  BEGIN
 +
    IF ((NEW.rb <> OLD.rb) OR (NEW.lb <> OLD.lb)) THEN
 +
    BEGIN
 +
      IF (RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK') IS NULL) THEN
 +
      BEGIN
 +
        NEW.lb = OLD.lb;
 +
        NEW.rb = OLD.rb;
 +
      END
 +
    END
 +
  END
 +
 +
  WHEN ANY DO
 +
  BEGIN
 +
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
 +
    EXCEPTION;
 
   END
 
   END
 
END
 
END

Версия 19:58, 2 апреля 2011

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

Описание объекта Таблица GD_CONTACT Таблица USR$FA_GROUP
Процедура вычисляет границы интервала для дочернего элемента. При необходимости родительский интервал расширяется. На вход передается родитель и границы существующего интервала элемента. Если это новый элемент, передаются границы -1, -1. GD_P_EL_CONTACT
Процедура GD_P_GCHC_CONTACT
Процедура сжимает интервалы всех элементов в дереве. GD_P_RESTRUCT_CONTACT
Триггер на вставку записи GD_BI_CONTACT10
Триггер на изменение записи GD_BU_CONTACT10
Индекс
Индекс
Исключение

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

Если вставка идет в корень дерева (PARENT IS NULL), то пытаемся отыскать местечко чтобы втиснуться между существующими корневыми элементами. Поиск "пробела" необходим, чтобы управлять скоростью растягивания дерева вправо при массовых операциях добавления/удаления элементов. Если свободного места нет — добавляем элемент правее самого правого.

Шириной интервала можно управлять с помощью переменной контекста транзакции LBRB_DELTA. По умолчанию принимается значение 10.

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

CREATE OR ALTER TRIGGER gd_bi_contact10 FOR gd_contact
active BEFORE INSERT POSITION 32000
AS
  DECLARE VARIABLE D    INTEGER;
  DECLARE VARIABLE L    INTEGER;
  DECLARE VARIABLE R    INTEGER;
  DECLARE VARIABLE Prev INTEGER;
BEGIN
  IF (NEW.parent IS NULL) THEN
  BEGIN
    D = CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER);
    Prev = 1;
    NEW.lb = NULL;
 
    FOR SELECT lb, rb FROM GD_CONTACT WHERE parent IS NULL ORDER BY lb INTO :L, :R
    DO BEGIN
      IF ((:L - :Prev) > :D) THEN 
      BEGIN
        NEW.lb = :Prev;
        LEAVE;
      END ELSE
        Prev = :R + 1;
    END
 
    NEW.lb = COALESCE(NEW.lb, :Prev);
    NEW.rb = NEW.lb + :D;
  END ELSE
  BEGIN
    EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, -1, -1)
      RETURNING_VALUES NEW.lb, NEW.rb;
  END
END

Триггер на изменение записи 

CREATE OR ALTER TRIGGER gd_bu_contact10 FOR gd_contact
active BEFORE UPDATE POSITION 32000
AS
  DECLARE VARIABLE OldDelta  INTEGER;
  DECLARE VARIABLE D         INTEGER;
  DECLARE VARIABLE L         INTEGER;
  DECLARE VARIABLE R         INTEGER;
  DECLARE VARIABLE Prev      INTEGER;
  DECLARE VARIABLE WasUnlock INTEGER;
BEGIN
  IF (NEW.parent IS DISTINCT FROM OLD.parent) THEN
  BEGIN
    /* Делаем проверку на зацикливание */
    IF (EXISTS (SELECT * FROM GD_CONTACT
          WHERE id = NEW.parent AND lb >= OLD.lb AND rb <= OLD.rb)) THEN
      EXCEPTION tree_e_invalid_parent 'Attempt to cycle branch in table GD_CONTACT.';
 
    IF (NEW.parent IS NULL) THEN
    BEGIN
      D = OLD.rb - OLD.lb;
      Prev = 1;
      NEW.lb = NULL;
 
      FOR SELECT lb, rb FROM GD_CONTACT WHERE parent IS NULL ORDER BY lb ASC INTO :L, :R
      DO BEGIN
        IF ((:L - :Prev) > :D) THEN 
        BEGIN
          NEW.lb = :Prev;
          LEAVE;
        END ELSE
          Prev = :R + 1;
      END
 
      NEW.lb = COALESCE(NEW.lb, :Prev);
      NEW.rb = NEW.lb + :D;
 
      /* Определяем величину сдвига */
      OldDelta = NEW.lb - OLD.lb;
      /* Сдвигаем границы детей */
      WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
      IF (:WasUnlock IS NULL) THEN
        RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
      UPDATE GD_CONTACT SET lb = lb + :OldDelta, rb = rb + :OldDelta
        WHERE lb > OLD.lb AND rb <= OLD.rb;
      IF (:WasUnlock IS NULL) THEN
        RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
    END ELSE
      EXECUTE PROCEDURE GD_p_el_CONTACT (NEW.parent, OLD.lb, OLD.rb)
        RETURNING_VALUES NEW.lb, NEW.rb;
  END ELSE
  BEGIN
    IF ((NEW.rb <> OLD.rb) OR (NEW.lb <> OLD.lb)) THEN
    BEGIN
      IF (RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK') IS NULL) THEN
      BEGIN
        NEW.lb = OLD.lb;
        NEW.rb = OLD.rb;
      END
    END
  END
 
  WHEN ANY DO
  BEGIN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
    EXCEPTION;
  END
END

См. также

Источник — «https://gsbelarus.com/gs/wiki/index.php?title=%D0%98%D0%BD%D1%84%D1%80%D0%B0%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D0%B5%D0%B2&oldid=4438»
Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты