Normalizzazione di Schemi S. Costantini 06/05/2006 (parte del materiale è tratto da slide del 2001 di Ceri-Atzeni) Forme normali • Una forma normale è una proprietà di una base di dati relazionale che ne garantisce la “qualità”, cioè l'assenza di determinati difetti • Quando una relazione non è normalizzata: • presenta ridondanze, • si presta a comportamenti poco desiderabili durante gli aggiornamenti • Le forme normali sono di solito definite sul modello relazionale, ma hanno senso in altri contesti, ad esempio il modello E-R 06/06/2006 Normalizzazione di Schemi Relazionali 2 Forme Normali • Forma normale: proprietà delle relazioni di un DB • Altrimenti: comportamenti indesiderati • Verifica forma normale = verifica di qualità • Metodologie di progettazione Schemi già in forma normale • Normalizzazione: Schema Schema normalizzato 06/06/2006 Normalizzazione di Schemi Relazionali 3 Normalizzazione • Procedura che permette di trasformare schemi non normalizzati in schemi che soddisfano una forma normale • La normalizzazione va utilizzata come tecnica di verifica dei risultati della progettazione di una base di dati • Non costituisce una metodologia di progettazione 06/06/2006 Normalizzazione di Schemi Relazionali 4 Una relazione con anomalie Impiegato Stipendio Progetto Rossi 20 Marte Verdi 35 Giove Verdi 35 Venere Neri 55 Venere Neri 55 Giove Neri 55 Marte Mori 48 Marte Mori 48 Venere Bianchi 48 Venere Bianchi 48 Giove 06/06/2006 Bilancio 2 15 15 15 15 2 2 15 15 15 Normalizzazione di Schemi Relazionali Funzione tecnico progettista progettista direttore consulente consulente direttore progettista progettista direttore 5 Proprietà di questa Tabella • lo stipendio di ciascun impiegato è unico (indipendentemente dai progetti cui partecipa) • il bilancio di ciascun progetto è unico (indipendentemente dagli impiegati che vi partecipano) • La funzione di un impiegato in un progetto è unica • Ridondanze: • stipendio di ciascun impiegato ripetuto in tutte le tuple relative ad esso • bilancio di ciascun progetto ripetuto per ogni impiegato che partecipa 06/06/2006 Normalizzazione di Schemi Relazionali 6 Anomalie • anomalia di aggiornamento: lo stipendio di un impiegato varia modifica di tutte le tuple corrispondenti • anomalia di cancellazione: un impiegato interrompe la partecipazione a tutti i progetti spariscono nome e stipendio (a meno di valori nulli sull'unica chiave) • anomalia di inserimento: impossibile inserire nuovo impiegato senza progetto motivo di questi inconvenienti: unica relazione per gestire dati e associazioni tra dati di tipo diverso. 06/06/2006 Normalizzazione di Schemi Relazionali 7 Difetti fra Relazioni su Concetti Disomogenei • Dati ripetuti in diverse tuple, senza aggiungere informazioni significative. • Informazioni ripetute aggiornamento ripetuto per ciascuna occorrenza • Informazioni ripetute la cancellazione di una tupla può comportare l’ eliminazione di concetti ancora necessari • Inserimento di informazioni relative ad uno solo dei concetti non possibile se esse non costituiscono una tupla completa (o almeno la sua chiave primaria) 06/06/2006 Normalizzazione di Schemi Relazionali 8 Perché questi fenomeni indesiderabili? • abbiamo usato un'unica relazione per rappresentare informazioni eterogenee • gli impiegati con i relativi stipendi • i progetti con i relativi bilanci • le partecipazioni degli impiegati ai progetti con le relative funzioni 06/06/2006 Normalizzazione di Schemi Relazionali 9 Per studiare in maniera sistematica questi aspetti, è necessario introdurre un vincolo di integrità: la dipendenza funzionale 06/06/2006 Normalizzazione di Schemi Relazionali 10 Proprietà • Ogni impiegato ha un solo stipendio (anche se partecipa a più progetti) • Ogni progetto ha un bilancio • Ogni impiegato in ciascun progetto ha una sola funzione (anche se può avere funzioni diverse in progetti diversi) 06/06/2006 Normalizzazione di Schemi Relazionali 11 Dipendenza Funzionale • dipendenza funzionale: vincolo di integrità per il modello relazionale descrive legami di tipo funzionale tra gli attributi di una relazione • Esempio: il valore dell'attributo Impiegato determina il valore dell'attributo Stipendio: • esiste una funzione che associa ad ogni elemento del dominio dell'attributo Impiegato un solo elemento del dominio dell'attributo Stipendio 06/06/2006 Normalizzazione di Schemi Relazionali 12 Formalizzazione • Relazione r su uno schema R(X) • sottoinsiemi di attributi non vuoti Y e Z di X • insieme I di coppie di tuple t1 e t2 di r con uguali valori sugli attributi Y • esiste su r una dipendenza funzionale tra Y e Z, se, per ogni coppia (t1,t2) I, t1 e t2 hanno gli stessi valori anche sugli attributi Z • Sintassi: Y Z • il vincolo cosi’ definito si associa a schema R(X) • Semantica: relazione r su schema R(X) corretta se soddisfa le dipendenze funzionali che la coinvolgono 06/06/2006 Normalizzazione di Schemi Relazionali 13 In sintesi • relazione r su R(X) • due sottoinsiemi non vuoti Y e Z di X • esiste in r una dipendenza funzionale (FD) da Y a Z se, per ogni coppia di ennuple t1 e t2 di r con gli stessi valori su Y, risulta che t1 e t2 hanno gli stessi valori anche su Z • FD = Functional Dependency 06/06/2006 Normalizzazione di Schemi Relazionali 14 Notazione XY • Esempi: Impiegato Stipendio Progetto Bilancio Impiegato Progetto Funzione 06/06/2006 Normalizzazione di Schemi Relazionali 15 Osservazione • Dato schema R(K,V) e dato insieme di attributi A V si ha sempre K V • ossia, il vincolo di dipendenza funzionale generalizza il vincolo di chiave • Una dipendenza funzionale Y Z su uno schema R(X) dove Y è la chiave degenera nel vincolo di chiave se Y Z = X • Nell’ esempio Impiegato Progetto Stipendio Bilancio Funzione 06/06/2006 Normalizzazione di Schemi Relazionali 16 Dipendenze Funzionali banali • Impiegato Progetto Progetto • Si tratta però di una FD “banale” (sempre soddisfatta) • Y A è non banale se A non appartiene a Y • Y Z è non banale se nessun attributo in Z appartiene a Y 06/06/2006 Normalizzazione di Schemi Relazionali 17 Le anomalie sono legate ad alcune FD • gli impiegati hanno un unico stipendio Impiegato Stipendio • i progetti hanno un unico bilancio Progetto Bilancio 06/06/2006 Normalizzazione di Schemi Relazionali 18 Non tutte le FD causano anomalie • In ciascun progetto, un impiegato svolge una sola funzione Impiegato Progetto Funzione • Il soddisfacimento è più "semplice" 06/06/2006 Normalizzazione di Schemi Relazionali 19 Una differenza fra FD Impiegato Stipendio Progetto Bilancio • causano anomalie Impiegato Progetto Funzione • non causa anomalie • Perché? 06/06/2006 Normalizzazione di Schemi Relazionali 20 Impiegato Stipendio Progetto Rossi 20 Marte Verdi 35 Giove Verdi 35 Venere Neri 55 Venere Neri 55 Giove Neri 55 Marte Mori 48 Marte Mori 48 Venere Bianchi 48 Venere Bianchi 48 Giove Bilancio 2 15 15 15 15 2 2 15 15 15 Funzione tecnico progettista progettista direttore consulente consulente direttore progettista progettista direttore Impiegato Stipendio Progetto Bilancio Impiegato Progetto Funzione 06/06/2006 Normalizzazione di Schemi Relazionali 21 FD e anomalie • La terza FD corrisponde ad una chiave e non causa anomalie • Le prime due FD non corrispondono a chiavi e causano anomalie • La relazione contiene alcune informazioni legate alla chiave e altre ad attributi che non formano una chiave 06/06/2006 Normalizzazione di Schemi Relazionali 22 Motivo delle Anomalie • abbiamo usato un'unica relazione per rappresentare informazioni eterogenee • gli impiegati con i relativi stipendi • i progetti con i relativi bilanci • le partecipazioni degli impiegati ai progetti con le relative funzioni 06/06/2006 Normalizzazione di Schemi Relazionali 23 • • • • Impiegato Stipendio Progetto Bilancio Impiegato Progetto Funzione Impiegato Progetto è chiave Impiegato solo no Progetto solo no Le anomalie sono causate dalla presenza di concetti eterogenei: • proprietà degli impiegati (lo stipendio) • proprietà di progetti (il bilancio) • proprietà della chiave Impiegato Progetto 06/06/2006 Normalizzazione di Schemi Relazionali 24 In particolare • La proprietà "Lo stipendio di ciascun impiegato è funzione del solo impiegato, indipendentemente dai progetti cui partecipa" vuol dire che Impiegato Stipendio • La proprietà "Il bilancio di ciascun progetto dipende dal solo progetto, indipendentemente dagli impiegati che vi partecipano" vuol dire che Progetto Bilancio • Queste due proprietà (e quindi le corrispondenti dipendenza funzionali) generano ridondanze e anomalie indesiderate 06/06/2006 Normalizzazione di Schemi Relazionali 25 In particolare • Poichè gli attributi Impiegato Progetto formano una chiave, allora Impiegato Progetto Funzione che significa: "In ciascun progetto, ciascuno degli impiegati coinvolti può svolgere una sola funzione" • Questa dipendenza non genera ridondanze o anomalie proprio perché Impiegato Progetto è una superchiave 06/06/2006 Normalizzazione di Schemi Relazionali 26 Forma normale di Boyce e Codd (BCNF) • Una relazione r è in forma normale di Boyce e Codd se, per ogni dipendenza funzionale (non banale) X Y definita su di essa, X contiene una chiave K di r 06/06/2006 Normalizzazione di Schemi Relazionali 27 Forma normale di Boyce e Codd (BCNF) • BCNF = Boyce-Codd Normal Form • La forma normale di Boyce-Codd richiede che i concetti in una relazione siano omogenei (solo proprietà direttamente associate alla chiave) 06/06/2006 Normalizzazione di Schemi Relazionali 28 Che facciamo se una relazione non soddisfa la BCNF? • La rimpiazziamo con altre relazioni che soddisfano la BCNF Come? • Decomponendo sulla base delle dipendenze funzionali, al fine di separare i concetti 06/06/2006 Normalizzazione di Schemi Relazionali 29 Impiegato Stipendio Progetto Impiegato Progetto Rossi 20 Marte Rossi Marte Impiegato Stipendio Verdi 35Verdi Giove Giove Rossi 20 Verdi 35 35Verdi Venere Venere Verdi Venere 55 Neri Venere Neri Neri 55 Giove Mori Neri 48 55 Neri Giove Neri Marte BianchiNeri 48 55 Mori Marte Marte Mori 48 Mori Marte Venere Venere Mori 48Bianchi Venere Giove Bianchi 48Bianchi Venere Bianchi 48 Giove 06/06/2006 Bilancio Funzione 2 tecnico 15 progettista 15 progettista direttore 15 consulente 15 consulente 2 direttore 2 progettista progettista 15 direttore 15 15 Normalizzazione di Schemi Relazionali Funzione tecnico progettista Progetto Bilancio progettista Marte 2 direttore 15 Giove consulente Venere 15 consulente direttore progettista progettista direttore 30 Normalizzazione • Procedimento che consiste nel decomporre r non in forma normale rispetto alle dipendenze funzionali D1, ..., Dk in n relazioni r1, ..., rn in forma normale • si vuole che: • r = r1 join r2 join rn (P1: decomposizione senza perdita) • ogni dipendenza funzionale Dj su r sia soddisfatta in almeno una delle r1, ..., rn date (P2: conservazione delle dipendenze) 06/06/2006 Normalizzazione di Schemi Relazionali 31 Caso favorevole della normalizzazione • si decompone r in tante relazioni quante sono le dipendenze funzionali (non banali) con diverso primo membro 06/06/2006 Normalizzazione di Schemi Relazionali 32 Rispetto all’esempio • D1: Impiegato Stipendio • D2: Progetto Bilancio • D3: Impiegato Progetto Funzione Decomposizione • R1(Impiegato , Stipendio ) • R2(Progetto, Bilancio) • R3(Impiegato, Progetto, Funzione) ciascuna dipendenza corrisponde ad una diversa relazione la cui chiave è proprio il primo membro della dipendenza stessa 06/06/2006 Normalizzazione di Schemi Relazionali 33 Dipendenze con struttura complessa • può non essere necessario (o possibile) basare la decomposizione su tutte le dipendenze • può essere difficile individuare quelle su cui si deve basare la decomposizione. Impiegato Categoria Stipendio Neri 3 30 Verdi 3 30 Rossi 4 50 Mori 4 50 Bianchi 5 72 06/06/2006 Normalizzazione di Schemi Relazionali 34 Proprietà Esempio • Relazione nell’esempio: soddisfa le dipendenze (non banali) D1: Impiegato Categoria D2: Categoria Stipendio 06/06/2006 Normalizzazione di Schemi Relazionali 35 Decomposizione in BCNF R1 Impiegato Neri Verdi Rossi Mori Bianchi 06/06/2006 Categoria 3 3 4 4 5 Normalizzazione di Schemi Relazionali 36 Decomposizione in BCNF R2 Categoria Stipendio 3 30 3 30 4 50 4 50 5 72 06/06/2006 Normalizzazione di Schemi Relazionali 37 Osservazione Attenzione: Scegliendo invece le dipendenze D1’: Impiegato Categoria Stipendio D2: Categoria Stipendio forma normale non possibile, perchè D1’ copre tutti gli attributi, quindi impossibile decomporre • Quindi: no dipendenze che coprono tutti gli attributi 06/06/2006 Normalizzazione di Schemi Relazionali 38 Non sempre così facile Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Sede Roma Milano Milano Milano Milano Impiegato Sede Progetto Sede 06/06/2006 Normalizzazione di Schemi Relazionali 39 Relazione nell’esempio soddisfa le dipendenze (non banali) D1: Impiegato Sede D2: Progetto Sede • Osservazione: ciascun impiegato può partecipare a più progetti , ma tutti nella stessa sede 06/06/2006 Normalizzazione di Schemi Relazionali 40 Decomponiamo sulla base delle dipendenze Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Impiegato Rossi Verdi Neri 06/06/2006 Sede Roma Milano Milano Sede Roma Milano Milano Milano Milano Progetto Marte Giove Saturno Venere Normalizzazione di Schemi Relazionali Sede Roma Milano Milano Milano 41 Proviamo a ricostruire Impiegato Rossi Verdi Neri Sede Roma Milano Milano Progetto Marte Giove Saturno Venere Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Verdi Saturno Neri Giove Sede Roma Milano Milano Milano Sede Roma Milano Milano Milano Milano Milano Milano Diversa dalla relazione di partenza! 06/06/2006 Normalizzazione di Schemi Relazionali 42 Cosa è accaduto? • Ci sono tuple “spurie” perchè, per ogni impioegato, la sua sede si è “combinata” nel join con tutti i progetti di quella sede. • C’è quindi perdita di informazione: a quali progetti partecipa realmente ciascun impiegato? Nel risultato del join se ne è persa traccia. 06/06/2006 Normalizzazione di Schemi Relazionali 43 Proprietà delle relazioni decomposte • Non si vuole perdita di informazione • Una decomposizione in BCNF è valida se è senza perdita (di informazione), ossia se il join delle relazioni decomposte restituisce la relazione di partenza (senza aggiungere tuple spurie) 06/06/2006 Normalizzazione di Schemi Relazionali 44 Formalizzazione • Relazione r su un insieme di attributi X dove X = X1 X2 • r1 ed r2 ottenute per proiezione da r su X1 e X2 • r1 join r2 contiene in generale tutte le tuple di r, più eventualmente tuple "spurie". • r si decompone senza perdita su X1 e X2 se r1 join r2 = r 06/06/2006 Normalizzazione di Schemi Relazionali 45 Decomposizione senza perdita • Una relazione r si decompone senza perdita su X1 e X2 se il join delle proiezioni di r su X1 e X2 è uguale a r stessa (cioè non contiene ennuple spurie) • La decomposizione senza perdita è garantita se gli attributi comuni alle relazioni decomposte contengono una chiave per almeno una di esse 06/06/2006 Normalizzazione di Schemi Relazionali 46 Osservazione • Ciò avviene se gli attributi comuni costituiscono il primo membro di almeno una delle dipendenze su cui si effettua la decomposizione • Nell'esempio: l'intersezione degli insiemi di attributi su cui sono effettuate le due proiezioni è costituita dall'attributo Sede che non è il primo membro di alcuna dipendenza funzionale 06/06/2006 Normalizzazione di Schemi Relazionali 47 Proviamo a decomporre senza perdita Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Impiegato Rossi Verdi Neri Sede Roma Milano Milano Sede Roma Milano Milano Milano Milano Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Impiegato Sede Progetto Sede 06/06/2006 Normalizzazione di Schemi Relazionali 48 Osservazione • Abbiamo usato il buon senso, non il metodo usuale • La decomposizione è soddisfacente, ma non è in BCNF 06/06/2006 Normalizzazione di Schemi Relazionali 49 Un altro problema • Supponiamo di voler inserire una nuova ennupla che specifica la partecipazione dell'impiegato Neri, che opera a Milano, al progetto Marte Impiegato Rossi Verdi Neri Sede Roma Milano Milano Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Impiegato Sede Progetto Sede 06/06/2006 Normalizzazione di Schemi Relazionali 50 Impiegato Rossi Verdi Neri Sede Roma Milano Milano Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Neri 06/06/2006 Normalizzazione di Schemi Relazionali Marte 51 Impiegato Progetto Rossi Marte Verdi Giove Verdi Venere Neri Saturno Neri Venere Neri 06/06/2006 Marte Normalizzazione di Schemi Relazionali Sede Roma Milano Milano Milano Milano Milano 52 Conservazione delle dipendenze • Una decomposizione conserva le dipendenze se ciascuna delle dipendenze funzionali dello schema originario coinvolge attributi che compaiono tutti insieme in uno degli schemi decomposti • Progetto Sede non è conservata 06/06/2006 Normalizzazione di Schemi Relazionali 53 Qualità delle decomposizioni • Una decomposizione dovrebbe sempre soddisfare: • la decomposizione senza perdita, che garantisce la ricostruzione delle informazioni originarie • la conservazione delle dipendenze, che garantisce il mantenimento dei vincoli di integrità originari 06/06/2006 Normalizzazione di Schemi Relazionali 54 Una relazione non-normalizzata Dirigente Progetto Rossi Marte Verdi Giove Verdi Marte Neri Saturno Neri Venere Sede Roma Milano Milano Milano Milano Progetto Sede Dirigente Dirigente Sede 06/06/2006 Normalizzazione di Schemi Relazionali 55 La decomposizione è problematica • Progetto Sede Dirigente coinvolge tutti gli attributi e quindi nessuna decomposizione può preservare tale dipendenza • quindi in alcuni casi la BCNF “non è raggiungibile” 06/06/2006 Normalizzazione di Schemi Relazionali 56 Una nuova forma normale • Una relazione r è in terza forma normale se, per ogni FD (non banale) X Y definita su r, è verificata almeno una delle seguenti condizioni: • X contiene una chiave K di r • ogni attributo in Y è contenuto in almeno una chiave di r 06/06/2006 Normalizzazione di Schemi Relazionali 57 BCNF e terza forma normale • la terza forma normale è meno restrittiva della forma normale di Boyce e Codd (e ammette relazioni con alcune anomalie) • ha il vantaggio però di essere sempre “raggiungibile” 06/06/2006 Normalizzazione di Schemi Relazionali 58 Decomposizione in terza forma normale • si crea una relazione per ogni gruppo di attributi coinvolti in una dipendenza funzionale • si verifica che alla fine una relazione contenga una chiave della relazione originaria • Dipende dalle dipendenze individuate 06/06/2006 Normalizzazione di Schemi Relazionali 59 Una possibile strategia • se la relazione non è normalizzata si decompone in terza forma normale • alla fine si verifica se lo schema ottenuto è anche in BCNF • Se una relazione ha una sola chiave allora le due forme normali coincidono 06/06/2006 Normalizzazione di Schemi Relazionali 60 Uno schema non decomponibile in BCNF Dirigente Progetto Rossi Marte Verdi Giove Verdi Marte Neri Saturno Neri Venere Sede Roma Milano Milano Milano Milano Dirigente Sede Progetto Sede Dirigente 06/06/2006 Normalizzazione di Schemi Relazionali 61 Una possibile riorganizzazione Dirigente Progetto Rossi Marte Verdi Giove Verdi Marte Neri Saturno Neri Venere Sede Roma Milano Milano Milano Milano Reparto 1 1 1 2 2 Dirigente Sede Reparto Sede Reparto Dirigente Progetto Sede Reparto 06/06/2006 Normalizzazione di Schemi Relazionali 62 Decomposizione in BCNF Dirigente Rossi Verdi Neri 06/06/2006 Sede Reparto Roma 1 Milano 1 Milano 2 Progetto Marte Giove Marte Saturno Venere Normalizzazione di Schemi Relazionali Sede Reparto Roma 1 Milano 1 Milano 1 Milano 2 Milano 2 63 Progettazione e normalizzazione • la teoria della normalizzazione può essere usata nella progettazione logica per verificare lo schema relazionale finale • si può usare anche durante la progettazione concettuale per verificare la qualità dello schema concettuale 06/06/2006 Normalizzazione di Schemi Relazionali 64 Nome fornitore Codice Nome prodotto Indirizzo Prodotto Partita IVA Prezzo PartitaIVA NomeFornitore Indirizzo 06/06/2006 Normalizzazione di Schemi Relazionali 65 Analisi dell’entità • L’entità viola la terza forma normale a causa della dipendenza: PartitaIVA NomeFornitore Indirizzo • Possiamo decomporre sulla base di questa dipendenza 06/06/2006 Normalizzazione di Schemi Relazionali 66 Partita Nome IVA fornitore Nome prodotto Codice (1,1) Prodotto (0,N) Fornitura Indirizzo Prezzo 06/06/2006 Fornitore Normalizzazione di Schemi Relazionali 67 Dipartimento (0,N) (0,N) Professore (0,1) Studente Tesi (0,N) Corso di laurea Studente Corso di laurea Studente Professore Professore Dipartimento 06/06/2006 Normalizzazione di Schemi Relazionali 68 Analisi della relationship • La relationship viola la terza forma normale a causa della dipendenza: Professore Dipartimento • Possiamo decomporre sulla base di questa dipendenza 06/06/2006 Normalizzazione di Schemi Relazionali 69 (0,N) Afferenza (1,1) Professore Dipartimento (0,N) (0,1) Tesi Studente (0,N) Corso di laurea 06/06/2006 Normalizzazione di Schemi Relazionali 70 Ulteriore analisi sulla base delle dipendenze • La relationship Tesi è in BCNF sulla base delle dipendenze Studente CorsoDiLaurea Studente Professore • le due proprietà sono indipendenti • questo suggerisce una ulteriore decomposizione 06/06/2006 Normalizzazione di Schemi Relazionali 71 (0,N) Professore (0,1) Tesi Studente (1,1) (1,1) (0,N) Afferenza Corso di laurea (0,N) (0,N) Corso di laurea Dipartimento 06/06/2006 Iscrizione Normalizzazione di Schemi Relazionali 72