Funksjonell avhengighet

I relasjonsdatabaser er en funksjonell avhengighet en begrensning mellom to mengder med attributter i en relasjon fra en database. Med andre ord er en funksjonell avhengighet en begrensning mellom to attributter i en relasjon. Gitt en relasjon R og mengde med attributter $X,Y\subseteq R$, sies X å funksjonelt bestemme Y (skrevet X → Y) hvis og bare hvis hver X-verdi i R er assosiert med nøyaktig én Y-verdi i R; R sies da å tilfredsstille den funksjonelle avhengigheten X → Y. Tilsvarende er projeksjonen $\Pi _{X,Y}R$ en funksjon, altså at Y er en funksjon av X. Sagt med enkle ord: Hvis verdiene for X-attributtene er kjente (si at de er x) så kan verdiene for Y-attributtene som tilsvarer x bestemmes ved å slå dem opp i en hvilken som helst tuppel av R som inneholder x. Vanligvis kalles X determinantmengden og Y den avhengige mengden. En funksjonell avhengighet FD: X → Y kalles triviell hvis Y er en delmengde av X.

Med andre ord betyr en avhengighet FD: X → Y at verdiene til Y bestemmes av verdiene til X. To tupler som deler de samme verdiene av X vil nødvendigvis ha de samme verdiene av Y.

Bestemmelse av funksjonelle avhengigheter er viktig i utforming av databaser i relasjonsmodellen, og i databasenormalisering og denormalisering. En enkel anvendelse av funksjonelle avhengigheter er Heaths teorem som sier at en relasjon R over en attributtmengde U og som tilfredsstiller en funksjonell avhengighet X → Y trygt kan deles i to relasjoner som har tapsfri skjøte-dekomposisjon til $\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)=R$ hvor Z = U − XY er resten av attributtene. (Unioner av attributtmengder stilles vanligvis opp ved siden av hverandre i databaseteori.) Et viktig element i denne sammenhengen er en kandidatnøkkel definert som en minimalt mengde attributter som funksjonelt bestemmer alle attributtene i en relasjon. De funksjonelle avhengighetene, sammen med attributtdomenenet, velges slik at man genererer begrensninger som vil ekskludere så mye data som er upassende for brukerdomenet fra systemet som mulig.

En type logisk implikasjon er definert for funksjonelle avhengigheter på følgende måte: En mengde funksjonelle avhengigheter $\Sigma$ (sigma) impliserer logisk en annen mengde avhengigheter $\Gamma$ (gamma) hvis de finnes en relasjon R som tilfredsstiller alle avhengigheter fra $\Sigma$ som også tilfredsstiller alle avhengigheter fra $\Gamma$; dette skrives vanligvis som $\Sigma \models \Gamma$. En slik logisk implikasjon for funksjonelle avhengigheter medfører en korrekt og komplett aksiomatisering kjent som Armstrongs aksiomer.

Eksempler

Biler

Anta at man designer et system for å spore kjøretøy og størrelsen på motorene deres. Hvert kjøretøy har et unikt rammenummer (VIN). Man kan da skrive VIN → engine_capacity fordi det ville være upassende for et kjøretøys motor å ha flere enn én størrelse. (Forutsatt at kjøretøy bare har én motor.) På den andre siden er engine_capacity → VIN feil fordi det kan være mange kjøretøy med samme motorstørrelse.

Denne funksjonelle avhengigheten kan foreslå at attributtet engine_capacity plasseres i en relasjon med kandidatnøkkelen VIN, men det er kanskje ikke alltid hensiktsmessig. For eksempel hvis den funksjonelle avhengigheten oppstår som et resultat av de transitive funksjonelle avhengighetene VIN → vehicle_model og vehicle_model → engine_capacity så vil det ikke resultere i en normalisert relasjon.

Forelesninger

Dette eksemplet illustrerer konseptet funksjonell avhengighet. Situasjonen som modelleres er at studenter besøker en eller flere forelesninger hvor de får tildelt en lærlæringsassistent. Anta videre at hver student befinner seg i et semester, og identifiseres med en unik heltalls-ID.

Student-ID	Semester	Forelesning	Læringsassistent
1234	6	Numeriske metoder	Emil
1221	4	Numeriske metoder	Emma
1234	6	Visuell databehandling	Oskar
1201	2	Numeriske metoder	Olivia
1201	2	Fysikk II	Simon

Legg merke til at når to rader i denne tabellen har samme Student-ID så har de også nødvendigvis de samme semester-verdi. Dette grunnleggende faktumet kan uttrykkes som en funksjonell avhengighet:

• Student-ID → Semester.

Dersom det ble lagt til en rad hvor studenten hadde en annen verdi for semester så ville ikke lenger den funksjonelle avhengigheten eksistert. Dette betyr at den funksjonelle avhengigheten antydes av dataene da det er mulig å ha verdier som vil ugyldiggjøre den funksjonelle avhengigheten.

Andre ikke-trivielle funksjonelle avhengigheter kan identifiseres, for eksempel:

• {Student-ID, Forelesning} → Læringsassistent
• {Student-ID, Forelesning} → {Læringsassistent, Semester}

Sistnevnte uttrykker det faktum at mengden {StudentID, Forelesning} er en supernøkkel av relasjonen.

Ansattes avdeling

Et klassisk eksempel på funksjonell avhengighet er hvilken avdeling arbeidere er ansatt i.

Ansatt-ID	Ansattes navn	Avdelings-ID	Avdelingsnavn
0001	Ola Nordmann	1	Personaladministrasjon
0002	Kari Nordmann	2	Markedsføring
0003	Ola Andersen	1	Personaladministrasjon
0004	Kari Jonsen	3	Salg

I dette eksempel er det flere funksjonelle avhengigheter innebygd i en enkelt representasjon av data. Merk at fordi en ansatt bare kan være medlem av én avdeling så vil den ansattes unike ID bestemme avdelingen.

• Ansatt-ID → Ansattnavn
• Ansatt-ID → Avdelings-ID

I tillegg til denne relasjonen har tabellen også en funksjonell avhengighet gjennom et ikke-nøkkelattributt

• Avdelings-ID → Avdelingsnavn

Dette eksemplet viser at selv om det finnes en funksjonell avhengighet Ansatt-ID → Avdelings-ID så vil ikke ansatt-ID være en logisk nøkkel for å bestemme avdelingsnavnet. I en prosess med normalisering av dataene vil man gjenkjenne alle funksjonelle avhengigheter, og tillate designeren å konstruere tabeller og relasjoner som er mer logiske basert på dataene.

Egenskaper og aksiomatisering av funksjonelle avhengigheter

Gitt at X, Y og Z er mengder med attributter i en relasjon R kan man utlede flere egenskaper av funksjonelle avhengigheter. Blant de viktigste er følgende, vanligvis kalt Armstrongs aksiomer:

• Refleksivitet: Hvis Y er en delmengde av X, så X → Y
• Utvidelse: Hvis X → Y, så XZ → YZ
• Transitivitet: Hvis X → Y og Y → Z, så X → Z

Refleksivitet kan svekkes til bare $X\rightarrow \varnothing$, altså at det er et faktisk aksiom, mens de to andre er anstendige slutningsregler, hvilket mer presist gir opphav til følgende regler for syntaktisk konsekvens:

$\vdash X\rightarrow \varnothing$$X\rightarrow Y\vdash XZ\rightarrow YZ$$X\rightarrow Y,Y\rightarrow Z\vdash X\rightarrow Z$

Disse tre reglene er en korrekt og komplett aksiomatisering av funksjonelle avhengigheter. Denne aksiomatiseringen beskrives noen ganger som endelig fordi antallet slutningsregler er endelig, med forbehold om at aksiomet og slutningsreglene alle er skjemaer, som betyr at X, Y og Z spenner over alle grunnledd (attributtmengder).

Ved å bruke utvidelse og transitivitet kan man utlede to tilleggsregler:

• Pseudotransitivitet: Hvis X → Y og YW → Z, så XW → Z
• Komposisjon: Hvis X → Y og Z → W, så XZ → YW

Man kan også utlede union- og dekomposisjonsreglene fra Armstrongs aksiomer:

X → Y og X → Z hvis og bare hvis X → YZ

Tillukking av funksjonell avhengighet

Tillukkingen er i hovedsak hele mengden verdier som kan bestemmes fra en mengde med kjente verdier for en gitt relasjon ved å bruke dets funksjonelle avhengigheter. Man bruker Armstrongs aksiomer for å gi et bevis, alså refleksivitet, utvidelse og transitivitet.

Gitt $R$ og $F$ vil en mengde funksjonelle avhengigheter som holder i $R$: Tillukninen av $F$ i $R$ (notert $F$⁺) er mengden av alle funksjonelle avhengigheter som logisk impliseres av $F$.

Tillukking av en mengde med attributter

Tillukking av en mengde attributter X med hensyn på $F$ er mengden X⁺ av alle attributter som er funksjonelt bestemt av X ved hjelp av $F$⁺.

Eksempel

Anta følgende liste over funksjonelle avhengigheter, og at det skal beregnes en tillukking for A fra denne relasjonen:

1. A → B
2. B → C
3. AB → D

Tillukkingen vil være som følger:

1. A → A (av Armstrongs refleksivitet)
2. A → AB (av 1. og (a))
3. A → ABD (av (b), 3 og Armstrongs transitivitet)
4. A → ABCD (av (c) og 2)

Tillukkingen er derfor A → ABCD. Ved å beregne tillukkingen av A har vi validert at A også er en god kandidatnøkkel da tillukkingen er hver enkelt dataverdi er i relasjonen.

Overdekking og ekvivalens

Ikke-redundante overdekker

Definisjon: $F$ overdekker $G$ hvis hver funksjonelle avhengighet i $G$ kan utledes av $F$. $F$ dekker $G$ hvis $G$⁺ ⊆ $F$⁺. Hver mengde av funksjonelle avhengigheter har en kanonisk overdekking.

Ekvivalens av to mengder med funksjonelle avhengigheter

To mengder med funksjonelle avhengigheter $F$ og $G$ over skjemaet $R$ er ekvivalente, som noteres $F$ ≡ $G$, hvis $F$⁺ = $G$⁺. Dersom $F$ ≡ $G$ vil $F$ overdekke for $G$ og vice versa. Med andre ord kalles ekvivalente mengder med funksjonelle avhengigheter for overdekker av hverandre.

Ikke-redundante overdekker

En mengde $F$ av funksjonelle avhengigheter er ikke-redundant hvis det ikke er en ekte delmengde $F'$ av $F$ med $F'$ ≡ $F$. Hvis en slik $F'$ eksisterer er $F$ redundant. $F$ er ikke-redundant overdekke for $G$ hvis $F$ er overdekke for $G$ og $F$ er ikke-redundant.En alternativ karakterisering av ikke-redundans er at $F$ er ikke-redundant hvis det er ingen funksjonelle avhengigheter X → Y i $F$ slik at $F$ - {X → Y} $\models$ X → Y. En funksjonell avhengighet X → Y i $F$ er redundant i $F$ hvis $F$ - {X → Y} $\models$ X → Y.

Bruksområder for normalisering

Heaths teorem

En viktig egenskap (som gir en umiddelbar anvendelse) av funksjonelle avhengigheter er at hvis R er en relasjon med kolonner navngitt fra en mengde attributter U og R tilfredsstiller en funksjonell avhengighet X → Y så er $R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)$ hvor Z = U − XY. Intuitivt, hvis en funksjonell avhengighet X → Y holder i R, kan relasjonen trygt deles i to relasjoner ved siden av kolonnen X (som er en nøkkel for $\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)$ ) som sikrer at når de to delene skjøtes sammen tilbake går ingen data tapt. Altså vil en funksjonell avhengighet gi en enkel måte å konstruere en tapsfri skjøte-dekomponering av R i to mindre relasjoner. Dette faktumet kalles noen ganger Heaths teorem, og er et av de tidlige resultatene innen databaseteori.

Heaths teorem sier effektivt at man kan trekke ut verdiene til Y fra den store relasjonen R og lagre dem i en, altså $\Pi _{XY}(R)$, som ikke har noen verdirepetisjoner i raden for X og er effektivt en oppslagstabell for Y tastet av X og som følgelig bare gir ett sted å oppdatere Y som tilsvarer hver X i motsetning til den "store" relasjonen R hvor det er potensielt mange kopier av hver X, hver med sin kopi av Y som må holdes synkronisert ved oppdateringer. (Denne elimineringen av redundans er en fordel i OLTP-kontekster hvor mange endringer forventes, men ikke så mye i OLAP-kontekster som hovedsakelig involverer spørringer.) Heaths dekomponering etterlater bare X som fungerer som en fremmednøkkel i resten av den store tabellen $\Pi _{XZ}(R)$.

Funksjonelle avhengigheter bør imidlertid ikke forveksles med inklusjonsavhengigheter som er formalismen for fremmednøkler: Selv om de brukes til normalisering så uttrykker funksjonelle avhengigheter begrensninger over en relasjon (skjema), mens inklusjonsavhengigheter uttrykker begrensninger mellom relasjonsskjemaer i et databaseskjema. Videre krysser de to konseptene ikke engang i klassifiseringen av avhengigheter: Funksjonelle avhengigheter er likhetsgenererende avhengigheter, mens inklusjonsavhengigheter er tuppelgenererende avhengigheter. Å håndheve referansebegrensninger etter dekomponering av relasjonsskjema (normalisering) krever en ny formalisme, altså inklusjonsavhengigheter. I dekomponeringen som følger av Heaths teorem er det ingenting som hindrer at innsetting av tupler i $\Pi _{XZ}(R)$ har en verdi av X som ikke finnes i $\Pi _{XY}(R)$.

Normalformer

Normalformer er nivåer av databasenormalisering som bestemmer "godheten" til en tabell. Vanligvis anses tredje normalform for å være en "god" standard for en relasjonsdatabaser.^{[trenger referanse]}

Normalisering tar sikte på å frigjøre databasen fra avvik forårsaket av oppdatering, innsetting og sletting. Den sikrer også at en ny verdi som introduseres i relasjonen vil ha minimal effekt på databasen, og dermed minimal effekt på applikasjonene som bruker databasen.^{[trenger referanse]}

Mengder avhengig av irredusible funksjoner

En mengde S med funksjonelle avhengigheter er irredusibel hvis mengden har følgende tre egenskaper:

1. Hver høyremengde av en funksjonell avhengighet av S inneholder bare ett attributt.
2. Hver venstremengde av en funksjonell avhengighet av S er irreduserbar. Dette betyr at å redusere et attributt fra venstre mengde vil endre innholdet i S (S vil miste noe informasjon).
3. Å redusere funksjonell avhengighet vil endre innholdet i S.

Mengder med funksjonelle avhengigheter med disse egenskapene kalles også kanoniske eller minimale. Å finne et slikt mengde S med funksjonelle avhengigheter som tilsvarer en inngangsmengde S' gitt som innputt kalles å finne et minimalt overdekke av S'. Dette problemet kan løses i polynomtid.

Se også

• Chase-algoritmen
• Inklusjonsavhengighet
• Skjøteavhengighet
• Flervaluert avhengighet
• Databasenormalisering
• Første normalform