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

Hiërarchie van normaalvormen

Er 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:

• 1^e Normaalvorm (1NF)
• 2^e Normaalvorm (2NF)
• 3^e Normaalvorm (3NF)
• Boyce-Codd-Normalform (BCNF)
• 4^e Normaalvorm (4NF)
• 5^e Normaalvorm (5NF)

Waarvoor geldt: ${\text{1NF}}\subseteq {\text{2NF}}\subseteq {\text{3NF}}\subseteq {\text{BCNF}}\subseteq {\text{4NF}}\subseteq {\text{5NF}}$.

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

Om 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

Ted Codd formuleerde het idee van normalisatie in A Relational Model of Data for Large Shared Data Banks in 1970.

There is, in fact, a very simple elimination 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 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. 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 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 definieerde hij nog een nieuwe normaalvorm, de projection-join normal form (PJ/NF) of vijfde normaalvorm.

Nulde normaalvorm (0NF)

Ieder 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

Cd 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.

Cd_Lied

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)

Elke 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

De gegevens van de platenzaak in 0NF:

Cd_Lied

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_Lied

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)

Een 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

Hieronder nogmaals de tabel in 1NF van de platenzaak.

Cd_Lied

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.

Cd CD_ID Albumtitel Artiest Sinds Verschijningsjaar 4711 Not That Kind Anastacia 1999 2000 4712 Wish You Were Here Pink Floyd 1965 1975 4713 Freak of Nature Anastacia 1999 2001

Lied CD_ID Track Single 4711 1 Not That Kind 4711 2 I’m Outta Love 4711 3 Cowboys & Kisses 4712 1 Shine On You Crazy Diamond 4713 1 Paid my Dues

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)

Een 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

Hieronder de tabel met de cd's:

Cd

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.

Cd CD_ID Albumtitel Verschijningsjaar Artiest_ID 4711 Not That Kind 2000 311 4712 Wish You Were Here 1975 312 4713 Freak of Nature 2001 311

Artiest Artiest_ID Naam Sinds 311 Anastacia 1999 312 Pink Floyd 1965

Lied CD_ID Track Single 4711 1 Not That Kind 4711 2 I’m Outta Love 4711 3 Cowboys & Kisses 4712 1 Shine On You Crazy Diamond 4713 1 Paid my Dues

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)

Een 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

Stel 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.

Cd

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:

Cd Albumtitel Track Not That Kind I'm Outta Love Not That Kind Not That Kind Wish You Were Here Shine On You Crazy Diamond Wish You Were Here Have a Cigar Ultimate Collection I'm Outta Love Ultimate Collection Paid My Dues

Tracks Track Artiest I'm Outta Love Anastacia Not That Kind Anastacia Paid My Dues Anastacia Shine On You Crazy Diamond Pink Floyd Have a Cigar Pink Floyd

In dit voorbeeld bevat ieder niet-sleutelattribuut (grijs) alleen informatie over de gehele primaire sleutel (blauw).

Vierde normaalvorm (4NF)

Een 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

Stel 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:

Bezittingen

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.

Huisdieren Persoon Dier Piet Kat Piet Hond Jan Hond

Voertuigen Persoon Auto Piet Volkswagen Piet Opel Jan Ford

Voordeel: Er ontstaat geen cartesisch product.

Vijfde normaalvorm (5NF)

• voldoet aan de vierde normaalvorm
• elke relatie uit de join-afhankelijkheid bevat een sleutel voor de relatie

Een voorbeeld

Hieronder volgt een voorbeeld van een groep rondreizende verkopers. Elke verkoper verkoopt bepaalde producten van bepaalde merken.

Aangeboden producten per merk en verkoper

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:

Producten per verkoper Verkoper Product Piet Stofzuiger Piet Schroevendraaier Maria Schaar Maria Stofzuiger Maria Schroevendraaier Maria Paraplu Steven Telescoop Steven Stofzuiger Steven Lavalamp Steven Kapstok

Merken per verkoper Verkoper Merk Piet Acme Maria Robusto Steven Robusto Steven Acme Steven Nimbus

Producten per merk Merk Product Acme Stofzuiger Acme Schroevendraaier Acme Lavalamp Robusto Schaar Robusto Stofzuiger Robusto Schroevendraaier Robusto Paraplu Robusto Telescoop Nimbus Kapstok

Zie ook

• Denormalisatie
• Data Vault

· ·

Databases

databasemanagementsysteem · databasemodel · databasenormalisatie · referentiële integriteit · relationele algebra · relationele database · relationeel model