Dipendenze funzionali e normalizzazione - BCNF e terza forma normale

Uno schema relazionale (Modello relazionale - relazioni, chiavi e vincoliIl modello relazionale (Codd, IBM, 1970) rappresenta i dati con relazioni, cioè tabelle, ed è basato su valori: i legami tra relazioni sono confronti di valori, non puntatori, il che garantisce indipendenza dalle strutture fisiche, portabilità e bidirezionalità. Una relazione matematica è un sottoinsieme del prodotto cartesiano di n domini (insieme di n-uple ordinate, senza duplicati né ordine tra le righe); una relazione del modello è un insieme di tuple, funzioni dagli attributi ai valori del dominio, quindi non posizionale. Si distinguono schema di relazione e istanza, schema di base di dati (relazioni più vincoli) e istanza. NULL è un valore speciale fuori da ogni dominio. I vincoli di integrità sono intra-relazionali (di dominio, di tupla, di chiave) e inter-relazionali (integrità referenziale, con la chiave esterna). Superchiave: insieme di attributi che non ripete mai i valori; chiave: superchiave minimale; ogni relazione ne ha almeno una (tutti gli attributi); la chiave primaria è una chiave scelta, senza NULL.Modello relazionale - relazioni, chiavi e vincoli →) può essere logicamente corretto ma di cattiva qualità: informazioni duplicate, aggiornamenti che richiedono molte modifiche, ricostruzioni sbagliate. La normalizzazione è il processo che analizza uno schema in base alle dipendenze funzionali e alle chiavi per minimizzare ridondanza, anomalie di aggiornamento e dati spuri. Si usa soprattutto quando lo schema è stato disegnato senza passare dall'ER: uno schema ER ben ristrutturato e tradotto (Ristrutturazione dello schema ER e traduzione nel modello relazionaleLa progettazione logica ha due passi. 1) Ristrutturazione dello schema ER, per togliere i costrutti che il modello relazionale non esprime: analisi delle ridondanze (attributi derivati e cicli di relazioni, decisa con volume dei dati e carico, tabelle di frequenza e accessi), eliminazione degli attributi multivalore (nuova entità), composti (appiattiti o nuova entità), delle IS-A (relazione con partecipazione (1,1) dalla sottoclasse) e delle generalizzazioni (opzione 1 relazioni, 2 accorpamento nel padre con attributo discriminante, 3 accorpamento nei figli, solo se completa e disgiunta), scelta degli identificatori principali (niente cicli di identificazione esterna), riscrittura dei vincoli esterni, partizionamento e accorpamento di entità. 2) Traduzione quasi automatica nel modello relazionale: ogni entità diventa una relazione con la chiave primaria data dall'identificatore principale (anche esterno); una relazione molti-a-molti diventa una relazione con le chiavi delle entità; una uno-a-molti con partecipazione obbligatoria si fonde con l'entità dal lato max 1 con una chiave esterna; con partecipazione opzionale si fonde (NULL) o si crea una relazione a parte; le uno-a-uno si fondono sul lato con partecipazione obbligatoria; le ternarie seguono la stessa logica con le chiavi di tutte le entità.Ristrutturazione dello schema ER e traduzione nel modello relazionale →) di solito è già normalizzato.

Linee guida informali

1. Semantica degli attributi. Una relazione deve essere facile da spiegare: non mescolare attributi di più entità o associazioni.

Schema di partenza (Impiegato, Dipartimento, Progetto): Impiegato(CF, Nome, DataNascita, Indirizzo, NDip), Dipartimento(NDip, Nome, CFDirettore), Progetto(NProg, Nome, Sede), Lavora(CF, NProg, Ore).

Due relazioni logicamente corrette ma di cattivo disegno: ImpDip(CF, Nome, DataNascita, Indirizzo, NDip, NomeDip, CFDirettore) e ImpProg(CF, NProg, Ore, NomeImp, NomeProg, SedeProg): mescolano concetti di entità diverse.

2. Ridondanza e anomalie di aggiornamento. In ImpDip i dati del dipartimento sono ripetuti per ogni impiegato:

• Anomalia di inserimento: per inserire un impiegato servono i dati del suo dipartimento, coerenti con quelli già presenti (o NULL se non ne ha uno); è difficile inserire un dipartimento senza impiegati.
• Anomalia di cancellazione: cancellando l'ultimo impiegato del dipartimento 4 (Neri) si perde l'informazione sul dipartimento.
• Anomalia di modifica: cambiando il nome del dipartimento 5 bisogna aggiornare tutte le righe dei suoi impiegati, altrimenti i dati sono incoerenti.

Linea guida: progettare in modo che non ci siano anomalie; se ce ne sono, annotarle e fare in modo che i programmi di aggiornamento operino correttamente.

3. Valori NULL. Se molti attributi non si applicano a tutte le tuple, ci sono molti NULL: sprecano spazio, perdono i diversi significati (non applicabile, sconosciuto, assente), complicano join (interno ed esterno danno risultati diversi) e aggregazioni. Non si vogliono togliere i NULL in assoluto, ma quelli sistematici: evitare attributi che spesso valgono NULL.

4. Niente tuple spurie. Si scompone in modo che le relazioni si possano riunire con join di uguaglianza su chiavi primarie o esterne, senza generare tuple inventate.

Esempio verificato. ImpProg(CF, NProg, Ore, NomeProg, SedeProg, NomeImp) con 5 tuple:

Si scompone in EmpProj1(CF, NProg, Ore, NomeProg, SedeProg) e EmpLocs(NomeImp, SedeProg) (le sedi dove lavora ogni impiegato, senza ripetizioni): 5 e 5 tuple. Il join naturale su SedeProg, che non è né chiave primaria né esterna, restituisce 9 tuple invece di 5: le 4 in più sono spurie, per esempio (123456, 1, 32.5, Prodotto X, Bellaire, Bianchi): Bianchi lavora a Bellaire, ma al progetto 1 con CF 123456 c'è Rossi. La scomposizione fa perdere informazione. Il controllo è stato eseguito con SQLite (5 tuple, join naturale 9 tuple, 4 spurie).

Forme normali: prerequisiti

Chiavi e attributi primi

Ricordare (Modello relazionale - relazioni, chiavi e vincoliIl modello relazionale (Codd, IBM, 1970) rappresenta i dati con relazioni, cioè tabelle, ed è basato su valori: i legami tra relazioni sono confronti di valori, non puntatori, il che garantisce indipendenza dalle strutture fisiche, portabilità e bidirezionalità. Una relazione matematica è un sottoinsieme del prodotto cartesiano di n domini (insieme di n-uple ordinate, senza duplicati né ordine tra le righe); una relazione del modello è un insieme di tuple, funzioni dagli attributi ai valori del dominio, quindi non posizionale. Si distinguono schema di relazione e istanza, schema di base di dati (relazioni più vincoli) e istanza. NULL è un valore speciale fuori da ogni dominio. I vincoli di integrità sono intra-relazionali (di dominio, di tupla, di chiave) e inter-relazionali (integrità referenziale, con la chiave esterna). Superchiave: insieme di attributi che non ripete mai i valori; chiave: superchiave minimale; ogni relazione ne ha almeno una (tutti gli attributi); la chiave primaria è una chiave scelta, senza NULL.Modello relazionale - relazioni, chiavi e vincoli →): superchiave $S$ se per ogni istanza $r$ e $t_1\ne t_2\in r$ vale $t_1[S]\ne t_2[S]$; chiave = superchiave minimale; ogni chiave è candidata, una è la primaria, le altre secondarie. Un attributo è primo se appartiene a almeno una chiave candidata, non primo altrimenti.

Dipendenza funzionale

Definizione (dipendenza funzionale, FD). Siano $X,Y$ insiemi di attributi di $R$. La dipendenza funzionale $X\to Y$ è un vincolo sulle istanze $r$ di $R$: $\forall t_1,t_2\in r:\ t_1[X]=t_2[X]\Rightarrow t_1[Y]=t_2[Y]$. Si dice che $X$ determina funzionalmente $Y$.

Osservazioni:

• Le FD sono una proprietà dello schema (della semantica), non di una singola istanza: un'istanza può soddisfarle per caso.
• Se $K$ è chiave di $R$, allora $K\to Y$ per ogni insieme $Y$ di attributi di $R$.
• $X\to Y$ non implica $Y\to X$.

Esempio (ImpProg): $\mathrm{CF}\to\mathrm{NomeImp}$; $\mathrm{NProg}\to\{\mathrm{NomeProg},\mathrm{SedeProg}\}$; $\{\mathrm{CF},\mathrm{NProg}\}\to\mathrm{Ore}$.

Regole di inferenza

Di solito si specificano le FD ovvie; ne valgono altre, che si ricavano con le regole di Armstrong:

Chiusura di un insieme di attributi

La chiusura $X^+$ è l'insieme degli attributi determinati da $X$ con le FD date. Algoritmo: partire da $X^+=X$; finché esiste una FD $V\to W$ con $V\subseteq X^+$ e $W\not\subseteq X^+$, aggiungere $W$. $X$ è una superchiave se $X^+$ contiene tutti gli attributi di $R$; una chiave è una superchiave minimale.

Esempio. In ImpProg(CF, NProg, Ore, NomeImp, NomeProg, SedeProg): $\mathrm{CF}^+=\{\mathrm{CF},\mathrm{NomeImp}\}$ (non basta). $\{\mathrm{CF},\mathrm{NProg}\}^+=\{\mathrm{CF},\mathrm{NProg},\mathrm{Ore},\mathrm{NomeImp},\mathrm{NomeProg},\mathrm{SedeProg}\}$: tutti, quindi {CF, NProg} è una superchiave, minimale (né CF né NProg da soli), quindi è l'unica chiave (calcolo verificato con un breve programma). Trucco: gli attributi che non compaiono mai a destra di una FD devono stare in ogni chiave.

Dipendenza completa e parziale

$X\to Y$ è completa (full) se nessun attributo si può togliere da $X$ mantenendo la dipendenza: $\forall A\in X:\ (X-A)\not\to Y$. È parziale se $\exists A\in X$ con $(X-A)\to Y$.

Nell'esempio: $\{\mathrm{CF},\mathrm{NProg}\}\to\mathrm{Ore}$ è completa; $\{\mathrm{CF},\mathrm{NProg}\}\to\mathrm{NomeImp}$ è parziale perché già $\mathrm{CF}\to\mathrm{NomeImp}$.

Dipendenza transitiva

$X\to Y$ è transitiva se esiste un insieme $Z$ che non è chiave né sottoinsieme di una chiave, con $X\to Z$ e $Z\to Y$.

In ImpDip(CF, Nome, DataNascita, Indirizzo, NDip, NomeDip, CFDirettore): $\mathrm{CF}\to\mathrm{NDip}$ e $\mathrm{NDip}\to\mathrm{CFDirettore}$, quindi $\mathrm{CF}\to\mathrm{CFDirettore}$ è transitiva tramite NDip (che non è chiave).

Le forme normali

Prima forma normale (1NF)

Definizione (1NF). Il dominio di ogni attributo contiene solo valori atomici (semplici, indivisibili) e il valore di ogni attributo di una tupla è un solo valore.

Storicamente vieta attributi multivalore, composti e loro combinazioni, e relazioni annidate (una tupla contiene una relazione). La rimozione di multivalore e composti nella ristrutturazione dell'ER garantisce già la 1NF.

Multivalore. Dipartimento(NDip, Nome, CFDirettore, Sedi) con Sedi = {Bellaire, Sugarland, Houston} non è in 1NF. Tre strategie:

1. togliere Sedi e metterlo in DeptSedi(NDip, Sede) con la chiave del dipartimento (la migliore);
2. estendere la chiave a {NDip, Sede}: introduce ridondanza;
3. se il numero massimo è noto, usare Sede1, Sede2, Sede3: introduce NULL e rende difficili le interrogazioni.

Relazione annidata. Imp(CF, Nome, Progetti(NProg, Ore)): si sposta la relazione annidata in una nuova relazione con la chiave propagata, Imp(CF, Nome) e ImpProg1(CF, NProg, Ore) (ricorsivamente se più livelli).

Seconda forma normale (2NF)

Definizione (2NF). $R$ è in 2NF se è in 1NF e ogni attributo non primo è in dipendenza completa da ogni chiave di $R$. Equivalente: nessun attributo non primo dipende da una parte di una chiave. Se ogni chiave ha un solo attributo, la 2NF è garantita.

ImpProg è in 1NF ma non in 2NF: NomeImp dipende da CF (parte della chiave {CF, NProg}), {NomeProg, SedeProg} da NProg. Si scompone, una relazione per ogni chiave parziale con i suoi dipendenti, mantenendo la relazione con la chiave originale e gli attributi completamente dipendenti:

EP1(CF, NProg, Ore), EP2(CF, NomeImp), EP3(NProg, NomeProg, SedeProg).

Terza forma normale (3NF)

Definizione (3NF). $R$ è in 3NF se è in 2NF e nessun attributo non primo è in dipendenza transitiva da una chiave. Intuitivamente: ogni FD con parte sinistra parte di una chiave o non chiave è un problema.

ImpDip è in 2NF (la chiave è CF, un solo attributo) ma non in 3NF per $\mathrm{CF}\to\mathrm{NDip}\to\mathrm{CFDirettore}$. Si scompone: ED1(CF, Nome, DataNascita, Indirizzo, NDip) e ED2(NDip, NomeDip, CFDirettore), con NDip chiave esterna di ED1 verso ED2.

Definizione equivalente (generale). $R$ è in 3NF se per ogni FD non banale $X\to A$ si ha: $X$ è una superchiave oppure $A$ è un attributo primo.

Forma normale di Boyce-Codd (BCNF)

Definizione (BCNF). $R$ è in BCNF se per ogni FD non banale $X\to A$ di $R$, $X$ è una superchiave.

La BCNF è più forte della 3NF (ogni relazione in BCNF è in 3NF): la 3NF tollera una FD $X\to A$ con $X$ non superchiave se $A$ è primo. Succede quando ci sono chiavi candidate sovrapposte.

Esempio. Iscrizione(Studente, Materia, Docente), FD: $\{\mathrm{Studente},\mathrm{Materia}\}\to\mathrm{Docente}$ (ogni studente segue un solo docente per materia) e $\mathrm{Docente}\to\mathrm{Materia}$ (ogni docente insegna una materia). Chiavi candidate: {Studente, Materia} e {Studente, Docente}; tutti gli attributi sono primi. È in 3NF (A=Materia è primo), ma non in BCNF perché Docente non è superchiave: la coppia (Docente, Materia) è ripetuta per ogni studente. Scomposizione BCNF: DocMat(Docente, Materia) e StDoc(Studente, Docente). Il join è senza perdita (l'intersezione {Docente} determina Materia, vedi sotto), ma la FD $\{\mathrm{Studente},\mathrm{Materia}\}\to\mathrm{Docente}$ non si può più controllare su una sola relazione: non è conservata.

(Calcolato con il programma: per Iscrizione chiavi {Studente, Docente} e {Studente, Materia}; $\mathrm{Docente}\to\mathrm{Materia}$ viola la BCNF ma non la 3NF.)

Riepilogo

Scomposizioni e proprietà

Scomponendo $R$ in $R_1,R_2$ si vuole:

• join senza perdita (lossless): $R_1\bowtie R_2=R$, senza tuple spurie. Condizione per due parti: $R_1\cap R_2\to R_1$ oppure $R_1\cap R_2\to R_2$ (l'intersezione è chiave di una delle due);
• conservazione delle dipendenze: ogni FD originale è controllabile su una delle relazioni (altrimenti per controllarla serve un join).

Algoritmo di scomposizione in BCNF. Finché esiste una relazione $R$ con una FD $X\to Y$ che viola la BCNF: si sostituisce $R$ con $R_1=X\cup Y$ e $R_2=R-(Y-X)$. Il join è sempre senza perdita; le dipendenze possono andare perse.

Sintesi in 3NF. Dato un insieme minimale di FD (parti destre singole, nessuna parte sinistra riducibile, nessuna FD ridondante): si crea una relazione per ogni FD $X\to A$ (raggruppando le FD con lo stesso $X$), si aggiunge una relazione con una chiave di $R$ se nessuna relazione contiene una chiave, si eliminano le relazioni contenute in altre. La 3NF si ottiene sempre con join senza perdita e conservazione delle dipendenze.

Per questo si arriva spesso alla 3NF, e alla BCNF solo se non si perdono dipendenze importanti. Il corso precisa che non serve normalizzare alla forma massima: per le prestazioni si può lasciare una relazione in una forma inferiore (per esempio la 2NF).

Un esercizio completo di normalizzazione, con il confronto con la traduzione dall'ER: Esercizio - Normalizzazione di libri, autori e case editrici (esercizio di normalizzazione).

Domande d'esame

1. Qual è la differenza tra 3NF e BCNF? Fare un esempio di relazione in 3NF ma non in BCNF. Traccia. BCNF: ogni FD non banale ha superchiave a sinistra; 3NF ammette anche che il lato destro sia un attributo primo. Esempio: Iscrizione(Studente, Materia, Docente) con {Studente, Materia}→Docente e Docente→Materia. Chiavi sovrapposte. La BCNF può perdere la FD {Studente, Materia}→Docente.

2. Calcolare la chiusura di un insieme di attributi e usarla per trovare le chiavi. Traccia. $X^+$ aggiunge ripetutamente i lati destri delle FD con lato sinistro contenuto in $X^+$; $X$ è superchiave se $X^+$ è l'intero schema; chiave = superchiave minimale.

3. Perché la scomposizione di EmpProj su Plocation è sbagliata? Traccia. Si unisce su un attributo che non è chiave: il join dà tuple spurie (9 invece di 5 nell'esempio) e perde informazione; una scomposizione deve essere senza perdita, con intersezione che determina una delle parti.