Moniarvoinen riippuvuus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. kesäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Moniarvoinen riippuvuus (myös MZZ ) on yleistys toiminnallisen riippuvuuden käsitteestä , jota käytetään laajalti tietokantateoriassa . Normaalimuotojen käsitteessä on tarkoitus määritellä muodollisesti neljäs normaalimuoto

Määritelmät

Olkoon jokin suhde skeemaan sekä kaksi mielivaltaista attribuuttien osajoukkoa . Anna . $r$ $R$ $A,B\subseteq R$ $C{\overset {\mathop {=} }{\,}}R\backslash (A\cup B)$

Tässä tapauksessa se riippuu , jos ja vain, jos annettua relaatioparia vastaava attribuuttiarvojen joukko riippuu ja ei riipu . $B$ $A$ $B$ $[a:A;c:C]$ $r$ $a$ $c$

Symbolisesti ilmaistu kirjoittamalla

A\twoheadrightarrow B

Muodollisesti

{\begin{aligned}&r\left(R\right),\ A,B\subseteq R,\ C=R\backslash (A\cup B)\\&\left(A\kaksipääoikeanuoli B\oikea )\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\in r\ \olemassa {{t}_{3}},{{t}_{4}}\ in 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\oikea)\\&{{t}_{4}}\left(B\right)={{t}_{2}}\vasen(B\oikea)\\&{{t}_{ 4}}\left(C\right)={{t}_{1}}\left(C\right)\\\end{aligned}}\right.\\\end{aligned}}

Moniarvoista riippuvuutta kutsutaan triviaaliksi , jos vähintään yksi seuraavista ehdoista on totta: $A\twoheadrightarrow B$

Setti on supersetti ; $A$ $B$ $B\subseteq A$
Unioni ja muodostaa suhteen koko otsikon. $A$ $B$ $A\cup B=R$

Esimerkki

Oletetaan, että meillä on suhde, joka sisältää luettelon akateemisista tieteenaloista, suositeltavasta kirjallisuudesta ja vastaavia kursseja opettavien luennoitsijoiden nimet:

Akateemiset tieteenalat

Kuri	Kirja	Lehtori
MatAn	Kudrjavtsev	Ivanov A.
MatAn	Fikhtengolts	Petrov B.
MatAn	Kudrjavtsev	Petrov B.
MatAn	Fikhtengolts	Ivanov A.
MatAn	Kudrjavtsev	Smirnov V.
MatAn	Fikhtengolts	Smirnov V.
VM	Kudrjavtsev	Ivanov A.
VM	Kudrjavtsev	Petrov B.

Koska aihetta lukevat luennoitsijat ja aiheesta suositellut kirjat eivät ole riippuvaisia toisistaan, tämä suhde sisältää moniarvoisen riippuvuuden. Tässä asenteessa on monia poikkeavuuksia. Yksi niistä on se, että jos haluamme suositella uutta kirjaa MatAn-kurssille, joudumme lisäämään niin monta uutta kirjaa kuin MatAnissa on luennoitsijoita ja päinvastoin.

Muodollisesti MZZ:tä on kaksi: {Discipline} {Book}|{Lecturer} . $\twoheadrightarrow$

Ensinnäkin se on tarpeeton. Ja toiseksi, tällaista suhdetta varten on tarpeen kehittää ylimääräinen eheyden valvontamekanismi. Optimaalinen ratkaisu ongelmaan olisi hajottaa relaatio kahdeksi otsikoilla {Tiete, kirja} ja {Tippi, luennoitsija} . Tällainen hajoaminen olisi 4NF :ssä . Hajoamisen hyväksyttävyys vahvistetaan Faginin lauseella (katso alla).

Lauseet

Yhdistetyt parit

Fagin osoitti, että moniarvoiset riippuvuudet muodostavat yhdistettyjä pareja (määritelmämerkinnöissä):

\left(A\kaksipääoikeanuoli B\oikea)\Leftrightarrow \left(A\kaksipääoikeanuoli C\oikea)

Siksi ne esitetään usein yhdessä symbolisella merkinnällä:

A\twoheadrightarrow B|C

Toiminnalliset riippuvuudet

Mikä tahansa toiminnallinen riippuvuus on moniarvoista. Toisin sanoen toiminnallinen riippuvuus on moniarvoinen riippuvuus, jossa tiettyä determinantin arvoa vastaavalla riippuvaisten arvojen joukolla on aina yksikköteho .

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

Tulostussäännöt

Vuonna 1977 Bury, Fagin ja Howard havaitsivat, että Armstrongin päättelysäännöt voidaan yleistää ja laajentaa koskemaan sekä toiminnallisia että moniarvoisia riippuvuuksia.

Oletetaan, että meillä on relaatio ja joukko attribuutteja . Tietueen lyhentämiseksi kirjoitamme sen sijaan yksinkertaisesti . $r\left(R\right)$ $A,B,C,D\subseteq R$ $X\cup Y$ $XY$

Ryhmä 1: perussäännöt.

Lisäys $\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\kaksipääoikeanuoli C\oikea)\oikea)$
Transitiivisuus $\left(A\kaksipääoikeanuoli B\oikea)\kiila \vasen(B\kaksipääoikeanuoli C\oikea)\Oikeanuoli \vasen(A\kaksipääoikeanuoli C\kenoviiva B\oikea)$
refleksiivisyys $\left(B\subseteq A\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
Lisäys $\left(A\twoheadrightarrow B\right)\wedge \left(C\subseteq D\right)\Rightarrow \left(AD\twoheadrightarrow BC\right)$

Ryhmä 2: Useita lisäsääntöjä johdetaan moniarvoisten riippuvuuksien päättelyn yksinkertaistamiseksi.

Pseudotransitiivisuus $\left(A\kaksipääoikeanuoli B\oikea)\kiila \vasen(BC\kaksipääoikeanuoli D\oikea)\Oikeanuoli \vasen(AC\kaksipääoikeanuoli D\backslash BC\right)$
Yhdistys $\left(A\kaksipääoikeanuoli B\oikea)\kiila \vasen(A\kaksipääoikeanuoli C\oikea)\Oikeanuoli \vasen(A\kaksipääoikeanuoli BC\oikea)$
Hajoaminen $\left(A\kaksipääoikeanuoli BC\oikea)\Oikeanuoli \vasen(A\kaksipääoikeanuoli B\cap C\oikea)\kiila \vasen(A\kaksipääoikeanuoli B\kenoviiva C\oikea)\kiila \vasen(A\ twoheadrightarrow C\backslash B\right)$

Ryhmä 3: Luodaan yhteys toiminnallisten ja moniarvoisten riippuvuuksien välille.

Replikointi (kopio) $\left(A\to B\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
fuusio $\left(A\kaksipääoikeanuoli B\oikea)\kiila \vasen(C\D\oikealle)\kiila \vasen(D\subseteq B\oikea)\kiila \vasen(B\cap C=\varnothing \ oikea)\Oikeanuoli \vasen(A\D\oikealle)$

Ryhmä 4: toiminnallisille riippuvuuksille, johdettu yllä olevista säännöistä.

$\left(A\kaksipääoikeanuoli B\oikea)\kiila \vasen(AB\C\oikealle)\Oikeanuoli \vasen(A\C\kenoviiva B\oikea)$

Armstrongin päättelysäännöt yhdessä tässä hahmoteltujen ryhmien 1 ja 3 sääntöjen kanssa muodostavat täydellisen (niitä käyttämällä voidaan johtaa kaikki muut moniarvoiset riippuvuudet, jotka niiden annettu joukko merkitsee) ja luotettavan ("ylimääräisiä" moniarvoisia riippuvuuksia ei voi johdettu moniarvoinen riippuvuus on voimassa missä tahansa moniarvoisten riippuvuuksien joukko, josta se on johdettu) sääntöjoukko moniarvoisten riippuvuuksien päättelemiseksi.

Sovellus

Suhteen hajoaminen

Faginin lause

Olkoon suhde annettu . Relaatio on yhtä suuri kuin sen projektioiden liitto, jos ja vain jos relaatio täyttää ei-triviaalin moniarvoisen riippuvuuden . $r\left(A,B,C\oikea)$ $r$ $r\left[A,B\oikea]$ $r\left[A,C\oikea]$ $r$ $A\twoheadrightarrow B|C$

\left(r\left(A,B,C\right)=r\left[A,B\oikea]\ {\teksti{JOIN))\ r\left[A,C\oikea]\oikea )\Leftrightarrow \left(A\kaksipääoikeanuoli B|C\oikea)

Tämä lause on tiukempi versio Heathin lauseesta .

Katso myös

Kirjallisuus

K. J. Päivämäärä. Johdatus tietokantajärjestelmiin = Tietokantajärjestelmien esittely. - 8. painos - M . : "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .