Normalizzazione (informatica)

Da Wikipedia, l'enciclopedia libera.

In informatica la normalizzazione è un procedimento volto all'eliminazione della ridondanza informativa e del rischio di incoerenza dal database. Esistono vari livelli di normalizzazione (forme normali) che certificano la qualità dello schema del database.

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 taluni casi potrebbe comportare una perdita d'informazioni.

Dipendenze funzionali[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Dipendenza funzionale.

Una dipendenza funzionale è un particolare vincolo di integrità per il modello relazionale che descrive legami di tipo funzionale tra gli attributi di una relazione o tabella.

Tipologie di forma normale[modifica | modifica sorgente]

Una forma normale è una proprietà di una base di dati relazionale che ne garantisce la “qualità”.

Cosa deve garantire una decomposizione di una relazione[modifica | modifica sorgente]

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 = R1 join R2

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

Prima Forma Normale[modifica | modifica sorgente]

Definizione: Si dice che una base dati è in 1NF (prima forma normale) se vale la seguente relazione per ogni relazione contenuta nella base dati: una relazione è in 1NF se e solo se:

  1. non presenta gruppi di attributi che si ripetono (ossia ciascun attributo è definito su un dominio con valori atomici).
  2. esiste una chiave primaria (ossia esiste un insieme di attributi, che identifica in modo univoco ogni tupla della relazione)

Violazioni della 1NF (atomicità dei valori)[modifica | modifica sorgente]

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

Violazioni della 1NF (chiave primaria)[modifica | modifica sorgente]

Il seguente esempio viola la 1NF, perché pur non presentando gruppi di attributi che si ripetono, manca una chiave primaria, rendendo impossibile distinguere studentesse e studenti con lo stesso nome:

Voti
Studente Materia Semestre Voto
Pietro Basi di Dati 1 A
Pietro Basi di Dati 2 A
Pietro Basi di Dati 1 A
Pietro Basi di Dati 2 A
Sara Basi di Dati 1 B
Sara Basi di Dati 2 A

È necessario ristrutturare la relazione, per esempio, come segue:

Voti
Matricola Studente Materia Semestre Voto
nnnn-nnn-nn Pietro Basi di Dati 1 A
... Pietro Basi di Dati 2 A
... Pietro Basi di Dati 1 A
... Pietro Basi di Dati 2 A
... Sara Basi di Dati 1 B
... Sara Basi di Dati 2 A

Seconda Forma Normale[modifica | modifica sorgente]

Definizione: Una base dati è invece in 2NF (seconda forma normale) quando è in 1NF e per ogni tabella tutti i campi non chiave dipendono funzionalmente dall'intera chiave composta e non da una parte di essa.

Come esempio supponiamo di avere una tabella con gli esami sostenuti dagli studenti universitari. 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" si perderebbero le informazioni relative allo studente e all'esame superato
  • "Codice esame" si perderebbero le informazioni relative allo studente ed al corso di laurea a cui l'esame appartiene
  • "Matricola studente" si perderebbero le informazioni relative all'esame superato e al corso di laurea a cui lo studente è iscritto.
  • "Codice corso di laurea", "Codice esame" si perderebbero le informazioni relative allo studente che ha superato l'esame
  • "Codice corso di laurea", "Matricola studente" si perderebbero le informazioni relative all'esame superato
  • "Matricola studente", "Codice esame" si perderebbero le informazioni relative al Corso di Laurea di appartenenza.

Terza Forma Normale[modifica | modifica sorgente]

Definizione: Una base dati è in 3NF (terza forma normale) se è in 2NF e per ogni dipendenza funzionale non banale X \to Y è vera una delle seguenti condizioni:

  • X è una superchiave della relazione
  • Y è membro di una chiave della relazione

Quindi, una relazione si dice in terza forma normale (3FN) quando è innanzitutto in seconda forma normale e tutti gli attributi non-chiave dipendono dalla chiave soltanto, ossia non esistono attributi che dipendono da altri attributi non-chiave. Tale normalizzazione elimina la dipendenza transitiva degli attributi dalla chiave.

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

Forma Normale di Boyce e Codd[modifica | modifica sorgente]

Definizione: Una relazione R è in forma normale di Boyce e Codd (BCNF) se e solo se è in 3NF e, per ogni dipendenza funzionale non banale X \to Y, 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

Normalizzazione nella Forma Normale di Boyce-Codd[modifica | modifica sorgente]

Se lo schema non è in BCNF è possibile utilizzare un algoritmo detto di analisi che sostanzialmente scompone lo schema fino ad ottenere uno schema in 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.

Quarta Forma Normale[modifica | modifica sorgente]

Una base dati è detta invece essere in 4NF quando per ogni relazione di dipendenza funzionale molti a molti X Twoheadrightarrow.gif Y, X sia una superchiave.

Quinta Forma Normale[modifica | modifica sorgente]

Infine, una base dati si dice in 5NF se e solo se:

  • è in 4NF;
  • ogni relazione di dipendenza è implicata dalle chiavi candidate.

Limiti di 4NF e 5NF[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica