Normalformer

Hvis du vet X, vet du Y

En funksjonell avhengighet (FD) er det formelle språket for hvordan attributter «bestemmer» hverandre. Vi skriver X → Y, og leser det «X bestemmer Y» — eller mer presist: hvis to rader er enige om alle attributter i X, så må de også være enige om alle attributter i Y.

Hva FD-er er og ikke er

• FD-en er en regel om alle gyldige instanser, ikke et empirisk faktum om en konkret tabell.
• Det at en konkret instans tilfeldigvis tilfredsstiller en FD, betyr ikke at FD-en holder på skjemaet.
• FD-er kommer fra domenekunnskap: «hver bil har én eier», «hvert rom har én kapasitet i en gitt bygning».

I instansen ovenfor: A → C er tilfredsstilt (begge a₁-rader har c₁; begge a₂-rader har c₂). Derimot er C → A ikke tilfredsstilt: rad 4 og 5 har samme C (c₂) men ulik A (a₂ vs a₃).

Trivielle FD-er

En FD X → Y er triviell hvis Y ⊆ X — den holder for alle instanser uansett. {A, B} → A er triviell. Vi bryr oss bare om ikke-trivielle FD-er.

Tre regler som genererer alle

Gitt en mengde FD-er F, finnes det andre FD-er som må holde som logisk konsekvens. Mengden av alle slike kalles lukningen F⁺. Tre aksiomer er nok til å utlede alle:

Disse aksiomene er sunne (de utleder bare gyldige FD-er) og komplette (alt som er logisk gyldig kan utledes). Tre nyttige avledede regler:

• Union: hvis X → Y og X → Z, så X → Y, Z.
• Dekomposisjon: hvis X → Y, Z, så X → Y og X → Z.
• Pseudotransitivitet: hvis X → Y og W, Y → Z, så W, X → Z.

Hva kan vi utlede?

Algoritmen

1. Initialiser resultat ← X.
2. For hver FD α → β i F: hvis α ⊆ resultat, oppdater resultat ← resultat ∪ β.
3. Gjenta steg 2 til resultat ikke endrer seg.

Hva bruker vi X⁺ til?

• Supernøkkel-test: X er supernøkkel hvis og bare hvis X⁺ = R.
• FD-test: X → Y følger fra F hvis og bare hvis Y ⊆ X⁺.
• Lossless join-test: for binær dekomposisjon R₁, R₂, sjekk om (R₁ ∩ R₂)⁺ ⊇ R₁ eller R₂.

Interaktiv lukningskalkulator

Et lite leksjonseksempel: R(A, B, C, D, E) med F = { A → B, B → C, CD → E, E → A }. Velg attributter for X, og se lukningen utvikle seg trinn for trinn.

Finn alle kandidatnøkler

Algoritme: alle kandidatnøkler

1. Identifiser hvilke attributter aldri er på høyre side i en FD (eller bare i en FD som også har dem på venstre side). De må være med i hver kandidatnøkkel.
2. Identifiser hvilke attributter aldri er på venstre side. De er ikke nødvendige.
3. For de mellomliggende attributtene: prøv minimale supersett av (1) og se om lukningen dekker R.

I R(A,B,C,D,E) med F fra forrige seksjon: D dukker aldri opp på høyre side, så D må være med i hver kandidatnøkkel. {A,B,C,E} er gjensidig avledbare via FD-syklusen A→B→C→A (gjennom CD→E→A). Så kandidatnøklene er {A,D}, {B,D}, {C,D}, {E,D}.

Splitt en relasjon — uten å miste informasjon

Når vi splitter R i to skjemaer R₁ og R₂, vil vi at den naturlige join-en av r₁ og r₂ reproduserer den opprinnelige r nøyaktig. Hvis det er tilfellet, er dekomposisjonen lossless.

Lossless join-testen

For binær dekomposisjon av R i R₁ og R₂, hvor minst én av disse FD-ene gjelder i F⁺:

• R₁ ∩ R₂ → R₁, eller
• R₁ ∩ R₂ → R₂.

Med andre ord: skjæringen må være supernøkkel for minst én av delene.

Eksempel: lossy

R(ID, navn, gate, by, lønn). Vi splitter på navn:

• R₁(ID, navn)
• R₂(navn, gate, by, lønn)

Skjæringen er {navn}. Men «navn» er ikke unikt — to ulike personer kan hete «Kim Hansen». {navn}⁺ = {navn} (ingen FD med navn på venstre side, alene). Ikke supernøkkel for noen av delene → lossy. Etter join får vi krysskobling mellom de to Kim-radene, og kan ikke lenger fortelle hvilken adresse som hører til hvilken Kim.

Eksempel: lossless

R(ID, navn, dept, bygning, budsjett). Vi splitter på dept:

• R₁(ID, navn, dept)
• R₂(dept, bygning, budsjett)

Skjæringen er {dept}. Vi vet at dept → bygning, budsjett, så {dept}⁺ ⊇ R₂. Supernøkkel for R₂ → lossless.

Dependency preservation

Lossless og dependency preserving er uavhengige egenskaper. Ideelt sett vil vi ha begge. Vi kan alltid få lossless. Vi kan ikke alltid få begge samtidig med BCNF — men 3NF garanterer det.

Fra 1NF til BCNF

3NF i ord

For hver ikke-triviell FD α → β som holder, må minst én av:

• α er supernøkkel for R, eller
• hvert attributt i β − α er med i en eller annen kandidatnøkkel for R.

BCNF i ord

For hver ikke-triviell FD α → β som holder, må:

• α er supernøkkel for R.

Det er det. BCNF har bare ett alternativ — det andre alternativet i 3NF er det som åpner for dependency preservation, men også for visse redundanser.

Boyce–Codd normalform

Algoritme: dekomposer R til BCNF

1. Beregn alle FD-er som holder (lukningen F⁺).
2. Finn en ikke-triviell FD α → β hvor α ikke er supernøkkel. Hvis ingen finnes, er R i BCNF — ferdig.
3. Splitt R i R₁ = α ∪ β og R₂ = R − (β − α).
4. Gjenta rekursivt på R₁ og R₂.

Eksempel

InDep(id, navn, lønn, dept, bygning, budsjett) med F = {id → navn, lønn, dept; dept → bygning, budsjett}.

• FD-en dept → bygning, budsjett bryter BCNF: dept er ikke supernøkkel.
• Splitt: α = dept, β = {bygning, budsjett}.
• R₁ = (dept, bygning, budsjett) → kalt Avdeling.
• R₂ = R − (β − α) = (id, navn, lønn, dept) → kalt Larer.

Verifiser: id → navn, lønn, dept har id som supernøkkel. dept → bygning, budsjett har dept som supernøkkel i R₁. Begge tabeller er nå i BCNF.

Helt fra tabell til BCNF

Gitt skjemaet R(prosjektkode, prosjektnavn, ansattnr, navn, timer) der vi registrerer hvor mange timer hver ansatt har jobbet på hvert prosjekt. Krav fra domenet:

• Hvert prosjekt har et unikt navn: prosjektkode → prosjektnavn.
• Hver ansatt har et navn (ikke unikt mellom personer): ansattnr → navn.
• For hver (ansatt, prosjekt) registreres timer: ansattnr, prosjektkode → timer.

Steg 1 · Finn kandidatnøkkel

Hvilke attributter er aldri på høyre side? ansattnr og prosjektkode. De må være med. {ansattnr, prosjektkode}⁺ = {ansattnr, prosjektkode, navn, prosjektnavn, timer} = R. Minimal supernøkkel → kandidatnøkkel.

Steg 2 · Sjekk BCNF

FD-er å sjekke:

1. prosjektkode → prosjektnavn — er {prosjektkode} supernøkkel? {prosjektkode}⁺ = {prosjektkode, prosjektnavn}. Ikke hele R. Bryter BCNF.
2. ansattnr → navn — er {ansattnr} supernøkkel? {ansattnr}⁺ = {ansattnr, navn}. Ikke hele R. Bryter BCNF.
3. ansattnr, prosjektkode → timer — er {ansattnr, prosjektkode} supernøkkel? Ja (det er kandidatnøkkelen). OK.

Steg 3 · Dekomponer

Velg første brudd: prosjektkode → prosjektnavn. Splitt:

• R₁ = {prosjektkode, prosjektnavn} → Prosjekt
• R₂ = R − {prosjektnavn} = {prosjektkode, ansattnr, navn, timer}

R₁ er i BCNF (skjema med to attributter er alltid i BCNF — et nyttig faktum). R₂ må sjekkes videre.

I R₂: ansattnr → navn bryter fortsatt. Splitt:

• R₂ₐ = {ansattnr, navn} → Ansatt
• R₂ᵦ = R₂ − {navn} = {prosjektkode, ansattnr, timer} → Jobber

Begge er nå i BCNF.

Sluttskjema

CREATE TABLE Prosjekt (
  prosjektkode    CHAR(6) PRIMARY KEY,
  prosjektnavn    VARCHAR(100) UNIQUE NOT NULL
);

CREATE TABLE Ansatt (
  ansattnr  INT PRIMARY KEY,
  navn      VARCHAR(80) NOT NULL
);

CREATE TABLE Jobber (
  ansattnr      INT,
  prosjektkode  CHAR(6),
  timer         DECIMAL(5,1) NOT NULL,
  PRIMARY KEY (ansattnr, prosjektkode),
  FOREIGN KEY (ansattnr) REFERENCES Ansatt(ansattnr),
  FOREIGN KEY (prosjektkode) REFERENCES Prosjekt(prosjektkode)
);

Når BCNF koster for mye

Det klassiske eksempelet: dept_advisor(student, lærer, dept) der:

• en lærer er knyttet til nøyaktig ett institutt: lærer → dept
• en student kan ha flere veiledere, men maks én per institutt: student, dept → lærer

Kandidatnøkler: {student, dept} og {student, lærer}. FD-en lærer → dept bryter BCNF (lærer er ikke supernøkkel). Splitt:

• R₁ = (lærer, dept)
• R₂ = (student, lærer)

Begge er i BCNF. Men: FD-en student, dept → lærer kan ikke lenger sjekkes lokalt — student er i R₂, dept er i R₁. Hver gang noen legger til en (student, lærer)-par, må vi joine for å verifisere constrainten.

Oppsummering av kapittel 4