Normalizzazione: dipendenze funzionali, BCNF e terza forma normale

Una tabella che mescola informazioni su oggetti diversi funziona finché non si deve modificarla: allora i dati ripetuti vanno aggiornati ovunque, e prima o poi qualcuno se ne dimentica. La normalizzazione è la teoria che dice quando uno schema è ben fatto e come correggerlo. In questa lezione vediamo le anomalie con un esempio, le dipendenze funzionali e gli assiomi di Armstrong, la chiusura di un insieme di attributi e il test di chiave, il teorema di Heath con la dimostrazione, la forma normale di Boyce-Codd e la terza forma normale.

Le anomalie

Si consideri la tabella Esami(matricola, nome, codice, titolo, voto), che registra gli esami con il nome dello studente e il titolo del corso. Il nome di uno studente compare in ogni suo esame, il titolo di un corso in ogni esame di quel corso. Ne nascono tre anomalie:

• di aggiornamento: per correggere il titolo di un corso bisogna modificare centinaia di righe, e se se ne salta una i dati diventano incoerenti;
• di inserimento: non si può registrare un corso nuovo finché nessuno ne ha sostenuto l’esame, perché la chiave (matricola, codice) richiede una matricola;
• di cancellazione: cancellando l’ultimo esame di un corso si perde anche il suo titolo.

La causa è che la tabella rappresenta tre concetti (studenti, corsi, esami) in uno. La teoria delle dipendenze funzionali lo rende preciso.

Le dipendenze funzionali

Dati due insiemi di attributi e di una relazione, ( determina ) se due tuple uguali su sono sempre uguali anche su . Nell’esempio: matricola → nome, codice → titolo, (matricola, codice) → voto. Le dipendenze funzionali sono regole del mondo reale, come le cardinalità del modello E-R, e una chiave è proprio un insieme di attributi tale che tutti gli attributi, in modo minimale.

Da alcune dipendenze se ne deducono altre con gli assiomi di Armstrong:

• riflessività: se , allora ;
• arricchimento: se , allora ;
• transitività: se e , allora .

Sono corretti (deducono solo dipendenze vere) e completi (deducono tutte quelle che seguono dalle iniziali).

La chiusura e il test di chiave

La chiusura di un insieme di attributi è l’insieme di tutti gli attributi determinati da . Si calcola partendo da e aggiungendo, finché si può, il lato destro di ogni dipendenza il cui lato sinistro è già contenuto in . è una superchiave se e solo se contiene tutti gli attributi.

Nell’esempio, : si parte da {matricola, codice}, si aggiunge nome (da matricola), titolo (da codice), voto (dalla terza dipendenza): tutti gli attributi, quindi è una superchiave, e poiché né matricola né codice da soli bastano, è una chiave.

Decomporre senza perdere informazione

Normalizzare vuol dire decomporre una relazione in relazioni più piccole. Ma la decomposizione deve essere senza perdita: rimettendo insieme le parti con la giunzione naturale si deve ottenere esattamente la relazione di partenza, senza tuple spurie.

Teorema (Heath). Se una relazione soddisfa , allora la decomposizione in e è senza perdita: .

Dimostrazione. *.* Ogni tupla di ha la proiezione in e in , che si combinano di nuovo in . *.* Sia una tupla della giunzione. Viene da , proiezione di una tupla di , e da , proiezione di una tupla di . Le due tuple di sono uguali su , quindi per la dipendenza sono uguali su : . Allora appartiene a . ∎

Senza la dipendenza la decomposizione può creare tuple false: se a corrispondessero e , la giunzione combinerebbe ogni con ogni di , anche con quelli mai visti insieme.

Le forme normali

Una relazione è in forma normale di Boyce-Codd (BCNF) se, per ogni dipendenza non banale , è una superchiave. In parole: ogni fatto che la tabella registra dipende dalla chiave, tutta la chiave e nient’altro. La tabella Esami non è in BCNF, perché matricola → nome e matricola non è superchiave. Applicando il teorema di Heath due volte si ottengono Studenti(matricola, nome), Corsi(codice, titolo) ed Esami(matricola, codice, voto): tutte in BCNF, e le anomalie spariscono. È lo stesso schema che la progettazione E-R avrebbe dato direttamente (lezione sul modello E-R).

La decomposizione in BCNF è sempre possibile senza perdita, ma a volte perde una dipendenza: non si riesce più a controllarla dentro una sola tabella. Il caso tipico: in Lezioni(studente, materia, docente), ogni docente insegna una sola materia (docente → materia) e ogni studente ha un solo docente per materia ((studente, materia) → docente). Portandola in BCNF si separa (docente, materia) da (studente, docente), e la regola che lega studente e materia al docente non si verifica più in una sola tabella. La terza forma normale (3NF) è un po’ più permissiva: ammette anche se non è superchiave, purché faccia parte di una chiave. Si dimostra che ogni schema si può sempre portare in 3NF senza perdita e conservando tutte le dipendenze.

Nella pratica si normalizza fino alla 3NF o alla BCNF, e si denormalizza consapevolmente solo dove serve velocità di lettura, come nei data warehouse (lezione sui dati distribuiti), accettando la ridondanza in cambio di meno giunzioni.