Wednesday, September 19, 2018

Basi di Dati: La Normalizzazione delle Relazioni

Il procedimento di normalizzazione serve per eliminare gli errori di progettazione da uno schema. La normalizzazione trasforma uno schema relazionale non normalizzato in uno normalizzato, senza alterare il contenuto informativo dello schema di partenza. Normalizzare uno schema significa eliminare le ridondanze che possono portare alle incongruenze anche dette anomalie.

Le anomalie che si possono presentare sono:

  • anomalie in inserimento
  • anomalie in aggiornamento
  • anomalie in cancellazione

Immaginate di inserire dei dati a mano in una tabella di excel. Supponiamo che la tabella excel contiene dati di un prodotto, con i campi: codice prodotto, descrizione, prezzo. Se nella tabella si aggiungono informazioni relative ad altre entita', ad esempio le informazioni del venditore (codiceFornitore, Nome, Indirizzo) il database va incontro ad anomalie. Infatti, se devo inserire un nuovo prodotto, sono costretto a ripetere le informazioni del venditore: ho anomalie di inserimento. Se modifico un indirizzo di un fornitore, lo devo modificare in tutte le righe dei prodotti che sono associati a quel fornitore: ho anomalie di aggiornamento. Se cancello un prodotto che e' legato ad un fornitore, perdo anche l'informazione del fornitore: ho anomalie in cancellazione.

Applicando il processo di normalizzazione ad uno schema, si ottengono relazioni che possono trovarsi a diversi livelli di bontà, detti forme normali. Avere un database che soddisfa le prima, la seconda e la terza forma normale, significa che lo schema relazionale e' progettato bene e da' una garanzia di qualita'.

1. Prima forma normale

Una relazione R è in prima forma normale (1NF) se rispetta i seguenti requisiti:

  • i valori di un attributo (colonna) sono tutti dello stesso tipo.
    Ad esempio, id della tabella Giocatore deve essere un numero intero. Una volta che si assegna un tipo ad un attributo, questo requisito e' certamente soddifatto.
  • i valori di una tupla sono diversi dalle altre tuple.
    In ogni tabella non possono esistere due righe uguali, ed e' sufficiente che tale vincolo sia sodisfatto per la chiave primaria. Si possono avere due persone cone nome Mario e cognome Rossi, ma l'id deve essere differente.
  • tutti gli attributi devono essere di tipo elementare (atomici), ovvero non possono ulteriormente scomponibili in attributi più semplici.
    Ad esempio indirizzo e' attributo composto quando inteso come terna di valori: via, civico e CAP. Nello schema sotto, per indirizzo, si intende la stringa con il nome della strada e il civico. Ad esempio, "via Alessandro Volta, 20".

Esempio: le relazioni Clienti ed Imprese sono in 1NF

 Clienti(CodiceCli, CodiceFiscale, PartitaIVA, Cognome, Nome, Indirizzo, Cap, Citta, Prov, Telefono, Cellulare, Email)
 Imprese(CodiceImp, CodiceFiscale, PartitaIVA, RagioneSociale, Indirizzo, Cap, Citta, Prov, Email, Url, Contatto, Telefono, Cellulare) 

Nel modello concettuale, si e' detto che gli attributi possono essere semplici, composti e multipli. Gli attributi semplici sono quelli che non sono ulteriormente scomponibili. Se una relazione ha attributi multipli o attributi composti, allora la relazione non e' in prima forma normale. Ad esempio, se un cliente ha due telefoni, telefono casa e telefono ufficio, posso tenere traccia di cio' aggiungendo due attributi distinti alla relazione Clienti, ma sarebbe scorretto avere un solo campo telefono valorizzato con tutti e due i numeri di telefono, perche' in questo caso l'attributo sarebbe multiplo.

Consideriamo la relazione Imprese. Le imprese possono avere varie sedi nel territorio, fino al massimo di quattro. Ad esempio, la "Computer Discount" ha sedi in viale Redi, viale Matteotti e viale Talenti. Una soluzione puo' essere quella di replicare gli attributi Indirizzo, Cap, Citta e Prov nella relazione Imprese, scrivendo: Imprese(... , Indirizzo1, Cap1, Citta1, Prov1, Indirizzo2, Cap2, Citta2, Prov2, Indirizzo3, Cap3, Citta3, Prov3, ...). Quindi, o nella stessa relazione si replicano gli attributi, in questo modo c'e' uno spreco di spazio, perche' l'80% delle imprese ha soltanto una sede. Oppure si puo' normalizzare la relazione Imprese, rimuovendo dalla relazione gli attributi multipli e creando una nuova relazione di nome SediImprese in associazione 1:N con Imprese. Infatti, la normalizzazione dice che gli attributi multipli vengono normalizzati in tante relazioni 1:N. Quindi, se si normalizza le relazione Imprese dagli attributi multipli, posso scrivere:

 Imprese(CodiceImpresa, CodiceFiscale, PartitaIVA, RagioneSociale, Email, Url, Contatto, Telefono, Cellulare)
 SediImprese(IdSede, Indirizzo, Cap, Citta, Prov, CodiceImpresa (FK))

Allora, ho creato una associazione 1:N, dove, nel lato N, ho trasferito tutti gli attributi multipli. In questo modo, se una impresa ha 4 sedi, si ha una tupla nella relazione Imprese e 4 tuple nella relazione SediImprese.

L'operazione di normalizzazione non viene effettuata sempre, infatti ci sono database reali in cui si preferisce avere la tabella Imprese con i campi ripetuti, perche' e' piu semplice e facile da gestire una sola tabella. Infatti, di solito, le imprese hanno una sede legale e una sede amministrativa, e siccome questi due valori sono quasi sempre valorizzati, ci si puo anche permettere di mettere tutto in una tabella. Se, invece, si sta facendo un catalogo dell'alta tecnologia in Toscana, in cui si contattano centinaia di imprese, che possono avere anche sedi diverse, fino a quattro, allora puo' essere il caso di normalizzare l'attributo in un'altra relazione. Poi sta al progettista del database decidere se vuole normalizzare la relazione, si puo' anche decidere di lasciare gli attributi indirizzo1, indirizzo2, indirizzo3, indirizzo4 nella relazione, tanto sono tutti attributi atomici. Se non si fa la normalizzazione ci puo' essere spreco di spazio, se si fa la normalizzazione le join possono essere piu' lente, soprattutto se le tabelle in questione sono molto grandi.

Quando l'attributo multiplo ha significato per le ricerche, allora conviene fare la normalizzazione. Ad esempio, l'entita' libro ha l'attributo autore, che e' un attributo multiplo. Se l'applicazione non deve fare ricerche per autore sul database, allora non rispetto la prima forma normale e aggiungo gli attributi autore1, autore2, autore3, autore4 alla relazione Libro oppure aggiungo l'attributo autore che contiene una stringa con tutti gli autori. Pero' un database che contiene un campo con gli autori concatenati parte male, perche' non permette la ricerca per autori. Per esempio, i libri didattici sono quasi sempre scritti da piu' autori. Allora, se sto facendo il sistema di gestione per una libreria o una biblioteca, conviene normalizzare l'attributo autore in una nuova entita'. A livello concettuale, lo schema ha le due entita' libro e autore, e siccome un libro puo' essere scritto da piu' autori e un autore puo' scrivere piu' libri, si ha un relazione N:N.


   __________________               / \               ____________________
  |                  |             /   \             |                    |
  |      LIBRO       |__________ SCRITTURA __________|       AUTORE       |
  |__________________|     (1,N)   \   /   (1,N)     |____________________|
                                    \ /


Libri(ISBN, Titolo, Editore, NumeroEdizione, ...)
Autori(IdAutore, Nome, Cognome, ...)
Rel_Libri_Autori(ISBN, IdAutore)

In conclusione, per la prima forma normale gli attributi non possono essere né multipli né composti, ma solo atomici.

2. Dipendenze funzionali

Per parlare di seconda forma normale bisogna introdurre il concetto di dipendenza funzionale. Data una relazione R ed un attributo X di R, si dice che un attributo Y di R dipende funzionalmente da X, e si scrive X → Y, se e solo se i valori degli attributi di X determinano univocamente il valore dell’attributo Y per ogni istanza della relazione R.

X → Y, significa X determina Y, ovvero Y dipende funzionalmente da X.

Es. dipendenza dalla chiave primaria CodiceCliente

 CodiceCliente  CodiceFiscale
 CodiceCliente  Cognome
 CodiceCliente  Nome

Ad esempio, per la relazione Giocatore-Penalita, gli attributi data e importo dipendono da IdPenalita e gli attributi cognome e nome dipendono funzionalmente da IdGiocatore.

La dipendenza funzionale vale a livello di relazione e non a livello di una singola istanza di una relazione, cioe' vale per tutte le n-ple della relazione e non per qualche n-pla della relazione.

3. Seconda forma normale

Una relazione R è in seconda forma normale (2NF) se rispetta i seguenti requisiti:

  • R è in 1NF
  • tutti gli attributi non chiave dipendono funzionalmente dalla chiave, cioè non esistono attributi dipendenti solo da una parte della chiave

La seconda forma normale ha senso perche' si indica, come chiave primaria di una relazione, l'accoppiata di due chiavi esterne. Ad esempio, nella relazione Rel_Libri_Autori, si potrebbe inserire un ID, numero intero progressivo, come chiave primaria, invece della combinazione delle due chiavi esterne (ISBN, IdAutore). Si usa la chiave primaria composta (ISBN, IdAutore) perche' c'e' un unico libro per autore: un autore non puo' comparire due volte sullo stesso libro. Secondo il prof. sarebbe meglio che ogni relazione abbia come chiave primaria un solo attributo, anche se inserito in modo ridondante, allo scopo di semplificare le interrogazioni, aggiornamenti e le cancellazioni sulle basi di dati. Usare chiavi primarie che siano un singolo attributo, permetterebbe di avere automaticamente il database gia' in seconda forma normale.

Esempio: relazione esami non in 2NF

 Esami(Matricola, Corso, NomeCorso, Voto, Lode, DataEsame)
 Anagrafe(Matricola, Nome, Cognome, DataNascita, ...)

La relazione Esami(Matricola, Corso, NomeCorso, Voto, Lode, DataEsame) non è in 2NF, perché l’attributo NomeCorso dipende funzionalmente soltanto da Corso, che è una parte della chiave. La soluzione consiste nel creare una nuova relazione Corsi, e spostare l'attributo NomeCorso dentro Corsi.

 Esami(Matricola, IDCorso, Voto, Lode, DataEsame)  
 Corsi(IDCorso, NomeCorso)
 Anagrafe(Matricola, Nome, Cognome, DataNascita, LuogoDiNascita, ...)

Adesso, nella relazione Corsi, gli attributi Voto, Lode e DataEsame dipendono funzionalmente dalla chiave (Matricola,IDCorso)

Altra implementazione della relazione Esami.

 Esami(IDEsame, Matricola (FK), Corso (FK), Voto, Lode, DataEsame)  
 Corsi(IDCorso, NomeCorso)
 Anagrafe(Matricola, Nome, Cognome, DataNascita, ...)

Ho inserito nella relazione Esami una chiave primaria IDEsame che e' un solo attributo, anche se inserito in modo ridondante, allo scopo di semplificare le interrogazioni sulle basi di dati.

4. Terza forma normale

Una relazione R è in terza forma normale (3NF) se rispetta i seguenti requisiti:

  • R è in 2NF
  • tutti gli attributi non chiave dipendono direttamente dalla chiave. Se ci sono attributi non chiave che dipendono da altri attributi non chiave, la relazione non e' in 3NF (dipendenza transitiva)

Esempio: relazione Uffici non in 3NF

 Uffici(IDUfficio, NomeUfficio, IDCapo(FK), NomeCapo)

La relazione Uffici non è in 3NF, perché l’attributo NomeCapo dipende funzionalmente da IDCapo, che non è l’attributo chiave della relazione. (Se il nome del capo cambia, lo devo modificare in tutte le tuple della relazione Uffici: anomalia da inserimento). La soluzione consiste nel creare una nuova relazione, di nome Anagrafica:

 Anagrafica(IDCapo, NomeCapo)
 Uffici(IDUfficio, NomeUfficio, IDCapo)

La normalizzazione in 3NF si ottiene quindi scomponendo la relazione di partenza in due nuove relazioni, nelle quali tutti gli attributi dipendono direttamente dalla chiave, togliendo gli attributi non chiave che dipendono da un altro attributo non chiave.

5. L’integrità referenziale

Per prevenire errori, sono state definite opportune regole di integrità sui dati, dette:

  • vincoli di tupla, (condizioni che devono essere soddisfatte dai valori di ciascuna tupla indipendentemente dalle altre),
    • vincolo di chiave primaria: valore non NULL e non duplicata della chiave primaria
    • vincolo su attributo a livello del suo dominio: ad esempio una data corretta
  • integrità referenziale, (condizioni che devono essere soddisfatte tra due relazioni associate tra loro attraverso la chiave esterna, allo scopo di eliminare gli errori di inserimento, modifica e cancellazione)

Esempio di base di dati con anomalie

La tabella Studenti contiene righe con anomalie (evidenziate con un asterisco): una foreign key CodScuola mancante oppure che non ha corrispondenza, una data di nascita troppo vecchia, un primary key matricola con valore duplicato. La tabella Scuole contiene una riga con primary key assente.


  Studenti                                                                      Scuole
  _______________________________________________________________________       ___________________________
 |             |             |             |              |              |     |             |             |
 |  MATRICOLA  |    NOME     |   COGNOME   | DATANASCITA  |  CODSCUOLA   |     |    CODICE   |    NOME     |
 |_____________|_____________|_____________|______________|______________|     |_____________|_____________|
 |             |             |             |              |              |     |             |             |
 |    2345     |    Mario    |   Rossi     |     NULL     |     S001     |     |    S001     | ITC Manzoni |
 |_____________|_____________|_____________|______________|______________|     |_____________|_____________|
 |             |             |             |              |              |     |             |             |
 |    2346     |    Luigi    |   Verdi     |   03/10/88   |     NULL  *  |     |    S002     | Liceo Dante |
 |_____________|_____________|_____________|______________|______________|     |_____________|_____________|
 |             |             |             |              |              |     |             |             |
 |    2347     |    Guido    |   Galli     |   20/09/29 * |     S001     |     |    S003     | Liceo Fermi |
 |_____________|_____________|_____________|______________|______________|     |_____________|_____________|
 |             |             |             |              |              |     |             |             |
 |    2345  *  |    Enrico   |   Bruni     |   17/3/91    |     S003     |     |    NULL *   |ITIS Galvani |
 |_____________|_____________|_____________|______________|______________|     |_____________|_____________|
 |             |             |             |              |              |
 |    2348     |    Paolo    |   Belli     |   28/5/97    |     S055  *  |
 |_____________|_____________|_____________|______________|______________|


Queste errori si risolvono a livello di progettazione fisica della tabella. Infatti, una volta progettato lo schema logico si passa allo schema fisico. Allora, per ogni tabella si stabiliscono i vincoli sulla chiave primaria, i vincoli sugli attributi obbligatori e i vincoli sul dominio dell'attributo. Un vincolo sul dominio di attributo potrebbe essere, ad esempio, che una ditta non assume persone con eta' maggiore di 40.

Quando viene applicata l’integrità referenziale, è necessario osservare le seguenti regole pratiche di carattere generale:

  • non è possibile immettere un valore nella chiave esterna della tabella associata se tale valore non esiste tra le chiavi della tabella primaria, è possibile però mettere un valore NULL nella chiave esterna (riga non correlata);
  • non è possibile eliminare una riga dalla tabella primaria se esistono righe ad essa collegata nella tabella correlata;
  • non si può modificare il valore della chiave nella tabella primaria se ad essa corrispondono righe nella tabella correlata.

Il vincolo di integrita' referenziale esistente tra le tabelle Studenti e Scuole, ci permette l'inserimento di nuove righe nella tabella Scuole, ma non permette l'inserimento di nuove righe nella tabella Studenti, a patto che queste non siano associate ad una scuola tramite un valore della chiave FK esistente sulla tabella Scuole. Di solito, questo lo fa l'applicativo: se si sviluppa una form per l'inserimento di un nuovo studente, il campo che specifica la scuola non e' una casella di testo, ma una lista che permette di selezionare un valore all'interno di un insieme di nomi di scuole. L'integrita' referenziale in inserimento e' garantita.

Esempio di base di dati con anomalia da cancellazione

Consideriamo l'associazione Giocatori-Penalita. Supponiamo che sullo schema fisico non ci sia l'intergrita referenziale, per cui cancello il giocatore con id=2, senza aver prima cancellato le sue penalita, dando origine ad una anomalia da cancellazione. Per poter ripristinare l'intergrita referenziale, si deve recuperare la Penalita che ha FK che non si riferisce a nessun giocatore e poi eliminarla. Questo si fa con una query con subquery.


  Giocatori                                       Penalita
  _________________________________________       _______________________________________________________ 
 |             |             |             |     |             |             |             |             |
 | IdGiocatore |    Nome     |   Cognome   |     | IdPenalita  |    Data     |   Importo   | IdGiocatore |
 |_____________|_____________|_____________|     |_____________|_____________|_____________|_____________|
 |             |             |             |     |             |             |             |             |   
 |     G01     |    Mario    |    Rossi    |     |     001     |  10/10/2015 |     100     |    G01      |
 |_____________|_____________|_____________|     |_____________|_____________|_____________|_____________|
 |             |             |             |     |             |             |             |             |  
 |      //     |     //      |      //     |     |     002     |  11/10/2015 |     500     |    G02      |
 |_____________|_____________|_____________|     |_____________|_____________|_____________|_____________|
 |             |             |             |
 |     G03     |    Paolo    |    Verdi    |
 |_____________|_____________|_____________|

Per selezionare l'ID della seconda riga della tabella Penalita, si fa la query Giocatori.IdGiocatore right join Penalita.IdGiocatore, la restrizione con la condizione Giocatore.IdGiocatore = NULL e la proiezione su IdPenalita. Per cancellare la penalita' con IdPenalita 002, utilizzo la prima query come query di partenza di una seconda query di cancellamento.

6. Esercizio: sistema per la gestione delle gite di una agenzia viaggi

Si progetti lo schema Entità-Relazione e lo schema relazionale di una base di dati in cui si vogliono memorizzare le seguenti informazioni relative ad una agenzia di viaggio che organizza gite turistiche. Ogni gita ha un responsabile, una data di partenza ed un elenco di partecipanti (di cui si vuole memorizzare nome ed età), ed inoltre fa riferimento ad un itinerario; di ogni itinerario si vuole memorizzare una durata, un prezzo ed un elenco delle tappe, corrispondenti alle località visitate (con durata del soggiorno in ogni località).

 

                                       /\                   ____________________ 
                                      /  \                 |                    |
                     ____________ PRENOTAZIONE ____________|    PARTECIPANTE    |
                    |        (1,N)    \  /     (1,N)       |____________________|
                    |                  \/                   /   /    ▲  \       \
                    |                                      id  nome  |  cognome  dataNascita
durata  prezzo  data|                                                |
    _\____\______/__|_                 / \                  _________|__________
   |                  |               /   \                |                    |
   |       GITA       |__________ PARTECIPAZIONE __________|    RESPONSABILE    |
   |__________________|      (1,1)    \   /     (1,1)      |____________________|
   /      /         |                  \ /
IdGita  descrizione |                   
                    |
                    |               / \               ____________________              / \              ________________  
                    |              /   \             |                    |            /   \            |                |
                    |_________ COMPOSIZIONE _________|       TAPPA        |_________ POSIZIONE _________|     COMUNE     |
                           (1,N)   \   /   (1,1)     |____________________|     (1,1)  \   /   (1,N)    |________________|
                                    \ /               /       /       \                 \ /              /     \
                                                   IdTappa  durata  localita                          codice  nomeComune

Si deve costruire uno schema relazionale che e' funzionale alle interrogazioni da fare sul database. Si suppone che l'agenzia di viaggio sia una sola e che non si voglia memorizzare informazioni relative alla agenzia di viaggi. Le entita' che descrivono la realta' di interesse sono: la gita, l'itinerario, le tappe, i partecipanti alla gita, il responsabile della gita. Il responsabile non puo' essere aggiunto come attributo alla gita, ma e' un partecipante speciale alla gita, una entita' specializzazione di partecipante, con tutte e sole le proprieta' di partecipante: un clone.

L'associazione Gita-Viaggiatore e' una associazione di tipo molti a molti, perche' si suppone che una gita ha piu' viaggiatori e un viaggiatore puo' partecipare a piu' gite organizzate dalla stessa agenzia di viaggi. Molte associazioni Cliente-Servizio sono di tipo molti a molti (ad esempio Cliente-AbbonamentoPalestra, Cliente-AnalisiMedica, Cliente-CorsoDiBallo, ecc.) perche' si suppone che il cliente si registra la prima volta quando usa quel servizio e, quando vuole usare quel servizio una seconda volta, il cliente risulta gia' registrato nel database. Anche l'associazione studente-scuola e' una associazione molti a molti, perche' uno studente puo' fare un anno presso un liceo e poi passare ad un istituto tecnico; per cui, se si vuole tener traccia dello storico, si deve modellare l'associazione come N:N. Allo stesso modo, se si vuole sapere a quante gite ha partecipato un cliente, si deve usare una associazione N:N.

L'associazione gita-responsabile e' di tipo uno ad uno. In realta', il responsabile della gita e' un partecipante alla gita, in piu' e' anche il responsabile della gita, come nell'associazione ufficio-capoUfficio di tipo uno ad uno, il capoufficio e' un impiegato che lavora in quell'ufficio ed e' anche il capo dell'ufficio. Siccome il responsabile e' anche un partecipante, significa che esso e' caratterizzato dagli attributi della tabella partecipante: (id, cognome, nome, dataNascita). Il fatto che il responsabile della gita e' un attributo della gita si sarebbe potuto tradurre aggiungendo gli attributi cognome e nome del responsabile alla gita, ma non sarebbe stato in 3FN, perche' il nome del responsabile non dipende da idGita, ma solo da idPartecipante. Quindi, si aggiunge a gita l'attributo idPartecipante come FK, rispettando la 3FN.

Gli attributi di Gita sono: descrizione, durata in giorni, prezzo, data di partenza. L'attributo descrizione vuole indicare, brevemente, la meta delle gita: ad esempio "Le Cinque Terre", "Arezzo-Cortona", "Isola del Giglio". La gita ha un itinerario, cioe' tutte le tappe della gita, ad esempio per le cinque terre le tappe sono: Monterosso al Mare, Vernazza, Corniglia, Manarola e Riomaggiore. La associazione tra le entita Gita-Tappa e' di tipo 1:N, supponendo che una tappa e' ad esclusivo uso e consumo di una sola gita. Non ha senso inserire una tappa nel database se non la collego ad una gita. Gli attributi di tappa sono durata e localita'. Siccome ci sono delle localita' che sono frazioni, non un comune, posso fare riferimento ad un comune. Un comune puo' essere associato a piu' tappe, una tappa si trova in solo un comune.

Schema relazionale

 Gite(IDGita, Descrizione, Durata, Prezzo, Data, IDResponsabile (FK))
 Partecipanti(IDPart, Cognome, Nome, DataNascita)
 Rel_GitePartecipanti(IDGita (FK), IDPart (FK))
 Tappe(IDTappa, Durata, Localita, IDComune (FK), IdGita(FK))
 Comuni(IDComune, NomeComune)

Lo schema relazionale e' in 3FN normale, poiche' ogni attributo e' atomico, ogni attributo non chiave dipende funzionalmente dalla chiave, ogni attributo non chiave dipende direttamente dalla chiave. Per controllare se lo schema relazionale e' valido, si controlla che la base di dati soddisfa i requisiti, cioe' si controlla se si possono eseguire le interrogazioni che servono al committente. Ad esempio, per trovare nome e cognome di tutti i partecipanti alla gita "Cinque Terre", si eseguono due join, in cui l'ordine in cui si incrociano le tabelle non conta:

 S = ( (Gita.IDGita JOIN RelGP.IDGita) JOIN Partecipanti.IDPart )
 T = restrict S where Descrizione = "Gita alle 5 Terre"
 project T on Cognome, Nome

La relazione S, risultato delle due join, ha tutti gli attributi di Gita, tutti gli attributi di RelGP e tutti gli attributi di Partecipanti.

No comments :

Post a Comment