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

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

Определения

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

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

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

<math>A \twoheadrightarrow B</math>.

Формально

<math>\begin{align}

 & 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{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}</math>

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

• Множество <math>A</math> является надмножеством <math>B</math>;

  <math>B\subseteq A</math>

• Объединение <math>A</math> и <math>B</math> образует весь заголовок отношения.

  <math>A\cup B=R</math>

Пример

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

Учебные дисциплины

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

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

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

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

Теоремы

Связные пары

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

<math>\left( A\twoheadrightarrow B \right)\Leftrightarrow \left( A\twoheadrightarrow C \right)</math>.

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

<math>A\twoheadrightarrow B|C</math>

Функциональные зависимости

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

<math>\left( A\to B \right)\Rightarrow \left( A\twoheadrightarrow B \right)</math>

Правила вывода

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

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

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

• Дополнение

  <math>\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)</math>

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

  <math>\left( A\twoheadrightarrow B \right)\wedge \left( B\twoheadrightarrow C \right)\Rightarrow \left( A\twoheadrightarrow C\backslash B \right)</math>

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

  <math>\left( B\subseteq A \right)\Rightarrow \left( A\twoheadrightarrow B \right)</math>

• Приращение

  <math>\left( A\twoheadrightarrow B \right)\wedge \left( C\subseteq D \right)\Rightarrow \left( AD\twoheadrightarrow BC \right)</math>

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

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

  <math>\left( A\twoheadrightarrow B \right)\wedge \left( BC\twoheadrightarrow D \right)\Rightarrow \left( AC\twoheadrightarrow D\backslash BC \right)</math>

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

  <math>\left( A\twoheadrightarrow B \right)\wedge \left( A\twoheadrightarrow C \right)\Rightarrow \left( A\twoheadrightarrow BC \right)</math>

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

  <math>\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)</math>

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

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

  <math>\left( A\to B \right)\Rightarrow \left( A\twoheadrightarrow B \right)</math>

• Слияние

  <math>\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)</math>

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

• <math>\left( A\twoheadrightarrow B \right)\wedge \left( AB\to C \right)\Rightarrow \left( A\to C\backslash B \right)</math>

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

Применение

Декомпозиция отношений

Теорема Феджина

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

<math>\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)</math>

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

См. также

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

Литература

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

Отрывок, характеризующий Многозначная зависимость

Лицо стало утешать ее; Элен же сквозь слезы говорила (как бы забывшись), что ничто не может мешать ей выйти замуж, что есть примеры (тогда еще мало было примеров, но она назвала Наполеона и других высоких особ), что она никогда не была женою своего мужа, что она была принесена в жертву.
– Но законы, религия… – уже сдаваясь, говорило лицо.
– Законы, религия… На что бы они были выдуманы, ежели бы они не могли сделать этого! – сказала Элен.
Важное лицо было удивлено тем, что такое простое рассуждение могло не приходить ему в голову, и обратилось за советом к святым братьям Общества Иисусова, с которыми оно находилось в близких отношениях.
Через несколько дней после этого, на одном из обворожительных праздников, который давала Элен на своей даче на Каменном острову, ей был представлен немолодой, с белыми как снег волосами и черными блестящими глазами, обворожительный m r de Jobert, un jesuite a robe courte, [г н Жобер, иезуит в коротком платье,] который долго в саду, при свете иллюминации и при звуках музыки, беседовал с Элен о любви к богу, к Христу, к сердцу божьей матери и об утешениях, доставляемых в этой и в будущей жизни единою истинною католическою религией. Элен была тронута, и несколько раз у нее и у m r Jobert в глазах стояли слезы и дрожал голос. Танец, на который кавалер пришел звать Элен, расстроил ее беседу с ее будущим directeur de conscience [блюстителем совести]; но на другой день m r de Jobert пришел один вечером к Элен и с того времени часто стал бывать у нее.
В один день он сводил графиню в католический храм, где она стала на колени перед алтарем, к которому она была подведена. Немолодой обворожительный француз положил ей на голову руки, и, как она сама потом рассказывала, она почувствовала что то вроде дуновения свежего ветра, которое сошло ей в душу. Ей объяснили, что это была la grace [благодать].
Потом ей привели аббата a robe longue [в длинном платье], он исповедовал ее и отпустил ей грехи ее. На другой день ей принесли ящик, в котором было причастие, и оставили ей на дому для употребления. После нескольких дней Элен, к удовольствию своему, узнала, что она теперь вступила в истинную католическую церковь и что на днях сам папа узнает о ней и пришлет ей какую то бумагу.
Все, что делалось за это время вокруг нее и с нею, все это внимание, обращенное на нее столькими умными людьми и выражающееся в таких приятных, утонченных формах, и голубиная чистота, в которой она теперь находилась (она носила все это время белые платья с белыми лентами), – все это доставляло ей удовольствие; но из за этого удовольствия она ни на минуту не упускала своей цели. И как всегда бывает, что в деле хитрости глупый человек проводит более умных, она, поняв, что цель всех этих слов и хлопот состояла преимущественно в том, чтобы, обратив ее в католичество, взять с нее денег в пользу иезуитских учреждений {о чем ей делали намеки), Элен, прежде чем давать деньги, настаивала на том, чтобы над нею произвели те различные операции, которые бы освободили ее от мужа. В ее понятиях значение всякой религии состояло только в том, чтобы при удовлетворении человеческих желаний соблюдать известные приличия. И с этою целью она в одной из своих бесед с духовником настоятельно потребовала от него ответа на вопрос о том, в какой мере ее брак связывает ее.
Они сидели в гостиной у окна. Были сумерки. Из окна пахло цветами. Элен была в белом платье, просвечивающем на плечах и груди. Аббат, хорошо откормленный, а пухлой, гладко бритой бородой, приятным крепким ртом и белыми руками, сложенными кротко на коленях, сидел близко к Элен и с тонкой улыбкой на губах, мирно – восхищенным ее красотою взглядом смотрел изредка на ее лицо и излагал свой взгляд на занимавший их вопрос. Элен беспокойно улыбалась, глядела на его вьющиеся волоса, гладко выбритые чернеющие полные щеки и всякую минуту ждала нового оборота разговора. Но аббат, хотя, очевидно, и наслаждаясь красотой и близостью своей собеседницы, был увлечен мастерством своего дела.
Ход рассуждения руководителя совести был следующий. В неведении значения того, что вы предпринимали, вы дали обет брачной верности человеку, который, с своей стороны, вступив в брак и не веря в религиозное значение брака, совершил кощунство. Брак этот не имел двоякого значения, которое должен он иметь. Но несмотря на то, обет ваш связывал вас. Вы отступили от него. Что вы совершили этим? Peche veniel или peche mortel? [Грех простительный или грех смертный?] Peche veniel, потому что вы без дурного умысла совершили поступок. Ежели вы теперь, с целью иметь детей, вступили бы в новый брак, то грех ваш мог бы быть прощен. Но вопрос опять распадается надвое: первое…
– Но я думаю, – сказала вдруг соскучившаяся Элен с своей обворожительной улыбкой, – что я, вступив в истинную религию, не могу быть связана тем, что наложила на меня ложная религия.
Directeur de conscience [Блюститель совести] был изумлен этим постановленным перед ним с такою простотою Колумбовым яйцом. Он восхищен был неожиданной быстротой успехов своей ученицы, но не мог отказаться от своего трудами умственными построенного здания аргументов.
– Entendons nous, comtesse, [Разберем дело, графиня,] – сказал он с улыбкой и стал опровергать рассуждения своей духовной дочери.


Элен понимала, что дело было очень просто и легко с духовной точки зрения, но что ее руководители делали затруднения только потому, что они опасались, каким образом светская власть посмотрит на это дело.
И вследствие этого Элен решила, что надо было в обществе подготовить это дело. Она вызвала ревность старика вельможи и сказала ему то же, что первому искателю, то есть поставила вопрос так, что единственное средство получить права на нее состояло в том, чтобы жениться на ней. Старое важное лицо первую минуту было так же поражено этим предложением выйти замуж от живого мужа, как и первое молодое лицо; но непоколебимая уверенность Элен в том, что это так же просто и естественно, как и выход девушки замуж, подействовала и на него. Ежели бы заметны были хоть малейшие признаки колебания, стыда или скрытности в самой Элен, то дело бы ее, несомненно, было проиграно; но не только не было этих признаков скрытности и стыда, но, напротив, она с простотой и добродушной наивностью рассказывала своим близким друзьям (а это был весь Петербург), что ей сделали предложение и принц и вельможа и что она любит обоих и боится огорчить того и другого.