Введение в рекурсивные структуры

Рассмотрим создание таблицы, реализующей рекурсивную иерархию, на примере данных, описывающих отношения подчиненности между сотрудниками. В таблице emp_mgr необходимо задать как имя сотрудника ( emp ), так и имя его начальника ( mgr ). Для рекурсивной связи одна и та же сущность является и родительской, и дочерней. При задании рекурсивной связи атрибут первичного ключа мигрирует в качестве внешнего ключа в состав неключевых атрибутов той же сущности (атрибуты emp – сотрудник и mgr – начальник таблицы emp_mgr ). Информация о руководителе содержится в той же сущности, поскольку руководитель – сотрудник той же организации. Связь руководит/подчиняется ( fk_emp ) позволяет хранить древовидную иерархию подчиненности. Такой вид рекурсивной связи называется иерархической рекурсией и задает связь, когда руководитель (экземпляр родительской сущности) может иметь множество подчиненных (экземпляров дочерней сущности), но подчиненный – только одного руководителя. В среде MS SQL Server создадим таблицу emp_mgr:

CREATE TABLE emp_mgr
  (emp CHAR(2) PRIMARY KEY,
  mgr CHAR(2) NULL,
  NoOfReports INT DEFAULT 0,
  CONSTRAINT fk_emp FOREIGN KEY (mgr)
    REFERENCES emp_mgr (emp) )

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

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

INSERT INTO emp_mgr(emp,mgr) VALUES('a',NULL)
INSERT INTO emp_mgr(emp,mgr) VALUES('b','a')
INSERT INTO emp_mgr(emp,mgr) VALUES('c','a')
INSERT INTO emp_mgr(emp,mgr) VALUES('d','a')
INSERT INTO emp_mgr(emp,mgr) VALUES('e','b')
INSERT INTO emp_mgr(emp,mgr) VALUES('f','b')
INSERT INTO emp_mgr(emp,mgr) VALUES('g','b')
INSERT INTO emp_mgr(emp,mgr) VALUES('i','c')
INSERT INTO emp_mgr(emp,mgr) VALUES('k','d')

После ввода данных в таблицу emp_mgr оператор SELECT * FROM emp_mgr возвращает следующий результат:

emp    mgr    NoOfReports
-------------------------
 a     NULL   3
 b     a      3
 c     a      1
 d     a      1
 e     b      0
 f     b      0
 g     b      0
 i     c      0
 k     d      0

Реализация правил целостности данных

Целостность, непротиворечивость и достоверность информации в таблицах с рекурсивными связями обеспечиваются выполнением ряда правил:

1. Каждый сотрудник имеет только одного руководителя.
2. Каждый сотрудник не является сам себе руководителем.
3. Каждый руководитель в первую очередь сотрудник.
4. Имеется только один сотрудник (директор организации), который никому не подчиняется.
5. Правило 2 необходимо усилить. Каждый сотрудник не должен находиться в роли собственного руководителя не только непосредственно, но и опосредствованно, через других сотрудников.

Выполнение правила 1 обеспечивается ограничением первичного ключа и не требует дополнительных SQL-операторов.

Рассмотрим правило 2. Имена сотрудника и его начальника в одной записи не должны совпадать. При добавлении и изменении записи в таблице emp_mgr это требование предъявляется к новой записи, которая до подтверждения транзакции располагается во временной таблице с именем inserted. Этому правилу соответствуют следующие SQL-операторы:

IF EXISTS (SELECT * FROM inserted 
           WHERE mgr=emp)
BEGIN
  ROLLBACK TRAN
  RAISERROR('САМ СЕБЕ НАЧАЛЬНИК',16,10)
  RETURN
END

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

В новой или измененной записи имя начальника должно быть указано и уже присутствовать в таблице в качестве имени сотрудника, что может быть записано следующими SQL-операторами:

IF EXISTS(SELECT * FROM inserted
    WHERE mgr IS NOT NULL) AND
    NOT EXISTS(SELECT * FROM inserted,emp_mgr
    WHERE emp_mgr.emp=inserted.mgr)
BEGIN
  RAISERROR('НЕТ НАЧАЛЬНИКА',16,10)
  ROLLBACK TRAN
  RETURN
END

или (что эквивалентно)

IF NOT EXISTS(SELECT * FROM emp_mgr, inserted
    WHERE emp_mgr.emp=inserted.mgr
    OR inserted.mgr IS NULL)
BEGIN
  RAISERROR('НЕТ НАЧАЛЬНИКА',16,10)
  ROLLBACK TRAN
  RETURN
END

В соответствии с правилом 4 необходимо проверить, введена ли запись о директоре (сотруднике, у которого нет начальника). Если такая запись уже есть, ввод нового директора запрещается с помощью следующих SQL-операторов:

IF EXISTS (SELECT * FROM inserted 
           WHERE mgr IS NULL)
    AND EXISTS 
	    (SELECT * FROM emp_mgr,inserted
    WHERE emp_mgr.mgr IS NULL
    AND emp_mgr.emp<>inserted.emp)
BEGIN
  ROLLBACK TRAN
  RAISERROR('ОДИН ДИРЕКТОР УЖЕ ЕСТЬ',16,10)
  RETURN
END

Оператор UPDATE может изменить иерархическую структуру таким образом, что возникает ситуация, когда сотрудник становится начальником самому себе через других сотрудников, т.е. в иерархии подчиненности возникает петля. Для исключения подобных преобразований используем SQL-операторы:

IF UPDATE(mgr)--изменился начальник
BEGIN
  DECLARE @x CHAR(2), @y CHAR(2), @xx CHAR(2)
--узнали имя сотрудника,
--у которого изменился начальник
  SELECT @xx=inserted.emp FROM inserted
  SELECT @x=@xx
  SELECT @y='*'
  WHILE @y IS NOT NULL 
--пока не дошли до директора
  BEGIN
--запомнили имя начальника
  SELECT @y=mgr FROM emp_mgr
  WHERE emp=@x
  IF @xx=@y
--имя сотрудника и его начальника совпали
  BEGIN
  RAISERROR('транзитивное замыкание',16,10)
    ROLLBACK TRAN
    RETURN
  END
  ELSE
--далее начальник становится сотрудником,
--и в цикле будем искать его начальника
    SELECT @x=@y
  END
END

Чтобы сработали триггеры, необходимо удалить ограничение внешнего ключа:

ALTER TABLE emp_mgr DROP CONSTRAINT fk_emp

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