Выявление зависимостей между атрибутами

Выявление зависимостей между атрибутами необходимо для выполнения проектирования БД методом нормальных форм, рассматриваемого далее.

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

Пример. Пусть задано отношение R со схемой R(A1, A2, A3) и числовыми значениями, приведенными в следующей таблице:

Априори известно, что в R существуют функциональные зависимости: А1->A2 и А2->A3.

Анализируя это отношение, можно увидеть, что в нем существуют еще зависимости:

А1-> A3, А1А2-> A3, А1А2АЗ-> А1А2, А1А2-> А2АЗ и т. п.

В то же время в отношении нет других функциональных зависимостей, что во введенных нами обозначениях можно отразить следующим образом: А2-,->А1, АЗ-,->А1 и т. д.

Отсутствие зависимости А1 от А2 (А2-.->А1) объясняется тем, что одному и тому же значению атрибута А2 (21) соответствуют разные значения атрибута А1 (12 и 17). Другими словами, имеет место многозначность, а не функциональность.

Перечислив все существующие функциональные зависимости в отношении R, получим полное множество функциональных зависимостей, которое обозначим F +.

Таким образом, для последнего примера исходное множество F = (А1-> А2, А2-> A3), а полное множество

F += (А1-> А2, А2-> A3, А1-> A3, А1А2-> A3, А1А2АЗ-> А1А2, А1А2->А2АЗ,...).

Для построения F+ из F необходимо знать ряд правил (или аксиом) вывода одних функциональных зависимостей из других. Существует 8 основных аксиом вывода:

рефлексивности

пополнения

транзитивности

расширения

продолжения

псевдотранзитивности

объединения

декомпозиции.

Перечисленные аксиомы обеспечивают получение всех ФЗ, т. е. их совокупность применительно к процедуре вывода можно считать "функционально полной". Выявим зависимости между атрибутами отношения ПРЕПОДАВАТЕЛЬ. При этом учтем следующее условие, которое выполняется в данном отношении: один преподаватель в одной группе может проводить один вид занятий (лекции или практические занятия). В результате анализа отношения получаем зависимости между атрибутами, показанные на рис. 5.5.

Рис. 5.5. Зависимости между атрибутами

ФИО->Oклад

ФИО->Должн

ФИО->Стаж

ФИО->Д_Стаж

ФИО->Каф

Стаж->Д_Стаж

Должн->0клад

Оклад->Должк

ФИО.Предм.Группа->ВидЗан

К выделению этих ФЗ для рассматриваемого примера приводят следующие соображения. Фамилия, имя и отчество у преподавателей факультета уникальны. Каждому преподавателю однозначно соответствует его стаж, т. е. имеет место функциональная зависимость ФИО->Стаж. Обратное утверждение неверно, так как одинаковый стаж может быть у разных преподавателей. Каждый преподаватель имеет определенную добавку за стаж, т. е. имеет место функциональная зависимость ФИО->Д_Стаж, но обратная функциональная зависимость отсутствует, так как одну и ту же надбавку могут иметь несколько преподавателей.

Каждый преподаватель имеет определенную должность (преп., ст.преп., доцент, профессор), но одну и ту же должность могут иметь несколько преподавателей, т. е. имеет место функциональная зависимость ФИО->Должн, а обратная функциональная зависимость отсутствует.

Каждый преподаватель является сотрудником одной и только одной кафедры. Поэтому функциональная зависимость ФИО->Каф имеет место. С другой стороны, на каждой кафедре много преподавателей, поэтому обратной функциональной зависимости нет.

Каждому преподавателю соответствует конкретный оклад, который одинаков для всех педагогов с одинаковыми должностями, что учитывается зависимостями ФИО->Oклад и Должн->Oклад. Нет одинаковых окладов для разных должностей, поэтому имеет место функциональная зависимость Оклад->Должн.

Один и тот же преподаватель в одной группе по разным предметам может проводить разные виды занятий. Определение вида занятий, которые проводит преподаватель, невозможно без указания предмета и группы, поэтому имеет место функциональная зависимость ФИО, Предм, Группа->ВидЗан. Действительно, Петров М.И. в 256 группе читает лекции и проводит пратические занятия. Но лекции он читает по СУБД, а практику проводит по Паскалю.

Нами не были выделены зависимости между атрибутами ФИО, Предм и Группа, поскольку они образуют составной ключ и не учитываются в процессе нормализации исходного отношения.

После того, как выделены все функциональные зависимости, следует проверить их согласованность с данными исходного отношения ПРЕПОДАВАТЕЛЬ.

Например, Должн.=преп и Оклад=500 всегда соответствуют друг другу во всех кортежах, т. е. подтверждается функциональная зависимость Должн<->Oклад. Так же следует верифицировать и остальные функциональные зависимости, не забывая об ограниченности имеющихся в отношении данных.

Нормальные формы

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

первая нормальная форма (1НФ);

вторая нормальная форма (2НФ);

третья нормальная форма (3НФ);

усиленная третья нормальная форма, или нормальная форма Бойса-Кодда (БКНФ);

четвертая нормальная форма (4НФ);

пятая нормальная форма (5НФ).

Первая нормальная форма. Отношение находится в 1НФ, если все его атрибуты являются простыми (имеют единственное значение). Исходное отношение строится таким образом, чтобы оно было в 1НФ.

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

Основной операцией метода является операция проекции. Поясним ее на примере. Предположим, что в отношении R(A,B,C,D,E,...) устранение функциональной зависимости C->D позволит перевести его в следующую нормальную форму Для решения этой задачи выполним декомпозицию отношения R на два новых отношения R1(A,B,C,E,...) и R2(C,D). Отношение R2 является проекцией отношения R на атрибуты С и D.

Исходное отношение ПРЕПОДАВАТЕЛЬ, используемое для иллюстрации метода, имеет составной ключ ФИО. Предм, Группа и находится в 1 НФ, поскольку все его атрибуты простые. В этом отношении в соответствии с рис. 5.5 можно выделить частичную зависимость атрибутов Стаж, Д_Стаж, Каф, Должн, Оклад от ключа - указанные атрибуты находятся в функциональной зависимости от атрибута ФИО, являющегося частью составного ключа. Эта частичная зависимость от ключа приводит к следующему:

1. В отношении присутствует явное и неявное избыточное дублирование данных, например:

повторение сведений о стаже, должности и окладе преподавателей, проводящих занятия в нескольких группах и/или по разным предметам;

повторение сведений об окладах для одной и той же должности или о надбавках за одинаковый стаж.

2. Следствием избыточного дублирования данных является проблема их редактирования. Например, изменение должности у преподавателя Иванова И.М. потребует просмотра всех кортежей отношения и внесения изменений в те из них, которые содержат сведения о данном преподавателе.

Часть избыточности устраняется при переводе отношения в 2НФ.

Вторая нормальная форма. Отношение находится в 2НФ, если оно находится в 1НФ и каждый неключевой атрибут функционально полно зависит от первичного ключа (составного). Для устранения частичной зависимости и перевода отношения в 2НФ необходимо, используя операцию проекции, разложить его на несколько отношений следующим образом:

построить проекцию без атрибутов, находящихся в частичной функциональной зависимости от первичного ключа;

построить проекции на части составного первичного ключа и атрибуты, зависящие от этих частей. В результате получим два отношения R1 и R2 в 2НФ (рис. 5.6).

В отношении R1 первичный ключ является составным и состоит из атрибутов ФИО, Предм, Группа. Напомним, что данный ключ в отношении R1 получен в предположении, что каждый преподаватель в одной группе по одному предмету может либо читать лекции, либо проводить практические занятия. В отношении R2 ключ ФИО.

Исследование отношений R1 и R2 показывает, что переход к 2НФ позволил исключить явную избыточность данных в таблице R2 - повторение строк со сведениями о преподавателях. В R2 по-прежнему имеет место неявное дублирование данных. Для дальнейшего совершенствования отношения необходимо преобразовать его в 3НФ.

Третья нормальная форма. Определение 1. Отношение находится в 3НФ, если оно находится в 2НФ и каждый неключевой атрибут нетранзитивно зависит от первичного ключа.

Существует и альтернативное определение.

Определение 2. Отношение находится в 3НФ в том и только в том случае, если все неключевые атрибуты отношения взаимно независимы и полностью зависят от первичного ключа.

Доказать справедливость этого утверждения несложно. Действительно, то, что неключевые атрибуты полностью зависят от первичного ключа, означает, что данное отношение находится в форме 2НФ. Взаимная независимость атрибутов (определение приведено выше) означает отсутствие всякой зависимости между атрибутами отношения, в том числе и транзитивной зависимости между ними. Таким образом, второе определение 3НФ сводится к первому определению.

Если в отношении R1 транзитивные зависимости отсутствуют, то в отношении R2 они есть:

ФИО->Должн->Оклад, ФИО->Оклад->Должн, ФИО->Стаж->Д_Стаж

Транзитивные зависимости также порождают избыточное дублирование информации в отношении. Устраним их. Для этого используя операцию проекции на атрибуты, являющиеся причиной транзитивных зависимостей, преобразуем отношение R2, получив при этом отношения R3, R4 и R5, каждое из которых находится в 3НФ. Заметим, что отношение R2 можно преобразовать по-другому, а именно: в отношении R3 вместо атрибута Должн взять атрибут Оклад.

На практике построение 3НФ схем отношений в большинстве случаев является достаточным и приведением к ним процесс проектирования реляционной БД заканчивается. Действительно, приведение отношений к 3НФ в нашем примере, привело к устранению избыточного дублирования.

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

Усиленная 3НФ или нормальная форма Бойса-Кодда (БКНФ). Отношение находится в БКНФ, если оно находится в 3НФ и в нем отсутствуют зависимости ключей (атрибутов составного ключа) от неключевых атрибутов.

У нас подобной зависимости нет, поэтому процесс проектирования на этом заканчивается. Результатом проектирования является БД, состоящая из следующих таблиц: Rl, R3, R4, R5. В полученной БД имеет место необходимое дублирование данных, но отсутствует избыточное.

Четвертая нормальная форма. Рассмотрим пример нового отношения ПРОЕКТЫ, схема которого выглядит следующим образом: ПРОЕКТЫ (Номер_проекта, Код_сотрудника, Задание_сотрудника). Первичным ключом отношения является вся совокупность атрибутов: Номер_проекта, Код_сотрудника и Задание_сотрудника. В отношении содержатся номера проектов, для каждого проекта - список кодов сотрудников-исполнителей, а также список заданий, предусмотренных каждым проектом. Сотрудники могут участвовать в нескольких проектах, и разные проекты могут содержать одинаковые задания. Предполагается, что каждый сотрудник, участвующий в некотором проекте, выполняет все задания по этому проекту (предположение не всегда справедливо, но желательно для нашего примера).

При такой постановке вопроса единственным возможным ключом отношения является составной атрибут Номер_проекта, Код_сотрудника, Задание_сотрудника. Он, естественно, и стал первичным ключом отношения. Отсюда следует, что отношение ПРОЕКТЫ, находится в форме БКНФ.

Главный недостаток отношения ПРОЕКТЫ состоит в том, что при подключении/отстранении от проекта некоторого сотрудника приходится добавлять/исключать из отношения столько кортежей, сколько заданий имеется в проекте. Внесение или исключение в отношении одного факта о некотором сотруднике требует серии элементарных операций из-за дублирования значений в кортежах.

Отсюда возникают вопросы: зачем хранить в кортежах повторяющиеся значения кодов сотрудников? Нужно ли перечислять все задания по каждому проекту, да еще для каждого сотрудника-исполнителя этого проекта? Нельзя ли информацию о привязке заданий к проектам поместить в отдельную таблицу и исключить повторения в основной таблице?

Заметим, что косвенный признак аномалии, как и ранее, - дублирование информации в таблице. Выскажем предположение, что причиной аномалии является наличие некоторой зависимости между атрибутами отношения (как увидим далее - многозначной зависимости). Действительно, в отношении ПРОЕКТЫ существуют следующие две многозначные зависимости:

Номер_проекта=> Код_сотрудника Номер_проекта=> 3адание_сотрудника

В произвольном отношении R(A,В,С) может одновременно существовать многозначная зависимость А=>В и А=>С. Это обстоятельство обозначим как А=>В |С. Дальнейшая нормализация отношений, схожих с отношением Проекты, основывается на следующей теореме.

Теорема Фейджина (Fagin R.). Отношение R(A,В,С) можно спроецировать без потерь в отношения R1(A,В) и R2(A,С) в том и только том случае, когда существует зависимость А=>В |С.

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

Поясним проецирование без потерь на примере. Пусть имеется простейшее отношение (A,В,С). Построим проекции R1 и R2 на атрибуты А, В и А, С соответственно. Результатом операции соединения бинарных отношений R1(A,В) и R2(A,С) по атрибуту А является тернарное отношение с атрибутами А, В и С, кортежи которого получаются путем связывания отношений R1 и R2 по типу 1:М на основе совпадения значений атрибута А (подраздел 3.3). Так, связывание кортежей (к,15) и {(к,1), (к,2)} дает кортежи {(к,15,1), (к,15,2)}. Нетрудно видеть, что связывание R1(A,В) и R2(A,С) в точности порождает исходное отношение R(A,В,С). В отношении R нет лишних кортежей, нет и потерь.

Определение четвертой нормальной формы. Отношение R находится в четвертой нормальной форме (4НФ) в том и только в том случае, когда существует многозначная зависимость А=>В, а все остальные атрибуты R функционально зависят от А.

Приведенное выше отношение ПРОЕКТЫ можно представить в виде двух отношений: ПРОЕКТЫ-СОТРУДНИКИ и ПРОЕКТЫ-ЗАДАНИЯ. Эти отношения имеют следующую структуру:

Как легко увидеть, оба этих отношения находятся в 4НФ и свободны от замеченных недостатков. Дублирование значений атрибутов кодов сотрудников пропало. Попробуйте самостоятельно соединить эти отношения и убедиться в том, что в точности получится отношение ПРОЕКТЫ.

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

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

Рассмотрим отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ, которое имеет заголовок СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ (Код_сотрудника, Код_отдела, Номер_проекта). Первичный ключ отношения включает все атрибуты: Код_сотруд-ника, Код_отдела и Номер_проекта. Пусть в этом отношении один сотрудник может работать в нескольких отделах, причем в каждом отделе он может принимать участие в нескольких проектах. В одном отделе могут работать несколько сотрудников, но каждый проект выполняет только один сотрудник. Функциональных и многозначных зависимостей между атрибутами не существует.

Это отношение является частью базы данных вымышленного научного подразделения НИИЧАВО - Научно-Исследовательского Института ЧАродейства и ВОлшебства из повести А. и Б.Стругацких "Понедельник начинается в субботу". Коды отделов здесь обозначают: АД - Администрация, ВЦ - Вычислительный центр, ЛС -Линейного счастья, РД - Родильный дом, СЖ - Смысла жизни, УП - Универсальных превращений.

Исходя из структуры отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ можно заключить, что оно находится в форме 4НФ. Тем не менее в отношении могут быть аномалии, связанные с возможностью повторения значений атрибутов в нескольких кортежах. Например, то что сотрудник может работать в нескольких отделах, при увольнении сотрудника требует отыскания и последующего удаления из исходной таблицы нескольких записей.

Введем определение зависимости соединения. Отношение R(X, Y,... , Z) удовлетворяет зависимости соединения, которую обозначим как *(Х, Y,..., Z), в том и только в том случае, если R восстанавливается без потерь путем соединения своих проекций на X, Y,..., Z. Зависимость соединения является обобщением функциональной и многозначной зависимостей.

Определение пятой нормальной формы. Отношение R находится в 5НФ (или нормальной форме проекции-соединения - PJ/NF) в том и только том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R.

Образуем составные атрибуты отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ:
С0={ Код_сотрудиика, Код_отдела}

СП=4 Код_сотрудника, Номер_проекта}

ОП={ Код_отдела, Номер_проекта}.

Покажем, что если отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ спроецировать на составные атрибуты СО, СП и ОП, то соединение этих проекций дает исходное отношение. Это значит, что в нашем отношении существовала зависимость соединения *(СО, СП, ОП). Проекции на составные атрибуты назовем соответственно СОТРУДНИКИ-ОТДЕЛЫ, СОТРУДНИКИ-ПРОЕКТЫ и ОТДЕЛЫ-ПРОЕКТЫ.

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

Замечание.

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

Отношения СОТРУДНИКИ-ОТДЕЛЫ, СОТРУДНИКИ-ПРОЕКТЫ и ОТДЕЛЫ-ПРОЕКТЫ находятся в 5НФ. Эта форма является последней из известных. Условия ее получения довольно нетривиальны и поэтому она почти не используется на практике. Более того, она имеет определенные недостатки!

Предположим, необходимо узнать, где и какие проекты исполняет сотрудник с кодом 02. Для этого в отношении СОТРУДНИКИ-ОТДЕЛЫ найдем, что сотрудник с кодом 02 работает в отделе АД, а из отношения ОТДЕЛЫ-ПРОЕКТЫ найдем, что в отделе АД выполняются проекты 004 и 019, А это значит, что сотрудник 02 должен выполнять проекты 004 и 019. Увы, информация о том, что сотрудник с кодом 02 выполняет проект 019, ошибочна (см. исходное отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ).

Такие противоречия можно устранить только путем совместного рассмотрения всех проекций основного отношения. Именно поэтому после соединения проекций и выполнялась операция их пересечения. Безусловно, это -'недостаток. Отметим, что наличие недостатков не требует обязательного отказа от определенных видов нормальных форм. Надо учитывать недостатки и условия их проявления. В некоторых постановках задач недостатки не проявляются.

На практике обычно ограничиваются структурой БД, соответствующей 3НФ или БКНФ. Поэтому процесс нормализации отношений методом нормальных форм предполагает последовательное удаление из исходного отношения следующих межатрибутных зависимостей:

частичных зависимостей неключевых атрибутов от ключа (удовлетворение требований 2НФ);

транзитивных зависимостей неключевых атрибутов от ключа (удовлетворение требований 3НФ);

зависимости ключей (атрибутов составных ключей) от неключевых атрибутов (удовлетворение требований БКНФ).

Кроме метода нормальных форм Кодда, используемого для проектирования небольших БД, применяют и другие методы, например, метод ER-диаграмм (метод "Сущность-связь"). Этот метод используется при проектировании больших БД, на нем основан ряд средств проектирования БД. На последнем этапе метода ER-диаграмм отношения, полученные в результате проектирования, проверяются на принадлежность их к БКНФ. Этот этап может выполняться уже с использованием метода нормальных форм. После завершения проектирования создается БД с помощью СУБД.