IN2090-ukesoppgaver: Uke 8
Normalformer og tapsfri dekomposisjon
Oppgave 1
Følgende relasjon bryter med 2NF:
EksamensResultat(emnekode, studentId, semester, emnenavn, karakter)
hvor emnekode
bestemmer emnenavn
;
primærnøkkel er {emnekode, studentId, semester}
.
- Forklar hvorfor denne relasjonen ikke oppfyller 2NF.
- Dekomponer tapsfritt til BCNF.
Løsningsforslag
a.
FDen emnekode → emnenavn
bryter med BNCF ettersom
emnekode
ikke er en supernøkkel. Videre bryter den med 3NF
siden emnenavn
ikke er en nøkkelattributt. Den bryter også
2NF siden emnekode
er en del av en kandidatnøkkel.
b.
Vi dekomponerer med hensyn på FDen emnekode → emnenavn
og finner at emnekode^+ = {emnekode, emnenavn}
, og får
da:
S1(emnekode, emnenavn)
S2(emnekode, studentId, semester, karakter)
Begge disse er på BCNF.
Oppgave 2
Følgende relasjon bryter med 2NF: R(A, B, C, D, E, F)
med følgende FD-er:
B,C → D
E → F
- Hvorfor bryter denne med 2NF?
- Dekomponer relasjonen til BCNF.
Løsningsforslag
a.
De attributtene som aldri forekommer på noen høyreside i FDene er
A, B, C, E
, så alle disse må være med i alle
kandidatnøkler. Det er enkelt å se at disse faktisk utgjør (den eneste)
kandidatnøkkelen.
Vi ser så at FDen B,C → D
bryter med BNCF fordi
B, C
ikke er en supernøkkel, den bryter med 3NF fordi
D
ikke er et nøkkelattributt, og den bryter med 2NF fordi
B, C
er en del av en kandidatnøkkel.
b.
Vi starter med å dekomponere mhp. B,C → D
og finner at
{B, C}⁺ = {B, C, D}
og får:
S1(B, C, D)
S2(B, C, A, E, F)
Vi ser at S1
er på BCNF siden kun første FD holder for
den, og den har da eneste kandidatnøkkel {B, C}
.
S2
derimot har FDen E → F
, hvor
E
ikke er en supernøkkel og dermed bryter med BCNF. Vi
dekomponerer derfor mhp. denne hvor E⁺ = {E, F}
og får:
S21(E, F)
S22(E, B, C, A)
Det er enkelt å se at begge disse er på BNCF, ettersom den øverste kun har én FD, mens den nederste ikke har noen.
Oppgave 3
Vi har relasjonen:
Timeliste(ansattnr, uke, år, navn, antTimer)
hvor
ansattnr
bestemmer navn
og
{ansattnr, uke år}
er eneste kandidatnøkkel.
- Hvilke funksjonelle avhengigheter har relasjonen?
- Tilfredsstiller denne relasjonen 2NF? Hvorfor/hvorfor ikke?
Løsningsforslag
a.
Vi har kun ansattnr → navn
og
ansattnr, uke, år → antTimer
.
b.
Ettersom relasjonen har et attributt navn
som avhenger
av kun deler av en kandidatnøkkel (ansattnr → navn
)
tilfredstiller den ikke 2NF.
Oppgave 4
Vi har relasjonen:
Ordre(ordre, kundenr, kundenavn, antall, sum, mva)
hvor
kundenummer
bestemmer kundenavn
,
mva
-verdien er alltid 25% av sum
og
ordre
er eneste kandidatnøkkel.
- Hvilke funksjonelle avhengigheter har relasjonen?
- Hvilken normalform har relasjonen?
Løsningsforslag
a.
ordre → kundenr, kundenavn, antall, sum, mva
kundenr → kundenavn
mva → sum
sum → mva
b.
Første FD bryter ikke med BNCF. Andre FD bryter med BCNF siden
kundenr
ikke er en supernøkkel; den bryter også med 3NF
siden kundenavn
ikke er en nøkkelattributt; men bryter ikke
med 2NF siden kundenr
ikke er en del av en kandidatnøkkel.
Det samme gjelder for de to siste FDene også.
Altså er relasjonen på 2NF.
Oppgave 5 (fra eksamen 2015)
I denne oppgaven skal vi bruke følgende relasjon:
Filmgenre(filmid, title, prodyear, genre)
Primærnøkkelen i
tabellen er kombinasjonen av filmid
og genre
;
altså {filmid, genre}
. Videre vet vi også at
filmid
bestemmer både tittel
og
produksjonsår
for en film.
- Bestem alle supernøklene i relasjonen
Filmgenre
. Skriv ned alle. - Bestem alle FD-ene i relasjonen
Filmgenre
. - Hvilken normalform er relasjonen
Filmgenre
på? Begrunn svaret ditt.
Løsningsforslag
a.
Det er enkelt å se at primærnøkkelen er den eneste kandidatnøkkelen.
Altså vil alle mengder attributter som inneholder filmid
og
genre
være en supernøkkel, altså:
{filmid, genre}
{filmid, genre, title}
{filmid, genre, prodyear}
{filmid, genre, title, prodyear}
b.
Vi får følgende FDer:
filmid → title, prodyear
Merk at primærnøkkelen også gir oss FDen
filmid, genre → title, prodyear
men denne er bare en triviell utvidelse av FDen over, og trenger derfor ikke listes opp.
c.
Vi må først skrive FDen om til følgende FDer:
filmid → title
filmid → prodyear
Den første FDen bryter med BNCF siden filmid
ikke er en
supernøkkel; den bryter med 3NF siden title
ikke er en
nøkkelattributt; og den bryter med 2NF siden filmid
er en
del av en kandidatnøkkel.
Altså er Filmgenre
på 1NF.