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

         

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


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


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