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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Многозна́чная зави́симость (тж. МЗЗ) — обобщение понятия функциональной зависимости, широко использующееся в теории баз данных. В концепции нормальных форм вводится для формального определения четвертой нормальной формы

Определения[править | править вики-текст]

Пусть существует некоторое отношение r со схемой R, а также два произвольных подмножества атрибутов A,B\subseteq R. Пусть C\overset{not}{\mathop{=}}\,R\backslash B.

В этом случае B многозначно зависит от A, тогда и только тогда, когда множество значений атрибута B, соответствующее заданной паре [a:A;c:C] отношения r, зависит от a и не зависит от c.

Символически выражается записью

A \twoheadrightarrow B.


Формально

\begin{align}
  & r\left( R \right),\ A,B\subseteq R,\ C=R\backslash B \\ 
 & \left( A\twoheadrightarrow B \right)\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\in r\ \exists {{t}_{3}},{{t}_{4}}\in r\ :\ \left\{ \begin{align}
  & {{t}_{1}}\left( A \right)={{t}_{2}}\left( A \right)={{t}_{3}}\left( A \right)={{t}_{4}}\left( A \right) \\ 
 & {{t}_{3}}\left( B \right)={{t}_{1}}\left( B \right) \\ 
 & {{t}_{3}}\left( C \right)={{t}_{2}}\left( C \right) \\ 
 & {{t}_{4}}\left( B \right)={{t}_{2}}\left( B \right) \\ 
 & {{t}_{4}}\left( C \right)={{t}_{1}}\left( C \right) \\ 
\end{align} \right. \\ 
\end{align}

Многозначная зависимость A\twoheadrightarrow B называется тривиальной, если выполняется хотя бы одно из условий:

  • Множество A является надмножеством B;
    B\subseteq A
  • Объединение A и B образует весь заголовок отношения.
    A\cup B=R

Пример[править | править вики-текст]

Предположим, у нас есть отношение, в которое входит список учебных дисциплин, рекомендованная литература и имена лекторов, читающих соответствующие курсы:

Учебные дисциплины
Дисциплина Книга Лектор
МатАн Кудрявцев Иванов А.
МатАн Фихтенгольц Петров Б.
МатАн Кудрявцев Петров Б.
МатАн Фихтенгольц Иванов А.
МатАн Кудрявцев Смирнов В.
МатАн Фихтенгольц Смирнов В.
ВМ Кудрявцев Иванов А.
ВМ Кудрявцев Петров Б.

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

Формально, здесь две МЗЗ: {Дисциплина} \twoheadrightarrow {Книга}|{Лектор}.

Во-первых, это избыточно. А во-вторых, для такого отношения необходимо разрабатывать дополнительный механизм контроля целостности. Оптимальным решением проблемы будет декомпозиция отношения на два с заголовками {Дисциплина, Книга} и {Дисциплина, Лектор}. Такая декомпозиция будет находиться в 4NF. Допустимость декомпозиции устанавливает теорема Феджина (см. далее).

Теоремы[править | править вики-текст]

Связные пары[править | править вики-текст]

Феджин показал, что многозначные зависимости образуют связные пары (в обозначениях определения):

\left( A\twoheadrightarrow B \right)\Leftrightarrow \left( A\twoheadrightarrow C \right).

Поэтому их часто представляют вместе в символической записи:

A\twoheadrightarrow B|C

Функциональные зависимости[править | править вики-текст]

Всякая функциональная зависимость является многозначной. Другими словами, функциональная зависимость — это многозначная зависимость, в которой множество зависимых значений, соответствующее заданному значению детерминанта, всегда имеет единичную мощность.

\left( A\to B \right)\Rightarrow \left( A\twoheadrightarrow B \right)

Правила вывода[править | править вики-текст]

В 1977 году Бэри, Феджин и Ховард установили, что правила вывода Армстронга можно обобщить и распространить, как на функциональные, так и на многозначные зависимости.

Пусть у нас есть отношение r\left( R \right) и множества атрибутов A,B,C,D\subseteq R. Для сокращения записи вместо X\cup Y будем писать просто XY.


Группа 1: базовые правила.

  • Дополнение
    \left( A\cup B\cup C=R \right)\wedge \left( B\cap C\subseteq A \right)\Rightarrow \left( \left( A\twoheadrightarrow B \right)\Leftrightarrow \left( A\twoheadrightarrow C \right) \right)
  • Транзитивность
    \left( A\twoheadrightarrow B \right)\wedge \left( B\twoheadrightarrow C \right)\Rightarrow \left( A\twoheadrightarrow C\backslash B \right)
  • Рефлексивность
    \left( B\subseteq A \right)\Rightarrow \left( A\twoheadrightarrow B \right)
  • Приращение
    \left( A\twoheadrightarrow B \right)\wedge \left( C\subseteq D \right)\Rightarrow \left( AD\twoheadrightarrow BC \right)


Группа 2: выводятся несколько дополнительных правил, упрощающих задачу вывода многозначных зависимостей.

  • Псевдотранзитивность
    \left( A\twoheadrightarrow B \right)\wedge \left( BC\twoheadrightarrow D \right)\Rightarrow \left( AC\twoheadrightarrow D\backslash BC \right)
  • Объединение
    \left( A\twoheadrightarrow B \right)\wedge \left( A\twoheadrightarrow C \right)\Rightarrow \left( A\twoheadrightarrow BC \right)
  • Декомпозиция
    \left( A\twoheadrightarrow BC \right)\Rightarrow \left( A\twoheadrightarrow B\cap C \right)\wedge \left( A\twoheadrightarrow B\backslash C \right)\wedge \left( A\twoheadrightarrow C\backslash B \right)


Группа 3: устанавливается связь между функциональными и многозначными зависимостями.

  • Репликация (копирование)
    \left( A\to B \right)\Rightarrow \left( A\twoheadrightarrow B \right)
  • Слияние
    \left( A\twoheadrightarrow B \right)\wedge \left( C\to D \right)\wedge \left( D\subseteq B \right)\wedge \left( B\cap C=\varnothing  \right)\Rightarrow \left( A\to D \right)


Группа 4: для функциональных зависимостей, выводятся из вышеприведенных правил.

  • \left( A\twoheadrightarrow B \right)\wedge \left( AB\to C \right)\Rightarrow \left( A\to C\backslash B \right)


Правила вывода Армстронга вместе с изложенными здесь правилами групп 1 и 3 образуют полный (используя их, можно вывести все остальные многозначные зависимости, подразумеваемые данным их множеством) и надежный («лишних» многозначных зависимостей вывести нельзя; выведенная многозначная зависимость справедлива везде, где справедливо то множество многозначных зависимостей, из которого она была выведена) набор правил вывода многозначных зависисмостей.

Применение[править | править вики-текст]

Декомпозиция отношений[править | править вики-текст]

Теорема Феджина[править | править вики-текст]

Пусть дано отношение r\left( A,B,C \right). Отношение r будет равно соединению его проекций r\left[ A,B \right] и r\left[ A,C \right] тогда и только тогда, когда для отношения r выполняется нетривиальная многозначная зависимость A\twoheadrightarrow B|C.

\left( r\left( A,B,C \right)=r\left[ A,B \right]\ \text{JOIN}\ r\left[ A,C \right] \right)\Leftrightarrow \left( A\twoheadrightarrow B|C \right)

Эта теорема является более строгой версией теоремы Хита.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • К. Дж. Дейт Введение в системы баз данных = Introduction to Database Systems. — 8-е изд. — М.: «Вильямс», 2006. — С. 1328. — ISBN 0-321-19784-4