Boyce–Codd normalform

Boyce–Codd normalform (BCNF eller 3.5NF) er en 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å funksjonelle avhengigheter.

Formen ble først beskrevet av Ian Heath i 1971, og har også blitt kalt Heath normalform av Chris Date.^[1]

Historie

I 1970 ga 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.^[2][1]

BCNF ble utviklet i 1974 av Raymond Francis Boyce og Edgar Frank Codd for å håndtere visse typer anomalier som ikke håndteres av tredje normalform.^[3]

Definisjon

Hvis et relasjonsskjema er i BCNF er all redundans basert på funksjonell avhengighet fjernet,^[4] 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 avhengigheter X → Y:^[5]

• X → Y er en triviell funksjonell avhengighet (Y ⊆ X),
• X er en supernøkkel for skjema R.^[5]

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økler er garantert på BCNF.^[6] 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:

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 hardbane (bane 1) og én 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økler er:

• S₁ = {Bane, starttid}
• S₂ = {Bane, sluttid}
• S₃ = {Prisklasse, starttid}
• S₄ = {Prisklasse, sluttid}
• S₅ = {Bane, starttid, sluttid}
• S₆ = {Prisklasse, starttid, sluttid}
• S₇ = {Bane, prisklasse, starttid}
• S₈ = {Bane, prisklasse, sluttid}
• S_T = {Bane, prisklasse, starttid, sluttid}, den trivielle supernøkkelen

Merk at selv om 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₁, S₂, S₃ og S₄ kandidatnøkler (det vil si minimale supernøkler for relasjonen) fordi f.eks. S₁ ⊂ S₅, så S₅ kan ikke være en kandidatnøkkel.

Ettersom at 2NF forbyr partielle funksjonelle avhengigheter av ikke-primære attributter (altså et attributt som ikke forekommer i noen kandidatnøkkel) og at 3NF forbyr 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:

Prisklasse Prisklasse Banenummer Medlemsflagg SPARE 1 Ja STANDARD 1 Nei PREMIUM-A 2 Ja PREMIUM-B 2 Nei

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

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.^[7]

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

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:

Butikk nær person Person Butikk Davidsen Ørneøye Davidsen Snippets Wold Merlin bøker Fredriksen Deigen Fredriksen Frisyr Fredriksen Ørneøye

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).^[8] Dette designet består av den originale "Nærmeste butikker"-tabellen supplert med "Butikk"-tabellen beskrevet ovenfor. Tabellstrukturen generert av Bernsteins skjemagenereringsalgoritme^[9] er faktisk EKNF, selv om den forbedringen av 3NF ikke hadde blitt gjenkjent på det tidspunktet algoritmen ble designet:

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

Butikk Butikk Butikktype Ørneøye Optiker Snippets Frisør Merlin bøker Bokhandel Deigen Bakeri Frisyr Frisør

Hvis en 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.^[10]

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:

1. En med attributtene X⁺,
2. og en annen med attributtene R-X⁺+X. Merk at R representerer alle attributtene i den opprinnelige relasjonen.

Detetter må det sjekkes om begge underrelasjonene er i BCNF, og prosessen gjentas rekursivt med enhver underrelasjon som ikke er i BCNF.^[11]

Referanser

1. Date, C. J. Database in Depth: Relational Theory for Practitioners. O'Reilly (2005), p. 142.
2. 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–12th, 1971).
3. Codd, E. F. "Recent Investigations into Relational Data Base" in Proc. 1974 Congress (Stockholm, Sweden, 1974). New York, N.Y.: North-Holland (1974).
4. Köhler, Henning; Link, Sebastian (1. juli 2018). «SQL schema design: foundations, normal forms, and normalization». Information Systems. 76: 88–113. doi:10.1016/j.is.2018.04.001.
5. Silberschatz, Abraham. Database System Concepts (6th utg.). McGraw-Hill. ISBN 978-0-07-352332-3.
6. 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.
7. 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.
8. Zaniolo, Carlo. "A New Normal Form for the Design of Relational Database Schemata". ACM Transactions on Database Systems 7(3), September 1982, p. 493.
9. Bernstein, P. A. "Synthesizing Third Normal Form relations from functional dependencies". ACM Transactions on Database Systems 1(4), December 1976 pp. 277–298.
10. Beeri, Catriel; Bernstein, Philip A. (1979). «Computational Problems Related to the Design of Normal Form Relational Schemas». ACM Transactions on Database Systems. 4: 30–59. doi:10.1145/320064.320066.Mal:Closed access, Corollary 3.
11. (på en) BCNF Decomposition, https://www.youtube.com/watch?v=WKJH3V7UAgg, besøkt 2023-03-15