Funktionellt beroende (programmering)

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

Funktionellt beroende är ett binärt förhållande mellan uppsättningar av attribut för en given relation och är i själva verket en en-till-många-relation. Dess användning beror på det faktum att det tillåter dig att formellt och strikt lösa många problem.

Funktionellt beroende är ett koncept som ligger till grund för många frågor relaterade till relationsdatabaser , inklusive i synnerhet deras design.

Definitioner

Funktionellt beroende

Låt en relation ges med ett schema (header) , och vara några delmängder av relationens attributuppsättning . En uppsättning är funktionellt beroende av om och endast om varje värde i uppsättningen är associerat med exakt ett värde av uppsättningen . Utsedda . $r$ $R$ $A$ $B$ $r$ $B$ $A$ $A$ $B$ $A till B$

Med andra ord, om två tupler har samma värde i , då har de samma värde i . $A$ $B$

r\left(R\right),\ A\subseteq R,\ B\subseteq R

\left(A\to B\right)\Leftrightarrow \left(\left(\forall {{t}_{1}},{{t}_{2}}\in r:{{t} _{1}}\left(A\right)={{t}_{2}}\left(A\right)\right)\Rightarrow \left({{t}_{1}}\left(B \right)={{t}_{2}}\left(B\right)\right)\right)

I det här fallet är determinanten den beroende delen. $A$ $B$

Ett funktionellt beroende sägs vara trivialt om den beroende delen är en delmängd av determinanten.

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

Stänga en uppsättning beroenden

Vissa funktionella beroenden kan innebära andra funktionella beroenden. Till exempel funktionellt beroende,

\left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)

Uppsättningen av alla funktionella beroenden som impliceras av en given uppsättning av funktionella beroenden kallas stängningen av uppsättningen . ${{S}^{+}}$ $S$ $S$

Attributuppsättning stängning

Låt vara en uppsättning av attribut för relationen , och vara uppsättningen av funktionella beroenden av denna relation. Stängningen av uppsättningen attribut inom gränserna är en sådan uppsättning av alla attribut i relationen att det funktionella beroendet är en medlem av stängningen . $Z$ $r$ $S$ ${{Z}^{+}}$ $Z$ $S$ ${{A}_{i))$ $r$ $Z\to {{A}_{i))$ ${{S}^{+}}$

r\left(R\right),\ S,\ Z\subseteq R,\ {{A}_{i}}\subseteq R,\ i={\overline {1,n}}

{{Z}^{+}}=\left\{{{A}_{i}}:\left(Z\to {{A}_{i}}\right)\in {{S }^{+}}\right\}

Oreducerbara uppsättningar av beroenden

Låt och vara några uppsättningar av funktionella beroenden. ${{S}_{1}}$ ${{S}_{2))$

Om något funktionellt beroende från går in och in , så kallas omslaget för uppsättningen funktionella beroenden . ${{S}_{1}}$ ${{S}_{2}^{+}}$ ${{S}_{2))$ ${{S}_{1}}$
Om är en täckning för , och är en täckning för (det vill säga ), så kallas sådana uppsättningar likvärdiga . ${{S}_{2))$ ${{S}_{1}}$ ${{S}_{1}}$ ${{S}_{2))$ ${\displaystyle S_{1}^{+}=S_{2}^{+))$
En uppsättning funktionella beroenden sägs vara irreducerbara om och endast om följande villkor är uppfyllda: $S$
- I varje funktionellt beroende innehåller den beroende delen endast ett element;
- Determinanten för varje funktionellt beroende är irreducerbar (inget attribut kan tas bort från determinanten utan att ändra stängningen ); ${{S}^{+}}$
- Inget av de funktionella beroenden från kan elimineras utan att ändra förslutningen . $S$ ${{S}^{+}}$
För varje uppsättning funktionella beroenden finns det minst en ekvivalent uppsättning som är irreducerbar. En sådan likvärdig uppsättning kallas ett irreducible cover .

Stängningsutvärdering

Armstrongs slutledningsregler

1974 föreslog William Armstrong en uppsättning regler för att sluta sig till nya funktionella beroenden från data.

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$

Reflexivitet : $\left(B\subseteq A\right)\Rightarrow \left(A\to B\right)$
Påfyllning : $\left(A\to B\right)\Rightarrow \left(AC\to BC\right)$
Transitivitet : $\left(A\to B\right)\wedge \left(B\to C\right)\Rightarrow \left(A\to C\right)$

Armstrongs slutledningsregler är kompletta (med hjälp av dem kan man härleda alla andra funktionella beroenden som impliceras av den givna mängden) och tillförlitliga ("överflödiga" funktionella beroenden kan inte härledas: det härledda funktionella beroendet är giltigt var de ursprungliga funktionella beroenden än var (från vilka det var härledda) är giltiga).

Dessutom härleds flera ytterligare regler helt enkelt från dessa regler, vilket förenklar uppgiften att härleda funktionella beroenden.

Självbestämmande : $A\to A$
Nedbrytning : $\left(A\to BC\right)\Rightarrow \left(A\to B\right)\wedge \left(A\to C\right)$
Konsolidering : $\left(A\to B\right)\wedge \left(A\to C\right)\Rightarrow \left(A\to BC\right)$
Komposition : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(AC\to BD\right)$
Darwens universella föreningssats : $\left(A\to B\right)\wedge \left(C\to D\right)\Rightarrow \left(A\cup \left(CB\right)\to BD\right)$

Teorem: Ett funktionellt beroende härleds från en given uppsättning funktionella beroenden enligt Armstrongs slutledningsregler om och endast om . $A till B$ $S$ $B\subseteq {{A}^{+}}$

Attributuppsättning stängning

Om vi tillämpar reglerna från föregående avsnitt tills skapandet av nya funktionella beroenden stoppar av sig själv, får vi en stängning för en given uppsättning funktionella beroenden. I praktiken är det sällan nödvändigt att beräkna denna stängning av sig själv, oftast är vi mycket mer intresserade av att veta om det eller det funktionella beroendet kommer att ingå i stängningen. För att göra detta räcker det för oss att beräkna stängningen av determinanten. Det finns en ganska enkel algoritm för detta.

Låt vara en uppsättning attribut som så småningom kommer att bli en stängning. $X$
Vi söker efter funktionella beroenden av formen , var och . Vi lägger till den beroende delen av varje hittat beroende till . ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\to C$ ${{B}_{1}}{{B}_{2}}\ldots {{B}_{m}}\subseteq X$ $C\not \subset X$ $X$
Upprepa steg 2 tills det är omöjligt att lägga till attribut till uppsättningen. $X$
En uppsättning som inga attribut kan läggas till kommer att vara en stängning. $X$

Applikation

Databasdesign

Funktionella beroenden är integritetsbegränsningar och definierar semantiken för data som lagras i databasen. Med varje uppdatering måste DBMS kontrollera deras överensstämmelse. Därför är närvaron av ett stort antal funktionella beroenden oönskad, annars saktar det ner arbetet. För att förenkla uppgiften är det nödvändigt att minska uppsättningen funktionella beroenden till det minimum som krävs.

Om är en irreducerbar täckning av den initiala uppsättningen av funktionella beroenden , då en kontroll av uppfyllandet av funktionella beroenden från garanterar automatiskt uppfyllandet av alla funktionella beroenden från . Således reduceras uppgiften att hitta den minsta nödvändiga uppsättningen till att hitta en irreducerbar täckning av uppsättningen funktionella beroenden, som kommer att användas istället för den ursprungliga uppsättningen. $jag$ $S$ $jag$ $S$

Se även

Relationsdatamodell
Databasdesign
normal form
Flervärdigt beroende är en generalisering av funktionellt beroende.

Litteratur

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