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

Страницы работы

Содержание работы

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

Похожие материалы

Информация о работе