Závislost s více hodnotami - Multivalued dependency

Podle teorie databáze, a více hodnot závislost je úplné omezení mezi dvěma sadami atributů v a vztah.

Na rozdíl od funkční závislost, vícehodnotová závislost vyžaduje to jisté n-tice být ve vztahu. Proto je vícehodnotová závislost zvláštním případem závislost generující n-tici. Závislost s více hodnotami hraje roli v Normalizace databáze 4NF.

Závislost s více hodnotami je speciální případ a připojit závislost, pouze s dvěma sadami hodnot, tj. jde o závislost binárního spojení.

Závislost s více hodnotami existuje, když existují alespoň tři atributy (jako X, Y a Z) v a vztah a pro hodnotu X existuje dobře definovaná množina hodnot Y a dobře definovaná množina hodnot Z. Sada hodnot Y je však nezávislá na množině Z a naopak.

Formální definice

Formální definice je uvedena následovně. ^[1]

Nechat ${displaystyle R}$ být relační schéma a nechte ${displaystyle alpha subseteq R}$ a ${displaystyle eta subseteq R}$ (podmnožiny). Závislost s více hodnotami
${displaystyle alpha woheadrightarrow eta}$
(který lze číst jako ${displaystyle alpha}$ multidetermines ${displaystyle eta}$) drží ${displaystyle R}$ pokud v jakémkoli právním vztahu ${displaystyle r (R)}$, pro všechny páry n-tic ${displaystyle t_ {1}}$ a ${displaystyle t_ {2}}$ v ${displaystyle r}$ takhle ${displaystyle t_ {1} [alfa] = t_ {2} [alfa]}$, existují n-tice ${displaystyle t_ {3}}$ a ${displaystyle t_ {4}}$ v ${displaystyle r}$ takhle
${displaystyle {egin {matrix} t_ {1} [alfa] = t_ {2} [alfa] = t_ {3} [alfa] = t_ {4} [alfa] t_ {1} [eta] = t_ {3 } [eta] t_ {2} [eta] = t_ {4} [eta] t_ {1} [Rsetminus (alfa pohár eta)] = t_ {4} [Rsetminus (alfa pohár eta)] t_ {2 } [Rsetminus (alfa pohár eta)] = t_ {3} [Rsetminus (alfa pohár eta)] konec {matice}}}$

Jednoduššími slovy lze výše uvedenou podmínku vyjádřit takto: označujeme-li pomocí ${displaystyle (x, y, z)}$ n-tice s hodnotami pro ${displaystyle alpha,}$ ${displaystyle eta,}$ ${displaystyle R-alfa - eta}$ kolektivně rovno ${displaystyle x,}$ ${displaystyle y,}$ ${displaystyle z,}$ odpovídajícím způsobem, pak kdykoli n-tice ${displaystyle (a, b, c)}$ a ${displaystyle (a, d, e)}$ existuje v ${displaystyle r}$, n-tice ${displaystyle (a, b, e)}$ a ${displaystyle (a, d, c)}$ by měl existovat také v ${displaystyle r}$.

Příklad

Zvažte tento příklad vztahu univerzitních kurzů, knih doporučených pro tento kurz a lektorů, kteří budou kurz vyučovat:

Protože lektoři připojeni ke kurzu a knihy připojené ke kurzu jsou navzájem nezávislé, má tento návrh databáze vícehodnotovou závislost; pokud bychom do kurzu AHA přidali novou knihu, museli bychom přidat jeden záznam pro každého z lektorů tohoto kurzu a naopak.
Formálně řečeno, v tomto vztahu existují dvě vícehodnotové závislosti: {course}${displaystyle woheadrightarrow}$ {book} a ekvivalentně {samozřejmě}${displaystyle woheadrightarrow}$ {přednášející}.
Databáze s vícehodnotovými závislostmi tak vykazují nadbytečnost. v normalizace databáze, čtvrtá normální forma to vyžaduje pro každou netriviální závislost s více hodnotami X ${displaystyle woheadrightarrow}$ Y, X je superklíč. Závislost s více hodnotami X ${displaystyle woheadrightarrow}$ Y je triviální, pokud Y je podmnožinou X, nebo když ${displaystyle Xcup Y}$ je celá sada atributů relace.

Vlastnosti

• Li ${displaystyle alpha woheadrightarrow eta}$, Pak ${displaystyle alpha woheadrightarrow R- eta}$
• Li ${displaystyle alpha woheadrightarrow eta}$ a ${displaystyle gamma subseteq delta}$, Pak ${displaystyle alfa delta woheadrightarrow eta gamma}$
• Li ${displaystyle alpha woheadrightarrow eta}$ a ${displaystyle eta woheadrightarrow gamma}$, pak ${displaystyle alpha woheadrightarrow gamma - eta}$

Následující zahrnuje také funkční závislosti:

• Li ${displaystyle alpha ightarrow eta}$, pak ${displaystyle alpha woheadrightarrow eta}$
• Li ${displaystyle alpha woheadrightarrow eta}$ a ${displaystyle eta ightarrow gamma}$, pak ${displaystyle alpha woheadrightarrow gamma - eta}$

Výše uvedená pravidla jsou spolehlivá a úplná.

• Rozklad R do (X, Y) a (X, R − Y) je bezztrátový rozklad kdyby a jen kdyby X ${displaystyle woheadrightarrow}$ Y drží seR.
• Každý FD je MVD protože pokud X ${displaystyle ightarrow}$ Y a potom přepínání Y mezi n-ticemi, které se shodují na X, nevytvoří nové n-tice.
• Rozdělení nedrží. Stejně jako FD nemůžeme obecně rozdělit levou stranu MVD. Ale na rozdíl od FD nemůžeme rozdělit ani pravou stranu, někdy musíte nechat několik atributů na pravé straně.
• Uzavření sady MVD je sada všech MVD, které lze odvodit pomocí následujících pravidel (Armstrongovy axiomy ):
  • Doplnění: Pokud X ${displaystyle woheadrightarrow}$ Y, pak X ${displaystyle woheadrightarrow}$ R - Y
  • Augmentace: Pokud X ${displaystyle woheadrightarrow}$ Y a Z. ${displaystyle subseteq}$ W, pak XW ${displaystyle woheadrightarrow}$ YZ
  • Přechodnost: Pokud X ${displaystyle woheadrightarrow}$ Y a Y. ${displaystyle woheadrightarrow}$Z, pak X ${displaystyle woheadrightarrow}$ Z Y
  • Replikace: Pokud X ${displaystyle ightarrow}$ Y, pak X ${displaystyle woheadrightarrow}$ Y
  • Srůstání: Pokud X ${displaystyle woheadrightarrow}$Y a ${displaystyle existuje}$ W s.t. Ž ${displaystyle cap}$ Y = ${displaystyle emptyset}$, Ž ${displaystyle ightarrow}$ Z a Z ${displaystyle subseteq}$ Y, pak X ${displaystyle ightarrow}$ Z

Definice

plné omezení

Omezení, které něco vyjadřuje Všechno atributy v databázi. (Na rozdíl od vložené omezení.) Závislost s více hodnotami je a plné omezení vyplývá z jeho definice, jako kde to říká něco o atributech ${displaystyle R- eta}$.

závislost generující n-tici

Závislost, která výslovně vyžaduje přítomnost určitých n-tic ve vztahu.

triviální vícehodnotová závislost 1

Závislost s více hodnotami, která zahrnuje všechny atributy relace, tj.${displaystyle R = alfa cup eta}$. Triviální závislost s více hodnotami znamená pro n-tice ${displaystyle t_ {1}}$ a ${displaystyle t_ {2}}$, n-tice ${displaystyle t_ {3}}$ a ${displaystyle t_ {4}}$ které se rovnají ${displaystyle t_ {1}}$ a ${displaystyle t_ {2}}$.

triviální vícehodnotová závislost 2

Závislost s více hodnotami ${displaystyle eta subseteq alpha}$.

Reference

externí odkazy

• Závislosti s více hodnotami a nový normální formulář pro relační databáze (PDF) - Ronald Fagin, IBM Research Lab
• O struktuře Armstrongových vztahů pro funkční závislosti (PDF) - CATRIEL BEERI (Hebrejská univerzita), MARTIN DOWD (Rutgersova univerzita), RONALD FAGIN (IBM Research Laboratory) A RICHARD STATMAN (Rutgersova univerzita)
• K problému Fagina týkajícího se vícehodnotových závislostí v relačních databázích (PDF) - Sven Hartmann, Massey University