Минимальное покрытие множества функциональных зависимостей
Определение 6.7. Покрытие множества FD
Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также и из S2. Конец определения.
Легко заметить, что S2 является покрытием S1 тогда и только тогда, когда S1+ Í S2+. Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т.е. S1+ = S2+.
Определение 6.8. Минимальное множество FD
Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:
a) правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);
b) детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута из детерминанта приводит к изменению замыкания S+, т.е. порождению множества FD, не эквивалентного S.*
c) удаление любой FD из S приводит к изменению S+, т.е. порождению множества FD, не эквивалентного S. Конец определения.
Чтобы продемонстрировать минимальные и не минимальные множества FD, вернемся к примеру отношения СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ,СЛУ_ИМЯ,СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК}с рис. 6.1. Если считать, что единственным возможным ключом этого отношения является атрибут СЛУ_НОМ, то множество FD {СЛУ_НОМ® СЛУ_ИМЯ, СЛУ_НОМ ® СЛУ_ЗАРП, СЛУ_НОМ ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК} является минимальным. Действительно, в правых частях FD этого множества находятся множества, состоящие ровно из одного атрибута; каждый из детерминантов тоже является множеством из одного атрибута, удаление которого, очевидно, недопустимо; удаление каждой FD явно приводит к изменению замыкания множества FD, поскольку утрачиваемая информация не выводится с помощью аксиом Армстронга.
С другой стороны, множества FD
(*) {СЛУ_НОМ® {СЛУ_ИМЯ, СЛУ_ЗАРП},СЛУ_НОМ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК},
(**) { СЛУ_НОМ® СЛУ_ИМЯ, { СЛУ_НОМ, СЛУ_ИМЯ} ® СЛУ_ЗАРП, СЛУ_НОМ ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК} и
(***) { СЛУ_НОМ ® СЛУ_НОМ, СЛУ_НОМ ® СЛУ_ИМЯ, СЛУ_НОМ ® СЛУ_ЗАРП, СЛУ_НОМ ® ПРО_НОМ, СЛУ_НОМ ® ПРОЕКТ_РУК, ПРО_НОМ ® ПРОЕКТ_РУК}
не являются минимальными. Для множества (*) в правой части первой FD присутствует множество из двух элементов. Для множества (**) удаление атрибута СЛУ_ИМЯиз детерминанта второй FD не меняет замыкание множества FD. Для множества (***) удаление первой 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 по построению.
Определение 6.9. Минимальное покрытие множества FD
Минимальным покрытием множества FD S называется любое минимальное множество FD SI, эквивалентное S. Конец определения.
Поскольку для каждого множества FD существует эквивалентное минимальное множество FD, у каждого множества FD имеется хотя бы одно минимальное покрытие, причем для его нахождения не обязательно находить замыкание исходного множества.