Теорема Хита.

Итак, целью нормализации является построение оптимальной полной декомпозиции. При построении этой декомпозиции используются функциональные зависимости, заданные для этого отношения. Однако, до сего момента мы не говорили о том, как ФЗ влияют на построение декомпозиций. Связь между функциональной зависимостью атрибутов отношения и его полной декомпозицией устанавливает теорема Хита (Heath T.). Для формулировки и доказательства этой теоремы введем в рассмотрение отношение Y, в котором выделим три атрибута (простых или составных): А, В и С.

При наличии функциональной зависимости С от В набор проекций ( А,В ) и ( В,С ) образует полную декомпозицию исходного отношения.

Или, если В -> C, то Y = proj A,B (Y) join proj B,C (Y)

Доказательство. Возможные значения А,В и С будем обозначать соответственно a и a’, b и b’, c и c’. Каждая из указанных величин может фактически представлять собой как простой атрибут, так и совокупность нескольких атрибутов. Введем в рассмотрение вспомогательное отношение Y₁:

Y₁ = proj A,B (Y) join proj B,C (Y)

Докажем тождество Y и Y₁. Возьмем произвольный кортеж abc, принадлежащий Y. Очевидно, что ab принадлежит proj A,B (Y), а bс принадлежит proj B,C (Y). Исходя из определения отношения Y₁ и свойств операции соединения, можно заключить, что кортеж abc входит в Y₁ . Так как речь идет о произвольном кортеже, то можно утверждать, что каждый кортеж Y одновременно принадлежит и Y₁.

Теперь рассмотрим произвольный кортеж a’b’c’, принадлежащий Y₁. Согласно определению Y₁, выполняется равенство:

proj A,B (Y₁) = proj A,B (Y)

Отсюда можно сделать вывод, что в Y присутствует кортеж a’b’c. Аналогичным образом равенство

proj B,C (Y₁) = proj B,C (Y)

позволяет утверждать, что Y содержит кортеж ab’c’. Поскольку B -> C, а в кортежи a’b’c и ab’c’ входит одно и то же значение b’, постольку c= c’ и a’b’c = a’b’c’. Последнее означает, что каждый кортеж Y₁ присутствует в Y. Учитывая, что выполняется и обратное, можно утверждать, что эти два отношения тождественны, что и требовалось доказать.

Дата добавления: 2015-07-19