Таким образом, без дополнительных ограничений
Пример 17
НОМЕР
ФАМИЛИЯ
ЗАРПЛАТА
| 1 |
Иванов |
1000 |
| 2 |
Петров |
1000 |
| 2 |
Петров |
2000 |
| 2 |
Сидоров |
1000 |
| 2 |
Сидоров |
2000 |
Таблица 16 Отношение
Вывод. Таким образом, без дополнительных ограничений на отношение
нельзя говорить о декомпозиции без потерь.
Такими дополнительными ограничениями и являются функциональные зависимости. Имеет место следующая теорема Хеза [54]:
Теорема (Хеза). Пусть
является отношением, и
- атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость
, то проекции
и
образуют декомпозицию без потерь.
Доказательство. Необходимо доказать, что
для любого состояния отношения
. В левой и правой части равенства стоят множества кортежей, поэтому для доказательства достаточно доказать два включения для двух множеств кортежей:
и
.
Докажем первое включение. Возьмем произвольный кортеж
. Докажем, что он включается также и в
. По определению проекции, кортежи
и
. По определению естественного соединения кортежи
и
, имеющие одинаковое значение
общего атрибута
, будут соединены в процессе естественного соединения в кортеж
. Таким образом, включение доказано.
Докажем обратное включение. Возьмем произвольный кортеж
. Докажем, что он включается также и в
. По определению естественного соединения получим, что в имеются кортежи
и
. Т.к.
, то существует некоторое значение
, такое что кортеж
. Аналогично, существует некоторое значение
, такое что кортеж
. Кортежи
и
имеют одинаковое значение атрибута
, равное
. Из этого, в силу функциональной зависимости
, следует, что
. Таким образом, кортеж
. Обратное включение доказано.
Теорема доказана.
Замечание. В доказательстве теоремы Хеза наличие функциональной зависимости не использовалось при доказательстве включения
. Это означает, что при выполнении декомпозиции и последующем восстановлении отношения при помощи естественного соединения, кортежи исходного отношения не будут потеряны. Основной смысл теоремы Хеза заключается в доказательстве того, что при этом не появятся новые кортежи, отсутствовавшие в исходном отношении.
Т.к. алгоритм нормализации (приведения отношений к 3НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т.е. в ходе нормализации не происходит потери информации.
Содержание раздела
