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

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



Пример 17

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание раздела



Главная сайта