Databasenormalisatie

Uit Wikipedia, de vrije encyclopedie

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[bewerken | brontekst bewerken]

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:

  • 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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

Ted 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)[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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)[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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)[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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)[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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)[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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)[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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)[bewerken | brontekst bewerken]

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

Een voorbeeld[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]