Минимальное покрытие множества функциональных зависимостей

Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.

Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+

S2+. Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1+ = S2+.

Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:

1. правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);
2. детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т. е. порождению множества FD, не эквивалентного S;
3. удаление любой FD из S приводит к изменению S+, т. е. порождению множества FD, не эквивалентного S.

Чтобы продемонстрировать минимальные и неминимальные множества FD, вернемся к примеру отношения СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК} с . Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ

СЛУ_ИМЯ, СЛУ_НОМСЛУ_ЗАРП, СЛУ_НОМПРО_НОМ, ПРО_НОМПРОЕКТ_РУК} будет минимальным. Действительно, в правых частях FD этого множества находятся множества, состоящие ровно из одного атрибута; каждый из детерминантов тоже является множеством из одного атрибута, удаление которого, очевидно, недопустимо; удаление каждой FD явно приводит к изменению замыкания множества FD, поскольку утрачиваемая информация не выводится с помощью аксиом Армстронга.

С другой стороны, множества FD

1. {СЛУ_НОМ
   
   {СЛУ_ИМЯ, СЛУ_ЗАРП}, СЛУ_НОМ
   
   ПРО_НОМ, СЛУ_НОМ
   
   ПРОЕКТ_РУК, ПРО_НОМ
   
   ПРОЕКТ_РУК},
2. {СЛУ_НОМ
   
   СЛУ_ИМЯ, {СЛУ_НОМ, СЛУ_ИМЯ}
   
   СЛУ_ЗАРП, СЛУ_НОМ
   
   ПРО_НОМ, СЛУ_НОМ
   
   ПРОЕКТ_РУК, ПРО_НОМ
   
   ПРОЕКТ_РУК} и
3. {СЛУ_НОМ
   
   СЛУ_НОМ, СЛУ_НОМ
   
   СЛУ_ИМЯ, СЛУ_НОМ
   
   СЛУ_ЗАРП, СЛУ_НОМ
   
   ПРО_НОМ, СЛУ_НОМ
   
   ПРОЕКТ_РУК, ПРО_НОМ
   
   ПРОЕКТ_РУК}

не являются минимальными. Для множества (1) в правой части первой FD присутствует множество из двух элементов. Для множества (2) удаление атрибута СЛУ_ИМЯ из детерминанта второй FD не меняет замыкание множества FD.
Для множества (3) удаление первой FD не приводит к изменению замыкания. Эти примеры показывают, что для определения минимальности множества FD не всегда требуется явное построение замыкания данного множества.

Интересным и важным является тот факт, что для любого множества FD S существует (и даже может быть построено) эквивалентное ему минимальное множество S-.

Приведем общую схему построения S- по заданному множеству FD S. Во-первых, используя правило (5) (декомпозиции), мы можем привести множество S к эквивалентному множеству FD S1, правые части FD которого содержат только одноэлементные множества (простые атрибуты). Далее, для каждой FD из S1, детерминант D {D1, D2, …, Dn} которой содержит более одного атрибута, будем пытаться удалять атрибуты Di, получая множество FD S2. Если после удаления атрибута Di S2 эквивалентно S1, то этот атрибут удаляется, и пробуется следующий атрибут. Назовем S3 множество FD, полученное путем допустимого удаления атрибутов из всех детерминантов FD множества S1. Наконец, для каждой FD f из множества S3 будем проверять эквивалентность множеств S3 и S3 MINUS {f}. Если эти множества эквивалентны, удалим f из множества S3, и в заключение получим множество S4, которое минимально и эквивалентно исходному множеству FD S.

Пусть, например, имеется отношение R {A, B, C, D} и задано множество FD S = {A

B, ABC, ABC, ACD, BC}. По правилу декомпозиции S эквивалентно множеству S1 {AB, AC, ABC, ACD, BC}. В детерминанте FD ACD можно удалить атрибут C, поскольку по правилу дополнения из FD AC следует AAC; по правилу транзитивности выводится FD AD, поэтому атрибут C в детерминанте FD ACD является избыточным. FD ABC может быть удалена, поскольку может быть выведена из FD AC (по правилу пополнения из этой FD выводится ABBC, а по правилу декомпозиции далее выводится ABC). Наконец, FD AC тоже выводится по правилу транзитивности из FD AB и BC. Таким образом, мы получаем множество зависимостей {AB, AD, BC}, которое является минимальным и эквивалентно S по построению.

Минимальным покрытием множества FD S называется любое минимальное множество FD S1, эквивалентное S.

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


Содержание раздела

---

---