МД и СУБД(Л7)

1.

МД и СУБД
Полные и неполные функциональные зависимости.
Зависимость X—>Y называется неполной, если существует такой атрибут х Х, что (Х\{х})+ Y,
то есть, если, вычеркнув некоторый атрибут х из X, получим Х' такое, что (X'—>Y) F+. Если
такого атрибута х в левой части зависимости не существует, зависимость называется
полной. В дальнейшем будем рассматривать только такие неполные зависимости Х—>Y, где
Y X. Система образующих структуры функциональных зависимостей называется
элементарной, если она содержит только полные зависимости.
Перейти от заданной зависимости Х >Y к полной можно вычеркиванием из Х
“избыточных” атрибутов, то есть, вычеркнув некоторый атрибут х и получив X', проверяем
(X')+ Y, если да, то атрибут х остается вычеркнутым, если нет – возвращается на место, так
проверяются все атрибуты множества X. Ясно, что по одной заданной зависимости
возможно получение нескольких полных зависимостей (в зависимости от порядка
вычеркивания атрибутов).
Пример.
Для схемы R=(U, F), где U={А1, А2, А3, А4}, F={А1—>А2; А2 >A3; A3 >А4; А1,А2—>А4})
определить неполные зависимости, входящие в множество зависимостей F.
Зависимость А1,А2—>А4 не является полной, поскольку зависимость (А1—>А4) F+ и
зависимость (А2—>А4) F+.

2.

МД и СУБД
Покрытие множеств зависимостей.
Пусть F1 и F2 – множества функциональных зависимостей на множестве атрибутов U.
Говорят, что F1 и F2 эквивалентны, если F1+=F2+. В этом случае говорят также, что F1
покрывает F2 (и F2 покрывает F1). Легко проверить, являются ли F1 и F2 эквивалентными.
Для этого не обязательно строить замыкания F1+ и F2+. Достаточно для каждой зависимости
(X—>Y) F1 проверить, содержится ли эта зависимость в F2+. Для этого проверяется,
содержится ли Y в X+F2, (индекс внизу означает, что замыкание строится относительно
набора функций F2); в свою очередь для каждой зависимости (V—>W) F2 проверяется,
содержится ли она в F1+. Если эти условия выполняются, то F1 и F2 эквивалентны, в
противном случае – неэквивалентны.
Заметим, что когда от заданных зависимостей переходим к полным, то получаем набор
функций, эквивалентный исходному.
Кроме того, всегда можно перейти к набору функций, эквивалентному исходному и такому,
что в правой части находится только один атрибут.

3.

МД и СУБД
Говорят, что множество зависимостей F является минимальным покрытием или
элементарным функциональным базисом структуры функциональных зависимостей,
если:
• правая часть каждой зависимости из F содержит единственный атрибут;
• ни для какой зависимости Х >Y в F множество F\(X >Y) не эквивалентно F;
• все зависимости набора F полные.
Заметим, что одному набору функций F может соответствовать несколько элементарных
функциональных базисов.
Пример.
Для схемы R=({А1, А2, А3, A4},
F={A1,A2 >A3; АЗ—>А4; А1—>А4; АЗ,А4 >А1; А1,А4 >А2; А2—>А1; A3 >А1; А4 >А1})
функциональными базисами являются, например, следующие множества функций:
F1 = {А1—>А2; А2 >A3; АЗ >А4; А4—>А1},
F2 = {Al > A2; А1—>АЗ; А1—>А4; А2—>А1; АЗ >А1; А4 >А1}.
Легко видеть, что F1+=F2+=F+и при этом F1 и F2 удовлетворяют приведенным выше трем
условиям.