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

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

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

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

${\displaystyle A\twoheadrightarrow B}$.

Формально

${\displaystyle {\begin{aligned}&r\left(R\right),\ A,B\subseteq R,\ C=R\backslash (A\cup B)\\&\left(A\twoheadrightarrow B\right)\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\in r\ \exists {{t}_{3}},{{t}_{4}}\in r\$ :\ \left\{{\begin{aligned}&{{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{aligned}}\right.\\\end{aligned}}}

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

• Множество ${\displaystyle A}$ является надмножеством ${\displaystyle B}$;

  ${\displaystyle B\subseteq A}$

• Объединение ${\displaystyle A}$ и ${\displaystyle B}$ образует весь заголовок отношения.

  ${\displaystyle A\cup B=R}$

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

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

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

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

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

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

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

• Дополнение

  ${\displaystyle \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)}$

• Транзитивность

  ${\displaystyle \left(A\twoheadrightarrow B\right)\wedge \left(B\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow C\backslash B\right)}$

• Рефлексивность

  ${\displaystyle \left(B\subseteq A\right)\Rightarrow \left(A\twoheadrightarrow B\right)}$

• Приращение

  ${\displaystyle \left(A\twoheadrightarrow B\right)\wedge \left(C\subseteq D\right)\Rightarrow \left(AD\twoheadrightarrow BC\right)}$

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

• Псевдотранзитивность

  ${\displaystyle \left(A\twoheadrightarrow B\right)\wedge \left(BC\twoheadrightarrow D\right)\Rightarrow \left(AC\twoheadrightarrow D\backslash BC\right)}$

• Объединение

  ${\displaystyle \left(A\twoheadrightarrow B\right)\wedge \left(A\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow BC\right)}$

• Декомпозиция

  ${\displaystyle \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: устанавливается связь между функциональными и многозначными зависимостями.

• Репликация (копирование)

  ${\displaystyle \left(A\to B\right)\Rightarrow \left(A\twoheadrightarrow B\right)}$

• Слияние

  ${\displaystyle \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: для функциональных зависимостей, выводятся из вышеприведенных правил.

• ${\displaystyle \left(A\twoheadrightarrow B\right)\wedge \left(AB\to C\right)\Rightarrow \left(A\to C\backslash B\right)}$

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

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

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