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

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

Определения

Пусть существует некоторое отношение $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)$

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

См. также

• Реляционная модель данных
• Проектирование баз данных
• Функциональная зависимость (программирование)
• 4NF

Литература

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