Построение неизбыточных покрытий

Построение неизбыточного покрытия рассмотрим на следующем примере.

Пример 21. Пусть U = ABC и F = {A ® B, B ® A, C ® A, A ® C, B ® C}. Попытаемся построить неизбыточное покрытие F, то есть множество без “лишних” зависимостей. Выберем направление просмотра зависимостей сначала слева – направо, а затем справа – налево и покажем, что различный порядок просмотра зависимостей из F может привести к разным результатам.

Просматриваем зависимости из F слева - направо.

Для получения результата зависимости выводить не будем, а будем использовать факт выводимости конкретной зависимости из остальных зависимостей (теорема 1 из раздела 1.4).

Для зависимости A ® B строим замыкание A+ (левой части этой зависимости) по множеству остальных зависимостей из F: F \ {A ® B} = {B ® A, C ® A, A ® C, B ® C}. Здесь символ “\” означает вычитание, в данном случае вычитание зависимостей. Получим A+ = AC. Так как правая часть зависимости B Ë A+ , то зависимость A ® B не является “лишней”, то есть она не выводится из остальных зависимостей из F.

Для зависимости B ® A имеем B+ = BCA. Так как A Ì B+, то зависимость B ® A – “лишняя”. Удалим ее из F. Получим новое множество F1 = {A ® B, C ® A, A ® C, B ® C}.

Для зависимости C ® A имеем C+ = C. Зависимость не является “лишней”.

Для зависимости A ® C имеем A+ = ABC и C Ì A+ . Зависимость является “лишней”. Удалим ее из F1. Получим F2 = {A ® B, C ® A, B ® C}.

Для зависимости B ® C имеем B+ = B и C Ë B+. Зависимость не является “лишней”.

Таким образом, получили неизбыточное покрытие множества F в виде

F0 (слева - направо)={A ® B, C ® A, B ® C}.

Просматривая зависимости в исходном множестве F справа - налево и удаляя “лишние” зависимости, как было сделано выше, получим неизбыточное покрытие F в виде

F0 (справа - налево) ={A ® B, B ® A, C ® A, A ® C}.

Видно, что полученные множества не совпадают и имеют разное количество зависимостей, т.е. выбор направления просмотра зависимостей влияет на результат.

Существует ли процедура построения неизбыточного покрытия, которая давала бы одинаковый результат независимо от направления просмотра зависимостей? Эта задача успешно решается, если воспользоваться понятием расширенного множества зависимостей.

Расширение касается правых частей каждой зависимости из F. Поскольку расширяется каждая зависимость, то количество зависимостей исходного и расширенного множеств одинаково.

Расширенное множество зависимостей строится по правилу:

= {(Xi ® i) ç(Xi ® Yi) Î F, i =Xi+ \ Xi},

где символ “ç” означает “при условии”, а символом “\”, как и всюду выше, обозначена операция вычитания (здесь имеется в виду вычитание множеств атрибутов). Это означает, что правая часть i каждой зависимости расширенного множества содержит все атрибуты из U, зависимость которых от атрибутов левой части X следует из F. Поэтому, если левые части каких-либо зависимостей из F совпадают, то и их правые части в расширенном множестве также будут совпадать. Так удается легко выявить “лишние” зависимости с одинаковой левой частью. Вычеркнув найденные таким образом “лишние” зависимости, получаем множество 0, в котором могут остаться лишние зависимости с разными левыми частями. Поэтому множество 0 будем называть условно неизбыточным или псевдонеизбыточным покрытием F. Далее можно осуществить поиск в множестве 0 “лишних” зависимостей так, как было выполнено в примере 21, результат которого уже не будет зависеть от направления просмотра зависимостей. Удаляя “лишние” зависимости, легко получаем неизбыточное покрытие множества F, которое в общем случае не является каноническим. В некоторых частных случаях оно может быть и минимальным покрытием.

Если условно неизбыточное покрытие 0 содержит большое количество зависимостей, то обычная процедура поиска “лишних” зависимостей может оказаться утомительной. Можно показать, что часть оставшихся “лишних” зависимостей будет находиться среди так называемых эквивалентных зависимостей. Процедура с использованием эквивалентных зависимостей будет подробно описана при изложении метода синтеза в разделе 2.2.

Построим расширенное множество зависимостей для примера 21.

Итак, исходное множество F = {A ® B, B ® A, C ® A, A ® C, B ® C}.

Расширяем первую зависимость A ® B. Для этого вычисляем замыкание атрибутов левой части зависимости: A+ = ABC. Отсюда следует (для обозначения следования, как и прежде, будем использовать символ Þ), что в расширенное множество будет включена зависимость A ® BC. Процедуру получения расширенной зависимости будем кратко записывать так: A+ = ABC Þ A ® BC.

Для второй зависимости B ® A: B+ = BAC Þ B ® AC

Для третьей зависимости C ® A: C+ = CAB Þ C ® AB

Для четвертой зависимости A ® C: A+ = ABC Þ A ® BC

Для пятой зависимости B ® C: B+ = BAC Þ B ® AC

Таким образом, расширенное множество зависимостей будет таким:

= {A ® BC, B ® AC, C ® AB, A ® BC, B ® AC}.

В этом множестве легко определяются “лишние” зависимости (подчеркнуты), и условно неизбыточное покрытие множества F будет включать три зависимости:

0= {A ® BC, B ® AC, C ® AB}.

Отметим, что это множество содержит также три зависимости, как и минимальное покрытие F0 (слева - направо), но не является каноническим.