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

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

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

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

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

Алгоритм SATISFIES.

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

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

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

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

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

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

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

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

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

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

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

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

                 X                                                Y