Flervaluert avhengighet

I databaseteori er en flervaluert avhengighet en full begrensning mellom to datamengder med attributter i en relasjon.

I motsetning til funksjonell avhengighet krever flervaluert avhengighet at visse tupler er til stede i en relasjon. Derfor er en flervaluert avhengighet et spesielt tilfelle av tuppelgenererende avhengighet. Flervaluert avhengighet spiller en rolle i fjerde normalform.

En flervaluert avhengighet er et spesialtilfelle av en skjøteavhengighet hvor bare to mengder med verdier involvert, altså er det en binær skjøteavhengighet.

En flervaluert avhengighet eksisterer når det er minst tre attributter (som X, Y og Z) i en relasjon og for en verdi av X er det en veldefinert mengde verdier av Y og en veldefinert mengde verdier av Z. Imidlertid er mengden verdier i Y uavhengig av mengden Z og omvendt.

Formell definisjon

Den formelle definisjonen er som følger:

La $R$ være en relasjon og la $\alpha \subseteq R$ og $\beta \subseteq R$ være mengden med attributter. Den flervaluerte avhengigheten $\alpha \twoheadrightarrow \beta$ ($\alpha$ "multibestemmer" $\beta$) holder i $R$ hvis, for enhver lovlige relasjon $r(R)$ og alle par av tupler $t_1$ og $t_2$ i $r$ slik at $t_1[\alpha ]=t_2[\alpha ]$, så finnes det tupler $t_3$ og $t_4$ i $r$ slik at:

$\begin{array}{cccc}\text{tuppel}& \alpha & \beta & R\setminus (\alpha \cup \beta )\\ t_1& a_1..a_n& b_1..b_m& d_1..d_k\\ t_2& a_1..a_n& c_1..c_m& e_1..e_k\\ t_3& a_1..a_n& b_1..b_m& e_1..e_k\\ t_4& a_1..a_n& c_1..c_m& d_1..d_k\end{array}$

Uformelt, hvis man angir ved $(x,y,z)$ tuppelen som har verdier for $\alpha ,$$\beta ,$$R-\alpha -\beta$ kollektivt lik med $x,$$y,$$z$, så bør det hver gang tuplene $(a,b,c)$ og $(a,d,e)$ eksisterer i $r$ være slik at tuplene $(a,b,e)$ og $(a,d,c)$ også eksistere i $r$.

Flervaluert avhengighet kan skjematisk fremstilles som vist nedenfor:

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

Eksempel

Anta eksempelet under med en relasjon mellom universitetsfag, anbefalte bøker for faget og foreleseren som skal undervise:

Universitetsfag

Kurs	Bok	Foreleser
AHA	Sørensen	Marius U
AHA	Moen	Marius U
AHA	Sørensen	Inger M
AHA	Moen	Inger M
AHA	Sørensen	Øyvind G
AHA	Moen	Øyvind G
OSO	Sørensen	Marius U
OSO	Sørensen	Inger M

Fordi foreleseren knyttet til kurset og bøkene knyttet til kurset er uavhengige av hverandre har dette databasedesignet en flervaluert avhengighet. Hvis man skulle legge til en ny bok til AHA-faget måtte det legges til en rad for hver av foreleserne i det faget, og omvendt. Formelt sett er det to flervaluerte avhengigheter i denne relasjonen: {kurs} $\twoheadrightarrow$ {bok} og tilsvarende {kurs} $\twoheadrightarrow$ {foreleser}. Databaser med flervaluerte avhengigheter har dermed redundans. I databasenormalisering krever fjerde normalform at X er en supernøkkel for hver ikke-trivielle flervaluerte avhengighet X $\twoheadrightarrow$ Y. En flervaluert avhengighet X $\twoheadrightarrow$ Y er triviell hvis Y er en delmengde av X, eller hvis $X\cup Y$ er hele mengden av attributter til relasjonen.

Egenskaper

• Hvis $\alpha \twoheadrightarrow \beta$, så $\alpha \twoheadrightarrow R-\beta$
• Hvis $\alpha \twoheadrightarrow \beta$ og $\gamma \subseteq \delta$, så $\alpha \delta \twoheadrightarrow \beta \gamma$
• Hvis $\alpha \twoheadrightarrow \beta$ og $\beta \twoheadrightarrow \gamma$, så $\alpha \twoheadrightarrow \gamma -\beta$

Følgende involverer også funksjonelle avhengigheter:

• Hvis $\alpha \to \beta$, så $\alpha \twoheadrightarrow \beta$
• Hvis $\alpha \twoheadrightarrow \beta$ og $\beta \to \gamma$, så $\alpha \twoheadrightarrow \gamma -\beta$

Reglene ovenfor er komplette og korrekte.

• En dekomponering av R til (X, Y) og (X, R − Y) er en trapsfri skjøte-dekomposisjon hvis og bare hvis X $\twoheadrightarrow$ Y holder i R.
• Hver funksjonelle avhengighet er en flervaluert avhengighet fordi hvis X $\to$ Y, så vil bytting av Y-er mellom tuplene som er enige om X ikke skape nye tupler.
• Splitting holder ikke: Lik som for funksjonelle avhengigheter kan man ikke generelt splitte venstre side av en flervaluert avheighghet. Men ulikt en funksjonell avhengighet kan vi ikke splitte høyre side heller, og noen ganger må man beholde flere attributter på høyre side.
• Overdekking av en mengde av flervaluerte avhengigheter er mengden av alle flervaluerte avhengigheter som kan infereres ved å bruke følgende regler (Armstrongs aksiomer):
  • Komplementering: Hvis X $\twoheadrightarrow$ Y, så X $\twoheadrightarrow$ R - Y
  • Utvidelse: Hvis X $\twoheadrightarrow$ Y og Z $\subseteq$ W, så XW $\twoheadrightarrow$ YZ
  • Transitivitet: Hvis X $\twoheadrightarrow$ Y og Y $\twoheadrightarrow$Z, så X $\twoheadrightarrow$ Z - Y
  • Replikering: Hvis X $\to$ Y, så X $\twoheadrightarrow$ Y
  • Koalisering: Hvis X $\twoheadrightarrow$Y and $\mathrm{\exists }$ W slik at W $\cap$ Y = $\mathrm{\varnothing }$, W $\to$ Z, og Z $\subseteq$ Y, så X $\to$ Z

Definisjoner

Full begrensning

En begrensning som uttrykker noe om alle attributter i en database. (I motsetning til en innebygd begrensning.) At en flervaluert avhengighet er en full begrensning følger av dens definisjon, som hvor den sier noe om attributtene $R-\beta$.

Tuppelgenererende avhengighet

En avhengighet som eksplisitt krever at visse tupler er tilstede i relasjonen.

Triviell flervaluert avhengighet 1

En flervaluert avhengighet som involverer alle egenskapene til en relasjon, altså $R=\alpha \cup \beta$. En triviell avhengighet med flere verdier innebærer, for tupler $t_1$ og $t_2$, at det er tupler $t_3$ og $t_4$ som er lik $t_1$ og $t_2$.

Triviell flervaluert avhengighet 2

En flervaluert avhengighet som $\beta \subseteq \alpha$ .