7.3. Декомпозиция без потерь и функциональные зависимости

Как уже отмечалось, в следующей лекции мы будем обсуждать подход к проектированию реляционных баз данных на основе нормализации, т. е. декомпозиции (разбиения путем проецирования) отношения, находящегося в предыдущей нормальной форме, на два или более отношений, удовлетворяющих требованиям следующей нормальной формы.

Считаются правильными такие декомпозиции отношения, которые обратимы, т. е. имеется возможность собрать исходное отношение из декомпозированных отношений без потери информации. Такие декомпозиции называются декомпозициями без потерь.

7.3.1. Корректные и некорректные декомпозиции отношений. Теорема Хита

На рис. 7.3приведены две возможные декомпозиции отношенияСЛУЖАЩИЕ_ПРОЕКТЫ(для экономии места мы сократили и слегка изменили тело отношения изрис. 7.1).

Рис. 7.3.Две возможные декомпозиции отношения СЛУЖАЩИЕ_ПРОЕКТЫ

Анализ рис. 7.3показывает, что в случае декомпозиции (1) мы не потеряли информацию о служащих – про каждого из них можно узнать имя, размер зарплаты, номер выполняемого проекта и имя руководителя проекта. Вторая декомпозиция не дает возможности получить данные о проекте служащего, поскольку Иванов и Иваненко получают одинаковую зарплату, следовательно, эта декомпозиция приводит к потере информации. Что же привело к тому, что одна декомпозиция является декомпозицией без потерь, а вторая – нет?

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

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

Корректность же декомпозиции 1 следует из теоремы Хита:

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

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

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

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

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

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

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

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

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

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

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