Normalisatie
Normaliseren Datamodellering 2008
1
Methodisch modelleren
Twee manieren:
bottom-up: normaliseren top-down: entity-relationship benadering
Deze week: normaliseren
gerelateerd aan de theorie van het relationele model maar ook als check bij ER-benadering
2/36
Normaliseren & DBMS-model
Normaliseren in de praktijk gekoppeld aan het relationele database model: tabellen Normaliseren vereist enige basiskennis van het relationele model
3/36
DMO 2008
1
Normalisatie
Historie relationele model
Ted Codd
IBM Engeland
A Relational Model of Data for Large Shared Data Banks (1970) → basis methodisch modelleren
daarvoor vooral pragmatisch bij bouwen van applicaties
Aanvankelijk verzet RDBMS ↔ IBM’s IMS/DB (hierarchisch DBMS) IBM geeft toe onder druk van klanten → System R (met SEQUEL)
Codd geeft wiskundige basis (publ.: Chris Date), o.a. normaliseren 4/36
Relationele tabel tabel = relatie
graad (degree)
*
cardinaliteit van de tabel
KlantNr
Init
Naam
Adres
Plaats
134
J.A.P.
Pieters
Westzoom 12
Breda
135
K.
Verhoog
Voorstraat 1
Utrecht
136
M.A.
Jansen
Zuidwal 3
Ede
etc.
etc.
etc.
etc.
etc.
cel (atomaire waarde) kolom = veld
)
rij = record = tuple records: verzameling → volgorde niet relevant voor het model 5/36
Relationele database
Relationele database: verzameling tabellen Relationele tabel
)
rechthoekig (dus ≠ spreadsheet tabel!)
Relationele operaties → tabel Tabellen gekoppeld via sleutels
primary key (pk) – foreign key (fk)
6/36
DMO 2008
2
Normalisatie
Identificering en koppeling
Eén veld (of een klein mogelijk combinatie van velden) = primary key → identificeert record Koppeling van records door verwijzing (primary key, foreign key) primary key foreign key
composite primary key KlantNr
Init
Naam
Adres
Plaats
134
J.A.P
Pieters
Westzoom 12
Breda
135
K.
Verhoog
Voorstraat 1
Utrecht
136
M.A.
Jansen
Zuidwal 3
Ede
KlantNr
Product
134
P23
134
P456
136
P003
7/36
Sleutels
Candidate key:
uniek niet-reduceerbare combinatie van attributen (indien composite) fungeert als determinant voor andere attributen in de tuple
Primary key (PK): een candidate key gekozen als identifier Foreign key (FK): kruisverwijzing naar primary key 8/36
Referentiële integriteit
Een foreign keywaarde moet altijd corresponderen met een bestaande primary keywaarde in de parent table of volledig NULL zijn.
Gebrekkige referentiële integriteit
9/36
DMO 2008
3
Normalisatie
Normaliseren: definities
“a technique for designing relational database tables to minimize duplication of information and, in so doing, to safeguard the database against certain types of logical or structural problems, namely data anomalies.” [Wikipedia] “the process of transforming data into well formed or natural groupings such that one fact is in one place and the correct relationships between facts exist.” [Avison & Fitzgerald] 10/36
Redundantie
Redundantie = onnodige dataduplicatie Voorbeeld: Suppliers-and-Parts: wat als een leverancier verhuist? S#
City
P#
Qty
S1 S1 S1 S2 S2 S3 S4 S4
London London London Paris Paris Paris London London
P1 P2 P3 P1 P2 P2 P2 P4
300 200 400 100 400 100 200 300 11/36
Meer redundantie-problemen anomalieën bij toevoegen en verwijderen
12/36
DMO 2008
4
Normalisatie
Samenvattend: normaliseren Data organiseren in tabellen, zó dat:
er minimale / geen redundantie is update-operaties (toevoegen, wijzigen, verwijderen) eenvoudig zijn uit te voeren records in een tabel te identificeren zijn m.b.v. een unieke sleutel (primary key) bij elkaar horende records gerelateerd zijn via primary-foreign key relaties 13/36
Normaliseren als techniek
Omvat een aantal stappen (= normaalvormen):
1NF 2NF 3NF BCNF 4NF 5NF 6NF
1NF 2NF 3NF BCNF 4NF 5NF 6NF
meestal voldoende: “relatie is genormaliseerd”
Centraal begrip: functionele afhankelijkheid
2NF veronderstelt, dat de dataset al in 1NF is, etc.
14/36
Functionele afhankelijkheid (1) S#
City
P#
Qty
S1 S1 S1 S2 S2 S3 S4 S4
London London London Paris Paris Paris London London
P1 P2 P3 P1 P2 P2 P2 P4
300 200 400 100 400 100 200 300
S#
City
P#
Qty
• S# is de determinant van City • City is functioneel afhankelijk van S# 15/36
DMO 2008
5
Normalisatie
Functionele afhankelijkheid (2) Given a relation R:
attribute Y of R is functionally dependent on attribute X if and only if each X-value in R has associated with it precisely one Y-value in R (at any one time).
in symbols, R.X → R.Y (read: “R.X functionally determines R.Y”)
Attributes X and Y may be composite. 16/36
Vooronderstellingen
Functionele afhankelijkheid kan ook te maken hebben met vooronderstellingen Jouw interpretatie van de requirements waar nodig expliciteren!
)
“Aangenomen: elke werknemer heeft niet meer dan één auto van de zaak” (als dit open wordt gelaten in de opgave)
Voor de opdrachten in deze cursus geldt: vermelding van vooronderstellingen = jouw toelichting bij de oplossing 17/36
Niet genormaliseerd Crse
Coursename
Level Mod
Mod-name
Status
Credits
B74
Comp Sci
Ba
B741
Program 1
Basic
8
B742
Hardware 1 Medium
11
Advanced
15
Basic
8
B94
Comp Apps
Ma
B743
Data Proc 1
B744
Program 2
B745
Hardware 2
B951
Information
B952
Web infosys
B741
Program 1
• Speadsheet format (GEEN relationele tabel) • Repeating groups: 1 Course-name met N Mod-names 18/36
DMO 2008
6
Normalisatie
Eerste normaalvorm (1NF) COURSE-DETAIL Crse
Coursename
Level
Mod
Mod-name
Status
Credits
B74
Comp Sci
Ba
B741
Program 1
Basic
8
B74
Comp Sci
Ba
B742
Hardware 1
Basic
8
B74
Comp Sci
Ba
B743
Data Proc 1
Basic
8
B74
Comp Sci
Ba
B744
Program 2
Medium
11
B74
Comp Sci
Ba
B745
Hardware 2
Medium
11
B94
Comp Apps
Ma
B951
Information
Advanced
15
B94
Comp Apps
Ma
B952
Web infosys
Advanced
15
B94
Comp Apps
Ma
B741
Program 1
Basic
8
• Relationele tabel, atomaire waarden in elke cel → geen repeating groups • Primary key: Crse Mod (composite) - candidate keys?
19/36
Notatie 1NF
COURSE-DETAIL (Crse, Course-name, Level, Mod, Mod-name, Status, Credits) Onderstreep primary keys Tabelnaam: hoofdletters Reeks velden tussen haakjes Veldnaam: kleine letters, evt. hoofdletter aan het begin 20/36
Naar tweede normaalvorm
Problemen met deze relatie in 1NF:
Redundantie veroorzaakt door de combinatie van Course en Module in één tabel → aparte tabel voor Module 2NF:
Relatie is in 1NF Alle niet-sleutel attributen zijn functioneel afhankelijk van de volledige sleutel (composite key!) 21/36
DMO 2008
7
Normalisatie
2NF – eerste stap COURSE-MODULE
MODULE
Crse
Coursename
Level
Mod
Mod
Mod-name
Status
Credits
B74
Comp Sci
Ba
B741
B741
Program 1
Basic
8
B74
Comp Sci
Ba
B742
B742
Hardware 1
Basic
8
B74
Comp Sci
Ba
B743
B743
Data Proc 1
Basic
8
Medium
11
B74
Comp Sci
Ba
B744
B745
Hardware 2
Medium
B745
B951
Information
Advanced
15
B952
Web infosys
Advanced
15
B741
Program 1
Basic
8
B74
Comp Sci
Ba
B94
Comp Apps
Ma
B951
B94
Comp Apps
Ma
B952
B94
Comp Apps
Ma
B741
B744
Program 2
11
2NF: “Every non-key column dependent on the entire PK” Is dat zo? 22/36
2NF - uitwerking
Stap 1:
COURSE-MODULE (Crse, Course-name, Level, Mod) MODULE (Mod, Mod-name, Status, Credits)
Stap 2:
(
COURSE (Crse, Course-name, Level) MODULE (Mod, Mod-name, Status, Credits) COURSE-MODULE (#Crse, #Mod)
Zet # vóór de foreign key! 23/36
2NF: nog steeds redundantie MODULE Status → Credits Redundantie, daarom naar 3NF
Mod
Mod-name
Status
B741
Program 1
Basic
Credits 8
B742
Hardware 1
Basic
8
B743
Data Proc 1
Basic
8
B744
Program 2
Medium
11
B745
Hardware 2
Medium
11
B951
Information
Advanced
15
B952
Web infosys
Advanced
15
24/36
DMO 2008
8
Normalisatie
Derde normaalvorm (3NF)
Relatie is in 2NF Geen functionele afhankelijkheid tussen niet-sleutelattrubuten = geen transitieve afhankelijkheid Credits via Status afhankelijk van Mod: Mod → Status → Credits
25/36
Notatie 3NF
In 2NF:
COURSE (Crse, Course-name, Level) MODULE (Mod, Mod-name, Status, Credits) COURSE-MODULE (#Crse, #Mod)
In 3NF:
COURSE (Crse, Course-name, Level) MODULE (Mod, Mod-name, #Status) STATUS (Status, Credits) COURSE-MODULE (#Crse, #Mod)
( 26/36
Hogere normaalvormen
Boyce-Codd Normal Form (BCNF): elke determinant = een candidate key 4NF: functionele afhankelijkheid oplossen tussen attributen binnen een composite key die uit 3 of meer velden bestaat Voorbeelden volgen
27/36
DMO 2008
9
Normalisatie
Normaliseren: samenvatting
(Informeel) genormaliseerd betekent:
Een tabel bevat data over slechts één thema (anders splitsen) Alle attributen zijn functioneel afhankelijk van de PK en ook alleen daarvan Een PK is minimaal Een FK verwijst naar een bestaande PK 28/36
Oefening 1: Fietsclub
Een fietsclub gaat elke zaterdag in groepjes van wisselende samenstelling erop uit; elk groepje rijdt een andere route naar keuze. Een groepje heeft een nummer (1 t/m 7; elke week gebruikt); een route een letter en een omschrijving. Niet-genormaliseerde dataverzameling: FIETSER (LidNr, Voornaam, Tussen, Achternaam, Adres, Woonplaats, Telefoon, E-mail, Datum_tocht, GroepsNr, Route_id, Route_omschr) Opdracht:
Breng de verzameling in 3NF Vermeld evt. vooronderstellingen Vermeld bij elke normalisatiestap de reden
29/36
Oefening 2: Vliegreizen Een vliegveld registreert voor vluchten (alfabetisch): Aandrijving: van het vliegtuig Geb_datum: geboortedatum passagier Maatschappij: vlieguigmaatschappij Opdracht: Naam: passagier • Zet dit in 3NF Pcode: plaatscode bestemming • Vermeld Plaats: plaatsnaam bestemming vooronderstellingen TicketNr: ticketnummer Type: type vliegtuig Vdatum: datum vlucht Vnr: vluchtnummer Vtijd: tijd vlucht Zitplaatsen: aantal zitplaatsen in vliegtuig 30/36
DMO 2008
10
Normalisatie
BCNF (1)
BCNF (Boyce-Codd Normal Form): Alle attributen in een relatie afhankelijk van elke candidate key, en niet alleen van de primary key (ofwel: elke determinant = candidate key)
Student
Module
Docent
De Vries
B741
Smits
De Vries
B742
Peters
Jansen
B741
Smits
Jansen
B742
Abels
Wel in 3NF, maar niet in BCNF: Docent → Module, maar Docent is geen candidate key! 31/36
BCNF (2)
Zo wel in BCNF: DOCENT
STUDENT-DOCENT
Module
Docent
Student
Docent
B741
Smits
De Vries
Smits
B742
Peters
De Vries
Peters
B742
Abels
Jansen
Smits
Jansen
Abels
32/36
4NF (1)
Deze tabel in in 3NF en BCNF, maar toch redundantie Probleem: multivalued dependencies (onafhankelijk van elkaar):
Module →→ Docent (module heeft een aantal docenten) Module →→ Handboek (module gebruikt een set handboeken)
Module
Docent
Handboek
B741
Smits
Database Fundamentals
B741
Smits
Introductie DMO
B741
Jansen
Database Fundamentals
B741
Jansen
Introductie DMO
B742
Smits
Database Fundamentals
B742
Smits
System Analysis
B742
Smits
Information Systems 33/36
DMO 2008
11
Normalisatie
4NF (2) Zo wel in 4NF:
MODULE-DOCENT
MODULE-HANDBOEK
Module
Docent
Module
Handboek
B741
Smits
B741
Database Fundamentals
B741
Jansen
B741
Introductie DMO
B742
Smits
B742
Database Fundamentals
B742
System Analysis
B742
Information Systems
34/36
Oefening 3: Pizzarestaurant Restaurant
Pizza Variety
Delivery Area
A1 Pizza
Thick Crust
Springfield
A1 Pizza
Thick Crust
Shelbyville
A1 Pizza
Thick Crust
Capital City
A1 Pizza
Stuffed Crust
Springfield
A1 Pizza
Stuffed Crust
Shelbyville
A1 Pizza
Stuffed Crust
Capital City
Elite Pizza
Thin Crust
Capital City
Elite Pizza
Stuffed Crust
Capital City
Vincenzo's Pizza
Thick Crust
Springfield
Vincenzo's Pizza
Thick Crust
Shelbyville
Vincenzo's Pizza
Thin Crust
Springfield
Vincenzo's Pizza
Thin Crust
Shelbyville
Opdracht: • Noteer afhankelijkheden • Normaliseer deze tabel (welke normaalvorm?) • Verklaar de oorzaak van de redundantie
35/36
Oefening 4: Klantgesprekken
FD:
(1) Staflid, Gesprek_datum, Gesprek_tijd → Klant (2) Kamer, Gesprek_datum, Gesprek_tijd → Klant, Staflid (3) Staflid, Gesprek_datum → Kamer
Welke candidate keys zijn er? Is deze relatie in BCNF? Zo niet, hoe dan wel? Klant
Gesprek_datum
Gesprek_tijd
Staflid
Kamer
76
18-09-2008
10.30
A
101
56
18-09-2008
12.00
A
101
74
18-09-2008
12.00
B
102
56
19-09-2008
10.30
A
102 36/36
DMO 2008
12
