Flervärdigt beroende

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 juni 2019; kontroller kräver 2 redigeringar .

Flervärdigt beroende (även MZZ ) är en generalisering av begreppet funktionellt beroende , flitigt använt i databasteorin . I begreppet normala former introduceras det för att formellt definiera den fjärde normalformen

Definitioner

Låt det finnas något samband med schemat , såväl som två godtyckliga delmängder av attribut . Låt . $r$ $R$ $A,B\subseteq R$ $C{\overset {\mathop {=} }{\,}}R\backslash (A\cup B)$

I det här fallet beror det på , om och bara om uppsättningen av attributvärden som motsvarar det givna relationsparet beror på och inte beror på . $B$ $A$ $B$ $[a:A;c:C]$ $r$ $a$ $c$

Symboliskt uttryckt genom att skriva

A\twoheadrightarrow B

Formellt

{\begin{aligned}&r\left(R\right),\ A,B\subseteq R,\ C=R\backslash (A\cup B)\\&\left(A\twoheadrightarrow B\right )\Leftrightarrow \forall {{t}_{1}},{{t}_{2}}\i r\ \exists {{t}_{3}},{{t}_{4}}\ i 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\ höger)={{t}_{1}}\left(B\right)\\&{{t}_{3}}\left(C\right)={{t}_{2}}\left (C\right)\\&{{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}}

Ett flervärdigt beroende kallas trivialt om minst ett av följande villkor är sant: $A\twoheadrightarrow B$

Uppsättningen är en superset ; $A$ $B$ $B\subseteq A$
Union och utgör hela rubriken i relationen. $A$ $B$ $A\cup B=R$

Exempel

Anta att vi har ett förhållande som inkluderar en lista över akademiska discipliner, rekommenderad litteratur och namnen på föreläsare som undervisar i motsvarande kurser:

Akademiska discipliner

Disciplin	bok	Föreläsare
MatAn	Kudryavtsev	Ivanov A.
MatAn	Fikhtengolts	Petrov B.
MatAn	Kudryavtsev	Petrov B.
MatAn	Fikhtengolts	Ivanov A.
MatAn	Kudryavtsev	Smirnov V.
MatAn	Fikhtengolts	Smirnov V.
VM	Kudryavtsev	Ivanov A.
VM	Kudryavtsev	Petrov B.

Eftersom föreläsarna som läser ämnet och de böcker som rekommenderas i ämnet inte är beroende av varandra, innehåller denna relation ett mångvärdigt beroende. Denna inställning har ett antal anomalier. En av dem är att om vi vill rekommendera en ny bok i en MatAn-kurs så måste vi lägga till lika många nya bidrag som det finns föreläsare i MatAn och vice versa.

Formellt finns det två MZZ: {Discipline} {Book}|{Lektor} . $\twoheadrightarrow$

För det första är det överflödigt. Och för det andra, för en sådan relation är det nödvändigt att utveckla en ytterligare integritetskontrollmekanism. Den optimala lösningen på problemet skulle vara att dela upp relationen i två med rubrikerna {Discipline, Book} och {Discipline, Lecturer} . En sådan nedbrytning skulle vara i 4NF . Tillåtligheten av nedbrytning fastställs av Fagins teorem (se nedan).

Satser

Anslutna par

Fagin visade att beroenden med flera värden bildar kopplade par (i definitionsnotation):

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

Därför representeras de ofta tillsammans i symbolisk notation:

A\twoheadrightarrow B|C

Funktionella beroenden

Varje funktionellt beroende är flervärdigt. Med andra ord, ett funktionellt beroende är ett flervärdigt beroende där uppsättningen av beroende värden som motsvarar ett givet värde på determinanten alltid har enhetseffekt .

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

Utdataregler

År 1977 fann Bury, Fagin och Howard att Armstrongs slutledningsregler kan generaliseras och utvidgas till både funktionella och flervärdiga beroenden.

Låt oss säga att vi har en relation och en uppsättning attribut . För att förkorta posten skriver vi helt enkelt istället . $r\left(R\right)$ $A,B,C,D\subseteq R$ $X\cup Y$ $XY$

Grupp 1: grundläggande regler.

Tillägg $\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)$
Transitivitet $\left(A\twoheadrightarrow B\right)\wedge \left(B\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow C\backslash B\right)$
reflexivitet $\left(B\subseteq A\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
Ökning $\left(A\twoheadrightarrow B\right)\wedge \left(C\subseteq D\right)\Rightarrow \left(AD\twoheadrightarrow BC\right)$

Grupp 2: Flera ytterligare regler härleds för att förenkla uppgiften att sluta sig till flervärdiga beroenden.

Pseudotransitivitet $\left(A\twoheadrightarrow B\right)\wedge \left(BC\twoheadrightarrow D\right)\Rightarrow \left(AC\twoheadrightarrow D\backslash BC\right)$
En förening $\left(A\twoheadrightarrow B\right)\wedge \left(A\twoheadrightarrow C\right)\Rightarrow \left(A\twoheadrightarrow BC\right)$
Sönderfall $\left(A\twoheadrightarrow BC\right)\Rightarrow \left(A\twoheadrightarrow B\cap C\right)\wedge \left(A\twoheadrightarrow B\backslash C\right)\wedge \left(A\ twoheadrightarrow C\backslash B\right)$

Grupp 3: En koppling upprättas mellan funktionella och flervärdiga beroenden.

Replikering (kopia) $\left(A\to B\right)\Rightarrow \left(A\twoheadrightarrow B\right)$
fusion $\left(A\twoheadrightarrow B\right)\wedge \left(C\to D\right)\wedge \left(D\subseteq B\right)\wedge \left(B\cap C=\varnothing \ höger)\högerpil \vänster(A\till D\höger)$

Grupp 4: för funktionella beroenden, härledd från reglerna ovan.

$\left(A\twoheadrightarrow B\right)\wedge \left(AB\to C\right)\Rightarrow \left(A\to C\backslash B\right)$

Armstrongs slutledningsregler, tillsammans med reglerna för grupperna 1 och 3 som beskrivs här, bildar en komplett (med hjälp av dem kan man härleda alla andra flervärdiga beroenden som antyds av deras givna uppsättning) och tillförlitliga (”extra” flervärdiga beroenden kan inte vara det härledda multi-värdiga beroendet är giltigt varhelst uppsättningen multi-värderade beroenden som det härleddes från) en uppsättning regler för att sluta sig till multi-värderade beroenden.

Applikation

Relationsupplösning

Fagins sats

Låt förhållandet anges . En relation kommer att vara lika med föreningen av dess projektioner om och endast om relationen uppfyller ett icke-trivialt flervärdigt beroende . $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\höger]\höger )\Leftrightarrow \left(A\twoheadrightarrow B|C\right)

Denna sats är en striktare version av Heaths sats .

Se även

Litteratur

K. J. Date. Introduktion till databassystem = Introduktion till databassystem. - 8:e uppl. - M . : "Williams" , 2006. - S. 1328. - ISBN 0-321-19784-4 .