Введение в системы управления базами данных


Пример 17



Пример 17


НОМЕР ФАМИЛИЯ ЗАРПЛАТА
1 Иванов 1000
2 Петров 1000
2 Петров 2000
2 Сидоров 1000
2 Сидоров 2000

Таблица 16 Отношение

Вывод. Таким образом, без дополнительных ограничений на отношение

нельзя говорить о декомпозиции без потерь.

Такими дополнительными ограничениями и являются функциональные зависимости. Имеет место следующая теорема Хеза [54]:

Теорема (Хеза). Пусть

является отношением, и
- атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость
, то проекции
и
образуют декомпозицию без потерь.

Доказательство. Необходимо доказать, что

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

Докажем первое включение. Возьмем произвольный кортеж

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

Докажем обратное включение. Возьмем произвольный кортеж

. Докажем, что он включается также и в
. По определению естественного соединения получим, что в имеются кортежи
и
. Т.к.
, то существует некоторое значение
, такое что кортеж
. Аналогично, существует некоторое значение
, такое что кортеж
. Кортежи
и
имеют одинаковое значение атрибута
, равное
. Из этого, в силу функциональной зависимости
, следует, что
. Таким образом, кортеж
. Обратное включение доказано. Теорема доказана.

Замечание. В доказательстве теоремы Хеза наличие функциональной зависимости не использовалось при доказательстве включения

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

Т.к. алгоритм нормализации (приведения отношений к 3НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т.е. в ходе нормализации не происходит потери информации.









Начало  Назад  Вперед



Книжный магазин