Normalizzazione (informatica)

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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

Dipendenze funzionali[modifica | modifica wikitesto]

Magnifying glass icon mgx2.svgLo stesso argomento in dettaglio: 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 wikitesto]

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 wikitesto]

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:

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 wikitesto]

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. 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)[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Definizione: Una base dati è in 3NF (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 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[modifica | modifica wikitesto]

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 (con non in ), è 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

Mettiamolo in forma canonica .

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 wikitesto]

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
while che non è in BCNF per una dipendenza do
begin
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.

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

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 wikitesto]

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