Базы данных. Вводный курс


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


Для множества (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, A
BC, AB
C, AC
D, B
C}. По правилу декомпозиции S эквивалентно множеству S1 {A
B, A
C, AB
C, AC
D, B
C}. В детерминанте FD AC
D можно удалить атрибут C, поскольку по правилу дополнения из FD A
C следует A
AC; по правилу транзитивности выводится FD A
D, поэтому атрибут C в детерминанте FD AC
D является избыточным. FD AB
C может быть удалена, поскольку может быть выведена из FD A
C (по правилу пополнения из этой FD выводится AB
BC, а по правилу декомпозиции далее выводится AB
C). Наконец, FD A
C тоже выводится по правилу транзитивности из FD A
B и B
C. Таким образом, мы получаем множество зависимостей {A
B, A
D, B
C}, которое является минимальным и эквивалентно S по построению.

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

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




Начало  Назад  Вперед