La Normalizzazione
Mattia Natali 3 febbraio 2012
Indice
1 Ridondanze e anomalie 1
2 Dipendenze funzionali 2
3 Forme normali 2
3.1 Prima forma normale . . . 2
3.2 Seconda forma normale . . . 2
3.3 Terza forma normale . . . 2
4 Forma normale di Boyce e Codd 3 4.1 Definizione . . . 3
4.1.1 Considerazioni utili . . . 3
4.2 Decomposizione in forma normale di Boyce e Codd . . . 3
4.2.1 Decomposizione senza perdita . . . 3
4.2.2 Conservazione delle dipendenze . . . 3
1 Ridondanze e anomalie
Se creiamo relazioni che riuniscono concetti fra loro dismogenei possiamo incappare nelle seguenti anomalie:
• Ridondanza: è possibile che alcuni dati debbano essere ripetuti in diverse tuple.
• Anomalia di aggiornamento: siccome abbiamo dati ripetuti per aggiornare un dato dobbiamo cambiarlo per tutte le sue occorrenze.
• Anomalia di cancellazione: potrebbero insorgere problemi di cancellazione, ossia can- cellando una tupla cancelliamo anche altri dati non attinenti ad esso.
• Anomalia di inserimento: vorremmo aggiungere dei dati, ma siccome la tupla contie- ne attributi dismogenei potrebbe capitare di non sapere che aggiungere in questi campi (esempio aggiungo i dati anagrafici dell’impiegato ma la tupla pretende anche i valori della retribuzione di un progetto).
1
La Normalizzazione Base di Dati Mattia Natali
2 Dipendenze funzionali
Data una relazione r su uno schema R (X) e due sottoinsiemi di attributi non vuoti Y e Z di X, diremo che esiste su r una dipendenza funzionale tra Y e Z, se, per ogni coppia di tuple t1 e t2di r aventi gli stessi valori di attributi Y , risulta che t1 e t2 hanno gli stessi valori anche sugli attributi Z. Generalmente la dipendenza funzionare “Y determina Z” oppure “Z dipende funzionalmente da Y ” si scrive:
Y → Z
Una dipendenza funzionale Y → A si dice non banale se A non compare tra gli attributi di Y . Esempio di dipendenza funzionale banale:
impiegato, progetto→ progetto
Possiamo notare inoltre che se K è una chiave in una relazione r (tabella) allora esiste una dipendenza funzionale tra K e ogni altro attributo dello schema r proprio per definizione di chiave; la dipendenza funzionale quindi generalizza il concetto di chiave.
3 Forme normali
3.1 Prima forma normale
Gli attributi delle relazioni sono definiti su valori atomici e non su valori complessi quali insiemi o relazioni.
3.2 Seconda forma normale
Una relazione è in seconda forma normale se su di essa non sono definite dipendenze parziali, cioè dipendenze fra un sottoinsieme proprio della chiave e altri attributi. Esempio:
in questa relazione
Tabella (Impiegato, P rogetto, Stipendio, Budget)
abbiamo le dipendenze funzionali Impiegato → Stipendio e Progetto → Budget, ossia delle dipendenze parziali: non è in seconda forma normale.
3.3 Terza forma normale
Una relazione è in terza forma normale se su di essa non sono definite dipendenze transitive, cioè dipendenze della forma K → A, dove K è la chiave ed esiste un altro insieme di attributi X, non chiave, con le dipendenze K → X e X → A.
Formalmente: una relazione r è in terza forma normale se, per ogni dipendenza funzionale (non banale) X → A definita su di essa, almeno una delle seguenti condizioni è verificata:
• X contiene una chiave K di r;
• A appartiene ad almeno una chiave di r.
Questa forma può generare delle ridondanze ma ha il vantaggio di essere sempre ottenibile.
Per miglior qualità del progetto dovremmo tendere alla forma normale di Boyce e Codd, ma non è sempre possibile farlo.
2
La Normalizzazione Base di Dati Mattia Natali
4 Forma normale di Boyce e Codd
4.1 Definizione
Una relazione r è in forma normale di Boyce e Codd se per ogni dipendenza funzionale (non banale) X → A definita su di essa, X contiene una chiave K di r, cioè X è una superchiave per r. La forma normale di Boyce e Codd non è sempre raggiungibile.
4.1.1 Considerazioni utili
Intuitivamente una chiave è un insieme di attributi utilizzato per identificare univocamente le tuple di una relazione, formalmente:
• Un insieme K di attributi è una superchiave di una relazione r se r non contiene due tuple distinte t1e t2 con t1[K] = t2[K].
• K è chiave di r se è una superchiave minimale di r.
Inoltre quando parliamo di relazione stiamo parlando di una tabella in SQL.
4.2 Decomposizione in forma normale di Boyce e Codd
Se una relazione rappresenta più concetti indipendenti, allora va decomposta in relazioni più piccole, una per ogni concetto. Questo processo viene chiamato normalizzazione. In molti casi pratici la decomposizione può essere effettuata producento tante relazioni quante sono le dipendenze funzionali definite. Le decomposizioni dovrebbero sempre soddisfare le proprietà di decomposizione senza perdita e conservazione delle dipendenze.
4.2.1 Decomposizione senza perdita
r si decompone senza perdita su X1 e X2 se il join delle due proiezioni è uguale a r stes- sa; ossia una volta decomposta se facciamo il join tra le nuove relazioni ottenute dobbiamo riottenere esattamente r (non dobbiamo avere tuple in meno oppure tuple “spurie”).
Condizione sufficiente ma non necessaria: ogni volta che decomponiamo una relazione in due parti, se l’insieme degli attributi comuni è chiave per una delle due relazioni allora possiamo essere certi che tutte le istanze della relazione si decompongono senza perdita.
4.2.2 Conservazione delle dipendenze
Una decomposizione conserva le dipendenze dello schema originario se ciascuna delle di- pendenze funzionali dello schema originario coinvolge attributi che compaiono tutti insieme in uno degli schemi decomposti. Ossia se abbiamo una dipendenza progetto→ sede nello sche- ma originario non possiamo scindere in due tabelle in modo tale che il primo schema abbia solo progetto e la seconda solo sede perchè facendo ciò perdiamo un vincolo.
3