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

Содержание Назад Вперед

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