Теория нормализации отношений

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

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

 Третья  нормальная форма. (Снова определение  дается в предположении существования  единственного ключа.)

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

 Можно  произвести декомпозицию отношения  СОТРУДНИКИ-ОТДЕЛЫ в два отношения  СОТРУДНИКИ и ОТДЕЛЫ:

 СОТРУДНИКИ (СОТР_НОМЕР, ОТД_НОМЕР)

 Первичный  ключ:

 СОТР_НОМЕР 

 Функциональные  зависимости: 

 СОТР_НОМЕР  -> ОТД_НОМЕР

 ОТДЕЛЫ (ОТД_НОМЕР, СОТР_ЗАРП)

 Первичный  ключ:

 ОТД_НОМЕР

 Функциональные  зависимости: 

 ОТД_НОМЕР -> СОТР_ЗАРП

 Каждое  из этих двух отношений находится  в 3NF и свободно от отмеченных  аномалий.

 Если  отказаться от того ограничения,  что отношение обладает единственным  ключом, то определение 3NF примет  следующую форму: 

 Отношение  R находится в третьей нормальной  форме (3NF) в том и только  в том случае, если находится  в 1NF, и каждый неключевой атрибут не является транзитивно зависимым от какого-либо ключа R.

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

Нормальная  форма Бойса-Кодда (НФБК)

Отношения находятся в НФБК, если каждый детерминант  является ключом-кандидатом  (А®В)  Два или более атрибута или группы атрибутов, которые могут быть ключом, называются ключами-кандидатами. Тот из ключей-кандидатов, который выбирается в качестве ключа называется первичным ключом. Рассмотрим следующий пример схемы отношения:

 СОТРУДНИКИ-ПРОЕКТЫ  (СОТР_НОМЕР, СОТР_ИМЯ, ПРО_НОМЕР,  СОТР_ЗАДАН) 

 Возможные  ключи: 

 СОТР_НОМЕР,  ПРО_НОМЕР 

 СОТР_ИМЯ,  ПРО_НОМЕР 

 Функциональные  зависимости: 

 СОТР_НОМЕР  -> CОТР_ИМЯ

 СОТР_НОМЕР  -> ПРО_НОМЕР 

 СОТР_ИМЯ  -> CОТР_НОМЕР

 СОТР_ИМЯ  -> ПРО_НОМЕР 

 СОТР_НОМЕР,  ПРО_НОМЕР -> CОТР_ЗАДАН

 СОТР_ИМЯ,  ПРО_НОМЕР -> CОТР_ЗАДАН

 В  этом примере мы предполагаем, что личность сотрудника полностью  определяется как его номером,  так и именем (это снова не  очень жизненное предположение,  но достаточное для примера).

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

 СОТРУДНИКИ (СОТР_НОМЕР, СОТР_ИМЯ) 

 Возможные  ключи: 

 СОТР_НОМЕР 

 СОТР_ИМЯ 

 Функциональные  зависимости: 

 СОТР_НОМЕР  -> CОТР_ИМЯ

 СОТР_ИМЯ  -> СОТР_НОМЕР 

 СОТРУДНИКИ-ПРОЕКТЫ  (СОТР_НОМЕР, ПРО_НОМЕР, СОТР_ЗАДАН) 

 Возможный  ключ:

 СОТР_НОМЕР,  ПРО_НОМЕР 

 Функциональные  зависимости: 

 СОТР_НОМЕР,  ПРО_НОМЕР -> CОТР_ЗАДАН

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

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

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

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

 Рассмотрим  пример следующей схемы отношения: 

 ПРОЕКТЫ  (ПРО_НОМЕР,ПРО_СОТР, ПРО_ЗАДАН)

 Отношение  ПРОЕКТЫ содержит номера проектов, для каждого проекта список  сотрудников, которые могут выполнять  проект, и список заданий, предусматриваемых  проектом. Сотрудники могут участвовать  в нескольких проектах, и разные  проекты могут включать одинаковые  задания. 

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

 Многозначные  зависимости. В отношении R (A, B, C) существует многозначная зависимость  R.A -> -> R.B в том и только в  том случае, если множество значений B, соответствующее паре значений A и C, зависит только от A и не  зависит от С. 

 В  отношении ПРОЕКТЫ существуют  следующие две многозначные зависимости: 

 ПРО_НОМЕР -> -> ПРО_СОТР

 ПРО_НОМЕР  -> -> ПРО_ЗАДАН

 Легко  показать, что в общем случае  в отношении R (A, B, C) существует  многозначная зависимость R.A -> -> R.B в том и только в том  случае, когда существует многозначная  зависимость R.A -> -> R.C.

 Дальнейшая  нормализация отношений, подобных  отношению ПРОЕКТЫ, основывается  на следующей теореме: 

 Теорема  Фейджина

 Отношение  R (A, B, C) можно спроецировать без  потерь в отношения R1 (A, B) и  R2 (A, C) в том и только в том  случае, когда существует MVD A -> -> B | C.

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

 Четвертая  нормальная форма. Отношение R находится в четвертой нормальной  форме (4NF) в том и только  в том случае, если в случае  существования многозначной зависимости  A -> -> B все остальные атрибуты R функционально зависят от A.

 В  нашем примере можно произвести  декомпозицию отношения ПРОЕКТЫ  в два отношения ПРОЕКТЫ-СОТРУДНИКИ  и ПРОЕКТЫ-ЗАДАНИЯ: 

 ПРОЕКТЫ-СОТРУДНИКИ (ПРО_НОМЕР, ПРО_СОТР)

 ПРОЕКТЫ-ЗАДАНИЯ  (ПРО_НОМЕР, ПРО_ЗАДАН)

 Оба  эти отношения находятся в  4NF и свободны от отмеченных  аномалий. 

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

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

 Рассмотрим, например, отношение 

 СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ  (СОТР_НОМЕР, ОТД_НОМЕР, ПРО_НОМЕР)

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

 Поэтому  отношение находится в 4NF. Однако  в нем могут существовать аномалии, которые можно устранить путем  декомпозиции в три отношения. 

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

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

 Введем  следующие имена составных атрибутов: 

 СО = {СОТР_НОМЕР, ОТД_НОМЕР}

 СП = {СОТР_НОМЕР, ПРО_НОМЕР} 

 ОП = {ОТД_НОМЕР, ПРО_НОМЕР}

 Предположим,  что в отношении СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ  существует зависимость соединения:

* (СО, СП, ОП)

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

 СОТРУДНИКИ-ОТДЕЛЫ (СОТР_НОМЕР, ОТД_НОМЕР)

 СОТРУДНИКИ-ПРОЕКТЫ  (СОТР_НОМЕР, ПРО_НОМЕР) 

 ОТДЕЛЫ-ПРОЕКТЫ  (ОТД_НОМЕР, ПРО_НОМЕР)

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

Доменно-ключевая нормальная форма (ДКНФ)

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

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