Redigerer Fjerde normalform

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

== Historie ==
Fjerde normalform ble introdusert i 1977 av Ronald Fagin.<ref>{{Kilde artikkel|tittel=Multivalued dependencies and a new normal form for relational databases|publikasjon=ACM Transactions on Database Systems|doi=10.1145/320557.320571|url=https://dl.acm.org/doi/10.1145/320557.320571|dato=1977-09-01|fornavn=Ronald|etternavn=Fagin|serie=3|bind=2|sider=262–278|issn=0362-5915|besøksdato=2024-03-26}}</ref><ref name="Fagin268">Fagin, p. 268</ref> [[Rissanen's theorem|Rissanens teorem]] er også anvendelig på [[Multivaluert avhengighet|flervaluerte avhengigheter]].

== Definisjon ==
En [[Tabell (database)|tabell]] er på 4NF [[hvis og bare hvis]] ''X'' er en [[supernøkkel]] for hver av dens ikke-[[Trivialitet (matematikk)|trivielle]] flervaluert avhengighet ''X'' <math>\twoheadrightarrow</math> ''Y'', altså at ''X'' enten er en [[kandidatnøkkel]] eller et [[overmengde]] derav.<ref name="Fagin">"A relation schema R* is in fourth normal form (4NF) if, whenever a nontrivial multivalued dependency X <math>\twoheadrightarrow</math> 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." {{Cite journal|first=Ronald|last=Fagin|title=Multivalued Dependencies and a New Normal Form for Relational Databases|journal=ACM Transactions on Database Systems|volume=2|issue=1|date=September 1977|pages=262–278|url=http://www.almaden.ibm.com/cs/people/fagin/tods77.pdf|doi=10.1145/320557.320571|accessdate=2024-03-26|archivedate=2007-11-29|archiveurl=https://web.archive.org/web/20071129092334/http://www.almaden.ibm.com/cs/people/fagin/tods77.pdf}}</ref>

== 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 [[Multivaluert avhengighet|flervaluert avhengighet]] ''X'' <math>\twoheadrightarrow</math> ''Y'' betyr at at hvis vi velger en hvilken som helst ''x'' som faktisk forekommer i tabellen (kall dette valget ''x<sub>c</sub>''), og kompilerer en liste over alle kombinasjonene ''x<sub>c</sub>yz'' som forekommer i tabellen vil vi finne at ''x<sub>c</sub>'' 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'' <math>\twoheadrightarrow</math> ''Y'' er en der enten ''Y'' er en delmengde av ''X'', eller ''X'' og ''Y'' sammen danner hele mengden [[Attributt|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:
{| class="wikitable"
|+[[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} <math>\twoheadrightarrow</math> {Pizzatype}
* {Restaurant} <math>\twoheadrightarrow</math> {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 [[Dataredundans|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} <math>\twoheadrightarrow</math> {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:

{| class="wikitable" style="margin: 10px; float:left;"
|+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
|}

{| class="wikitable" style="margin: 10px; float:left;"
|+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
|}
{{Clear}}

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 [[Applikasjonsprogramvare|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.<ref name="Wu">{{Cite journal|first=Margaret S.|last=Wu|title=The Practical Need for Fourth Normal Form|journal=ACM SIGCSE Bulletin|volume=24|issue=1|date=mars 1992|pages=19–23|doi=10.1145/135250.134515}}</ref>

== Normalisering utover 4NF ==
Bare i sjeldne situasjoner samsvarer ikke en 4NF-tabell med den høyere normalformen [[Femte normalform|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å ==
* [[Attributt–verdi-system]]
* [[Injektiv funksjon]]
* [[Bijeksjon]]

== Referanser ==
<references/>

{{Databasenormalisering}}

[[Kategori:Databaser]]