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

4.5.Замыкание множества заданных функциональных зависимостей.

            При декомпозиции отношения R с целью его нормализации на два отношения R1 и R2 может оказаться, что в R1 или R2 появятся новые функциональные зависимости, которых не было в отношении R. В этом случае нужно получить из множества функциональных зависимостей F, присущих отношению R полное множество функциональных зависимостей – F⁺ , которое называется замыканием F.

            Если F1 – множество функциональных зависимостей, присущих отношению R1, то декомпозиция будет верной, если F1≤ F⁺  и если F2≤ F⁺ , где F2 – множество функциональных зависимостей, присущих отношению R2.

            Существует несколько методов получения  F⁺ из F. Рассмотрим 2 метода.

Алгоритм SATISFIES.

            Пусть задано отношение График(Пилот, Рейс, Дата, Время вылета)

Пилот	Рейс	Дата	Время вылета
1 1 2 2 2 3 3 4 4 4	83 116 281 301 83 83 116 281 281 412	9Августа 10 Августа 8 Августа 12 Августа 11 Августа 12 Августа 13 Августа 9 Августа 13 Августа 15 Августа	10:15 13:25 5:50 18:35 10:15 10:15 13:25 5:50 5:50 13:25
Куминг-1 Кларк-2 Чин-3 Коул-4

            Для этого отношения иметься следующая семантика:

                        F={Рейс → Время вылета,

      Пилот, Дата, Время вылета → Рейс,

      Рейс, Дата → Пилот}

            Имея это множество F мы можем задаться  вопросом о том, а существует ли зависимость, например, такого типа: Время вылета → Рейс или другие, более сложные зависимости.

 Ответ на этот вопрос можно получить используя следующий алгоритм:

Пусть задано отношение R  и F- зависимость x → y.

            1.Пересортируем отношение R по x- столбцам так, чтобы собрать кортежи с равными x- значениями вместе.

            2.Если каждая совокупность кортежей с равными x-значениями имеет так же равные y-значения, то существует зависимость x→y. В противном случае нет.

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

            Проверим зависимость: Рейс → Время вылета.

                 X                                                Y

Пилот	Рейс	Дата	Время вылета
1 2 3		9Августа 11 Августа 13 Августа	=
1 3		10 Августа 12 Августа	=
2 4 4		8 Августа 9 Августа 13 Августа	=
2	301	12 Августа	18:35
4	412	15 Августа	13:25