Базы данных. Вводный курс


Корректные и некорректные декомпозиции отношений. Теорема Хита - часть 2



Рис. 7.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}. Конец доказательства.

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

СЛУ_ОТД, но один служащий может участвовать в нескольких проектах.


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

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

СЛУ_ОТД оказывается достаточно для декомпозиции этого отношения без потерь.

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

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

B.

Например, в отношении СЛУЖАЩИЕ_ПРОЕКТЫ выполняются FD СЛУ_НОМ

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




Начало  Назад  Вперед



Книжный магазин