На главную   ::   Содержание



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

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

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

Определение 2.  

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

Определение 3.   Функциональной зависимостью $ B\subseteq S_R$ от $ A\subseteq S_R$, обозначаемой $ R.A\to R.B$ называется такое соотношение проекций $ R[A]$ и $ R[B]$, что любому элементу $ R[A]$ соответствует только один элемент $ R[B]$, входящий в какой-нибудь кортеж $ R$. Зависимость называется полной, если $ \not\exists  A^1\subseteq A: 
A^1\to B$. Зависимость называется транзитивной, если $ \exists  C:
  C\not\subseteq A,   C\not\supseteq B,   A\to C, C\not\to A,
C\to B$.

Определение 4.   Возможным ключом называется неуменьшаемый набор атрибутов, который однозначно определяет кортеж.

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

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

Определение 7.   $ A,B$ -- взаимно-независимые атрибуты, если $ A\not\to B, B\not\to
A$.

Основные аксиомы зависимости:
  1. $ B\subseteq A\Rightarrow A\to B$;
  2. $ A\to B\Rightarrow AC\to BC$;
  3. $ A\to B, B\to C\Rightarrow A\to C$.

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

Определение 9.   Отношение находится во второй нормальной форме $ \Leftrightarrow$ оно находится в 1НФ и не содержит неполных функциональных зависимостей непервичных атрибутов от атрибутов первичного ключа.

Например, таблица сдачи экзаменов:
{ФИО, Номер зач.кн., Группа, Дисциплина, Оценка}
Здесь Номер зач.кн $ \to$ Группа, ФИО, в то время как первичный ключ -- Номер зач.кн., Дисциплина. Нужно разбить на два отношения:
{ФИО, Номер зач.кн., Группа}
{Номер зач.кн., Дисциплина, Оценка}
Это удобно, например, если студент меняет группу -- нужно исправить лишь одну запись.

Определение 10.   Отношение находится в третьей нормальной форме $ \Leftrightarrow$ оно находится в 2НФ и не содержит транзитивных зависимостей.

Например, таблица связей с группами, факультетами, специальностями:
{ФИО, НЗК, Группа, Факультет, Специальность, Кафедра}
Это отношение содержит зависимости: Группа определяет Факультет, Специальность и, например, Кафедру. Кафедра определяет факультет и т.д. Для избавления от зависимостей разбивается на отношения:
{НЗК, ФИО, Специальность, Группа}
{Группа, Кафедра}
{Кафедра,Факультет}

Определение 11.   Отношение находится в нормальной форме Бойса--Кодда, если оно находится в 3НФ и каждый детерминант отношения является возможным ключом отношения.

Например, таблица по сессии:
{НЗК, ID_Студента, Дисциплина, Дата, Оценка}
Таблица содержит зависимости: НЗК, Дисциплина, Дата $ \to$ Оценка; ID_Студента, Дисциплина, Дата $ \to$ Оценка; НЗК $ \to$ ID_Студента; ID_Студента $ \to$ НЗК. В последних двух зависимостях детерминанты не являются возможными ключами отношения. Избавимся так:
{НЗК, Дисциплина, Дата, Оценка}
{НЗК, ID_Студента}

Определение 12.   В отношении $ R$ существует многозначная зависимость $ A\twoheadrightarrow B$, если $ A\subseteq S_R,
B\subseteq S_R, C\cup A\cup B=S_R$ и множество значений $ B$, соответствующее паре значений $ A,C$ зависит от $ A$ и не зависит от $ C$. Т.е. одному значению $ A$ соответствует некоторое постоянное множество значений $ B$.

Теорема 1. (Фейджина)   Отношение $ R(A,B,C)$ можно без потерь спроецировать на отношения $ R_1(A,B)$ и $ R_2(A,C)$ $ \Leftrightarrow$ существуют многозначные зависимости $ A\twoheadrightarrow B$ и $ A\twoheadrightarrow С$.

Определение 13.   Отношение находится в четвертой нормальной форме, если в случае существования многозначной зависимости $ A\twoheadrightarrow B$ все остальные атрибуты $ R$ функционально зависят от $ A$.

Например,
{НЗК, Группа, Дисциплина}
Здесь группа определяет дисциплины, которые изучает студент и группа определяет студентов, которые в ней учатся. Для избавления от зависимостей разобъем отношение на два:
{НЗК, Группа}
{Группа, Дисциплина}

Определение 14.   Отношение $ R(X,Y,\dots)$ удовлетворяет зависимости соединения $ (X,Y,\dots)$ $ \Leftrightarrow$ $ R$ восстанавливается без потерь путем соединения своих проекций на $ X,Y,\dots$. Здесь $ X,Y,\dots$ -- наборы атрибутов отношения $ R$.

Определение 15.   Отношение находится в пятой нормальной форме $ \Leftrightarrow$ любая зависимость соединения в $ R$ следует из существования некоторого возможного ключа в $ R$.

Пример: пусть каждый преподаватель может работать на нескольких кафедрах и на каждой кафедре вести несколько дисциплин. Тогда ключ отношения
{Преподаватель, Кафедра, Дисциплина}
-- это полный набор атрибутов. Обозначим наборы атрибутов ПК (Преподаватель, Кафедра), ПД (Преподаватель, Дисциплина), КД (Кафедра, Дисциплина). Отношение не находится в 5НФ, т.к. наличие зависимости соединения (ПК, ПД, КД) связано с атрибутами, которые не составляют возможные ключи. Т.е. если построить проекции на ПК, ПД, КД, то таблицу можно по этим проекциям восстановить, но сами ПК, ПД, КД не являются ключами. Разбивая на три отношения
{Преподаватель, Кафедра}
{Преподаватель, Дисциплина}
{Кафедра,Дисциплина}
получим 5НФ.

На главную   ::   Содержание