Теорема Хита

Пусть задано отношение r {A, B, C} (A, B и C, в общем случае, являются составными атрибутами) и выполняется FD A B.

Рис. 6.4. Результат естественного соединения отношений СЛУЖ и ЗАРП_ПРО

Тогда r = (r PROJECT {A, B}) NATURAL JOIN (r PROJECT {A, C}).

Доказательство. Прежде всего, докажем, что в теле результата естественного соединения (обозначим этот результат через r1) содержатся все кортежи тела отношения r. Действительно, пусть кортеж {a, b, c} r. Тогда по определению операции взятия проекции {a, b} (r PROJECT {A, B}) и {a, с} (r PROJECT {A, С}). Следовательно, {a, b, c} r1. Теперь докажем, что в теле результата естественного соединения нет лишних кортежей, т. е. что если кортеж {a, b, c} r1, то {a, b, c} r. Если {a, b, c} r1, то существуют {a, b} (r PROJECT {A, B}) и {a, с} (r PROJECT {A, С}). Последнее условие может выполняться в том и только в том случае, когда существует кортеж {a, b*, c} r. Но поскольку выполняется FD A B, то b = b* и, следовательно, {a, b, c} = {a, b*, c}. Конец доказательства.

Для иллюстрации общего случая применения теоремы Хита рассмотрим отношение СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ОТД, ПРО_НОМ} (рис. 6.5). Атрибут СЛУ_ОТД содержит номера отделов, в которых работают служащие, а ПРО_НОМ – номера проектов, в которых служащие принимают участие. Каждый служащий работает только в одном отделе, т. е. имеется FD СЛУ_НОМ СЛУ_ОТД, но один служащий может участвовать в нескольких проектах.

Рис. 6.5. Декомпозиция без потерь по теореме Хита

В отношении СЛУЖАЩИЕ_ОТДЕЛЫ_ПРОЕКТЫ атрибут СЛУ_НОМ не является возможным ключом, но, как показано на рис. 6.5, наличия FD СЛУ_НОМ СЛУ_ОТД оказывается достаточно для декомпозиции этого отношения без потерь.

Для дальнейшего изложения нам потребуется ввести еще одно определение и сделать пару замечаний.

Атрибут B минимально зависит от атрибута A, если выполняется минимальная слева FD A B.

Например, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ выполняются FD СЛУ_НОМ СЛУ_ЗАРП и {СЛУ_НОМ, СЛУ_ИМЯ} СЛУ_ЗАРП. Первая FD является минимальной слева, а вторая – нет. Поэтому СЛУ_ЗАРП минимально зависит от СЛУ_НОМ, а для {СЛУ_НОМ, СЛУ_ИМЯ} свойство минимальной зависимости не выполняется.

Дата добавления: 2015-04-29