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

Согласно теории баз данных , многозначная зависимость - это полное ограничение между двумя наборами атрибутов в отношении .

В отличие от функциональной зависимости , многозначная зависимость требует, чтобы в отношении присутствовали определенные кортежи . Следовательно, многозначная зависимость - это частный случай зависимости, порождающей кортежи . Многозначная зависимость играет роль в нормализации базы данных 4NF .

Многозначная зависимость - это частный случай зависимости соединения , в котором задействованы только два набора значений, т. Е. Это зависимость двоичного соединения.

Многозначное зависимость существует тогда , когда существует по меньшей мере три атрибута (например , X, Y и Z) в отношении и для величины X существует четко определенный набор значений Y и хорошо определенный набор значений Z. Однако, набор значений Y не зависит от набора Z и наоборот.

Формальное определение [ править ]

Формальное определение дается следующим образом. ^[1]

Позвольте быть реляционной схемой и пусть и быть наборами атрибутов. Многозначная зависимость (которая может быть прочитана как multidetermines ) сохраняется, если в любом правовом отношении для всех пар кортежей и в таком случае существуют кортежи и в таком, что${\ displaystyle R}$${\displaystyle \alpha \subseteq R}$${\displaystyle \beta \subseteq R}$
${\displaystyle \alpha \twoheadrightarrow \beta }$
${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle R}$${\displaystyle r(R)}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle r}$${\displaystyle t_{1}[\alpha ]=t_{2}[\alpha ]}$${\displaystyle t_{3}}$${\displaystyle t_{4}}$${\displaystyle r}$
${\displaystyle {\begin{matrix}t_{1}[\alpha ]=t_{2}[\alpha ]=t_{3}[\alpha ]=t_{4}[\alpha ]\\t_{1}[\beta ]=t_{3}[\beta ]\\t_{2}[\beta ]=t_{4}[\beta ]\\t_{1}[R\setminus (\alpha \cup \beta )]=t_{4}[R\setminus (\alpha \cup \beta )]\\t_{2}[R\setminus (\alpha \cup \beta )]=t_{3}[R\setminus (\alpha \cup \beta )]\end{matrix}}}$

Проще говоря, вышеуказанное условие может быть выражено следующим образом: если мы обозначим кортежем, имеющим значения для в совокупности равные соответственно, то всякий раз, когда кортежи и существуют в , кортежи и также должны существовать в .${\displaystyle (x,y,z)}$${\displaystyle \alpha ,}$ ${\displaystyle \beta ,}$ ${\displaystyle R-\alpha -\beta }$${\displaystyle x,}$ ${\displaystyle y,}$ ${\displaystyle z,}$${\displaystyle (a,b,c)}$${\displaystyle (a,d,e)}$${\displaystyle r}$${\displaystyle (a,b,e)}$${\displaystyle (a,d,c)}$${\displaystyle r}$

Пример [ править ]

Рассмотрим этот пример связи университетских курсов, книг, рекомендованных для курса, и преподавателей, которые будут вести курс:

Поскольку преподаватели, прикрепленные к курсу, и книги, прикрепленные к курсу, не зависят друг от друга, этот дизайн базы данных имеет многозначную зависимость; если бы мы добавили новую книгу к курсу AHA, нам пришлось бы добавить по одной записи для каждого лектора этого курса, и наоборот.
Формально, в этом отношении есть две многозначные зависимости: {course}   {book} и эквивалентно {course}   {lecturer}. Таким образом, базы данных с многозначными зависимостями демонстрируют избыточность. В нормализации баз данных , четвёртая нормальная форма требует , чтобы для каждого нетривиальная многозначная зависимость X Y , X является суперключ . Многозначная зависимость${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$
 ${\displaystyle \twoheadrightarrow }$ X Y тривиально, если Y - подмножество X , или если это весь набор атрибутов отношения.${\displaystyle \twoheadrightarrow }$ ${\displaystyle X\cup Y}$

Свойства [ править ]

• Если , то${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \alpha \twoheadrightarrow R-\beta }$
• Если и , то${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \gamma \subseteq \delta }$${\displaystyle \alpha \delta \twoheadrightarrow \beta \gamma }$
• Если и , то${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \beta \twoheadrightarrow \gamma }$${\displaystyle \alpha \twoheadrightarrow \gamma -\beta }$

Следующее также включает функциональные зависимости :

• Если , то${\displaystyle \alpha \rightarrow \beta }$${\displaystyle \alpha \twoheadrightarrow \beta }$
• Если и , то${\displaystyle \alpha \twoheadrightarrow \beta }$${\displaystyle \beta \rightarrow \gamma }$${\displaystyle \alpha \twoheadrightarrow \gamma -\beta }$

Приведенные выше правила полны и полны.

• Разложение R в ( X ,  Y ) и ( X ,  R  -  Y ) является без потерь присоединиться разложение тогда и только тогда , когда Х  Y имеет место в  R .${\displaystyle \twoheadrightarrow }$ 
• Каждый FD является MVD, потому что если X Y, то замена Y между кортежами, которые согласуются с X, не создает новых кортежей.${\displaystyle \rightarrow }$
• Расщепление не выполняется. Как и у FD, мы не можем разделить левую часть MVD, но, в отличие от FD, мы не можем разделить и правую часть, иногда вам нужно оставить несколько атрибутов на правой стороне.
• Замыкание набора МВД - это набор всех МВД, которые могут быть выведены с использованием следующих правил ( аксиомы Армстронга ):
  • Дополнение : Если X Y, то X R - Y${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$
  • Увеличение : если X Y и Z W, то XW YZ${\displaystyle \twoheadrightarrow }$${\displaystyle \subseteq }$${\displaystyle \twoheadrightarrow }$
  • Транзитивность : если X Y и Y Z, то X Z - Y${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$${\displaystyle \twoheadrightarrow }$
  • Репликация : если X Y, то X Y${\displaystyle \rightarrow }$${\displaystyle \twoheadrightarrow }$
  • Слияние : если X Y и W st W Y = , W Z и Z Y, то X Z${\displaystyle \twoheadrightarrow }$${\displaystyle \exists }$${\displaystyle \cap }$${\displaystyle \emptyset }$${\displaystyle \rightarrow }$${\displaystyle \subseteq }$${\displaystyle \rightarrow }$

Определения [ править ]

полное ограничение

Ограничение, которое что-то выражает обо всех атрибутах в базе данных. (В отличие от встроенного ограничения .) То, что многозначная зависимость является полным ограничением, следует из его определения, где что-то говорится об атрибутах .${\displaystyle R-\beta }$

зависимость, генерирующая кортежи

Зависимость, которая явно требует наличия в отношении определенных кортежей.

тривиальная многозначная зависимость 1

Многозначное зависимость , которая включает в себя все атрибуты отношения т . Простейшее многозначное зависимость подразумевает, для кортежей и , кортежей и которые равны и .${\displaystyle R=\alpha \cup \beta }$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{3}}$${\displaystyle t_{4}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$

тривиальная многозначная зависимость 2

Многозначная зависимость, для которой .${\displaystyle \beta \subseteq \alpha }$

Ссылки [ править ]

Внешние ссылки [ править ]

• Многозначные зависимости и новая нормальная форма для реляционных баз данных (PDF) - Рональд Фэджин, IBM Research Lab
• О структуре отношений Армстронга для функциональных зависимостей (PDF) - CATRIEL BEERI (Еврейский университет), MARTIN DOWD (Rutgers University), RONALD FAGIN (Исследовательская лаборатория IBM) И RICHARD STATMAN (Rutgers University)
• К проблеме Феджина о многозначных зависимостях в реляционных базах данных (PDF) - Свен Хартманн, Университет Мэсси