Fjerde normalform

Fjerde normalform (4NF) er en normalform som brukes i databasenormalisering, og ansees som det neste normaliseringsnivået etter Boyce-Codd normalform (BCNF). Mens normalformene 2NF, 3NF og BCNF er opptatt av funksjonelle avhengigheter er 4NF opptatt av en mer generell type avhengighet kjent som en flervaluert avhengighet.

Historie

Fjerde normalform ble introdusert i 1977 av Ronald Fagin.^[1]^[2] Rissanens teorem er også anvendelig på flervaluerte avhengigheter.

Definisjon

En tabell er på 4NF hvis og bare hvis X er en supernøkkel for hver av dens ikke-trivielle flervaluert avhengighet X $\twoheadrightarrow$ Y, altså at X enten er en kandidatnøkkel eller et overmengde derav.^[3]

Flervaluerte avhengigheter

Hvis kolonnenavnene i en relasjonsdatabasetabell er delt inn i tre disjunkte mengder X, Y og Z kan man i forbindelse med en bestemt rad referere til dataene under hver kolonne som henholdsvis x, y og z. En flervaluert avhengighet X $\twoheadrightarrow$ Y betyr at at hvis vi velger en hvilken som helst x som faktisk forekommer i tabellen (kall dette valget x_c), og kompilerer en liste over alle kombinasjonene x_cyz som forekommer i tabellen vil vi finne at x_c er assosiert med samme y-oppføringer uavhengig av z. Dermed gir tilstedeværelsen av z ingen nyttig informasjon for å begrense de mulige verdiene til y.

En triviell flervaluert avhengighet X $\twoheadrightarrow$ Y er en der enten Y er en delmengde av X, eller X og Y sammen danner hele mengden attributter til relasjonen.

En funksjonell avhengighet er et spesielt tilfelle av flervaluert avhengighet. I en funksjonell avhengighet X → Y bestemmer hver x eksakt én y, og aldri mer enn én.

Eksempel

Anta følgende eksempel:

Permutasjoner for pizzalevering
Restaurant	Pizzatype	Leveringsområde
Elgsnes pizzeria	Tykk skorpe	Grønnebakkan
Elgsnes pizzeria	Tykk skorpe	Gansås
Elgsnes pizzeria	Tykk skorpe	Bergseng
Elgsnes pizzeria	Fylt skorpe	Grønnebakkan
Elgsnes pizzeria	Fylt skorpe	Gansås
Elgsnes pizzeria	Fylt skorpe	Bergseng
Elite pizza	Tynn skorpe	Bergseng
Elite pizza	Fylt skorpe	Bergseng
Hårek pizzeria	Tykk skorpe	Grønnebakkan
Hårek pizzeria	Tykk skorpe	Gansås
Hårek pizzeria	Tynn skorpe	Grønnebakkan
Hårek pizzeria	Tynn skorpe	Gansås

Hver rad indikerer at en gitt restaurant kan levere et gitt utvalg av pizza til et gitt område.

Tabellen har ingen ikke-nøkkelattributter fordi den eneste kandidatnøkkelen er {Restaurant, pizzatype, leveringsområde}. Derfor tilfredsstiller den alle normalformer opp til BCNF.

Hvis vi imidlertid antar at pizzatyper som tilbys av en restaurant ikke påvirkes av leveringsområdet (altså at en restaurant tilbyr alle pizzatyper den lager til alle områder den leverer) så vil ikke tabellen oppfylle 4NF. Problemet er at tabellen inneholder to ikke-trivielle flervaluerte avhengigheter på {Restaurant}-attributtet (som ikke er en supernøkkel). Avhengighetene er:

{Restaurant} $\twoheadrightarrow$ {Pizzatype}
{Restaurant} $\twoheadrightarrow$ {Leveringsområde}

Disse ikke-trivielle flervaluerte avhengighetene av en ikke-supernøkkel reflekterer faktumet at variantene av pizza en restaurant tilbyr er uavhengig av områdene restauranten leverer til. Denne tilstanden fører til redundans i tabellen. For eksempel blir vi fortalt tre ganger at Elgsnes pizzeria tilbyr fylt skorpe, og hvis Elgsnes pizzeria begynner å produsere pizzaer med osteskorper må vi legge til flere rader; altså en for hver av Elgsnes pizzeria sine leveringsområder. Det er dessuten ingenting som hindrer oss i å gjøre dette feil: Vi kan legge til rader med osteskorpe for alle unntatt ett av Elgsnes pizzeria sine leveringsområder, og dermed unnlate å respektere den flervaluerte avhengigheten {Restaurant} $\twoheadrightarrow$ {Pizzatype}.

For å eliminere muligheten for disse uregelmessighetene må fakta om varianter som tilbys plasseres i en annen tabell enn faktaene om leveringsområde, hvilket gir to tabeller som begge er på 4NF:

Typer etter restaurant
Restaurant	Pizzatype
Elgsnes pizzeria	Tykk skorpe
Elgsnes pizzeria	Fylt skorpe
Elite pizza	Tynn skorpe
Elite pizza	Fylt skorpe
Hårek pizzeria	Tykk skorpe
Hårek pizzeria	Tynn skorpe

Leveringsområde etter restaurant
Restaurant	Leveringsområde
Elgsnes pizzeria	Grønnebakkan
Elgsnes pizzeria	Gansås
Elgsnes pizzeria	Bergseng
Elite pizza	Bergseng
Hårek pizzeria	Grønnebakkan
Hårek pizzeria	Gansås

Til motsetning: Dersom det faktisk stemmer at pizzatypene som tilbys av en restaurant noen ganger legitimt varierer fra et leveringsområde til et annet ville den originale tre-kolonnede tabellen tilfredsstilt 4NF.

4NF i praksis

I en artikkel fra 1992 av Margaret S. Wu ble det bemerket at undervisning i databasenormalisering vanligvis stopper før man kommer til 4NF, muligens på grunn av en oppfatning av at tabeller som bryter 4NF (men oppfyller alle lavere normale former) sjelden oppstår i forretningsapplikasjoner. Denne oppfatningen er kanskje ikke korrekt. Ifølge Wu resulterte en studie av 40 organisasjonsdatabaser i at over 20% inneholdt en eller flere tabeller som krenket 4NF, mens de tilfredsstilte alle lavere normalformer.^[4]

Normalisering utover 4NF

Bare i sjeldne situasjoner samsvarer ikke en 4NF-tabell med den høyere normalformen 5NF. Dette er situasjoner der en kompleks begrensning fra den virkelige verden styrer de gyldige kombinasjonene av attributtverdier i 4NF-tabellen ikke er implisitt i strukturen til den tabellen.

Se også

Referanser

^ Fagin, Ronald (1. september 1977). «Multivalued dependencies and a new normal form for relational databases». ACM Transactions on Database Systems. 3. 2: 262–278. ISSN 0362-5915. doi:10.1145/320557.320571. Besøkt 26. mars 2024.
^ Fagin, p. 268
^ "A relation schema R* is in fourth normal form (4NF) if, whenever a nontrivial multivalued dependency X $\twoheadrightarrow$ Y holds for R*, then so does the functional dependency X → A for every column name A of R*. Intuitively all dependencies are the result of keys." Fagin, Ronald (September 1977). «Multivalued Dependencies and a New Normal Form for Relational Databases» (PDF). ACM Transactions on Database Systems. 2 (1): 262–278. doi:10.1145/320557.320571. Arkivert fra originalen (PDF) 29. november 2007. Besøkt 26. mars 2024.
^ Wu, Margaret S. (mars 1992). «The Practical Need for Fourth Normal Form». ACM SIGCSE Bulletin. 24 (1): 19–23. doi:10.1145/135250.134515.

[1] Fagin, Ronald (1. september 1977). «Multivalued dependencies and a new normal form for relational databases». ACM Transactions on Database Systems. 3. 2: 262–278. ISSN 0362-5915. doi:10.1145/320557.320571. Besøkt 26. mars 2024.

[Fagin268-2] Fagin, p. 268

[Fagin-3] "A relation schema R* is in fourth normal form (4NF) if, whenever a nontrivial multivalued dependency X $\twoheadrightarrow$ Y holds for R*, then so does the functional dependency X → A for every column name A of R*. Intuitively all dependencies are the result of keys." Fagin, Ronald (September 1977). «Multivalued Dependencies and a New Normal Form for Relational Databases» (PDF). ACM Transactions on Database Systems. 2 (1): 262–278. doi:10.1145/320557.320571. Arkivert fra originalen (PDF) 29. november 2007. Besøkt 26. mars 2024.

[Wu-4] Wu, Margaret S. (mars 1992). «The Practical Need for Fourth Normal Form». ACM SIGCSE Bulletin. 24 (1): 19–23. doi:10.1145/135250.134515.

[1]

[2]

[3]

[4]

v d r Databasenormalisering
Unormalisert form (0NF) Første normalform (1NF) Andre normalform (2NF) Tredje normalform (3NF) Elementærnøkkel normalform (EKNF) Boyce–Codd normalform (3.5NF / BCNF) Fjerde normalform (4NF) Femte normalform (5NF / PJNF) Domene–nøkkel normalform (DKNF) Sjette normalform (6NF)
Avhengigheter Funksjonell avhengighet Flervaluert avhengighet Skjøteavhengighet Tapsfri dekomposisjon Temporal database Gyldigtid Transaksjonstid Beslutningstid
Denormalisering