Основы проектирования реляционных баз данных



Алгоритм метода синтеза отношений - часть 3


В результате получается множество ФЗ F2.

Этап 3. Сокращение справа элементов F2

Удаляются последовательно один за другим атрибуты ФЗ из правых частей ФЗ F2; проверяется, может ли исходная ФЗ быть выведена из полученной ФЗ и имеющихся ФЗ F2. Если да, то исходная ФЗ заменяется на новую ФЗ. Этап завершается после перебора всех ФЗ F2. В результате получается множество ФЗ F3.

На этом сокращение ФЗ закончено. Избыточность отсутствует. Необходимо приступать к построению минимального покрытия.

Этап 4. Разделение F3 на классы эквивалентности по правым частям

Строится разбиение F3 на группы: две ФЗ принадлежат одной и той же группе тогда и только тогда, когда их правые части эквивалентны. В результате получается множество классов эквивалентности ФЗ

F_4 = \cup fd
.

Этап 5. Удаление в классах эквивалентности избыточных ФЗ

Для всех пар ФЗ fdi и fdj из одной и той же группы проверяется, может ли ФЗ левой стороны fdj от правой стороны fdj быть выведена из этой группы ФЗ. Если да, то из fdj ФЗ удаляется и добавляется в правую часть этой ФЗ к правой fdi. Новая ФЗ будет находиться в той же группе, что и исходная ФЗ. В результате получается минимальное число ФЗ F5, покрывающих F3.

Этап 6. Получение классов эквивалентности по левым частям F5 и составных ФЗ C1

Для каждого множества ФЗ с эквивалентными левыми частями из F5 создается составная ФЗ

(X_1, \dots, X_n) \to {Y}
. Если какой-либо атрибут из Y есть в Xi, то этот атрибут удаляется. В результате получается множество составных ФЗ С1.

Этап 7. Удаление избыточных зависимостей из С1

Для каждой составной ФЗ из С1 и для каждого атрибута Xi из левой части С сдвигаются атрибуты в правую часть. В результате получается множество составных ФЗ С'. Если fd(C') эквивалентно fd(C1), то С1 заменяется на С'. В результате получается множество ФЗ С2.

Этап 8. Формирование кольцевого минимального покрытия

Для каждой составной ФЗ c из С2 и каждого атрибута A из правой части c удаляется атрибут А. В результате получается С', состоящее из с'. Если fd(C') эквивалентно fd(C2), то С2 заменяется на С'.В результате получается множество ФЗ С3.

Этап 9. Формирования схемы полной базы данных

Для каждой составной ФЗ с из С3 формируется таблица атрибутов, которые появляются в с. Ключами для этой таблицы являются Хi из левой части с. Таблица послужит для усиления ФЗ в F.

Алгоритм поэтапного синтеза отношений обладает хорошей сходимостью, его целесообразно использовать в запрограммированном виде. Для этого можно воспользоваться уже готовой программой, или написать свою программу с учетом специфики своих задач, обратившись к монографии Д. Мейера [3].




Содержание  Назад  Вперед