Зависимости соединения и пятая нормальная форма

Множественная декомпозиция

Рассмотрим отношение и его декомпозицию:

Course	Lecturer	Group
СУБД	Корнеев Г. А.	M3438
СУБД	Корнеев Г. А.	M3439
Мат.ан.	Кохась К. П.	M3237
Мат.ан.	Виноградов О. Л.	M3239
Java	Корнеев Г. А.	M3239

Course	Lecturer
СУБД	Корнеев Г. А.
СУБД	Корнеев Г. А.
Мат.ан.	Кохась К. П.
Мат.ан.	Виноградов О. Л.
Java	Корнеев Г. А.

Course	Group
СУБД	M3438
СУБД	M3439
Мат.ан.	M3237
Мат.ан.	M3239
Java	M3239

Lecturer	Group
Корнеев Г. А.	M3438
Корнеев Г. А.	M3439
Кохась К. П.	M3237
Виноградов О. Л.	M3239
Корнеев Г. А.	M3239

Тогда необходимо задать ограничения для обеспечения корректности, то есть:

Если

• Лектор $L$ читает курс $C$
• Лектор $L$ читает группе $G$
• Группа $G$ слушает курс $C$

То лектор $L$ читает курс $C$ группе $G$.

При этом есть все 3 вида аномалии: вставки, удаления и обновления. Например, когда лектор читает что-то группе, группа слушает курс, но лектор конкретно этот курс не читает.

Зависимость соединения

Определение:

В отношении есть зависимость соединения [math]∗\{X_{1},X_{2},\ldots,X_{n}\}[/math] тогда и тогда тогда, когда соответствующая декомпозиция корректна: [math]R(X_{1}X_{2}\ldots X_{n})=\pi_{X1}(R)\bowtie\pi_{X2}(R)\bowtie\ldots\bowtie \pi_{X_{n}}(R)[/math]. При этом все [math]X_{i}[/math] должны быть подмножествами исходного множества атрибутов.

Теорема Фейгина в терминах зависимости соединения будет выглядеть следующим образом:

Для [math]R(XYZ): X \twoheadrightarrow Y{|}Z \Leftrightarrow ∗\{XY,XZ\}[/math]

Определение:

Тривиальные зависимости соединения $-$ зависимости соединения, у которых одно из отношений, на которые мы проецируем, совпадает с исходным: [math]\forall R: *\{R, X_{1}, X_{2}, \ldots, X_{n}\}[/math]

Утверждение:

Тривиальные зависимости соединения являются обобщением для тривиальных множественных зависимостей.

[math]\triangleright[/math]

Из тривиальности зависимости соединения следует, что либо [math]XY[/math] составляет все атрибуты, что означает, что [math]Z[/math] пустой, либо [math]XZ[/math] составляет все атрибуты, из чего следует, что [math]Y[/math] пустой. То есть либо [math]Z[/math], либо [math]Y[/math] пустые в зависимости соединения на двух проекциях. Значит, это была тривиальная множественная зависимость.

[math]\triangleleft[/math]

Пятая нормальная форма (Проекционно-соединительная)

Определение:

Отношение находится в пятой нормальной форме тогда и только тогда, когда для каждой нетривиальной ЗС [math]∗\{X_{1},X_{2},\ldots,X_{n}\}[/math] каждое $X_{i} -$ надключ.

Утверждение:

Если отношение находится в 5НФ, то оно находится в 4НФ.

[math]\triangleright[/math]

По теореме Фейгина [math]R(XYZ): X \twoheadrightarrow Y{|}Z \Leftrightarrow ∗\{XY,XZ\}[/math]. В этой многозначной зависимости $X -$ надключ. Значит, отношение находится в 4НФ.

[math]\triangleleft[/math]

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

Если

• [math](x_{1},x_{2}) \in \pi{X_{1}X_{2}}(R)[/math]
• [math](x_{2},x_{3}) \in \pi{X_{2}X_{3}}(R)[/math]
• $\ldots$
• [math](x_{n−1},x_{n}) \in \pi{X_{n−1}X_{n}}(R)[/math]
• [math](x_{n},x_{1}) \in \pi{X_{n}X_{1}}(R) [/math]

То [math](x_{1},x_{2},\ldots,x_{n}) \in R[/math]

Если данные условия выполняются, то возможно есть зависимость соединения и стоит декомпозировать.

Замечание. 5 нормальная форма - лучшая форма с точки зрения операций проекции и соединения.