Замыкание множества зависимостей

Как уже упоминалось выше, некоторые ФЗ могут означать другие ФЗ. Например, приведенная ниже зависимость

подразумевает следующие ФЗ:

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

Множество всех ФЗ, которые задаются данным множеством функциональных зависимостей 5, называется замыканием S и обозначается символом S⁺. Из сказанного выше становится ясно, что для выполнения сформулированной задачи следует найти способ вычисления S⁺ на основе S. Первой попыткой решить эту проблему была статья Армстронга (Armstrong) [9.1], в которой представлен набор правил вывода функциональных зависимостей на основе заданных (эти правила также называются аксиомами Армстронга). Правила могут формулироваться разными способами, а самый простой из них приводится ниже.

■ ■ Правила вывода Армстронга. Пусть в перечисленных ниже правилах А, В и С — произвольные подмножества множества атрибутов заданного отношения R, а символическая запись АВ означает объединение А и В.

1. 1. Рефлексивность: если В является подмножеством А, А ® В.

2. 2. Дополнение: если А ® В, то АС ® ВС.

3. 3. Транзитивность: если А ® В и В ® С, то А ® С

Каждое из этих правил может быть непосредственно доказано на основе определения функциональной зависимости (первое из них — это всего лишь определение тривиальной зависимости). Более того, эти правила являются полными в том смысле, что для заданного множества функциональных зависимостей S минимальный набор ФЗ, которые подразумевают все зависимости S, может быть выведен из S на основе этих правил. Они также являются исчерпывающими, поскольку никакие дополнительные ФЗ не могут быть выведены (т.е. ФЗ, которые не подразумеваются зависимостями множества S). Иначе говоря, эти правила могут быть использованы для получения замыкания S⁺.

Из трех описанных выше правил для упрощения задачи практического вычисления замыкания S⁺ можно вывести несколько других правил. (Пусть D — это другое произвольное подмножество множества атрибутов R.)

4. 4. Самоопределение: А ® А.

5. 5. Деклмпозиция: если А ® ВС, то А ® В и A ® С.

6. 6. Объединение: если А ® В и А ® С, А ® ВС.

7. 7. Композиция: если А ® В и С ® D, то АС ® ВD.

Кроме того, Дарвен (Darwen) в своей работе [9.6] доказал следующее правило, которое назвал теоремой всеобщего объединения:

8. 8. Если А ® В и С ® D, то (где символ “ ” обозначает объединение множеств, а символ “–” — их разность).

Название “теорема всеобщего объединения” указывает на то, что некоторые перечисленные ранее правила могут быть выведены как частные случаи этой теоремы [9.6].

Пример. Пусть дано некоторое отношение R с атрибутами А, В, С, D, E, F и следующими ФЗ:

Обратите внимание, что способ записи несколько изменился (без ущерба для смысла): например, символы ВС означают множество, состоящее из атрибутов В и С, хотя ранее эти символы означали объединение В и С, где В и С были множествами атрибутов.

Замечание. Если необходимо, этому примеру можно придать более конкретный смысл, а именно: А — номер сотрудника, В — номер отдела, С — номер руководителя (начальника) данного сотрудника, D — номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно взятого руководителя), Е — название отдела, F — доля времени, уделяемая данным руководителем заданному проекту.

Теперь можно показать, что зависимость AD®F выполняется для отношения R и таким образом принадлежит замыканию данного множества ФЗ.