Рассмотрим создание таблицы, реализующей рекурсивную иерархию, на примере данных, описывающих отношения подчиненности между сотрудниками. В таблице 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
Целостность, непротиворечивость и достоверность информации в таблицах с рекурсивными связями обеспечиваются выполнением ряда правил:
Каждый сотрудник имеет только одного руководителя.
Каждый сотрудник не является сам себе руководителем.
Каждый руководитель в первую очередь сотрудник.
Имеется только один сотрудник (директор организации), который никому не подчиняется.
Правило 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
Ниже приведен текст триггеров, поддерживающих целостность данных в иерархических структурах. Предполагается, что триггеры обрабатывают ввод, изменение или удаление одной записи.
