Databasenormalisatie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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.

Er bestaan vijf normaalvormen, waarbij in de eerste normaalvorm (1NF) de eenvoudigste variant is en de vijfde (5NF) de meest complexe. Bij 1NF wordt de data in één of meerdere tabellen opgeslagen maar men maakt zich niet druk om de structuur, niet om de gebruikt 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 is de data voor een gebruiker echter lastiger te doorzoeken. Vaak wordt voor een tussenvorm gekozen, namelijk de 3NF.

Het beperken van de schijfruimte is belangrijk omdat bij de 1NF de tabellen vaak erg breed worden, dezelfde data wel erg vaak opgeslagen wordt terwijl tegelijkertijd veel velden in een kolom leeg gelaten worden. Dit heeft tot gevolg dat zoekalgoritmen meer tijd nodig hebben. Nog belangrijker is het om te voorkomen dat een gegeven meerdere malen wordt opgeslagen, daar dit tot fouten kan leiden. 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. Bij een hogere normaalvorm zijn ook de algoritmen die de data aanpassen efficiënter.

Normaalvormen[bewerken]

Hiërarchie van normaalvormen

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

Er zijn meerdere normaalvormen bekend, maar de meest gebruikte zijn de zogenaamde eerste, tweede, derde en vierde normaalvorm. 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.

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* procedure which we shall call normalization. Through decomposition nonsimple domains are replaced by "domains whose elements are atomic (nondecomposable) values."
* 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

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): Niet-genormaliseerde gegevens[bewerken]

Ieder niet gestructureerd gegevensbestand is in de nulde normaalvorm (0NF) of niet-genormaliseerd. Gegevens van verschillende soorten kunnen op elke regel voorkomen, hierdoor kunnen deze niet in kolommen worden opgedeeld.

Een voorbeeld:

verg. BRZZ, laptop mee!
di: combi naar garage
Jos jarig?

Eerste normaalvorm (1NF): Data ondergebracht in één of meer tabellen[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 is 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 komt. Alle data van een bedrijf zou 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]

Ter vergelijking: tabel uit het personeelsbestand van een fictief bedrijf in 0NF:

Naam Adres Salaris Afdeling
P.Jansen Stationsweg 14 Venlo Schaal 2: € 1503,00 Boekhouding
W.de Vries 't Steegke 23 Epe Schaal 1: € 1245,00 Kantine
T.Oud Dorpsstraat 1 Roermond Schaal 3: € 1789,00 Boekhouding

Bovenstaande data staat weliswaar in een tabel maar om te voldoen aan de 1NF zou het adres opgesplitst moeten worden, ook de salarisschaal en het salaris zouden in aparte kolommen moeten staan.

Diezelfde tabel uit het personeelsbestand van een fictief bedrijf in 1NF:

Naam Tussenvoegsel Initialen Straat Nr Plaats Afdeling Schaal Salaris
Jansen NULL P. Stationsweg 14 Venlo Boekhouding 2 1503
Vries de W. 't Steegke 23 Epe Kantine 1 1245
Oud NULL T. Dorpsstraat 1 Roermond Boekhouding 3 1789

Tweede normaalvorm (2NF): Repeterende attributen in een aparte tabel[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.

  • voldoet aan de eerste normaalvorm
  • alle niet-sleutelattributen zijn volledig functioneel afhankelijk van de primaire sleutel.

Een voorbeeld[bewerken]

Ter vergelijking: tabel uit het personeelsbestand van een fictief bedrijf in 1NF:

Naam Tussenvoegsel Initialen Straat Nr Plaats Provincie
Jansen NULL P. Stationsweg 14 Venlo Limburg
Vries de W. 't Steegke 23 Epe Gelderland
Vries - Zeilstra de A. 't Steegke 23 Epe Gelderland
Oud NULL T. Dorpsstraat 1 Roermond Limburg

Diezelfde data uit het personeelsbestand van een fictief bedrijf in 2NF:

Werknemer
Werknemer_ID Naam Tussenvoegsel Initialen Adres_ID
77 Jansen NULL P. 34
78 Vries de W. 45
79 Vries - Zeilstra de A. 45
80 Oud NULL T. 67
Adres
Adres_ID Straat Nr Plaats Provincie
34 Stationsweg 14 Venlo Limburg
45 't Steegke 23 Epe Gelderland
67 Dorpsstraat 1 Roermond Limburg

Het attribuut Adres_ID is nu een vreemde sleutel die verwijst naar de primaire sleutel in de tabel Adres. Adres is ondergebracht in een nieuwe tabel, omdat een adres niet onlosmakelijk verbonden is aan een persoon. Er kunnen immers meerdere personen op een adres wonen en mensen kunnen verhuizen. Let wel, de plaatsnamen en provincies 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 het adres.

Voordeel hiervan is dat elk gegeven, persoon en adres, slechts één keer wordt opgeslagen en de relatie daartussen ligt ook slechts één keer vast. Wanneer iemand verhuist hoeft het dus ook maar één keer aangepast te worden.

Derde normaalvorm (3NF)[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]

Ter vergelijking: tabellen uit het personeelsbestand van een fictief bedrijf in 2NF:

Werknemer
Werknemer_ID Naam Tussenvoegsel Initialen Adres_ID
77 Jansen NULL P. 34
78 Vries de W. 45
79 Vries - Zeilstra de A. 45
80 Dijk NULL D. 47
Adres
Adres_ID Straat Nr Plaats Provincie
34 Stationsweg 14 Venlo Limburg
45 't Steegke 23 Epe Gelderland
47 Straatweg 1 Apeldoorn Gelderland

Niet-sleutel Provincie hangt hier af van niet-sleutelattribuut Plaats en is in het geval van Gelderland dus redundant opgeslagen.

Diezelfde data uit het personeelsbestand van een fictief bedrijf in 3NF:

Werknemer
Werknemer_ID Naam Tussenvoegsel Initialen Adres_ID
77 Jansen NULL P. 34
78 Vries de W. 45
79 Vries - Zeilstra de A. 45
80 Dijk NULL D. 47
Adres
Adres_ID Straat Nr Plaats Provincie_ID
34 Stationsweg 14 Venlo 12
45 't Steegke 23 Epe 6
47 Straatweg 1 Apeldoorn 6
Provincie
Provincie_ID Provincie
12 Limburg
6 Gelderland

In dit voorbeeld is geen enkel niet-sleutelattribuut (grijze cellen) afhankelijk van een ander niet-sleutelattribuut. De waarden in de kolom Plaats komen niet herhalend voor en daarom worden de plaatsnamen niet in een aparte tabel opgenomen. In de praktijk zal men hier wel voor kiezen wanneer te verwachten valt dat een plaatsnaam in meerdere adressen op zal duiken.

Het voordeel van de 3NF is dat data niet meer redundant opgeslagen wordt en dat de structuur van de data meteen duidelijk is, ook wanneer men de data zelf nog niet kent.

Boyce-Codd-normaalvorm (BCNF)[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]

Een tabel uit een database met aannemers. In dit voorbeeld wordt aangenomen dat een werknemer niet bij twee aannemers hetzelfde werk mag doen, maar dat hij wel verschillende werkzaamheden mag uitvoeren bij verschillende bedrijven.

Aannemers
Naam Werk Aannemer
Janssen Loodgieter B.V. De Loden Gieter
Zeilstra Loodgieter B.V. De Loden Gieter
Zeilstra Elektromonteur Elektrobedrijf B.V.

In deze tabel zijn twee mogelijkheden voor primaire sleutels, namelijk de combinatie van Naam en Aannemer en de combinatie van Naam en Werk. In beide gevallen zal het overgebleven niet-sleutelattribuut informatie bevatten over een deel van de primaire sleutel en niet over de gehele primaire sleutel.

Diezelfde data uit een database met aannemers in BCNF:

Medewerkers
Naam Aannemer
Janssen B.V. De Loden Gieter
Zeilstra B.V. De Loden Gieter
Zeilstra Elektrobedrijf B.V.
Aannemers
Aannemer Werk
B.V. De Loden Gieter Loodgieter
Elektrobedrijf B.V. Elektromonteur

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

Vierde normaalvorm (4NF)[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

Vijfde normaalvorm (5NF)[bewerken]

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

Referenties[bewerken]

  1. 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
  2. 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
  3. Codd, E.F., Recent Investigations into Relational Data Base Systems, Proc. IFIP Congress, Stockholm, 1974
  4. Fagin, R., Multivalued Dependencies and a New Normal Form for Relational Databases, ACM Transactions on Database Systems 2 (3), sept 1977
  5. Fagin, R., Normal Forms and Relational Database Operators, ACM SIGMOD International Conference on Management of Data, May 31-June 1, 1979, Boston, Mass.

Zie ook[bewerken]