Databasenormalisatie
Databasenormalisatie is een techniek bij het ontwerpen van databases. Ze dient twee doelen: het spaarzaam omgaan met opslagruimte en het vermijden van meervoudige vastlegging van dezelfde data (redundantie), een potentiële bron van fouten. Bij het normaliseren dient men zich er bewust van te zijn dat er geen informatie verloren gaat. Er bestaan algoritmen die deze normaalvormen automatisch uitwerken voor een willekeurige database.
De techniek van databasenormalisatie wordt in het bijzonder gebruikt in relationele databases. Het woord "relationeel" geeft aan dat de relatie tussen de gegevens deel uitmaakt van de database. In computerdatabases worden de relaties tussen de gegevens bewaakt door een software-tussenlaag, het RDBMS.
Normaalvormen
bewerkenEr bestaan meerdere normaalvormen, waarbij in de eerste normaalvorm (1NF) de eenvoudigste variant is en de vijfde (5NF) de meest complexe. Hoe hoger de normaalvorm, hoe meer eisen er gesteld worden aan het ontwerp. Wanneer aan geen van de eisen voldaan is spreekt men van 0NF. De database is dan dusdanig slecht ontworpen dat deze in de praktijk beperkt bruikbaar is.
De verschillende normaalvormen zijn:
- 1e Normaalvorm (1NF)
- 2e Normaalvorm (2NF)
- 3e Normaalvorm (3NF)
- Boyce-Codd-Normalform (BCNF)
- 4e Normaalvorm (4NF)
- 5e Normaalvorm (5NF)
Waarvoor geldt: .
De normalisatie leidt ertoe dat elke regel in elke tabel met behulp van een unieke identificatie, een sleutel, opgevraagd kan worden. Elke normaalvorm stelt daartoe bepaalde eisen aan de manier waarop de gegevens zijn opgeslagen (zoals eisen aan de geldende functionele afhankelijkheden). De gegevens staan in een bepaalde normaalvorm wanneer aan een aantal voorgeschreven voorwaarden voldaan is. Gegevens staan bijvoorbeeld in de tweede normaalvorm als en slechts als ze voldoen aan de eerste normaalvorm en aan een aantal extra regels.
Bij 1NF worden de data in één of meer tabellen opgeslagen, maar men maakt zich niet druk om de structuur, niet om de gebruikte schijfruimte en ook niet over het feit dat een gegeven meerdere malen opgeslagen is. Bij 5NF is weer sprake van het tegenovergestelde, elk gegeven is slechts één keer opgeslagen en er wordt zo weinig mogelijk schijfruimte gebruikt. Bij 5NF zijn de data voor een gebruiker echter lastiger te doorzoeken. Vaak wordt voor een tussenvorm gekozen, namelijk de 3NF.
Redenen
bewerkenOm te normaliseren bestaan verschillende redenen en bij de keuze tot een bepaalde normaalvorm zal altijd een afweging gemaakt worden, maar de keuze hangt sterk samen met de complexiteit van de data. Zoals eerder gesteld is 1NF de minimale vereiste voor een bruikbare database. Problemen die men door middel van een hogere normaalvorm voorkomt zijn:
- Update-anomalie: Wanneer dezelfde gegevens op meerdere plekken worden opgeslagen dan zal dit bij een aanpassing ook op meerdere plaatsen moeten gebeuren. Als het adres van een klant in vijf tabellen opgeslagen is dan kan men dit bij een adreswijziging zomaar op vier plekken aanpassen en vergeten dat er nog een vijfde plek is.
- Insert-anomalie: Bij een slecht ontworpen database kan men tegen het probleem aanlopen dat een gegeven pas ingevoerd kan worden wanneer ook andere gegevens bekend zijn. Bijvoorbeeld, als de verkoopgegevens en de klantgegevens in dezelfde tabel staan dan kan een klant pas opgevoerd worden wanneer deze ook al iets besteld heeft. Omgekeerd geldt hetzelfde, een nieuw product kan pas opgevoerd worden als het al door iemand besteld is.
- Verwijder-anomalie: Dit probleem draagt het probleem van de vorige anomalie in zich. Het verwijderen van een product kan leiden tot het verwijderen van klanten.
Ook het beperken van schijfruimte en efficiënt gebruik van rekenkracht kunnen een reden zijn. Deze dragen echter geen fouten in zich mee. Een zoekopdracht die wat langer duurt zal immers niet tot foute resultaten leiden.
Geschiedenis
bewerkenTed Codd formuleerde het idee van normalisatie in A Relational Model of Data for Large Shared Data Banks[1] in 1970.
There is, in fact, a very simple elimination[noot 1] procedure which we shall call normalization. Through decomposition nonsimple domains are replaced by "domains whose elements are atomic (nondecomposable) values."
De eerste drie normaalvormen (1NF, 2NF en 3NF) werden gedefinieerd door Codd in Further normalization of the Data Base Relational Model[2] Alle genormaliseerde gegevens staan minstens in 1NF. Sommige gegevens staan ook in 2NF, sommige zelfs in 3NF. Codd gaf aan dat gegevens in 2NF wenselijker waren dan deze in 1NF, 3NF was nog wenselijker. De ontwerper van de database zou dus moeten streven naar gegevens in 3NF.
Codds oorspronkelijke definitie van 3NF bleek later niet volmaakt. De definitie werd herbekeken en versterkt door Boyce en Codd in Recent Investigations into Relational Data Base Systems.[3] Gegevens in 3NF in deze nieuwe definitie voldeden ook aan de oude definitie, maar gegevens die aan 3NF voldeden volgens de oude definitie voldeden niet noodzakelijk aan de nieuwe. De nieuwe definitie was dus sterker dan de oude en werd later de Boyce/Codd normaalvorm genoemd als een versterking van de voorwaarden van de oude 3NF.
Later introduceerde Ron Fagin nog enkele sterke normaalvormen. In Multivalued Dependencies and a New Normal Form for Relational Databases[4] definieerde hij een nieuwe vierde normaalvorm (in die tijd werd de latere BCNF nog steeds de derde normaalvorm genoemd). In Normal Forms and Relational Database Operators[5] definieerde hij nog een nieuwe normaalvorm, de projection-join normal form (PJ/NF) of vijfde normaalvorm.
Nulde normaalvorm (0NF)
bewerkenIeder ongestructureerd gegevensbestand is in de nulde normaalvorm (0NF) oftewel niet-genormaliseerd. Gegevens van verschillende soorten kunnen op elke regel voorkomen, waardoor deze niet in kolommen kunnen worden opgedeeld en de data niet goed te doorzoeken zijn.
Een voorbeeld
bewerkenCd van Anastacia met de titel Not That Kind uit 2000 heeft de nummers Not That Kind, I’m Outta Love Wish You Were Here van Pink Floyd met Shine On You Crazy Diamond, uitgebracht in 1975 Pink Floyd is actief sinds 1965 en Anastacia zingt pas vanaf 1999
Ook wanneer de gegevens in een tabel worden gezet kan er nog steeds sprake zijn van 0NF, zoals hieronder te zien is. De gegevens zijn niet atomair want in de kolom Album worden zowel het album, het verschijningsjaar als het jaar van het eerste optreden genoemd. En de kolommen zijn niet uniek want de kolom Track komt wel drie keer voor.
Album | Verschijningsjaar | Track | Track | Track |
---|---|---|---|---|
Anastacia (1999) – Not That Kind | 2000 | Not That Kind | I’m Outta Love | Cowboys & Kisses |
Pink Floyd (1965) – Wish You Were Here | 1975 | Shine On You Crazy Diamond | ||
Anastacia (1999) – Freak of Nature | 2001 | Paid my Dues |
Eerste normaalvorm (1NF)
bewerkenElke tabel met gegevens die voldoet aan de definitie van een relatie is in de eerste normaalvorm (1NF). Wanneer gegevens aan een relatie voldoen zijn ze dus reeds genormaliseerd.
- elk attribuut is atomair, en bevat dus één enkele waarde (bijvoorbeeld een telefoonnummer-attribuut mag slechts een telefoonnummer bevatten); indien een attribuut meerdere waarden bevat zouden deze waarden in een andere tabel moeten worden ondergebracht.
- geen enkel attribuut wordt herhaald
- alle attributen blijven constant in de tijd
Kortom, als alle data in één of meer tabellen zijn ondergebracht, is er al sprake van de eerste normaalvorm. Er is dan wel sprake van een vaste structuur voor de data, maar er is nog niet goed nagedacht over welke data in welke tabel komen. Alle data van een bedrijf zouden bijvoorbeeld in één platte tabel geplaatst kunnen worden. Bij een tabel waarin de aankopen van klanten worden bijgehouden, zou je dan bij elke aankoopregel ook het adres aantreffen, met als gevolg dat bij elke nieuwe aankoop ook het adres van de klant weer ingevoerd wordt, waardoor één adres wellicht honderden malen in de tabel opduikt.
Een voorbeeld
bewerkenDe gegevens van de platenzaak in 0NF:
CD_ID | Album | Verschijningsjaar | Track1 | Track2 | Track3 |
---|---|---|---|---|---|
4711 | Anastacia (1999) – Not That Kind | 2000 | Not That Kind | I’m Outta Love | Cowboys & Kisses |
4712 | Pink Floyd (1965) – Wish You Were Here | 1975 | Shine On You Crazy Diamond | Null | Null |
4713 | Anastacia (1999) – Freak of Nature | 2001 | Paid my Dues | Null | Null |
Bovenstaande data staan weliswaar in een tabel, maar deze voldoet nog niet aan 1NF. Naam van de artiest en het eerste optreden staan samen in één kolom én voor de tracks zijn meerdere kolommen aangemaakt. Om te voldoen aan de 1NF zouden alle verschijningsjaren, artiesten en hun eerste optreden in een aparte kolommen en records moeten worden geplaatst en de tracks moeten onder elkaar in één kolom. Om het niet onnodig complex te maken, gaan we ervan uit dat een lied slechts op één cd voor kan komen en dat een cd slechts één artiest heeft.
CD_ID | Albumtitel | Artiest | Actief sinds | Verschijningsjaar | Track | Single |
---|---|---|---|---|---|---|
4711 | Not That Kind | Anastacia | 1999 | 2000 | 1 | Not That Kind |
4711 | Not That Kind | Anastacia | 1999 | 2000 | 2 | I’m Outta Love |
4711 | Not That Kind | Anastacia | 1999 | 2000 | 3 | Cowboys & Kisses |
4712 | Wish You Were Here | Pink Floyd | 1965 | 1975 | 1 | Shine On You Crazy Diamond |
4713 | Freak of Nature | Anastacia | 1999 | 2001 | 1 | Paid my Dues |
In bovenstaande tabel staan de data nu wel in 1NF. Voordeel: De data zijn nu door middel van een SELECT-statement te doorzoeken. Nadeel: Er kunnen zich de volgende problemen voordoen. Wanneer de naam van een cd gewijzigd moet worden, moet deze wijziging op verschillende regels worden uitgevoerd, wanneer een cd wordt opgevoerd maar de tracks zijn nog onbekend, dan kan dat alleen als in de kolom Track ook null-waarden worden toegestaan. Wanneer alle nummers van een cd verwijderd worden dan verdwijnt de hele cd uit de tabel.
Tweede normaalvorm (2NF)
bewerkenEen relatie is in 2NF als alle attributen die niet in de sleutel zijn opgenomen, functioneel afhankelijk zijn van de gehele sleutel (geen gedeeltelijke afhankelijkheid) . Een relatie met één attribuut als sleutel is automatisch in 2NF. Oftewel, repeterende attributen worden opgenomen in een aparte tabel.
- voldoet aan de eerste normaalvorm
- alle niet-sleutelattributen zijn volledig functioneel afhankelijk van de primaire sleutel.
Een voorbeeld
bewerkenHieronder nogmaals de tabel in 1NF van de platenzaak.
CD_ID | Albumtitel | Artiest | Sinds | Verschijningsjaar | Track | Single |
---|---|---|---|---|---|---|
4711 | Not That Kind | Anastacia | 1999 | 2000 | 1 | Not That Kind |
4711 | Not That Kind | Anastacia | 1999 | 2000 | 2 | I’m Outta Love |
4711 | Not That Kind | Anastacia | 1999 | 2000 | 3 | Cowboys & Kisses |
4712 | Wish You Were Here | Pink Floyd | 1965 | 1975 | 1 | Shine On You Crazy Diamond |
4713 | Freak of Nature | Anastacia | 1999 | 2001 | 1 | Paid my Dues |
De kolommen met betrekking tot de albums (in roze) kunnen als repeterende attributen gezien worden. Om te voorkomen dat deze data meerdere malen opgeslagen (of gewijzigd) moeten worden, komen deze in een aparte tabel. In de tabel met de overige velden (de singles) komt een verwijzing naar de cd waar deze op staan.
|
|
Het attribuut CD_ID is nu een vreemde sleutel die verwijst naar de primaire sleutel in de tabel CD. De informatie over de cd's is nu ondergebracht in een nieuwe tabel. Let wel, de artiesten worden bij 2NF niet in een aparte tabel gezet. Ook niet als ze meerdere malen voorkomen. Ze worden immers niet als een aparte entiteit gezien, maar slechts als attribuut van de cd.
Voordeel: Elk gegeven, cd of lied is nu slechts één keer opgeslagen en de relatie daartussen ligt ook slechts één keer vast. Het hoeft maar één keer ingevoerd en eventueel slechts één keer gewijzigd te worden.
Derde normaalvorm (3NF)
bewerkenEen relatie is in 3NF indien ze in 2NF is en geen transitieve afhankelijkheid kent.
- voldoet aan de tweede normaalvorm
- alle attributen die niet tot een sleutel behoren hangen niet af van een niet-sleutelattribuut
Een voorbeeld
bewerkenHieronder de tabel met de cd's:
CD_ID | Albumtitel | Verschijningsjaar | Artiest | Sinds |
---|---|---|---|---|
4711 | Not That Kind | 2000 | Anastacia | 1999 |
4712 | Wish You Were Here | 1975 | Pink Floyd | 1965 |
4713 | Freak of Nature | 2001 | Anastacia | 1999 |
Bij 2NF wordt er nog van uitgegaan dat een artiest een attribuut is van de cd. De artiesten en hun eerste optreden worden bij 3NF wél als aparte entiteit gezien. Hun eerste optreden is een attribuut van de artiest en het verschijningsjaar is volledig afhankelijk van de cd en daar een attribuut van.
|
|
|
In dit voorbeeld is geen enkel niet-sleutelattribuut (grijze cellen) afhankelijk van een ander niet-sleutelattribuut.
Voordeel: De data zijn niet meer redundant opgeslagen en de structuur van de data is meteen duidelijk, ook wanneer men de data zelf nog niet kent.
Boyce-Codd-normaalvorm (BCNF)
bewerkenEen relatie is in BCNF (Boyce-Codd Normal Form) als elke determinant een kandidaatsleutel is.
- voldoet aan de derde normaalvorm
- er zijn geen transitieve afhankelijkheden, dus geen enkele sleutel bevat informatie over een andere sleutel binnen dezelfde tabel, behalve over de gehele primaire sleutel
Een voorbeeld
bewerkenStel nu dat we het vorige voorbeeld iets complexer maken door te stellen dat een lied op meerdere cd's voor kan komen. Zoals te zien is, komt het nummer I'm Outta Love op twee verschillende cd's voor.
Albumtitel | Track | Artiest |
---|---|---|
Not That Kind | I'm Outta Love | Anastacia |
Not That Kind | Not That Kind | Anastacia |
Wish You Were Here | Shine On You Crazy Diamond | Pink Floyd |
Wish You Were Here | Have a Cigar | Pink Floyd |
Ultimate Collection | I'm Outta Love | Anastacia |
Ultimate Collection | Paid My Dues | Anastacia |
In deze tabel is het veld Artiest afhankelijk van het veld Track, maar Track is niet bruikbaar als primary key. Uit het veld Track valt immers niet af te leiden om welke Albumtitel het gaat.
In BCNF wordt dit opgelost door de tabel te splitsen in twee combinaties, Track en Artiest & Track en Albumtitel:
|
|
In dit voorbeeld bevat ieder niet-sleutelattribuut (grijs) alleen informatie over de gehele primaire sleutel (blauw).
Vierde normaalvorm (4NF)
bewerkenEen relatie is in 4NF als ze in BCNF staat en geen meerwaardige afhankelijkheden kent.
- voldoet aan de Boyce-Codd-normaalvorm
- bevat geen enkele meervoudige functionele afhankelijkheid
Een voorbeeld
bewerkenStel er is een database met daarin personen met huisdieren en auto's. De tabel is ontworpen met de gedachte dat elke persoon één huisdier heeft en één auto, maar dit blijkt niet het geval. Sommige mensen hebben meerdere huisdieren en anderen geen. Hetzelfde geldt voor het autobezit:
Persoon | Huisdier | Auto |
---|---|---|
Piet | Kat | Volkswagen |
Piet | Hond | Opel |
Piet | Kat | Opel |
Piet | Hond | Volkswagen |
Jan | Hond | Ford |
Er is geen afhankelijkheid tussen de huisdieren en de auto's. Als iemand meerdere huisdieren of auto's heeft dan ontstaat er meervoudige functionele afhankelijkheid. Immers, in het geval van Piet worden er vier regels aangemaakt, terwijl deze maar twee huisdieren en twee auto's heeft. Hierbij ontstaat een cartesisch product: Wanneer iemand bijvoorbeeld vijf huisdieren heeft en twee auto's dan worden er 5 x 2 = 10 regels aangemaakt. Om dit probleem op te lossen wordt de tabel opgesplitst in twee.
|
|
Voordeel: Er ontstaat geen cartesisch product.
Vijfde normaalvorm (5NF)
bewerken- voldoet aan de vierde normaalvorm
- elke relatie uit de join-afhankelijkheid bevat een sleutel voor de relatie
Een voorbeeld
bewerkenHieronder volgt een voorbeeld van een groep rondreizende verkopers. Elke verkoper verkoopt bepaalde producten van bepaalde merken.
Verkoper | Merk | Product |
---|---|---|
Piet | Acme | Stofzuiger |
Piet | Acme | Schroevendraaier |
Maria | Robusto | Schaar |
Maria | Robusto | Stofzuiger |
Maria | Robusto | Schroevendraaier |
Maria | Robusto | Paraplu |
Steven | Robusto | Stofzuiger |
Steven | Robusto | Telescoop |
Steven | Acme | Stofzuiger |
Steven | Acme | Lavalamp |
Steven | Nimbus | Kapstok |
Wanneer deze informatie in twee tabellen geplaatst zou worden met in achtneming van de vierde normaalvorm dan zou er bij het joinen het volgende probleem ontstaan. Er zijn immers geen twee maar drie relaties te onderscheiden:
- Verkoper - Product
- Verkoper - Merk
- Merk - Product
Nu is het zo dat verkoper Steven vier verschillende producten van drie verschillende merken verkoopt. Wanneer slechts aan de vierde normaalvorm was voldaan zou men bij een join zomaar tot de conclusie kunnen komen dat deze verkoper 3 x 4 = 12 verschillende producten verkoopt. Een andere foute conclusie zou zijn dat Maria stofzuigers verkoopt maar dat niet meer duidelijk is van welk merk. Om dit probleem het hoofd te bieden, worden de data in drie tabellen opgesplitst:
|
|
|
Zie ook
bewerken- ↑ Codd, E.F., A Relational Model of Data for Large Shared Data Banks, in Communications of the ACM 13 (6), pp 377-387, juni 1970
- ↑ Codd E.F., Further normalization of the Data Base Relational Model in Rustin, Randall J. (ed.), Data Base Systems, Courant Computer Science Symposia Series 6. Englewood Cliffs, N.J., Prentice-Hall, 1972
- ↑ Codd, E.F., Recent Investigations into Relational Data Base Systems, Proc. IFIP Congress, Stockholm, 1974
- ↑ Fagin, R., Multivalued Dependencies and a New Normal Form for Relational Databases, ACM Transactions on Database Systems 2 (3), sept 1977
- ↑ Fagin, R., Normal Forms and Relational Database Operators, ACM SIGMOD International Conference on Management of Data, May 31-June 1, 1979, Boston, Mass.
- Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Normalisierung (Datenbank) op de Duitstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.
- Normalization in DBMS: 1NF, 2NF, 3NF, BCNF, 4NF & 5NF op YouTube
- ↑ Zijn term elimineren is enigszins misleidend: er gaat geen informatie verloren tijdens normalisatie; hij doelde waarschijnlijk op de wiskundige betekenis van het elimineren van complexiteit of redundantie.