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

Материал из GedeminWiki
Перейти к: навигация, поиск

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

N Описание объекта Таблица GD_CONTACT Таблица USR$FA_GROUP
1 Процедура вычисляет границы интервала для элемента. GD_P_EL_CONTACT USR$_P_EXLIM_USR$FA_GROUP
2 Процедура сжимает интервалы всех элементов заданного поддерева. GD_P_GCHC_CONTACT USR$_P_CHLDCT_USR$FA_GROUP
3 Процедура сжимает интервалы всех элементов в дереве. GD_P_RESTRUCT_CONTACT USR$_P_RESTR_USR$FA_GROUP
4 Триггер на вставку записи GD_BI_CONTACT10 usr$_bi_fa_group10
5 Триггер на изменение записи GD_BU_CONTACT10 usr$_bu_fa_group10
6 Индекс по полю LB GD_X_CONTACT_LB USR$_X_USR$FA_GROUP_LB
7 Индекс по полю RB GD_X_CONTACT_RB USR$_X_USR$FA_GROUP_RB
8 Ограничение на границы интервала GD_CHK_CONTACT_TR_LMT USR$_CHK_FA_GROUP_TR_LMT
9 Исключение (общее для всех деревьев в базе) TREE_E_INVALID_PARENT TREE_E_INVALID_PARENT

Предназначение каждого объекта раскрыто ниже на примере таблицы GD_CONTACT.

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

Если вставка идет в корень дерева (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

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

Триггер отслеживает изменение поля PARENT, т.е. перемещение поддерева в другую ветвь или на корневой уровень. Логика действий такая же как и при вставке записи. Дополнительно выполняется проверка на зацикливание, т.е. когда родителя пытаются вставить в один из подуровней потомка. Обратите внимание, как с помощью переменной контекста транзакции LBRB_UNLOCK мы запрещаем несанкционирование редактирование границ элемента. 

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

Процедура определения границ интервала

На вход передается идентификатор родителя и границы существующего интервала вставляемого элемента. Если идет вставка новой записи — передаются границы -1, -1. Задача процедуры — найти свободный промежуток нужной ширины или раздвинуть родительский интервал. Возвращаются значения левой и правой границы интервала. 

CREATE OR ALTER PROCEDURE GD_P_EL_CONTACT (
    PARENT INTEGER,
    LB2 INTEGER,
    RB2 INTEGER)
RETURNS (
    LEFTBORDER INTEGER,
    RIGHTBORDER INTEGER)
AS
DECLARE variable R INTEGER = NULL;
DECLARE variable L INTEGER = NULL;
DECLARE variable PREV INTEGER;
DECLARE variable LCHLD INTEGER = NULL;
DECLARE variable RCHLD INTEGER = NULL;
DECLARE variable DELTA INTEGER;
DECLARE variable DIST INTEGER;
DECLARE variable DIFF INTEGER;
DECLARE variable WASUNLOCK INTEGER;
BEGIN
  IF (:LB2 = -1 AND :RB2 = -1) THEN
    Delta = CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER);
  ELSE
    Delta = :RB2 - :LB2;
 
  SELECT lb, rb
  FROM GD_CONTACT
  WHERE id = :Parent
  INTO :L, :R;
 
  IF (:L IS NULL) THEN
    EXCEPTION tree_e_invalid_parent 'Invalid parent specified.';
 
  Prev = :L + 1;
  LeftBorder = NULL;
 
  FOR SELECT lb, rb FROM GD_CONTACT WHERE parent = :Parent ORDER BY lb ASC INTO :LChld, :RChld
  DO BEGIN
    IF ((:LChld - :Prev) > :Delta) THEN 
    BEGIN
      LeftBorder = :Prev;
      LEAVE;
    END ELSE
      Prev = :RChld + 1;
  END
 
  LeftBorder = COALESCE(:LeftBorder, :Prev);
  RightBorder = :LeftBorder + :Delta;
 
  WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
  IF (:WasUnlock IS NULL) THEN
     RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
 
  IF (:RightBorder >= :R) THEN
  BEGIN
    Diff = :R - :L;
    IF (:RightBorder >= (:R + :Diff)) THEN
      Diff = :RightBorder - :R + 1;
 
    IF (:Delta < 1000) THEN
      Diff = :Diff + :Delta * 10;
    ELSE
      Diff = :Diff + 10000;
 
    /* Сдвигаем все интервалы справа */
    UPDATE GD_CONTACT SET lb = lb + :Diff, rb = rb + :Diff
      WHERE lb > :R;
 
    /* Расширяем родительские интервалы */
    UPDATE GD_CONTACT SET rb = rb + :Diff
      WHERE lb <= :L AND rb >= :R;
 
    IF (:LB2 <> -1 AND :RB2 <> -1) THEN
    BEGIN
      IF (:LB2 > :R) THEN
      BEGIN
        LB2 = :LB2 + :Diff;
        RB2 = :RB2 + :Diff;
      END
      Dist = :LeftBorder - :LB2;
      UPDATE GD_CONTACT SET lb = lb + :Dist, rb = rb + :Dist 
        WHERE lb > :LB2 AND rb <= :RB2;
    END
  END ELSE
  BEGIN
    IF (:LB2 <> -1 AND :RB2 <> -1) THEN
    BEGIN
      Dist = :LeftBorder - :LB2;
      UPDATE GD_CONTACT SET lb = lb + :Dist, rb = rb + :Dist 
        WHERE lb > :LB2 AND rb <= :RB2;
    END
  END
 
  IF (:WasUnlock IS NULL) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
END

Процедура перестроения дерева

В процессе перестроения интервалы изменяются следующим образом:

  • Все листья получают ширину из переменной контекста транзации LBRB_DELTA. Если последняя не задана, то принимается ширина 10.
  • Ширина остальных узлов определяется как сумма интервалов непосредственных потомков. 
CREATE OR ALTER PROCEDURE GD_P_RESTRUCT_CONTACT
AS
DECLARE variable CURRENTINDEX INTEGER;
DECLARE variable CHILDKEY INTEGER;
DECLARE variable WASUNLOCK INTEGER;
BEGIN
  CurrentIndex = 1;
 
  WasUnlock = RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK');
  IF (:WasUnlock IS NULL) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', 1);
 
  /* Для всех корневых элементов ... */
  FOR
    SELECT id
    FROM GD_CONTACT
    WHERE parent IS NULL
    INTO :ChildKey
  DO
  BEGIN
    /* ... меняем границы детей */
    EXECUTE PROCEDURE GD_p_gchc_CONTACT (:ChildKey, :CurrentIndex)
      RETURNING_VALUES :CurrentIndex;
  END
 
  IF (:WasUnlock IS NULL) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_UNLOCK', NULL);
END

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

Процедура рекурсивного перестроения указанного элемента дерева

Данная процедура вызывается из процедуры перестроения дерева (см. выше) и не предназначена для самостоятельного использования. На вход передается идентификатор элемента и новое значение левой границы. Процедура действует для поддерева следующим образом:

  • Все листья получают ширину из переменной контекста транзации LBRB_DELTA. Если последняя не задана, то принимается ширина 10.
  • Ширина остальных узлов определяется как сумма интервалов непосредственных потомков. 
CREATE OR ALTER PROCEDURE GD_P_GCHC_CONTACT (
    PARENT INTEGER,
    FIRSTINDEX INTEGER)
RETURNS (
    LASTINDEX INTEGER)
AS
DECLARE variable CHILDKEY INTEGER;
BEGIN
  LastIndex = :FirstIndex + 1;
 
  /* Изменяем границы детей */
  FOR
    SELECT id
    FROM GD_CONTACT
    WHERE parent = :Parent
    INTO :ChildKey
  DO
  BEGIN
    EXECUTE PROCEDURE GD_p_gchc_CONTACT (:ChildKey, :LastIndex)
      RETURNING_VALUES :LastIndex;
  END
 
  LastIndex = :LastIndex + CAST(COALESCE(RDB$GET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA'), '10') AS INTEGER) - 1;
 
  /* Изменяем границы родителя */
  UPDATE GD_CONTACT SET lb = :FirstIndex + 1, rb = :LastIndex
    WHERE id = :Parent;
END

Прочие метаданные

Ограничение, контролирующее расположение левой и правой границы интервала: 

ALTER TABLE GD_CONTACT ADD CONSTRAINT GD_CHK_CONTACT_TR_LMT CHECK (lb <= rb);

Одно, общее на все деревья исключение, которое вызывается, если, например, предпринимается попытка "зациклить" ветвь дерева: 

CREATE EXCEPTION TREE_E_INVALID_PARENT 'Invalid parent specified';

Индексы для ускорения выборки элементов дерева по условиям левой и правой границы: 

CREATE INDEX GD_X_CONTACT_LB ON GD_CONTACT (LB);
CREATE DESCENDING INDEX GD_X_CONTACT_RB ON GD_CONTACT (RB);

Управление начальной шириной интервала

Ширина интервала добавляемого в дерево элемента определяется значением переменной контекста транзакции LBRB_DELTA. По умолчанию принимается значение 10. Разработчик может указать другую ширину начального интервала. Как правило, это делается в триггере, который по своей позиции вызывается раньше триггера интервального дерева. Например, с помощью триггера приведенного ниже, для таких объектов справочника контактов как Папка и Подразделение ширина начального интервала устанавливается в 100, а для остальных объектов — 1. 

CREATE OR ALTER TRIGGER gd_bi_contact FOR gd_contact
active BEFORE INSERT POSITION 0
AS
BEGIN
  IF (NEW.id IS NULL) THEN
    NEW.id = GEN_ID(gd_g_unique, 1) + GEN_ID(gd_g_offset, 0);
 
  IF (NEW.name IS NULL) THEN
    NEW.name = '<' || NEW.id || '>';
 
  IF (NEW.CONTACTTYPE = 0 OR NEW.CONTACTTYPE = 4) THEN
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA', '100');
  ELSE
    RDB$SET_CONTEXT('USER_TRANSACTION', 'LBRB_DELTA', '1');
END

Проверка целостности дерева

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

/* Проверка границ */
SELECT a.lb FROM GD_CONTACT a WHERE a.lb > a.rb
 
/* Проверка дублирования левых границ */
SELECT a.lb FROM GD_CONTACT a JOIN GD_CONTACT b ON a.lb = b.lb AND a.id <> b.id
 
/* Проверка перекрытия интервалов по левым границам */
SELECT a.id || ',' || b.id FROM GD_CONTACT a JOIN GD_CONTACT b ON a.lb < b.lb AND a.rb >= b.lb AND a.rb < b.rb
 
/* Проверка перекрытия интервалов по правым границам */
SELECT a.id || ',' || b.id FROM GD_CONTACT a JOIN GD_CONTACT b ON a.lb > b.lb AND a.lb <= b.rb AND a.rb > b.rb
 
/* Проверка размера родительского интервала */
SELECT a.id, b.id FROM gd_contact a JOIN gd_contact b 
  ON a.parent = b.id AND a.lb <= b.lb AND a.rb >= b.rb

Для корректного дерева все пять запросов вернут пустые наборы данных. Восстановить целостность можно выполнением процедуры перестроения дерева.

Вместо последовательного выполнения отдельных запросов можно воспользоваться приведенным ниже параметризованным оператором EXECUTE BLOCK на вход которого передается имя тестируемой таблицы: 

EXECUTE BLOCK (TN VARCHAR(31) = :TABLE_NAME)
  RETURNS (
    LBGTRB INTEGER,
    DBLLB INTEGER,
    LBOVERL1 INTEGER,
    LBOVERL2 INTEGER,
    RBOVERL1 INTEGER,
    RBOVERL2 INTEGER,
    PRNTSM1 INTEGER,
    PRNTSM2 INTEGER)
AS
BEGIN
  /* Проверка границ */
  EXECUTE STATEMENT 'SELECT FIRST 1 a.lb FROM ' || :TN || ' a WHERE a.lb > a.rb'
    INTO :LBGTRB;
 
  /* Проверка дублирования левых границ */
  IF (:LBGTRB IS NULL) THEN
    EXECUTE STATEMENT 'SELECT FIRST 1 a.lb FROM ' || :TN || 
      ' a JOIN ' || :TN || ' b ON a.lb = b.lb AND a.id <> b.id'
      INTO :DBLLB;
 
  /* Проверка перекрытия интервалов по левым границам */
  IF (:DBLLB IS NULL) THEN
    EXECUTE STATEMENT 'SELECT FIRST 1 a.id, b.id FROM ' || :TN || 
      ' a JOIN ' || :TN || ' b ON a.lb < b.lb AND a.rb >= b.lb AND a.rb < b.rb'
      INTO :LBOVERL1, :LBOVERL2;
 
  /* Проверка перекрытия интервалов по правым границам */
  IF (:LBOVERL1 IS NULL) THEN
    EXECUTE STATEMENT 'SELECT FIRST 1 a.id, b.id FROM ' || :TN || 
      ' a JOIN ' || :TN || ' b ON a.lb > b.lb AND a.lb <= b.rb AND a.rb > b.rb'
      INTO :RBOVERL1, :RBOVERL2;
 
  /* Проверка размера родительского интервала */
  IF (:RBOVERL1 IS NULL) THEN
    EXECUTE STATEMENT 'SELECT FIRST 1 a.id, b.id FROM ' || :TN || 
      ' a JOIN ' || :TN || ' b ON a.parent = b.id AND a.lb <= b.lb AND a.rb >= b.rb'
      INTO :PRNTSM1, :PRNTSM2;
 
  SUSPEND;
END

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

Создание метаданных интервального дерева

За работу с метаданными интервального дерева отвечают процедуры из модуля gdcLBRBTreeMetadata.pas.

См. также

Источник — «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=5304»
Персональные инструменты
Пространства имён

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