Программные продукты и системы

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

Рассмотрим иерархическую рекурсию на примере базы данных для хранения и модификации информации о сотрудниках некоторой организации и об их руководителях, являющихся сотрудниками той же организации [1]. Информация как о самом сотруднике, так и о его руководителе содержится в одной и той же сущности emp_mgr. Чтобы сослаться на руководителя сотрудника, следует создать рекурсивную связь «руководит/подчиняется» (связь lead для сущности emp_mgr показана на рисунке 1).

Связь «руководит/подчиняется» позволяет хранить древовидную иерархию подчиненности сотрудников, когда руководитель (экземпляр родительской сущности) может иметь множество подчиненных (экземпляров дочерней сущности), но подчиненный имеет только одного руководителя (рис. 2). При наличии рекурсивной связи одна и та же сущность является и родительской, и дочерней одновременно.

Для каждого сотрудника введем дополнительный атрибут NoOfReports – количество подчиненных.

На основе логической модели данных (рис. 1) в среде MS SQL Server может быть сгенерирована физическая модель путем выполнения следующих SQL-операторов:

USE BASA

IF EXISTS ( SELECT TABLE_NAME

FROM INFORMATION_SCHEMA.TABLES

WHERE TABLE_NAME='emp_mgr')

DROP TABLE emp_mgr

GO

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))

Обеспечение целостности данных

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

При формировании правил будем исходить из двух множеств данных: De ={x} – множество сотрудников и Dm ={y} – множество руководителей. Причем Dm Ì De. Введем отношение «руководит/подчиняется» R, которому отвечает некоторое подмножество R Ì De x Dm:

R={(x, y) | x Î De , y ÎDm OR y = NULL},

то есть элемент x подчиняется элементу y или элемент y является руководителем элемента x.

Правило 1. Каждый сотрудник имеет только одного руководителя:

"x $y ((x, y) Î R, (y¹z)) ® ("z (x, z)ÏR).           (1)

Правило 2. Каждый сотрудник не является сам себе руководителем:

"x (x, x)Ï R.                                                               (2)

Правило 3. Каждый руководитель является в первую очередь сотрудником:

"y $x ((x, y) Î R,

y¹NULL)®($ z (y, z) Î R).                                     (3)

Правило 4. Имеется только один сотрудник (директор организации), который никому не подчиняется:

$y $x ((x, y) Î R, y = NULL,

(z¹x))®("z (z, y) Ï R).                                             (4)

Правило 5. Правило 2 необходимо усилить. Каждый сотрудник не должен быть себе руководителем не только непосредственно, но и опосредствованно через других сотрудников.

Введем отношение R' – транзитивно замкнутое относительно отношения R: R Ì R', ((x, y) Î R', (y, z) Î R') ® ((x, z) Î R', (x ¹z)).

Тогда правило 5 имеет вид:

"x (x, x) Î R'.                                                      (5)

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

"x j(x)=k®($y1, ..., yk (yi , x) ÎR,

"z¹y1, ..., yk (z, x)ÏR).                                        (6)

Реализация правил целостности и достоверности информации при модификации данных в таблице с рекурсивными связями показана в таблице, где символ «*» означает, что правило при модификации данных в таблице не нарушается, а символ «-» говорит, что нарушение правила возможно.

Управление целостностью осуществляется посредством ограничений первичного и внешнего ключа, а также за счет использования триггеров. Ограничение первичного ключа PK (PRIMARY KEY) и ограничение внешнего ключа FK (FOREIGN KEY) являются основным механизмом для поддержания ссылочной целостности между таблицами реляционной базы данных [2].

Ограничение первичного ключа PK делает каждую строку данных уникальной, обеспечивая тем самым выполнение правила 1 при добавлении и изменении записи в таблице emp_mgr. Удаление любой записи к нарушению правила 1 не приводит.

Правило 3 обеспечивается ограничением внешнего ключа FK, которое не позволит добавить запись о сотруднике, руководитель которого отсутствует в таблице emp_mgr. Удаление сотрудников, имеющих подчиненных, будет блокировано.

Как видно из таблицы, выполнение правил 2, 4, 5 и 6 не обеспечивается ограничениями пер- вичного PK и внешнего FK ключа. Для проверки и обеспечения целостности данных в этом случае могут быть использованы триггеры, выполняемые всякий раз при вставке, замене или удалении записи в таблице.

Триггеры для добавления и изменения записи

Для реализации правила 6 в [3] представлены триггеры для добавления и изменения записи в таблице emp_mgr. Основная задача триггера, обрабатывающего вставку записей в таблицу emp_mgr, заключается в увеличении на 1 числа подчиненных у вышестоящего руководителя. Рассмотрим триггер emp_ins, выполняемый при добавлении записи в таблицу с рекурсивными связями emp_mgr:

IF EXISTS ( SELECT name FROM sysobjects

WHERE name='emp_ins' AND type='TR')

DROP TRIGGER emp_ins

GO

CREATE TRIGGER emp_ins

ON emp_mgr FOR INSERT

AS

DECLARE @e CHAR(2), @m CHAR(2)

DECLARE e1 CURSOR FOR

     SELECT emp_mgr.emp FROM emp_mgr, inserted

WHERE emp_mgr.emp=inserted.mgr

OPEN e1

FETCH NEXT FROM e1 INTO @e

WHILE @@FETCH_STATUS=0

BEGIN

UPDATE emp_mgr

SET emp_mgr.NoOfReports= emp_mgr.NoOfReports+1

WHERE emp_mgr.emp=@e

FETCH NEXT FROM e1 INTO @e

END

CLOSE e1

DEALLOCATE e1

Формирование таблицы emp_mgr, соответствующей структуре рисунка 2, показано в левом окне рисунка 6. Столбец NoOfReports – количество подчиненных – формируется триггером emp_ins.

Приведем из [3] текст триггера emp_upd, который выполняется при изменении записи в таблице emp_mgr:

IF EXISTS ( SELECT name FROM sysobjects

WHERE name='emp_upd' AND type='TR')

DROP TRIGGER emp_upd

GO

CREATE TRIGGER emp_upd ON emp_mgr FOR UPDATE

AS

IF UPDATE(mgr)

BEGIN

UPDATE emp_mgr

SET emp_mgr.NoOfReports=emp_mgr.NoOfReports+1

FROM inserted WHERE emp_mgr.emp=inserted.mgr

UPDATE emp_mgr

SET emp_mgr.NoOfReports=emp_mgr.NoOfReports-1

FROM deleted WHERE emp_mgr.emp=deleted.mgr

END

В задачу триггера emp_upd входит увеличение на 1 числа подчиненных у нового руководителя и уменьшение на 1 числа подчиненных у прежнего руководителя. Пример изменения записи в таблице emp_mgr приведен в левом окне рисунка 7. Структура данных после преобразования показана на рисунке 3.

Разработка триггера для удаления записи

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

Исправить данный недостаток можно созданием триггера, который будет выполняться при удалении записи о сотрудниках, не имеющих подчиненных. Задача такого триггера – уменьшить на 1 количество подчиненных у непосредственного руководителя удаленного сотрудника.

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

Пример удаления из таблицы emp_mgr сотрудника «а» показан в правом окне рисунка 6. Иерархическая структура после удаления элемента «а» представлена на рисунке 4.

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

USE BASA

IF EXISTS ( SELECT name FROM sysobjects

WHERE name='emp_del' AND type='TR')

DROP TRIGGER emp_del

GO

CREATE TRIGGER emp_del ON emp_mgr FOR DELETE

AS

DECLARE @e CHAR(2), @m CHAR(2), @r INT

SELECT @e=emp,@m=mgr,@r=NoOfReports FROM deleted

IF @m IS NOT NULL

BEGIN --удаляется не директор

IF @r=0 --удаляется сотрудник, у которого нет подчиненных

UPDATE emp_mgr SET NoOfReports=NoOfReports-1

WHERE emp=@m

ELSE

BEGIN --удаляется сотрудник, у которого есть подчиненные

UPDATE emp_mgr SET NoOfReports=NoOfReports+@r-2

WHERE emp=@m

UPDATE emp_mgr SET mgr=@m

WHERE mgr=@e

END

END

ELSE --удаляется директор

IF EXISTS(SELECT * FROM emp_mgr)

BEGIN --в таблице имеются записи о сотрудниках

ROLLBACK TRAN

RAISERROR('НЕЛЬЗЯ УДАЛЯТЬ ДИРЕКТОРА',16,10)

RETURN

END

Однако данный триггер не будет выполняться при удалении записи из таблицы emp_mgr, поскольку ограничение внешнего ключа будет блокировать данный процесс. С помощью оператора ALTER TABLE emp_mgr DROP CONSTRAINT fk_emp необходимо удалить ограничение внешнего ключа FK.

Удаление ограничения внешнего ключа fk_emp влечет за собой нарушение правила 3 при модификации данных в таблице emp_mgr. Для восстановления алгоритма, выполняемого ограничением внешнего ключа, а также для обеспечения правил 2 и 4 в триггеры emp_ins и emp_upd для добавления и изменения записи в таблице emp_mgr необходимо внести дополнительные SQL-операторы.

Признаки нарушения достоверности информации

Запишем признаки нарушения достоверности информации в таблице с рекурсивными связями посредством формул в языке исчисления предикатов первого порядка [4]. Поскольку структурированный язык запросов SQL является разновидностью языка исчисления предикатов, от формул будет очень легко перейти к реализации правил в среде MS SQL Server.

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

Рассмотрим правило 2. При добавлении и изменении записи в таблице emp_mgr это требование предъявляется к новой записи, которая до подтверждения транзакции находится во временной таблице с именем inserted. Признаком ошибки будет нарушение правила. Для получения признака ошибки применим к формуле 2 операцию отрицания:

Ø("x (x, x)Ï R)=$x (x, x)ÎR.                           (7)

Данной формуле соответствуют следующие SQL-операторы.

IF EXISTS (SELECT * FROM inserted WHERE mgr=emp)

BEGIN

ROLLBACK TRAN

RAISERROR('САМ СЕБЕ НАЧАЛЬНИК',16,10)

RETURN

END

Для правила 3, представленного формулой 3, запишем признак ошибки:

Ø("y $x ((x, y) Î R,

y¹NULL)®($ z (y, z) Î R)).                             (8)

Здесь отношение (x,y) соответствует новой записи, которая находится до подтверждения транзакции во временной таблице inserted, а отношение (y,z) – записи, имеющейся в таблице emp_mgr. В формуле использована операция ЕСЛИ A ТО B: A®B. Тогда Ø (A®B) = Ø(`A Ú B ) или Ø (A®B) = A &`B. После преобразования формулы 8 признаком ошибки для правила 3 будет формула:

("y $x ((x, y) Î R,

y¹NULL), Ø($ z (y, z) Î R))                             (9)

или формула

Ø("y $x ((x, y) Î R,y = NULL)Ú

($ z (y, z) Î R))                                                     (10)

Формулы 9 и 10 являются эквивалентными. Соответствующие им SQL-операторы представлены ниже.

Для формулы 9:

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

Для формулы 10:

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, представленного формулой 4, будет следующая формула:

$y $x ((x, y) Î R, y = NULL,

(z¹x), $z (z, y) Î R).                                                  (11)

Формуле 11 соответствуют 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

Признаком ошибки для правила 5 (формула 5) является наличие транзитивного замыкания, что отображается формулой

Ø("x (x, x)Ï R¢)=$x (x, x)ÎR¢                               (12)

или формулой

$x $y (x = y, (x, y)ÎR¢).                                            (13)

В формуле 12 в отношении (x,y) x – идентификатор сотрудника из новой записи, находящейся до завершения транзакции в таблице inserted, y – идентификатор руководителя из таблицы emp_mgr.

Оператор UPDATE может изменить иерархическую структуру таким образом, что возникает транзитивное замыкание, проиллюстрированное на рисунке 5. Для исключения подобных преобразований используем 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

Пример блокирования нарушения иерархической структуры показан в правом окне рисунка 7.

SQL-операторы, построенные по формулам 7, 9 и 11, необходимо добавить в триггеры emp_ins и emp_upd после ключевого слова AS. В триггер emp_upd включается также и фрагмент, разработанный для исключения транзитивных замыканий.

Список литературы

1.       Маклаков С.В. Bpwin и Erwin – CASE-средства разработки информационных систем. -М.: ДИАЛОГ-МИФИ, 1999.-256 с.

2.       Райан Стивен, Рональд Плю. SQL./ Пер. с англ. –М.: ЗАО «Издательство БИНОМ», 1998. – 400 с.

3.       Microsoft SQL Server: Database Developer’s Companion. - Microsoft Corporation, 1998. -709 p.

4.       Грей П. Логика, алгебра и базы данных /Пер. с англ. Х.И. Килова, Г.Е. Минца; Под ред. Е.В. Орловского, А.О. Слисенко. - М.: Машиностроение, 1989.-368 с.