Переход от ненормализованных отношений к отношениям в 3НФ может быть выполнен при помощи алгоритма нормализации.

Алгоритм нормализации заключается в последовательной декомпозиции отношений для устранения функциональных зависимостей атрибутов от части сложного ключа (приведение к 2НФ) и устранения функциональных зависимостей неключевых атрибутов друг от друга (приведение к 3НФ).
Корректность процедуры нормализации (декомпозиция без потери информации) доказывается теоремой Хеза.
Проекция R[X] отношения R на множество атрибутов X называется собственной, если множество атрибутов X является собственным подмножеством множества атрибутов отношения R(т.е. множество атрибутов X не совпадает с множеством всех атрибутов отношения R).
Определение 7. Собственные проекции R1 и R2 отношения R называются декомпозицией без потерь, если отношение R точно восстанавливается из них при помощи естественного соединения для любого состояния отношения R:
.
Теорема (Хеза). Пусть R(A,B,C) является отношением, и A,B,C - атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость , то проекции и образуют декомпози-цию без потерь.
Доказательство. Необходимо доказать, что для любого состояния отношения R. В левой и правой части равенства стоят множества кортежей, поэтому для доказа-тельства достаточно доказать два включения для двух множеств кортежей: и .
Докажем первое включение. Возьмем произвольный кортеж . Докажем, что он включается также и в . По определению проекции, кортежи и . По определению естественного соединения кортежи r1 и r2 , имеющие одинаковое значение a общего атрибута A, будут соединены в процессе естественного соединения в кортеж . Таким образом, включение доказано.
Докажем обратное включение. Возьмем произвольный кортеж . Докажем, что он включается также и в R. По определению естественного соединения получим, что в имеются кортежи и . Т.к. , то существует некоторое значение c1, такое что кортеж . Аналогично, существует некоторое значение b1, такое что кортеж . Кортежи r1 и r2 имеют одинаковое значение атрибута A, равное a. Из этого, в силу функциональ-ной зависимости , следует, что b=b1. Таким образом, кортеж . Обратное включение доказано. Теорема доказана.
Замечание. В доказательстве теоремы Хеза наличие функциональной зависимости не использовалось при доказательстве включения . Это означает, что при выполнении декомпозиции и последующем восстанов-лении отношения при помощи естественного соединения, кортежи исходного отношения не будут потеряны. Основной смысл теоремы Хеза заключается в доказательстве того, что при этом не появятся новые кортежи, отсутствовавшие в исходном отношении.
Т.к. алгоритм нормализации (приведения отношений к 3НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т.е. в ходе нормализации не происходит потери информации.

Найти похожие вопросы