Vícehodnotová závislost

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. června 2019; kontroly vyžadují 2 úpravy .

Vícehodnotová závislost (také MZZ ) je zobecněním konceptu funkční závislosti , široce používaného v teorii databází . V pojetí normálních forem , to je představeno formálně definovat čtvrtou normální formu

Definice

Nechť existuje nějaký vztah se schématem , stejně jako dvě libovolné podmnožiny atributů . Nechte _ $r$ $R$ $A,B\subseteq R$ $C{\overset {\mathop {=} }{\,}}R\zpětné lomítko (A\cup B)$

V tomto případě závisí na , zda a pouze v případě, že množina hodnot atributů odpovídající danému relačnímu páru závisí a nezávisí na . $B$ $A$ $B$ $[a:A;c:C]$ $r$ $A$ $C$

Symbolicky vyjádřeno písmem

A\twoheadrightarrow B

Formálně

{\begin{aligned}&r\left(R\right),\ A,B\subseteq R,\ C=R\backslash (A\cup B)\\&\left(A\twoheadrightarrow B\right )\Šipka doleva \forall {{t}_{1}},{{t}_{2}}\v r\ \existuje {{t}_{3}},{{t}_{4}}\ v 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\vpravo)\\&{{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}}

Vícehodnotová závislost se nazývá triviální , pokud platí alespoň jedna z následujících podmínek: $A\twoheadrightarrow B$

Sada je nadmnožinou ; $A$ $B$ $B\subseteq A$
Union a tvoří celou hlavičku vztahu. $A$ $B$ $A\cup B=R$

Příklad

Předpokládejme, že máme vztah, který zahrnuje seznam akademických oborů, doporučenou literaturu a jména lektorů, kteří vyučují odpovídající kurzy:

Akademické obory

Disciplína	Rezervovat	Přednášející
MatAn	Kudrjavcev	Ivanov A.
MatAn	Fikhtengolts	Petrov B.
MatAn	Kudrjavcev	Petrov B.
MatAn	Fikhtengolts	Ivanov A.
MatAn	Kudrjavcev	Smirnov V.
MatAn	Fikhtengolts	Smirnov V.
VM	Kudrjavcev	Ivanov A.
VM	Kudrjavcev	Petrov B.

Vzhledem k tomu, že lektoři čtoucí předmět a doporučené knihy nejsou na sobě závislé, obsahuje tento vztah mnohohodnotovou závislost. Tento postoj má řadu anomálií. Jedním z nich je, že pokud chceme doporučit novou knihu v kurzu MatAn, budeme muset přidat tolik nových příspěvků, kolik je lektorů v MatAn a naopak.

Formálně existují dvě MZZ: {Disciplína} {Kniha}|{Přednášející} . $\twoheadrightarrow$

Za prvé, je to nadbytečné. A za druhé, pro takový vztah je nutné vyvinout další mechanismus kontroly integrity. Optimálním řešením problému by bylo rozložit vztah na dva s nadpisy {Disciplína, Kniha} a {Disciplína, Přednášející} . Takový rozklad by byl v 4NF . Přípustnost rozkladu je stanovena Faginovou větou (viz níže).

Věty

Spojené páry

Fagin ukázal, že vícehodnotové závislosti tvoří spojené dvojice (v definiční notaci):

\left(A\twoheadrightarrow B\right)\Leftrightarrow \left(A\twoheadrightarrow C\right)

Proto jsou často reprezentovány společně v symbolické notaci:

A\twoheadrightarrow B|C

Funkční závislosti

Jakákoli funkční závislost je vícehodnotová. Jinými slovy, funkční závislost je vícehodnotová závislost, ve které má množina závislých hodnot odpovídajících dané hodnotě determinantu vždy jednotkovou mocninu .

\left(A\to B\right)\Rightarrow \left(A\twoheadrightarrow B\right)

Pravidla výstupu

V roce 1977 Bury, Fagin a Howard zjistili, že Armstrongova inferenční pravidla lze zobecnit a rozšířit na funkční i vícehodnotové závislosti.

Řekněme, že máme vztah a sadu atributů . Pro zkrácení záznamu napíšeme místo toho jednoduše . $r\left(R\right)$ $A,B,C,D\subseteq R$ $X\cup Y$ $XY$

Skupina 1: základní pravidla.

Přidání $\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)$
Tranzitivita $\left(A\twoheadrightarrow B\right)\wedge \left(B\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow C\backslash B\right)$
reflexivita $\left(B\subseteq A\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
Přírůstek $\left(A\twoheadrightarrow B\right)\wedge \left(C\subseteq D\right)\Rightarrow \left(AD\twoheadrightarrow BC\right)$

Skupina 2: Je odvozeno několik dalších pravidel pro zjednodušení úlohy vyvozování vícehodnotových závislostí.

Pseudotranzitivita $\left(A\twoheadrightarrow B\right)\wedge \left(BC\twoheadrightarrow D\right)\Rightarrow \left(AC\twoheadrightarrow D\backslash BC\right)$
Sdružení $\left(A\twoheadrightarrow B\right)\wedge \left(A\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow BC\right)$
Rozklad $\left(A\twoheadrightarrow BC\right)\rightarrow \left(A\dvěheadrightarrow B\cap C\right)\wedge \left(A\twoheadrightarrow B\backslash C\right)\wedge \left(A\ dvě šipka vpravo C\obrácené lomítko B\vpravo)$

Skupina 3: Je vytvořeno spojení mezi funkčními a vícehodnotovými závislostmi.

Replikace (kopie) $\left(A\to B\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
fúze $\left(A\twoheadrightarrow B\right)\wedge \left(C\to D\right)\wedge \left(D\subseteq B\right)\wedge \left(B\cap C=\varnothing \ vpravo)\Šipka doprava \levá(A\do D\vpravo)$

Skupina 4: pro funkční závislosti odvozené z výše uvedených pravidel.

$\left(A\twoheadrightarrow B\right)\wedge \left(AB\to C\right)\Rightarrow \left(A\to C\obrácené lomítko B\vpravo)$

Armstrongova inferenční pravidla spolu s pravidly skupin 1 a 3 zde nastíněnými tvoří úplnou (s jejich pomocí lze odvodit všechny ostatní vícehodnotové závislosti implikované jejich danou množinou) a spolehlivé („extra“ vícehodnotové závislosti nelze odvozená vícehodnotová závislost je platná všude tam, kde je množina vícehodnotových závislostí, ze kterých byla odvozena) sada pravidel pro odvozování vícehodnotových závislostí.

Aplikace

Dekompozice vztahů

Faginova věta

Nechť je dán poměr . Relace se bude rovnat sjednocení svých projekcí právě tehdy , když relace splňuje netriviální vícehodnotovou závislost . $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 )\Šipka doleva \left(A\dvahlavašipka doprava B|C\doprava)

Tato věta je přísnější verzí Heathovy věty .

Viz také

Literatura

K. J. Datum. Úvod do databázových systémů = Introduction to Database Systems. - 8. vyd. - M .: "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .