Redigerer Boyce–Codd normalform

'''Boyce–Codd normalform''' ('''BCNF''' eller '''3.5NF''') er en [[Databasenormalisering|normalform]] som brukes i [[databasenormalisering]]. Det er en litt strengere versjon av [[tredje normalform]] (3NF). Ved å bruke BCNF vil en [[database]] fjerne all redundans basert på [[Funksjonell avhengighet|funksjonelle avhengigheter]].

Formen ble først beskrevet av Ian Heath i 1971, og har også blitt kalt '''Heath normalform''' av Chris Date.<ref name="Date">Date, C. J. ''Database in Depth: Relational Theory for Practitioners''. O'Reilly (2005), p. 142.</ref>

== Historie ==
I 1970 ga [[Edgar F. Codd|Edgar Frank Codd]] ut den velkjente artikkelen ''A Relational Model of Data for Large Shared Databanks''. Dette var første gang ideen om en [[relasjonsdatabase]] ble publisert. Alt arbeid etter dette, inkludert Boyce–Codd normalformen, er basert på denne relasjonsmodellen.

Boyce–Codd normalformen ble først beskrevet i 1971 av Ian Heath, og formen har derfor også blitt kalt ''Heath normalform'' av Chris Date.<ref name="Heath">Heath, I. "Unacceptable File Operations in a Relational Database". ''Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access, and Control'', San Diego, Calif. (November 11th&#x2013;12th, 1971).</ref><ref name="Date" />

BCNF ble utviklet i 1974 av [[Raymond F. Boyce|Raymond Francis Boyce]] og [[Edgar F. Codd|Edgar Frank Codd]] for å håndtere visse typer anomalier som ikke håndteres av tredje normalform.<ref name="Codd">Codd, E. F. "Recent Investigations into Relational Data Base" in ''Proc. 1974 Congress'' (Stockholm, Sweden, 1974). New York, N.Y.: North-Holland (1974).</ref>

== Definisjon ==
Hvis et [[Databaseskjema|relasjonsskjema]] er i BCNF er all redundans basert på [[funksjonell avhengighet]] fjernet,<ref>{{Cite journal|last=Köhler|first=Henning|last2=Link|first2=Sebastian|date=2018-07-01|title=SQL schema design: foundations, normal forms, and normalization|url=https://linkinghub.elsevier.com/retrieve/pii/S0306437917305069|journal=Information Systems|language=en|volume=76|pages=88–113|doi=10.1016/j.is.2018.04.001}}</ref> selv om det fortsatt kan eksistere andre typer redundans. Et relasjonsskjema ''R'' er på Boyce-Codd normalform [[hvis og bare hvis]] minst én av følgende betingelser gjelder for hver av dens [[Funksjonell avhengighet|avhengigheter]] ''X → Y'':<ref name=":0">{{Kilde bok|url=https://archive.org/details/databasesystemco00silb_973|tittel=Database System Concepts|etternavn=Silberschatz|fornavn=Abraham|utgiver=McGraw-Hill|isbn=978-0-07-352332-3|utgave=6th}}</ref>

* ''X'' → ''Y'' er en [[Trivialitet (matematikk)|triviell]] funksjonell avhengighet (Y ⊆ X),
* ''X'' er en [[supernøkkel]] for skjema ''R.''<ref name=":0"/>

Merk at hvis et relasjonsskjema tilfredstiller BCNF så tilfredstiller det også 3NF.

== 3NF-tabell som alltid tilfredsstiller BCNF ==
Bare i sjeldne tilfeller oppfyller ikke 3NF-tabeller kravene til BCNF. En 3NF-tabell som ikke har flere overlappende [[Kandidatnøkkel|kandidatnøkler]] er garantert på BCNF.<ref name="Vincent">Vincent, M. W. and B. Srinivasan. "A Note on Relational Schemes Which Are in 3NF But Not in BCNF". ''Information Processing Letters'' 48(6), 1993, pp. 281–283.</ref> Avhengig av hva dens funksjonelle avhengigheter er kan en 3NF-tabell med to eller flere overlappende kandidatnøkler være på BCNF eller ikke.

Et eksempel på en 3NF-tabell som ''ikke'' oppfyller BCNF er:
{| class="wikitable"
|+Dagens tennisbane-bestillinger
! Banenummer
! Starttid
! Sluttid
! Prisklasse
|-
| 1
| 09:30
| 10:30
| SPARE
|-
| 1
| 11:00
| 12:00
| SPARE
|-
| 1
| 14:00
| 15:30
| STANDARD
|-
| 2
| 10:00
| 11:30
| PREMIUM-B
|-
| 2
| 11:30
| 13:30
| PREMIUM-B
|-
| 2
| 15:00
| 16:30
| PREMIUM-A
|-
|}

* Hver rad i tabellen representerer en bestilling på en tennisbane. Denne tennisklubben har én [[Hardcourt|hardbane]] (bane 1) og én [[Gressbane (tennis)|gressbane]] (bane 2).
* En bestilling er definert av banenummer og perioden den er reservert for.
* I tillegg er hver bestilling tilknyttet en prisklasse. Det er fire forskjellige prisklasser:
** STANDARD, for bane 1-bestillinger gjort av ikke-medlemmer
** SPARE, for bane 1-bestillinger gjort av medlemmer
** PREMIUM-B, for bane 2-bestillinger gjort av ikke-medlemmer
** PREMIUM-A, for bane 2-bestillinger gjort av medlemmer

Tabellens [[Supernøkkel|supernøkler]] er:

* S<sub>1</sub> = {Bane, starttid}
* S<sub>2</sub> = {Bane, sluttid}
* S<sub>3</sub> = {Prisklasse, starttid}
* S<sub>4</sub> = {Prisklasse, sluttid}
* S<sub>5</sub> = {Bane, starttid, sluttid}
* S<sub>6</sub> = {Prisklasse, starttid, sluttid}
* S<sub>7</sub> = {Bane, prisklasse, starttid}
* S<sub>8</sub> = {Bane, prisklasse, sluttid}
* S<sub>T</sub> = {Bane, prisklasse, starttid, sluttid}, den [[Trivialitet (matematikk)|trivielle]] supernøkkelen

Merk at selv om [[Attributt|attributtene]] for ''starttid'' og ''sluttid'' i tabellen ovenfor ikke har noen dupliserte verdier for hver av dem, må vi likevel innrømme at det på noen dager kan være to forskjellige bookinger på bane 1 og bane 2 som ''starter samtidig'' eller ''slutter samtidig''. Dette er grunnen til at {Starttid} og {Sluttid} ikke kan betraktes som tabellens supernøkler.

Imidlertid er bare S<sub>1</sub>, S<sub>2</sub>, S<sub>3</sub> og S<sub>4</sub> [[Kandidatnøkkel|kandidatnøkler]] (det vil si minimale supernøkler for relasjonen) fordi f.eks. S<sub>1</sub> ⊂ S<sub>5</sub>, så S<sub>5</sub> kan ikke være en kandidatnøkkel.

Ettersom at [[Andre normalform|2NF]] forbyr partielle funksjonelle avhengigheter av ikke-primære attributter (altså et attributt som ikke forekommer i ''noen'' [[kandidatnøkkel]]) og at [[Tredje normalform|3NF]] forbyr [[Transitiv avhengighet|transitive funksjonelle avhengigheter]] av ikke-primære attributter på kandidatnøkler.

I tabellen ''Dagens tennisbane-bestillinger'' er det ingen ikke-primære attributter, det vil si at alle attributter tilhører en eller annen kandidatnøkkel. Derfor overholder tabellen både 2NF og 3NF.

Tabellen overholder imidlertid ikke BCNF på grunn av avhengigheten Prisklasse → Banenummer hvor det bestemmende attributtet Prisklasse – som Banenummer avhenger av – (1) verken er en kandidatnøkkel eller en [[overmengde]] av en kandidatnøkkel og (2) Banenummer er ingen [[delmengde]] av Prisklasse.

Avhengigheten Prisklasse → Banenummer respekteres her, siden en prisklasse kun skal gjelde for en enkelt bane.

Designet kan endres slik at det oppfyller BCNF:

{| style="border-spacing:2em 0; margin-left:-2em"
| style="vertical-align:top" |
{| class="wikitable"
|+ Prisklasse
! Prisklasse
! Banenummer
! Medlemsflagg
|-
| SPARE
| 1
| Ja
|-
| STANDARD
| 1
| Nei
|-
| PREMIUM-A
| 2
| Ja
|-
| PREMIUM-B
| 2
| Nei
|-
|}
| style="vertical-align:top" |
{| class="wikitable"
|+ Dagens bestillinger
!Banenummer
! Starttid
! Sluttid
! Medlemsflagg
|-
| 1
| 09:30
| 10:30
| Ja
|-
| 1
| 11:00
| 12:00
| Ja
|-
| 1
| 14:00
| 15:30
| Nei
|-
| 2
| 10:00
| 11:30
| Nei
|-
| 2
| 11:30
| 13:30
| Nei
|-
| 2
| 15:00
| 16:30
| Ja
|-
|}
|}
{{Clear}}

Kandidatnøklene for tabellen ''Prisklasse'' er {Prisklasse} og {Banenummer, Medlemsflagg}. Kandidatnøklene for tabellen ''Dagens bestillinger'' er {Banenummer, starttid} og {Banenummer, sluttid}. Begge tabellene er på BCNF. Når {Prisklasse} er en nøkkel i satstypetabellen, er det umulig å ha én satstype assosiert med to forskjellige banenummer, så ved å bruke {Prisklasse} som en nøkkel i prisklasse-tabellen har anomalien som påvirket den opprinnelige tabellen blitt eliminert.

== Oppnåbarhet av BCNF ==
I noen tilfeller er det umulig å dekomponere en ikke-BCNF-tabell til tabeller som tilfredsstiller BCNF og samtidig bevarer avhengighetene som holdt i den opprinnelige tabellen. Beeri og Bernstein viste i 1979 for eksempel at en mengde med funksjonelle avhengigheter {AB → C, C → B} ikke kan representeres av et BCNF-skjema.<ref name="Beeri">Beeri, Catriel and Bernstein, Philip A. "Computational problems related to the design of normal form relational schemas". ''ACM Transactions on Database Systems'' 4(1), March 1979, p. 50.</ref>

Anta følgende ikke-BCNF-tabell hvis funksjonelle avhengigheter følger {AB → C, C → B}-mønsteret:

{| class="wikitable"
|+Nærmeste butikker
! Person
! Butikktype
! Nærmeste butikk
|-
| Davidsen
| Optiker
| Ørneøye
|-
| Davidsen
| Frisør
| Snippets
|-
| Wold
| Bokhandel
| Merlin bøker
|-
| Fredriksen
| Bakeri
| Deigen
|-
| Fredriksen
| Frisør
| Frisyr
|-
| Fredriksen
| Optiker
| Ørneøye
|}

For hver kombinasjon av person/butikktype gir tabellen hvilken butikk av denne typen som er geografisk nærmest personens hjem. Vi antar for enkelhets skyld at en enkelt butikk ikke kan være av mer enn én type.

Tabellens kandidatnøkler er:
* {Person, butikktype},
* {Person, nærmeste butikk}.

Fordi alle tre attributtene er primære attributter (det vil si tilhører kandidatnøkler) er tabellen på 3NF. Tabellen er imidlertid ikke på BCNF siden butikktype-attributten er funksjonelt avhengig av ikke-supernøkkelen nærmeste butikk.

Brudd på BCNF betyr at tabellen er gjenstand for uregelmessigheter. For eksempel kan Ørneøye få butikktypen endret til "[[optometrist]]" på Fredriksen-raden, mens butikktypen "[[optiker]]" beholdes på Davidsen-raden. Dette ville innebære motstridende svar på spørsmålet: "Hva er Ørneøye sin butikktype?" Å holde hver butikks butikktype bare én gang virker å foretrekke, da dette vil forhindre at slike uregelmessigheter oppstår:

{| style="border-spacing:2em 0; margin-left:-2em"
| style="vertical-align:top" |
{| class="wikitable"
|+ Butikk nær person
! Person
! Butikk
|-
| Davidsen
| Ørneøye
|-
| Davidsen
| Snippets
|-
| Wold
| Merlin bøker
|-
| Fredriksen
| Deigen
|-
| Fredriksen
| Frisyr
|-
| Fredriksen
| Ørneøye
|}
| style="vertical-align:top" |
{| class="wikitable"
|+ Butikk
! Butikk
! Butikktype
|-
| Ørneøye
| Optiker
|-
| Snippets
| Frisør
|-
| Merlin bøker
| Bokhandel
|-
| Deigen
| Bakeri
|-
| Frisyr
| Frisør
|}
|}

I dette reviderte designet har tabellen "Butikk nær person" kandidatnøkkelen {Person, butikk}, og "Butikk"-tabellen har kandidatnøkkelen {Butikk}. Selv om dette designet tilfredsstiller BCNF er denne løsningen dessverre uakseptabel av andre årsaker: Den lar oss registrere flere butikker av samme type mot samme person. Med andre ord garanterer ikke kandidatnøklene at funksjonsavhengigheten {Person, butikktype} → {Butikk} vil bli respektert.

Et design som eliminerer alle disse anomaliene (men ikke samsvarer med BCNF) er mulig. Dette designet introduserer en ny normalform kjent som [[elementærnøkkel normalform]] (EKNF).<ref name="Zaniolo">Zaniolo, Carlo. "A New Normal Form for the Design of Relational Database Schemata". ''ACM Transactions on Database Systems'' 7(3), September 1982, p. 493.</ref> Dette designet består av den originale "Nærmeste butikker"-tabellen supplert med "Butikk"-tabellen beskrevet ovenfor. Tabellstrukturen generert av Bernsteins skjemagenereringsalgoritme<ref name="Bernstein">Bernstein, P. A. "Synthesizing Third Normal Form relations from functional dependencies". ''ACM Transactions on Database Systems'' 1(4), December 1976 pp. 277–298.</ref> er faktisk EKNF, selv om den forbedringen av 3NF ikke hadde blitt gjenkjent på det tidspunktet algoritmen ble designet:

{| style="border-spacing:2em 0; margin-left:-2em"
| style="vertical-align:top" |
{| class="wikitable"
|+ Nærmeste butikker
! Person
! Butikktype
! Nærmeste butikk
|-
| Davidsen
| Optiker
| Ørneøye
|-
| Davidsen
| Frisør
| Snippets
|-
| Wold
| Bokhandel
| Merlin bøker
|-
| Fredriksen
| Bakeri
| Deigen
|-
| Fredriksen
| Frisør
| Frisyr
|-
| Fredriksen
| Optiker
| Ørneøye
|}
| style="vertical-align:top" |
{| class="wikitable" style="float:left;"
|+ Butikk
! Butikk
! Butikktype
|-
| Ørneøye
| Optiker
|-
| Snippets
| Frisør
|-
| Merlin bøker
| Bokhandel
|-
| Deigen
| Bakeri
|-
| Frisyr
| Frisør
|}
|}
Hvis en [[Referanseintegritet|referanseintegritets-begrensning]] er definert slik at {Butikktype, nærmeste butikk} fra den første tabellen må referere til en {Butikktype, Butikk} fra den andre tabellen så forhindres dataavvikene beskrevet tidligere.

== Uløselighet ==
Gitt et databaseskjema på [[tredje normalform]] er det [[NP-komplett]] å avgjøre om det bryter med Boyce–Codd normalform.<ref>{{Cite journal|last1=Beeri|first1=Catriel|last2=Bernstein|first2=Philip A.|title=Computational Problems Related to the Design of Normal Form Relational Schemas|url=https://archive.org/details/sim_acm-transactions-on-database-systems_1979-03_4_1/page/30|journal=[[ACM Transactions on Database Systems]]|year=1979|volume=4|pages=30–59|doi=10.1145/320064.320066|s2cid=11409132|doi-access=free}}{{Closed access}}, Corollary 3.</ref>

== Dekomponering til BCNF ==
Hvis en relasjon R ikke er i BCNF på grunn av en funksjonell avhengighet X→Y så kan man dekompone R til BCNF ved å erstatte relasjonen med to underrelasjoner:

# En med attributtene X<sup>+</sup>,
# og en annen med attributtene R-X<sup>+</sup>+X. Merk at R representerer alle attributtene i den opprinnelige relasjonen.

Detetter må det sjekkes om begge underrelasjonene er i BCNF, og prosessen gjentas [[Rekursjon|rekursivt]] med enhver underrelasjon som ikke er i BCNF.<ref>{{Citation|title=BCNF Decomposition|url=https://www.youtube.com/watch?v=WKJH3V7UAgg|access-date=2023-03-15|language=en}}</ref>

== Referanser ==
<references/>

{{Databasenormalisering}}

[[Kategori:Databaser]]