Hopp til innhold

Boyce–Codd normalform

Fra Wikipedia, den frie encyklopedi

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]

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

[rediger | rediger kilde]

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]

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

3NF-tabell som alltid tilfredsstiller BCNF

[rediger | rediger kilde]

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:

  • S1 = {Bane, starttid}
  • S2 = {Bane, sluttid}
  • S3 = {Prisklasse, starttid}
  • S4 = {Prisklasse, sluttid}
  • S5 = {Bane, starttid, sluttid}
  • S6 = {Prisklasse, starttid, sluttid}
  • S7 = {Bane, prisklasse, starttid}
  • S8 = {Bane, prisklasse, sluttid}
  • ST = {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 S1, S2, S3 og S4 kandidatnøkler (det vil si minimale supernøkler for relasjonen) fordi f.eks. S1 ⊂ S5, så S5 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

[rediger | rediger kilde]

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

[rediger | rediger kilde]

Gitt et databaseskjema på tredje normalform er det NP-komplett å avgjøre om det bryter med Boyce–Codd normalform.[10]

Dekomponering til BCNF

[rediger | rediger kilde]

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

[rediger | rediger kilde]
  1. ^ a b 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. ^ a b 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