Normalizzazione (informatica)

In informatica la normalizzazione è un procedimento volto alla mitigazione di una serie di difetti sistematici di una base di dati relazionale.

Esistono vari livelli di normalizzazione, via via più stringenti, che se applicati correttamente portano la base di dati in una delle cosiddette "forme normali". Ovvero uno stato in cui risultano rispettati una precisa serie di vincoli di integrità, che garantiscono l'assenza, dimostrabile formalmente, di determinate classi di problemi.

Forme normali

Prima forma normale

Definizione: Si dice che una base dati è in 1NF (prima forma normale) se ogni relazione contenuta in essa è in 1NF; una relazione è in 1NF se e solo se:

1. Ciascun attributo è definito su un dominio con valori atomici (indivisibili);
2. Ogni attributo contiene un singolo valore da quel dominio.

Violazioni della 1NF (atomicità dei valori)

Il seguente esempio viola la 1NF, perché pur esistendo una chiave primaria ({Matricola,Materia}), l'attributo Voto non è definito su un dominio con valori atomici:

Voti

Matricola	Studente	Materia	Voto
0000-000-01	Pietro	Basi di Dati	1 sem, B ; 2 sem, F
0000-000-02	Pietro	Basi di Dati	1 sem, A ; 2 sem, A
0000-000-03	Sara	Basi di Dati	1 sem, B ; 2 sem, A

È necessario ristrutturare la relazione come segue:

Voti

Matricola	Studente	Materia	Semestre	Voto
0000-000-01	Pietro	Basi di Dati	1	B
0000-000-01	Pietro	Basi di Dati	2	F
0000-000-02	Pietro	Basi di Dati	1	A
0000-000-02	Pietro	Basi di Dati	2	A
0000-000-03	Sara	Basi di Dati	1	B
0000-000-03	Sara	Basi di Dati	2	A

Seconda forma normale

Definizione: Una base dati è invece in 2NF (seconda forma normale) quando è in 1NF e per ogni relazione tutti gli attributi non-chiave dipendono funzionalmente dall'intera chiave composta (ovvero la relazione non ha attributi che dipendono funzionalmente da una parte della chiave).

Come esempio supponiamo di avere una tabella con gli esami sostenuti dagli studenti universitari per diversi corsi di laurea. I campi di interesse potrebbero quindi essere i seguenti:

• "Codice corso di laurea"
• "Codice esame"
• "Matricola studente"
• "Voto conseguito"
• "Data superamento"

La tabella avrà quindi la seguente intestazione

id_corso_laurea

id_esame

id_studente

voto

data

La chiave candidata (tale terminologia è riservata alle superchiavi minimali, anche dette semplicemente chiavi) è rappresentata dalla tripla evidenziata, ossia da:

• "Codice corso di laurea"
• "Codice esame"
• "Matricola studente"

Essa infatti risulta essere l'insieme di chiavi minimale per poter identificare in modo univoco le tuple (i record) della tabella.

I campi "Voto conseguito" e "Data superamento", invece, sono campi non chiave, e fanno riferimento all'intera superchiave.

Difatti, se dipendessero solo da:

• "Codice corso di laurea" non potrebbero essere inseriti o reperiti i valori legati a diversi studenti per diversi esami superati
• "Codice esame" non potrebbero essere inseriti o reperiti i valori legati agli studenti ed al/ai corso di laurea
• "Matricola studente" non potrebbero essere inseriti o reperiti i valori legati ai diversi esame superati e ai corsi di laurea a cui gli studenti sono iscritti.
• "Codice corso di laurea", "Codice esame" non potrebbero essere inseriti o reperiti i valori legati ai diversi studenti che hanno superato l'esame per quel corso di laurea
• "Codice corso di laurea", "Matricola studente" non potrebbero essere inseriti o reperiti i valori legati ai diversi esami superati da uno studente iscritto ad un corso di laurea
• "Matricola studente", "Codice esame" non potrebbero essere inseriti o reperiti i valori legati ai diversi Corsi di Laurea sostenuti dagli studenti cui quell'esame può appartenere.

Terza forma normale

Definizione: Una base dati è in 3FN (terza forma normale) se è in 2NF e se tutti gli attributi non-chiave dipendono dalla chiave soltanto, ossia non esistono attributi non-chiave che dipendono da altri attributi non-chiave. Tale normalizzazione elimina la dipendenza transitiva degli attributi dalla chiave.

Per ogni dipendenza funzionale non banale $X\to Y$ almeno una delle seguenti condizioni è verificata:

• X contiene almeno una chiave K di r
• ogni attributo di Y appartiene ad almeno una chiave di r

Teorema: Ogni relazione può essere portata in 3NF.

Forma normale di Boyce e Codd

Definizione: Una relazione R è in forma normale di Boyce e Codd (BCNF) è anche in 3NF e, per ogni dipendenza funzionale non banale $X\to Y$ (con $Y$ non in $X$), $X$ è una superchiave per R.

Dato un insieme di relazioni, non è possibile garantire sempre il raggiungimento della BCNF; in particolare il mancato raggiungimento di questo obiettivo è indice che la base dati è affetta da un'anomalia di cancellazione (ossia è possibile perdere dati a seguito di un'operazione di cancellazione).

Es: Facciamo un esempio molto banale, se abbiamo uno schema relazionale $R<{ABCDE},{ABC\to DE}>$

Mettiamolo in forma canonica $ABC\to D,ABC\to E$.

Calcoliamo le chiavi: A, B e C non stanno a destra di nessuna dipendenza, quindi appartengono a tutte le chiavi

La chiusura di ABC è ABCDE quindi ABC è una chiave

Ora, visto che una chiave è una superchiave minimale (ovvero una superchiave con tutti attributi essenziali per derivare ogni attributo del sistema) lo schema relazionale è in BCNF

Limiti di 4NF e 5NF

La quarta e quinta forma normale, in realtà, raramente vengono utilizzate, in quanto ad un incremento di rigore nell'eliminazione della ridondanza corrisponde un degrado delle prestazioni (query di selezione o, peggio, modifica dei dati, richiedono molto più tempo per l'esecuzione).

Metodologie di normalizzazione

Decomposizione delle relazioni

Questo processo si fonda su un semplice criterio: se una relazione presenta più concetti tra loro indipendenti, la si decompone in relazioni più piccole, una per ogni concetto. Questo tipo di processo non è sempre applicabile in tutte le tabelle, dato che in alcuni casi potrebbe comportare una perdita d'informazioni.

Una decomposizione dovrebbe sempre soddisfare due proprietà:

• la decomposizione senza perdita, che garantisce la ricostruzione delle informazioni originarie
• la conservazione delle dipendenze, che garantisce il mantenimento dei vincoli di integrità originari.

Per "decomposizione senza perdita" si intende l'atto della manipolazione di una relazione R volta ad ottenere (eventualmente) due o più relazioni (ad esempio R1 e R2) che oltre a conservare le dipendenze funzionali verificano anche la seguente condizione: $R=R1joinR2$

Teorema: Sia data una relazione R(X), con X insieme degli attributi di R, e due sottoinsiemi A, B di X tali che A unito B coincide con X; siano inoltre R1 e R2 due relazioni rispettivamente su A e su B. Allora è condizione sufficiente affinché la decomposizione su A e B sia senza perdita se, detto C l'insieme intersezione tra A e B, è superchiave per R1(A) o R2(B).

Normalizzazione alla BCNF

Di seguito è presentato il più comune:

dati input R(T, F) // F copertura canonica

dati output p=(R1,...., Rm) // decomposizione di R in BCNF preservante i dati

begin

$\rho ={R_{1}(T_{1},F_{1})}$

$n=1$

while $\exists R_{i}(T_{i},F_{i})\in \rho$ che non è in BCNF per una dipendenza $X\to A$ do

begin

$n=n+1\,\!$

$T'=X^{+}\,\!$

$F'=\pi _{T'}(F_{i})\,\!$

$T''=T_{i}-(T'-X)\,\!$

$F''=\pi _{T''}(F_{i})\,\!$

$\rho =\rho -R_{i}(T_{i},F_{i})+\{R_{i}(T',F'),R_{n}(T'',F'')\}\,\!$

end

end

L'algoritmo in questione ha complessità esponenziale (per le proiezioni delle dipendenze funzionali), e produce una decomposizione che preserva i dati, sebbene non sia garantito che preservi anche le dipendenze.

Bibliografia

• Paolo Atzeni, Stefano Ceri, Piero Fraternali, Stefano Paraboschi e Riccardo Torlone, Basi di dati, 5ª ed., Milano, McGraw-Hill, 2018, ISBN 978-88-386-9445-5.

Voci correlate

• Denormalizzazione
• Data cleaning

Collegamenti esterni

• (EN) Normalizzazione, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL