Normalizzazione

Fin qui abbiamo raggruppato gli attributi in tabelle usando il buon senso e la traduzione dallo schema E-R. Ma «buon senso» non è un criterio verificabile: serve un modo formale per dire perché un raggruppamento è migliore di un altro.

Quel modo esiste e si basa sulle dipendenze funzionali. Da esse si ricavano le forme normali, cioè proprietà che certificano l'assenza di certi difetti, e gli algoritmi per ottenerle. Attenzione però: la normalizzazione è una tecnica di verifica, non una metodologia di progetto. Serve a controllare il lavoro fatto, non a sostituirlo.

Perché normalizzare

Le anomalie

Partiamo da una tabella sbagliata, che mette insieme informazioni eterogenee: gli impiegati con il loro stipendio, i progetti con il loro bilancio, e la funzione svolta da ciascun impiegato in ciascun progetto.

I difetti sono quattro, e hanno tutti lo stesso nome tecnico:

Tre linee guida

1. Semplice è bello. Uno schema deve essere facile da spiegare: se corrisponde a una sola entità o a una sola associazione, il suo significato è ovvio. Se mescola concetti, nasce ambiguità semantica.
2. Niente anomalie. E se per ragioni di efficienza si decide di tenerne, vanno documentate e gestite dai programmi che aggiornano i dati.
3. Pochi NULL. Un attributo quasi sempre nullo è un attributo che sta nella tabella sbagliata.

Dipendenze funzionali

Definizione

Dati uno schema R(X) e due sottoinsiemi non vuoti Y e Z di X, esiste la dipendenza funzionale Y → Z se, in ogni istanza valida, due tuple che hanno gli stessi valori su Y hanno gli stessi valori anche su Z.

Nell'esempio precedente le dipendenze sono tre, e corrispondono a tre fatti del mondo reale:

La chiave della relazione è (Impiegato, Progetto). Nota il legame con le anomalie: le due dipendenze la cui parte sinistra non è chiave sono proprio quelle che generano ripetizioni. La terza, la cui sinistra è la chiave, non causa problemi. Questa osservazione è il cuore di tutta la teoria.

Dipendenze particolari

• Banale: sempre soddisfatta, perché la parte destra è contenuta nella sinistra (AB → A).
• Completa: Y → Z vale ma nessun sottoinsieme proprio di Y determina già Z. Se la parte sinistra si può ridurre, la dipendenza contiene un attributo estraneo.
• Superchiave: se Y determina tutti gli attributi dello schema, allora Y è una superchiave; se in più è minimale, è una chiave.

Gli assiomi di Armstrong

Un insieme F di dipendenze ne implica logicamente altre: se valgono Impiegato → Categoria e Categoria → Stipendio, allora vale necessariamente Impiegato → Stipendio. La definizione di implicazione («per ogni istanza…») non è utilizzabile in pratica; Armstrong ha dato tre regole che permettono di derivare costruttivamente tutte e sole le dipendenze implicate.

Le tre regole sono corrette (producono solo dipendenze implicate), complete (le producono tutte) e minimali (togliendone una si perde la completezza). Da esse se ne derivano altre, comodissime nei conti:

La chiusura di un insieme di attributi

Calcolare F⁺, cioè tutte le dipendenze implicate, costa un tempo esponenziale. Fortunatamente quasi sempre non serve: basta sapere se una certa dipendenza è implicata, e per questo esiste uno strumento efficiente, la chiusura di un insieme di attributi.

L'algoritmo è elementare: si parte da X⁺ = X e finché qualcosa cambia, per ogni dipendenza W → V con W già dentro X⁺ si aggiunge V.

// R(T, F), X ⊆ T
X⁺ ← X
while (X⁺ cambia)
    for each (W → V) in F
        if W ⊆ X⁺ and V ⊄ X⁺
            X⁺ ← X⁺ ∪ V
return X⁺

Esempio. R(ABCDE) con F = {A→B, BC→D, B→E, E→C}. Calcoliamo A⁺: si parte da A; con A→B si arriva ad AB; con B→E ad ABE; con E→C ad ABCE; ora BC ⊆ ABCE, quindi con BC→D si arriva ad ABCDE. Conclusione: A⁺ = ABCDE, cioè A è superchiave, e siccome è un singolo attributo è anche chiave.

Trovare le chiavi

Con la chiusura si verifica un candidato; per trovarle tutte si procede così:

1. gli attributi che compaiono solo a sinistra delle dipendenze (o che non compaiono affatto) stanno in tutte le chiavi: chiamiamo N questo insieme;
2. gli attributi che compaiono solo a destra non stanno in nessuna chiave;
3. si calcola N⁺: se copre tutto lo schema, N è l'unica chiave;
4. altrimenti si aggiunge a N un attributo alla volta fra i rimanenti, poi coppie, e così via, controllando ogni volta la chiusura e scartando i sovrainsiemi di chiavi già trovate.

Laboratorio

Calcolatore di chiusure, chiavi e forme normali

Scrivi lo schema e le dipendenze: il calcolatore mostra la chiusura passo per passo, tutte le chiavi, e verifica BCNF e 3NF spiegando quali dipendenze le violano. Usa una lettera per attributo.

Equivalenza e coperture

Quando due insiemi di dipendenze dicono la stessa cosa

Due insiemi F e G sono equivalenti (F ≡ G) se F⁺ = G⁺; ciascuno si dice copertura dell'altro. Verificarlo con le chiusure degli insiemi sarebbe esponenziale, ma c'è la scorciatoia: per ogni X → Y di F basta controllare che Y ⊆ X⁺ calcolata usando G, e viceversa. Tutto polinomiale.

Esempio. F = {A→C, AC→D, E→AD, E→H} e G = {A→CD, E→AH}. Usando G: A⁺ = ACD (contiene C e D, quindi A→C e AC→D sono coperte) ed E⁺ = EADCH (contiene A, D e H). Usando F: A⁺ = ACD ed E⁺ = EADHC. I due insiemi sono equivalenti.

Copertura minimale

Una copertura minimale è un insieme equivalente in cui:

1. ogni parte destra ha un solo attributo;
2. non ci sono attributi estranei nelle parti sinistre;
3. non ci sono dipendenze ridondanti.

Un attributo A è estraneo in X → Y se togliendolo la dipendenza continua a valere; una dipendenza è ridondante se è implicata dalle altre. L'algoritmo procede in tre fasi nell'ordine indicato, e l'ordine conta: eliminando prima le dipendenze ridondanti si può restare bloccati con attributi estranei non più eliminabili.

// 1. parti destre singole: X → AB diventa X → A, X → B
// 2. attributi estranei
for each (X → A) in G
    for each B in X
        if A ∈ (X − B)⁺ then sostituisci X con X − B
// 3. dipendenze ridondanti
for each f in G
    if f ∈ (G − f)⁺ then togli f

Esempio. F = {AB→C, B→A, C→A}. In AB→C, l'attributo A è estraneo perché B⁺ = BAC contiene già C: resta {B→C, B→A, C→A}. Ora B→A è ridondante, perché da B→C e C→A si ottiene per transitività. Copertura minimale: {B→C, C→A}. Nota che la copertura minimale non è unica.

Forme normali

Forma normale di Boyce-Codd

L'idea: una dipendenza X → A dice che esiste una collezione di entità identificate da X. Se X non è chiave della relazione, allora dentro quella relazione stiamo descrivendo due collezioni diverse, e i fatti dell'una si ripetono per ogni fatto dell'altra: ecco la ridondanza.

La definizione parla di F⁺, ma per fortuna vale un teorema: basta controllare le dipendenze di F. La verifica è quindi polinomiale.

for each (X → Y) in F
    if Y ⊄ X // non banale
       and T ⊄ X⁺ // X non è superchiave
        return false
return true

Sulla tabella degli impiegati: Impiegato → Stipendio ha la sinistra che non è superchiave (la chiave è Impiegato+Progetto) → non è in BCNF. La cura intuitiva è staccare ogni dipendenza colpevole in una relazione a parte:

Decomposizioni: due cose da non perdere

Decomporre è facile; decomporre bene no. Una decomposizione deve conservare due cose.

1. I dati. Ricomponendo le proiezioni con un join naturale si deve riottenere esattamente l'istanza di partenza. In generale si ottiene un sovrainsieme: le tuple in più (dette spurie) sono informazione falsa.

Controesempio classico: R(Impiegato, Progetto, Sede) con Impiegato→Sede e Progetto→Sede, decomposta in (Impiegato, Sede) e (Progetto, Sede). L'attributo comune è Sede, che non è chiave di nessuna delle due: ricomponendo compaiono coppie impiegato-progetto che non erano mai esistite.

2. Le dipendenze. Ogni vincolo originario deve restare verificabile dentro una singola relazione, altrimenti per controllarlo servirebbe un join a ogni inserimento. Formalmente: l'unione delle proiezioni di F sui frammenti deve essere equivalente a F.

Algoritmo di decomposizione in BCNF

ρ ← { R(T, F) }
while esiste Rᵢ(Tᵢ, Fᵢ) in ρ non in BCNF
    scegli (X → A) in Fᵢ non banale con X non superchiave
    R1 ← Rᵢ(Tᵢ − A)
    R2 ← Rᵢ(X ∪ A)
    ρ ← ρ − {Rᵢ} ∪ {R1, R2}
return ρ

L'algoritmo termina sempre, produce frammenti in BCNF e preserva i dati (l'attributo comune X è chiave di R2). Non garantisce però di preservare le dipendenze.

Esempio. Telefoni(Prefisso, Numero, Località) con Prefisso,Numero → Località e Località → Prefisso. La seconda viola la BCNF; decomponendo si ottiene (Numero, Località) e (Località, Prefisso): schema in BCNF, dati preservati, ma la dipendenza Prefisso,Numero → Località è andata perduta, perché i suoi attributi ora stanno in relazioni diverse.

Terza forma normale

Quando la BCNF costa troppo si scende di un gradino.

La 3NF è meno restrittiva: BCNF ⟹ 3NF, non il contrario. In cambio di un po' di ridondanza residua offre una garanzia che la BCNF non ha: esiste sempre una decomposizione in 3NF che preserva sia i dati sia le dipendenze, calcolabile in tempo polinomiale.

Esempio. R(Dirigente, Progetto, Sede) con Dirigente → Sede e Progetto,Sede → Dirigente. Le chiavi sono (Progetto, Sede) e (Dirigente, Progetto). Dirigente → Sede viola la BCNF perché Dirigente non è superchiave; ma Sede è un attributo primo (sta nella prima chiave), quindi la relazione è in 3NF. La ridondanza residua è la sede del dirigente ripetuta per ogni suo progetto.

Sintesi in 3NF

L'algoritmo si chiama "di sintesi" perché costruisce le relazioni a partire dalle dipendenze, invece di spezzare quella iniziale.

1. calcola una copertura minimale G di F;
2. raggruppa in G le dipendenze con la stessa parte sinistra: X→A₁, …, X→Aₕ diventa X→A₁…Aₕ;
3. per ogni X→Y crea una relazione con attributi XY e chiave X (detta chiave sintetizzata);
4. elimina le relazioni i cui attributi sono contenuti in un'altra;
5. se nessuna relazione contiene una chiave di R, aggiungine una formata da una chiave di R (serve a non perdere i dati).

Esempio. R(ABCD) con F = {AB→C, C→D, D→B}, già minimale. Si ottengono R₁(ABC) con chiave AB, R₂(CD) con chiave C, R₃(BD) con chiave D. Nessuna è contenuta in un'altra, e R₁ contiene la chiave AB di R: la decomposizione è completa, in 3NF, e preserva dati e dipendenze.

Esercizi svolti

Verifica e decomposizione

Riconoscere le anomalie