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

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

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

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

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

2. детерминант каждой FD изSобладает свойствомминимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыканияS⁺, т. е. порождению множества FD, не эквивалентногоS³⁰⁾;

3. удаление любой FD из Sприводит к изменениюS⁺, т. е. порождению множества FD, не эквивалентногоS.

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

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

29 Мы используем здесь знаки операций проверки включения множеств, что не совсем корректно, поскольку если, например, множество B состоит из одного элемента, то для его обозначения используется имя соответствующего атрибута, и в этом случае правильнее было бы использовать знак «» (проверка вхождения элемента во множество).

30 FD с минимальным детерминантом называется минимальной слева.

к изменению замыкания множества FD, поскольку утрачиваемая информация не выводится с помощью аксиом Армстронга.

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

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

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

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

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

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

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

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

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

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