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

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

Определения

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

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

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

$A\twoheadrightarrow B$.

Формально

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

Многозначная зависимость $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.