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