Многозначные зависимости и четвертая нормальная форма

Материал из Викиконспекты
Версия от 14:52, 22 декабря 2021; 178.252.88.207 (обсуждение) (Теорема Фейгина)
Перейти к: навигация, поиск

Аномалии в НФБК

Рассмотрим следующий пример:

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

В данном отношении подразумевается, что набор книг по курсу не зависит от преподавателя.

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

При этом, если мы предполагаем, что набор литературы не зависит от преподавателя, то у нас будут все 3 вида аномалии:

  • Вставки: невозможно указать литературу по курсу без преподавателя.
  • Удаления: нельзя удалить преподавателя, не потеряв литературу по курсу.
  • Изменения: если есть два преподавателя по одному и тому же курсу и один рекомендует книгу, а другой нет. При этом для курса должен быть конкретный набор книг.

Для таких случаев было введено понятие многозначной зависимости.

Многозначная зависимость

Определение:
[math]X \twoheadrightarrow Y[/math] [math](X[/math] многозначно определяет [math]Y)[/math] в отношении [math]R:[/math]
  • [math]X[/math] и [math]Y - [/math] множества атрибутов
  • Множество значений [math]Y[/math] не зависит от [math]R \setminus X \setminus Y[/math]
  • [math]\forall x,y1,z1,y2,z2[/math] если [math](x,y1,z1)∈R[/math] и [math](x,y2,z2) \in R[/math] то [math]{y{|}(x,y,z1) \in R}={y{|}(x,y,z2) \in R}[/math]


Утверждение:
Любая функциональная зависимость является множественной зависимостью.
[math]\triangleright[/math]
У $Y$ при фиксированном $X$ есть ровно одно значение. То есть мощность множества, которое зависит, равна одному.
[math]\triangleleft[/math]

Теорема Фейгина

Теорема:
Обобщение теоремы Хита: [math]R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Leftrightarrow X \twoheadrightarrow Y [/math]
Доказательство:
[math]\triangleright[/math]
  • [math]\Rightarrow[/math]
    • [math]R(XYZ)=\pi_{XY}(R) \bowtie \pi_{XZ}(R) \Rightarrow (x,y,z) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R)∧(x,z) \in \pi_{XZ}(R)[/math]
    • Пусть [math](x,z1) \in \pi_{XZ}(R),(x,z2) \in \pi_{XZ}(R),[/math] тогда [math](x,y,z1) \in R \Leftrightarrow (x,y) \in \pi_{XY}(R) \Leftrightarrow (x,y,z2) \in R[/math]
  • [math]\Leftarrow[/math]
    • [math]\forall(x,y,z) \in \pi_{XY}(R) \bowtie \pi_{XZ}(R) \Rightarrow (x,y) \in \pi_{XY}(R)\wedge(x,z) \in \pi_{XY}(R)[/math]
    • Тогда [math]\exists y',z':(x,y',z) \in R\wedge(x,y,z') \in R[/math]
    • Так как [math]X \twoheadrightarrow Y, то (x,y,z) \in R \wedge (x,y',z') \in R [/math]
[math]\triangleleft[/math]

В отличие от теоремы Хита, где доказывалась только достаточность, в теореме Фейгина доказывается необходимость и достаточность.

Теорема о дополнении

Теорема:
[math]R(XYZ)[/math] и [math]X \twoheadrightarrow Y \Rightarrow X \twoheadrightarrow Z[/math]
Доказательство:
[math]\triangleright[/math]

Из [math]X \twoheadrightarrow Y[/math] по теореме Фейгина следует [math]R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R).[/math]

Вследствие коммутативности [math]R(XYZ) = \pi_{XY}(R) \bowtie \pi_{XZ}(R) = \pi_{XZ}(R) \bowtie \pi_{XY}(R).[/math]

Применяя еще раз теорему Фейгина, получаем, что [math]X \twoheadrightarrow Z.[/math]
[math]\triangleleft[/math]


[math]X \twoheadrightarrow Y {|} Z[/math] обозначается: [math]X[/math] множественно определяет [math]Y[/math] и [math]Z[/math].

Следствие. [math]\forall R(XY) \Rightarrow X \twoheadrightarrow Y{|}\emptyset[/math]

[math]X \twoheadrightarrow Y{|}\emptyset[/math] называется тривиальной множественной зависимостью.

Четвертая нормальная форма

Определение:
Отношение находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда
  • Для каждой нетривиальной множественной зависимости [math]X \twoheadrightarrow Y {|} Z [/math] и атрибута [math]A: X \rightarrow A[/math]
  • Для каждой нетривиальной множественной зависимости [math]X \twoheadrightarrow Y{|}Z: X[/math] – надключ
  • Каждая нетривиальная множественная зависимость является функциональной зависимостью и отношение находится в нормальной форме Бойса-Кодда


Достижимость

Теорема:
Любое отношение можно декомпозировать на отношения, находящиеся в 4НФ
Доказательство:
[math]\triangleright[/math]
  • Пока есть множественная зависимость, декомпозируем на два отношения.
  • Количество атрибутов в каждом отношении всегда уменьшается.
  • в конце останутся либо отношения из одного атрибута, которые находятся в 4НФ, либо отношения, в которых нет неудовлетворяющих зависимостей и которые находятся в 4НФ по определению
[math]\triangleleft[/math]

Пример приведения к 4НФ

Пусть задано отношение:

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

В данном отношении есть множественная зависимость: [math]Course \twoheadrightarrow Lecturer {|} Book[/math], поэтому декомпозируем его следующим образом:

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