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

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

Определение: Функциональная зависимость

В отношении rатрибутYфункционально зависит от атрибутаX(XиYмогут быть составными) в том и только в том случае, если каждому значению X соответствует в точности одно значениеY: r.Xr.Y.

Определение: Минимальная (полная) функциональная зависимость

Функциональная зависимость r.X r.Yназывается минимальной (или полной), если атрибутYне зависит функционально от любого точного подмножестваX.

Определение: Транзитивная функциональная зависимость

Функциональная зависимость r.X r.Yназывается транзитивной, если существует такой атрибутZ, что имеются функциональные зависимостиr.Xr.Zиr.Zr.Yи отсутствует функциональная зависимостьr.Z r.X. (При отсутствии последнего требования мы имели бы "неинтересные" транзитивные зависимости в любом отношении, обладающем несколькими ключами.)

Определение: Неключевой атрибут

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

Определение: Взаимно независимые атрибуты

Два или более атрибута взаимно независимы, если ни один из этих атрибутов не является функционально зависимым от других.

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

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

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

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

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

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

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

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

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

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