Boyce–Codd normalform
Boyce-Codd normal form (eller BCNF eller 3.5NF ) är en normal form som används i databasnormalisering . Det är en något starkare version av den tredje normalformen (3NF). BCNF utvecklades 1974 av Raymond F. Boyce och Edgar F. Codd för att ta itu med vissa typer av anomalier som inte hanteras av 3NF som ursprungligen definierades.
Om ett relationsschema finns i BCNF har all redundans baserad på funktionellt beroende tagits bort, även om andra typer av redundans fortfarande kan finnas. Ett relationsschema R är i Boyce-Codd normalform om och endast om för vart och ett av dess beroenden X → Y , minst ett av följande villkor gäller:
- X → Y är ett trivialt funktionellt beroende (Y ⊆ X),
- X är en supernyckel för schema R .
3NF-tabellen möter alltid BCNF (Boyce–Codd normalform)
Endast i sällsynta fall uppfyller en 3NF-tabell inte kraven i BCNF. En 3NF-tabell som inte har flera överlappande kandidatnycklar är garanterat i BCNF. Beroende på vad dess funktionella beroenden är, kan en 3NF-tabell med två eller flera överlappande kandidatnycklar finnas i BCNF eller inte.
Ett exempel på en 3NF-tabell som inte uppfyller BCNF är:
| Domstol | Starttid | Sluttid | Pristyp |
|---|---|---|---|
| 1 | 09:30 | 10:30 | SPARARE |
| 1 | 11:00 | 12:00 | SPARARE |
| 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 |
- Varje rad i tabellen representerar en banbokning hos en tennisklubb. Den klubben har en hårdbana (plan 1) och en gräsplan (plan 2)
- En bokning definieras av dess domstol och den period för vilken domstolen är reserverad
- Dessutom har varje bokning en pristyp kopplad till sig. Det finns fyra distinkta pristyper:
- SAVER, för Court 1-bokningar gjorda av medlemmar
- STANDARD, för Court 1-bokningar gjorda av icke-medlemmar
- PREMIUM-A, för Court 2-bokningar gjorda av medlemmar
- PREMIUM-B, för Court 2-bokningar gjorda av icke-medlemmar
Tabellens supernycklar är:
- S 1 = {Domstol, starttid}
- S 2 = {domstol, sluttid}
- S 3 = {Rate type, Start time}
- S 4 = {Rate type, End time}
- S 5 = {Court, Start time, End time}
- S 6 = {Rate type, Start time, End time}
- S 7 = {domstol, pristyp, starttid}
- S 8 = {Court, Rate type, End time}
- S T = {Court, Rate type, Start time, End time}, den triviala supernyckeln
Observera att även om attributen Starttid och Sluttid i tabellen ovan inte har några dubbla värden för var och en av dem, måste vi ändå erkänna att under vissa andra dagar kan två olika bokningar på bana 1 och bana 2 starta samtidigt eller sluta samtidigt . Detta är anledningen till att {Starttid} och {Sluttid} inte kan betraktas som tabellens supernycklar.
är endast S1 , S2 , S3 och S4 kandidatnycklar ( det vill säga minimala supernycklar för den relationen) eftersom t.ex. S1 ⊂ S5 , så S5 inte kan vara en kandidatnyckel.
Kom ihåg att 2NF förbjuder partiella funktionella beroenden av icke-primära attribut (dvs. ett attribut som inte förekommer i någon kandidatnyckel. Se " kandidatnycklar ") och att 3NF förbjuder transitiva funktionella beroenden av icke-primära attribut på kandidatnycklar.
I dagens domstolsbokningstabell finns det inga icke-primära attribut: det vill säga alla attribut tillhör någon kandidatnyckel. Därför följer tabellen både 2NF och 3NF.
Tabellen följer inte BCNF. Detta beror på beroendet Rate type → Court där det avgörande attributet Rate type – som Court är beroende av – (1) varken är en kandidatnyckel eller en supplering av en kandidatnyckel och (2) Court är ingen delmängd av Rate-typen.
Beroendegradstyp → Domstol respekteras, eftersom en satstyp alltid endast bör gälla för en enda domstol.
Designen kan ändras så att den uppfyller BCNF:
|
|
Kandidatnycklarna för tabellen Pristyper är {Rate type} och {Court, Member flag}; kandidatnycklarna för dagens bokningstabell är {Court, Start time} och {Court, End time}. Båda tabellerna är i BCNF. När {Rate type} är en nyckel i tabellen Pristyper, är det omöjligt att ha en pristyp associerad med två olika domstolar, så genom att använda {Rate type} som en nyckel i tabellen Pristyper har anomalien som påverkar den ursprungliga tabellen blivit utslagen.
Uppnåbarhet av BCNF
I vissa fall kan en icke-BCNF-tabell inte delas upp i tabeller som uppfyller BCNF och bevara de beroenden som fanns i den ursprungliga tabellen. Beeri och Bernstein visade 1979 att till exempel en uppsättning funktionella beroenden {AB → C, C → B} inte kan representeras av ett BCNF-schema.
Betrakta följande icke-BCNF-tabell vars funktionella beroenden följer {AB → C, C → B}-mönstret:
| Person | Butikstyp | Närmaste butik |
|---|---|---|
| Davidson | Optiker | Örn öga |
| Davidson | Frisör | Utdrag |
| Wright | Bokhandel | Merlin böcker |
| Fullare | Bageri | Doughy's |
| Fullare | Frisör | Sweeney Todds |
| Fullare | Optiker | Örn öga |
För varje kombination av person/butikstyp visar tabellen vilken butik av denna typ som geografiskt ligger närmast personens hem. Vi antar för enkelhetens skull att en enskild butik inte kan vara av mer än en typ.
Tabellens kandidatnycklar är:
- {Person, Butikstyp},
- {Person, närmaste butik}.
Eftersom alla tre attributen är primära attribut (dvs. tillhör kandidatnycklar), är tabellen i 2NF. Tabellen är dock inte i BCNF, eftersom attributet Butikstyp är funktionellt beroende av en icke-supernyckel: Närmaste butik.
Brott mot BCNF innebär att tabellen är föremål för anomalier. Till exempel kan Eagle Eye få sin butikstyp ändrad till "Optometrist" på sin "Fuller"-post medan butikstypen "Optician" behålls på sin "Davidson"-post. Detta skulle innebära motsägelsefulla svar på frågan: "Vad är Eagle Eyes butikstyp?" Att hålla varje butiks butikstyp bara en gång verkar vara att föredra, eftersom det skulle förhindra att sådana anomalier uppstår:
|
|
I denna reviderade design har tabellen "Handla nära person" kandidatnyckeln {Person, Butik} och tabellen "Shop" har kandidatnyckeln {Shop}. Tyvärr, även om denna design följer BCNF, är den oacceptabel på olika grunder: den tillåter oss att spela in flera butiker av samma typ mot samma person. Med andra ord, dess kandidatnycklar garanterar inte att det funktionella beroendet {Person, Butikstyp} → {Butik} kommer att respekteras.
En design som eliminerar alla dessa anomalier (men inte överensstämmer med BCNF) är möjlig. Denna design introducerar en ny normal form, känd som Elementary Key Normal Form . Denna design består av det ursprungliga "Nearest shops"-bordet kompletterat med "Shop"-bordet som beskrivs ovan. Tabellstrukturen som genereras av Bernsteins schemagenereringsalgoritm är faktiskt EKNF, även om den förbättringen till 3NF inte kändes igen när algoritmen designades:
|
|
Om en referensintegritetsbegränsning definieras så att {Butikstyp, Närmaste butik} från den första tabellen måste hänvisa till en {Butikstyp, Butik} från den andra tabellen, så förhindras de dataavvikelser som beskrivits tidigare.
Omöjlighet
Det är NP-komplett , givet ett databasschema i tredje normalform , för att avgöra om det bryter mot Boyce-Codds normala form.
Historia
Chris Date har påpekat att en definition av vad vi nu känner som BCNF dök upp i en tidning av Ian Heath 1971. Date skriver:
Eftersom den definitionen föregick Boyce och Codds egen definition med cirka tre år, förefaller det mig som att BCNF med rätta borde kallas Heath normalform. Men det är det inte .
Edgar F. Codd släppte sin originalartikel "A Relational Model of Data for Large Shared Databanks" i juni 1970. Detta var första gången idén om en relationsdatabas publicerades. Allt arbete efter detta, inklusive Boyce–Codds normalformsmetod baserades på denna relationsmodell.
Bibliografi
- Date, CJ (1999). En introduktion till databassystem (8:e upplagan). Addison-Wesley Longman. ISBN 0-321-19784-4 .
externa länkar
- Regler för datanormalisering
- Advanced Normalization av ITS, University of Texas.