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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

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

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

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

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 нормальная форма - лучшая форма с точки зрения операций проекции и соединения.