Покрытие множеств зависимостей.

Пусть 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 эквивалентны, в противном случае – неэквивалентны.

Заметим, что когда от заданных зависимостей переходим к полным, то получаем набор функций, эквивалентный исходному.

Кроме того, всегда можно перейти к набору функций, эквивалентному исходному и такому, что в правой части находится только один атрибут.

Говорят, что множество зависимостей F является минимальным покрытием или элементарным функциональным базисом структуры функциональных зависимостей, если:

1) правая часть каждой зависимости из F содержит единственный атрибут;

2) ни для какой зависимости Х¾>Y в F множество F\(X¾>Y) не эквивалентно F;

3) все зависимости набора F полные.

В литературе, при определении функционального базиса иногда не требуют выполнения условий 1) и 3), а функциональный базис, удовлетворяющий 3), называют элементарным.

Заметим, что одному набору функций 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 удовлетворяют приведенным выше трем условиям.