Зависимости соединения и пятая нормальная форма — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Множественная декомпозиция)
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Зависимость соединения ==
+
== Множественная декомпозиция ==
=== Множественная декомпозиция ===
 
 
Рассмотрим отношение и его декомпозицию:
 
Рассмотрим отношение и его декомпозицию:
 
{| class="wikitable"
 
{| class="wikitable"
Строка 67: Строка 66:
  
 
При этом есть все 3 вида аномалии: вставки, удаления и обновления. Например, когда лектор читает что-то группе, группа слушает курс, но лектор конкретно этот курс не читает.
 
При этом есть все 3 вида аномалии: вставки, удаления и обновления. Например, когда лектор читает что-то группе, группа слушает курс, но лектор конкретно этот курс не читает.
 +
== Зависимость соединения ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
В отношении есть зависимость соединения <tex>∗\{X_{1},X_{2},\ldots,X_{n}\}</tex> тогда и тогда тогда, когда соответствующая декомпозиция корректна: <tex>R(X_{1}X_{2}\ldots X_{n})=\pi_{X1}(R)\bowtie\pi_{X2}(R)\bowtie\ldots\bowtie \pi_{X_{n}}(R)</tex>. При этом все <tex>{X_{i}</tex> должны быть подмножествами исходного множества атрибутов.
+
В отношении есть зависимость соединения <tex>∗\{X_{1},X_{2},\ldots,X_{n}\}</tex> тогда и тогда тогда, когда соответствующая декомпозиция корректна: <tex>R(X_{1}X_{2}\ldots X_{n})=\pi_{X1}(R)\bowtie\pi_{X2}(R)\bowtie\ldots\bowtie \pi_{X_{n}}(R)</tex>. При этом все <tex>X_{i}</tex> должны быть подмножествами исходного множества атрибутов.
 
}}
 
}}
 
'''Теорема Фейгина''' в терминах зависимости соединения будет выглядеть следующим образом:  
 
'''Теорема Фейгина''' в терминах зависимости соединения будет выглядеть следующим образом:  
Строка 77: Строка 77:
 
|definition=
 
|definition=
 
Тривиальные зависимости соединения $-$ зависимости соединения, у которых одно из отношений, на которые мы проецируем, совпадает с исходным:  <tex>\forall R: *\{R, X_{1}, X_{2}, \ldots, X_{n}\}</tex>
 
Тривиальные зависимости соединения $-$ зависимости соединения, у которых одно из отношений, на которые мы проецируем, совпадает с исходным:  <tex>\forall R: *\{R, X_{1}, X_{2}, \ldots, X_{n}\}</tex>
 +
}}
 +
 +
{{Утверждение
 +
|statement=
 +
Тривиальные зависимости соединения являются обобщением для тривиальных множественных зависимостей.
 +
|proof=
 +
Из тривиальности зависимости соединения следует, что либо <tex>XY</tex> составляет все атрибуты, что означает, что <tex>Z</tex> пустой, либо <tex>XZ</tex> составляет все атрибуты, из чего следует, что <tex>Y</tex> пустой. То есть либо <tex>Z</tex>, либо <tex>Y</tex> пустые в зависимости соединения на двух проекциях. Значит, это была тривиальная множественная зависимость.
 
}}
 
}}
  
Строка 94: Строка 101:
  
 
Формально, для приведения к 5 нормальной форме необходимо найти все зависимости соединения, однако это достаточно сложно.
 
Формально, для приведения к 5 нормальной форме необходимо найти все зависимости соединения, однако это достаточно сложно.
На практике ЗС, не являющиеся МЗ, встречаются редко. Обычно это можно выяснить с помощью '''кольцевых ограничений''':
+
На практике ЗС, не являющиеся МЗ, встречаются редко.  
 +
Попробовать выяснить, находится ли отношение в 5НФ, можно с помощью '''кольцевых ограничений''':
  
 
Если  
 
Если  
Строка 103: Строка 111:
 
*<tex>(x_{n},x_{1}) \in \pi{X_{n}X_{1}}(R) </tex>
 
*<tex>(x_{n},x_{1}) \in \pi{X_{n}X_{1}}(R) </tex>
 
То <tex>(x_{1},x_{2},\ldots,x_{n}) \in R</tex>
 
То <tex>(x_{1},x_{2},\ldots,x_{n}) \in R</tex>
 +
 +
Если данные условия выполняются, то возможно есть зависимость соединения и стоит декомпозировать.
 +
 +
'''Замечание.''' 5 нормальная форма - лучшая форма с точки зрения операций проекции и соединения.
  
 
[[Категория: Базы данных]]
 
[[Категория: Базы данных]]

Текущая версия на 19:40, 4 сентября 2022

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

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

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