NORMALIZZAZIONE DELLE RELAZIONI IN UN DATABASE
di Marco Bonora (1)

Unità di apprendimento per la scuola secondaria di 2° grado

Introduzione
Di seguito si illustra la pianificazione di una Unità di Apprendimento riguardo la Normalizzazione dei Databasestudiato per una quinta classe di un Istituto Tecnico Industriale.

Prerequisiti

• Concetti e nozioni di teoria degli insiemi: insieme, elemento, sottoinsieme, unione, intersezione, prodotto cartesiano.
• Nozioni di base di informatica: dato, hardware, software, utente.
• Conoscenza dei database relazionali

Obiettivi formativi

• Comprendere l’utilità e la fruibilità dell’algebra.
• Comprendere la differenza tra dati e informazioni.
• Comprendere l’importanza delle relazioni univoche tra le informazioni in un archivio

Obiettivi specifici di apprendimento

Conoscenze

• Conoscere le varie forme di normalizzazione
• Conoscere le gerarchie tra le differenti forme di normalizzazione
• Conoscere l’importanza della normalizzazione nella progettazione di un database
• Comprendere le motivazioni e le regole di normalizzazione

Capacità

• Essere in grado di organizzare un insieme di dati nella struttura del database relazionale
• Saper individuare ed eliminare le ridondanze in un database
• Saper progettare un database normalizzato

Atteggiamenti

• Sviluppare le abilità per la gestione delle relazioni tra teoria e pratica adattando le proprie competenze in contesti interdisciplinari

Metodo
Lezione frontale con supporto in Power Point, discussione guidata, attività laboratoriale.

Strumenti
Laboratorio, testo in adozione, dispense e diapositive animate.

Verifiche insegnamento-apprendimento
Le verifiche in itinere e finali, effettuate attraverso osservazioni, interviste, ed esercitazioni laboratoriali, saranno utilizzate per la valutazione dell’apprendimento dei singoli allievi.

Modalità e tempi del percorso didattico
I contenuti dell’unità di apprendimento verranno proposti in seguito alla spiegazione della gestione di un archivio di dati e del modello relazionale dei database.

• Esame dei prerequisiti: 1 ora;
• 1° Presentazione Power Point (lezione frontale): 2 ore;
• 1° esercitazione in Laboratorio in itinere: 4 ore;
• 2°Presentazione Power Point (lezione frontale): 2 ore;
• 2° esercitazione in Laboratorio in itinere: 4 ore;
• Test finale di verifica: 3 ore

Tempo totale = 16 ore 3-4 settimane.

Dispense per lo studente

Introduzione
La teoria della normalizzazione è costruita attorno al concetto di forme normali. Una relazione è detta essere in una particolare forma normale se soddisfa un certo insieme di condizioni. I principi della normalizzazione rappresentano strumenti per controllare la struttura dei dati. Originariamente Codd definì prima, seconda e terza forma normale (abbreviate in 1NF, 2NF e 3NF), ma la terza fu rivisitata da Boyce e Codd che ne formularono una più forte, nel senso che ogni relazione che soddisfa la nuova versione della terza forma normale soddisfa sicuramente anche la vecchia, ma non il viceversa. La nuova versione viene chiamata forma normale di Boyce e Codd (BCNF), per essere distinta dalla vecchia. In seguito, Fagin definì una nuova quarta forma normale (abbreviata in 4NF e chiamata “quarta” perché a quel tempo quella di Boyce e Codd era ancora chiamata terza). Più recentemente, Fagin ne ha definito un’altra, che ha chiamato projection-join normal form (PJ/NF) conosciuta anche come quinta forma normale (5NF). Infine, l’ultima forma normale definita è conosciuta come la Domain Key Normal Form . Le forme normali specificano regole via via sempre più stringenti per la struttura delle relazioni; ciascuna forma estende la precedente (vedi figura 1) in modo da evitare ridondanze e determinati tipi di anomalie di aggiornamento. Prima di definire le diverse forme normali, introduciamo i problemi per i quali esse sono state create.

• lo stipendio di ciascun impiegato è unico ed è funzione del solo impiegato, indipendentemente dai progetti a cui partecipa;
• il bilancio di ciascun progetto è unico e dipende dal solo progetto, indipendentemente dagli impiegati che vi partecipano.
• L’abbreviazione dipende esclusivamente dalla funzione.

Queste hanno alcune conseguenze sul contenuto della relazione e sulle operazioni che si possono effettuare su di essa. Ad esempio, riguardo alla proprietà A:

• il valore dello stipendio di ciascun impiegato è ripetuto in tutte le tuple relative all’impiegato: si ha quindi una ridondanza; se per esempio un impiegato partecipasse a trenta progetti, il suo stipendio verrebbe ripetuto trenta volte;
• se lo stipendio di un impiegato varia, è necessario andarne a modificare il valore in tutte le tuple corrispondenti, affinché la dipendenza continui a valere; questo inconveniente va sotto il nome di anomalia di aggiornamento;
• se un impiegato interrompe la partecipazione a tutti i progetti senza lasciare l’azienda, tutte le tuple che lo riguardano vengono eliminate, pertanto non è possibile conservare traccia del suo nome e del suo stipendio; questo problema viene indicato come anomalia di cancellazione;
• infine, un nuovo impiegato al quale non sia ancora stato assegnato alcun progetto non può essere inserito nella relazione; si ha quindi una anomalia di inserimento.

Analoghe considerazioni valgono per la proprietà B e C. Una motivazione della presenza di questi inconvenienti è che abbiamo usato un’unica relazione per rappresentare informazioni eterogenee. In particolare, nella relazione sono rappresentati gli impiegati con i relativi stipendi, i progetti con i relativi bilanci e le partecipazioni degli impiegati ai progetti con le relative funzioni.

Generalizzando, possiamo trarre le seguenti conclusioni:

• è possibile che alcuni dati siano ripetuti in diverse tuple senza aggiungere informazioni significative;
• se alcune informazioni sono ripetute in modo ridondante, il relativo aggiornamento deve essere ripetuto per ciascuna occorrenza dei relativi dati;
• la cancellazione di una tupla, motivata dal fatto che non è più valido l’intero insieme di concetti da essa espressi, può comportare l’eliminazione di tutti i concetti in questione, anche quelli che conservano la loro validità e sono ancora un dato di interesse;
• non è possibile l’inserimento di informazioni relative ad uno solo dei concetti di pertinenza per una relazione se non esiste un intero insieme di concetti in grado di costituire una tupla completa (o almeno la sua chiave primaria in cui non sono ammessi valori nulli).

DEFINIZIONE 1 (Dipendenza funzionale).
In una relazione R(A,B,C) l’insieme B degli attributi dipende funzionalmente dall’insieme A se ad ogni valore di A corrisponde, all’interno di una relazione, sempre lo stesso valore di B.
Si determina quindi un rapporto biunivoco tra i valori di A e quelli di B, per cui è sufficiente conoscere il valore di A per determinare quello assunto da B. Nell’esempio preso in considerazione possiamo dunque dire che esistono le FD:
impiegato astipendio
progetto a bilancio.
In base alla definizione data, è possibile affermare che, nella relazione in esame, è verificata anche la FD:
(impiegato, progetto) a progetto.
Questa è in effetti una FD banale perché asserisce una proprietà ovvia di una relazione.
Un esempio semplice di dipendenza funzionale è quello che mette in relazione ad esempio il codice fiscale di uno studente con la sua matricola universitaria: per ogni iscritto all’università esiste una sola matricola e viceversa pertanto la relazione è anche biunivoca.

Consideriamo allora la seguente:
DEFINIZIONE 2 (dipendenza funzionale non banale)
Una dipendenza funzionale Y à Z è non banale se nessun attributo di Z compare tra gli attributi di Y.
Si noti che ogni FD del tipo
Yà ( Y, Z )
può essere resa non banale eliminando, dal secondo membro, tutti gli attributi che compaiono al primo membro.
OSSERVAZIONE: se siconsidera una chiave K di una relazione R, si può facilmente verificare che esiste una FD tra K e un qualunque altro attributo o insieme di attributi dello schema di R. Questo discende dalla definizione stessa di chiave, secondo la quale non possono esistere due tuple con gli stessi valori su K e la definizione di FD è soddisfatta. Per esempio, poiché nella relazione di figura 1 una chiave K è rappresentata dagli attributi Impiegato e Progetto, possiamo affermare che vale la FD:
(impiegato, progetto) a funzione.
In particolare, esiste una FD tra una chiave di una relazione e tutti gli attributi della relazione esclusi quelli della chiave (per non incorrere nella FD banale). Nel nostro caso si ha:
(impiegato, progetto) a (stipendio, bilancio, funzione, abbreviazione).

Definizione delle forme normali

DEFINIZIONE 3 (Prima forma normale – 1FN).
Una relazione è in prima forma normale se i domini sui quali i suoi attributi sono definiti sono scalari (o atomici).
La prima forma normale stabilisce semplicemente una condizione che sta alla base del modello relazionale stesso: gli attributi della relazione sono definiti su valori atomici e non su valori complessi quali insiemi o relazioni.

DEFINIZIONE 4 (Seconda forma normale – 2FN).
Una relazione è in seconda forma normale se è in prima forma normale e se tutti i suoi attributi sono dipendenti dall’intera chiave primaria.
Secondo tale forma si vuole non rappresentare due entità distinte in una singola relazione.

DEFINIZIONE 5 (Terza forma normale – 3FN).
Una relazione è in terza forma normale se essa è in seconda forma normale e tutti gli attributi che non sono chiavi sono mutuamente indipendenti.
Per introdurre la forma normale di Boyce e Codd consideriamo ancora una volta l’esempio riportato in figura 1. Le proprietà A,B e C del § 2 implicano, rispettivamente, il soddisfacimento delle dipendenze funzionali
impiegato a stipendio,
progetto a bilancio,
funzione a abbreviazione.
Si noti, inoltre, che l’attributo funzione indica, per ciascuna tupla, il ruolo svolto dall’impiegato nel progetto. Tale ruolo è unico, per ciascuna coppia impiegato-progetto. Anche questa proprietà, che diciamo D, può essere rappresentata da una dipendenza funzionale:
(impiegato, progetto) a funzione.
ciò giustifica il motivo per cui gli attributi impiegato e progetto formano la chiave primaria della relazione complessiva.
Le proprietà A, B e C generano ridondanze e anomalie indesiderate attraverso la corrispondente dipendenza funzionale. La proprietà D, invece, non genera mai ridondanze perché, essendo la coppia (impiegato, progetto) la chiave primaria, la relazione non può contenere due tuple uguali su questi attributi. Per quanto riguarda le anomalie, da un punto di vista concettuale possiamo dire che essa non ne può generare, in quanto per ogni coppia impiegato-progetto è possibile avere valori univoci per tutti gli altri attributi della relazione. In alcuni casi tali valori potrebbero non essere disponibili ma, non facendo essi parte della chiave primaria, potremmo sostituirli senza problemi con valori nulli.
Possiamo quindi dedurre che le dipendenze:
impiegato a stipendio
progetto a bilancio
funzione a abbreviazione.
sono causa ridondanza e anomalie, mentre la dipendenza
(impiegato, progetto) a funzione
non lo è.
Generalizzando, ridondanze e anomalie sono causate dalle dipendenze funzionali X à Y che permettono la presenza di più tuple fra loro uguali sugli attributi in X, ovvero tali che X non contiene una chiave candidata. Si ha quindi la seguente

DEFINIZIONE 6 (forma normale di Boyce e Codd – BCFN).
Una relazione R è in forma normale di Boyce e Codd se e solo se ciascun determinante è una chiave candidata
Per poter “sanare” la relazione di figura 1 secondo la BCNF bisogna decomporla in due o più relazioni normalizzate attraverso un processo detto di normalizzazione. Questo processo si fonda su un semplice criterio: se una relazione rappresenta più concetti indipendenti, allora va decomposta in relazioni più piccole, una per ogni concetto.
Se alla relazione di figura 1 sostituiamo le quattro relazioni di figura 2, ottenute per mezzo di proiezioni sugli insiemi di attributi rispettivamente corrispondenti ai quattro concetti relativi alle proprietà A, B , C e D, eliminiamo anomalie e ridondanze, le quattro relazioni sono infatti in BCNF.
Si osservi che le quattro relazioni sono costruite in modo tale che a ciascuna dipendenza corrisponda una diversa relazione la cui chiave primaria è proprio il primo membro della dipendenza stessa. In tal modo è garantito che la relazione sia in BCNF. Nell’esempio, la separazione delle dipendenze (quindi dei concetti da esse rappresentati) è stata facilitata dalla struttura delle dipendenze stesse, “naturalmente” separate e indipendenti l’una dall’altra.

Figura 2 – Decomposizione della relazione in figura 1 in due relazioni in BCNF.

Nella pratica accade spesso che la decomposizione venga effettuata producendo tante relazioni quante sono le dipendenze funzionali definite (o meglio le dipendenze funzionali con diverso primo membro). In generale, purtroppo, le dipendenze possono avere una struttura complessa: può non essere necessario (o possibile) basare la decomposizione su tutte le dipendenze e può essere difficile individuare quelle su cui si deve basare la decomposizione.

La normalizzazione di un database

TEST SEMISTRUTTURATO DI VERIFICA

Alunno_____________________________________Classe_______Data__________

Avvertenze e indicazioni

La prova prevede 4 items a risposta multipla, 3 items a risposta aperta.

• Gli items a risposta multipla hanno un’unica risposta esatta fra quelle proposte. Saranno attribuiti 1 punto per ogni risposta esatta; 0,25 punti per ogni risposta omessa; 0 punti per ogni risposta errata.
• Per ogni problema (item a risposta aperta) saranno attribuiti un massimo di 2 punti secondo i seguenti indicatori:

• Compilare l’intestazione del seguente modulo.
• Il tempo a disposizione è 60 min.
• Il punteggio massimo è di 10 punti.

1. Quale tra le seguenti frasi esprime meglio il concetto di terza forma normale?

1. Una relazione nella quale ogni determinante è una chiave candidata.
2. La forma normale che elimina la dipendenza transitiva degli attributi della chiave
3. Una relazione che rispetta i requisiti fondamentali del modello relazionale
4. La forma normale che elimina la dipendenza parziale degli attributi della chiave

2. Cos’è un determinante ?

1. Un attributo chiave primaria
2. Un attributo da cui dipendono funzionalmente uno o più attributi
3. Uno schema derivante da una operazione di scomposizione
4. Un attributo che è chiave esterna in una relazione

3. Data la tabella, quale affermazione è vera:

1. il valore dello stipendio di ciascun impiegato è ripetuto solo in una tupla relativa all’impiegato
2. Se lo stipendio di un impiegato varia, è necessario andarne a modificare il valore in tutte le tuple corrispondenti
3. Se un impiegato interrompe la partecipazione a tutti i progetti senza lasciare l’azienda, tutte le tuple che lo riguardano rimangono nella tabella
4. La tabella è in terza forma normale

4. La seconda forma normale sancisce….

• Che gli attributi della relazione sono atomici
• Che si vuole non rappresentare due entità distinte in una singola relazione
• Che gli attributi sono minimali
• Che la relazione è in forma normale di Boyce e Codd

5. Si consideri il problema della gestione anagrafica di un’associazione di studenti. Le informazioni più importanti sono rappresentate con la seguente relazione:
Studenti (Nome, Scuola, Telefono Scuola);

Normalizzare la relazione nella terza forma.

6. Dato il problema dell’inventario delle merci che si trovano in alcuni magazzini dislocati in diversi parti della città. Le informazioni si possono riassumere:
Merci (Codice, Magazzino, Quantità, LocalitàMagazzino);

Normalizzare la relazione nella seconda forma.

7. Individuare un insieme di informazioni correlata organizzabili mediante un database ed indicare brevemente le possibili strategie di normalizzazione delle relazioni

SCHEDA PER L’INSEGNANTE:
Questa prova semistrutturata ha i fini di una verifica formativa dei discenti.
La valutazione formativa ha lo scopo di fornire una informazione continua ed analitica circa il modo in cui ciascun allievo procede nell’itinerario di apprendimento. Tale valutazione si colloca all’interno delle attività didattiche e concorre a determinare lo sviluppo successivo.
Si chiariscono innanzitutto il significato attribuito ai seguenti termini utilizzati nell’analisi della prova semistrutturata:

• Conoscenze: lo studente conosce le regole e la teoria alla base delle applicazioni.
• Capacità: il discente è capace di applicare le nozioni nelle varie situazioni.
• Atteggiamenti: l’alunno sa rielaborare con creatività le conoscenze acquisite e riconosce l’esigenza di introdurre il concetto di normalizzazione e di database anche in situazioni non prettamente informatiche.

Le prime 4 domande sono a risposta chiusa e mirano a valutare le conoscenze raggiunte dai singoli studenti nello studio della materia. Le domande presentano una risposta vere e tre false attraverso l’utilizzo, in ogni domanda, di due distrattori deboli e di uno forte.
Le domande 5 e 6 sono a risposta aperta e puntano a valutare le competenze raggiunte dagli studenti. In particolare le domande chiedono di individuare, e applicare alcune regole di normalizzazione alle relazioni proposte
La domanda 7 mira ad verificare le capacità acquisite dagli alunni per riportare ed ampliare i concetti appresi nelle lezioni in contesti interdisciplinari in cui la presenza dell’informatica può essere da supporto allo sviluppo di progetti. In altre parole in questa domanda specifica lo studente deve individuare come inserire le abilità sviluppate nel campo dei database e delle normalizzazioni per raggruppare in maniera ordinata un insieme di informazioni correlate tra di loro.

------
(1) prof. Marco Bonora - Docente di Sistemi Informatici presso l’ITI Galileo Ferraris di Napoli