Алгоритм нормализации заключается в последовательной декомпозиции отношений для устранения функциональных зависимостей атрибутов от части сложного ключа (приведение к 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НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т. е. в ходе нормализации не происходит потери информации.