S. Costantini 06/05/2006 (parte del materiale è tratto da slide del 2001 di Ceri-Atzeni)...

S. Costantini

06/05/2006

(parte del materiale è tratto da slide

del 2001 di Ceri-Atzeni)

Normalizzazione di SchemiNormalizzazione di Schemi

06/06/2006 Normalizzazione di Schemi Relazionali

2

Forme normaliForme 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


3

Forme NormaliForme 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


4

NormalizzazioneNormalizzazione

• 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


5

Una relazione con Una relazione con anomalieanomalie

Impiegato Stipendio Progetto Bilancio Funzione

Rossi 20 Marte 2 tecnicoVerdi 35 Giove 15 progettistaVerdi 35 Venere 15 progettistaNeri 55 Venere 15 direttoreNeri 55 Giove 15 consulenteNeri 55 Marte 2 consulenteMori 48 Marte 2 direttoreMori 48 Venere 15 progettista

Bianchi 48 Venere 15 progettistaBianchi 48 Giove 15 direttore


6

Proprietà di questa TabellaProprietà 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


7

AnomalieAnomalie

• 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.


8

Difetti fra Relazioni su Concetti Difetti fra Relazioni su Concetti DisomogeneiDisomogenei

• 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)


9

Come eliminare le anomalie?Come eliminare le anomalie?

• Mediante un procedimento di normalizzazione

• Ossia, trasformando una tabella non in forma normale in un’insieme di tabelle in forma normale

• Forme Normali:• Boyce-Codd Normal Form (BCNF)• Terza Forma Normale (in subordine)


10

Perché questi fenomeni indesiderabili?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


11

Normalizzazione: Definizione IntuitivaNormalizzazione: Definizione Intuitiva

• Occorre separare le informazioni eterogenee in sottoinsiemi omogenei.

• Ciascun sottoinsieme individuato deve rappresentare un ben preciso concetto.

• I concetti individuati corrispondono ad un insieme di attributi che nel suo interno ha una potenziale chiave.

• Dopo aver individuato i concetti rilevanti, la tabella data può essere decomposta in altrettante tabelle separate.


12

Per studiare in maniera sistematica come Per studiare in maniera sistematica come individuare e separare i concetti, è individuare e separare i concetti, è

necessario introdurre come strumento un necessario introdurre come strumento un vincolo di integrità:vincolo di integrità:

la dipendenza funzionalela dipendenza funzionale


13

Proprietà dell’esempio consideratoProprietà dell’esempio considerato

• 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)


14

Dipendenza FunzionaleDipendenza 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


15

FormalizzazioneFormalizzazione

• 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


16


• 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


17

In sintesiIn 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


18

NotazioneNotazione

XY

• Esempi:

Impiegato Stipendio

Progetto Bilancio

Impiegato Progetto Funzione


19

OsservazioneOsservazione

• 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


20

Dipendenze Funzionali banaliDipendenze 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


21

Le anomalie sono legate ad alcune FDLe anomalie sono legate ad alcune FD

• gli impiegati hanno un unico stipendio

Impiegato Stipendio• i progetti hanno un unico bilancio

Progetto Bilancio


22

Non tutte le FD causano anomalieNon tutte le FD causano anomalie

• In ciascun progetto, un impiegato svolge una sola funzione


• Il soddisfacimento è più "semplice"


23

Una differenza fra FD Una differenza fra FD

Impiegato Stipendio

Progetto Bilancio• causano anomalie

Impiegato Progetto Funzione• non causa anomalie• Perché?


24




Impiegato StipendioProgetto Bilancio



25

FD e anomalieFD 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


26

Motivo delle AnomalieMotivo 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


27

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


28

In particolareIn 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, in dipendentemente dagli impiegati che vi partecipano" vuol dire che

Progetto Bilancio• Queste due proprietà (e quindi le corrispondenti

dipendenza funzionali) generano ridondanze e anomalie indesiderate


29

In particolareIn particolare

• Poichè gli attributi Impiegato Progetto formano una chiave, allora


che significa: "In ciascun progetto, ciascuno degli impiegati coinvolti può svolgere una sola funzione“ non genera ridondanze e anomalie

• Questo proprio perché

Impiegato Progetto è una superchiave


30

Forma normale di Boyce e Codd (BCNF)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


31

Forma normale di Boyce e Codd (BCNF)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)


32

Cosa fare se una relazione non soddisfa Cosa fare se una relazione non soddisfa la BCNF?la BCNF?

• La rimpiazziamo con altre relazioni che soddisfano la BCNF

Come?• Decomponendo sulla base delle dipendenze

funzionali, al fine di separare i concetti


33




Impiegato StipendioRossi 20Verdi 35Neri 55Mori 48

Bianchi 48

Impiegato Progetto Funzione Rossi Marte tecnico Verdi Giove progettista Verdi Venere progettista Neri Venere direttore Neri Giove consulente Neri Marte consulente Mori Marte direttore Mori Venere progettista

Bianchi Venere progettista Bianchi Giove direttore

Progetto BilancioMarte 2Giove 15Venere 15


34

NormalizzazioneNormalizzazione

• 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)


35

Caso favorevole della normalizzazioneCaso favorevole della normalizzazione

• si decompone r in tante relazioni quante sono le dipendenze funzionali significative (non banali) con diverso primo membro

• Le relazioni risultanti sono in BCNF• Le proprietà P1 (decomposizione senza

perdita) e P2 (conservazione delle dipendenze) sono mantenute.


36

Rispetto all’esempioRispetto 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


37

Dipendenze con struttura complessaDipendenze 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


38

Proprietà EsempioProprietà Esempio

• Relazione nell’esempio:

soddisfa le dipendenze (non banali)

D1: Impiegato Categoria

D2: Categoria Stipendio


39

Decomposizione in BCNF R1Decomposizione in BCNF R1

Impiegato Categoria

Neri 3

Verdi 3

Rossi 4

Mori 4

Bianchi 5


40

Decomposizione in BCNF R2Decomposizione in BCNF R2

Categoria Stipendio

3 30

4 50

5 72


41


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


42

Non sempre così facileNon sempre così facile

Impiegato Progetto SedeRossi Marte RomaVerdi Giove MilanoVerdi Venere MilanoNeri Saturno MilanoNeri Venere Milano

Impiegato SedeProgetto Sede


43

Relazione nell’esempioRelazione 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


44


Decomponiamo sulla base Decomponiamo sulla base delle dipendenzedelle dipendenze

Impiegato SedeRossi RomaVerdi MilanoNeri Milano

Progetto SedeMarte RomaGiove Milano

Saturno MilanoVenere Milano


45

Proviamo a ricostruireProviamo a ricostruire

Impiegato Progetto SedeRossi Marte RomaVerdi Giove MilanoVerdi Venere MilanoNeri Saturno MilanoNeri Venere MilanoVerdi Saturno MilanoNeri Giove Milano

Diversa dalla relazione di partenza!


Progetto SedeMarte RomaGiove Milano

Saturno MilanoVenere Milano


46

Cosa è accaduto?Cosa è accaduto?

• Ci sono tuple “spurie” perchè, per ogni impiegato, 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.


47

Proprietà delle relazioni decomposteProprietà 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)


48


• 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


49

Decomposizione senza perdita 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


50

Condizione sufficiente per la Condizione sufficiente per la Decomposizione senza PerditaDecomposizione senza Perdita

• relazione r sugli attributi ABC • proiezioni r1 su AB e r2 su AC.• sia A C• Allora, A è chiave per la proiezione r2 su AC

non ci sono in r2 due tuple diverse con gli stessi valori su A

decomposizione senza perdita


51

Perchè la condizione data è sufficiente?Perchè la condizione data è sufficiente?

• generica tupla t in r1 join r2

t = (a,b,c) è ottenuta da t1 = (a,b) r1 e t2 = (a,c) r2 • in r, A C, dunque esiste un solo valore per C in r

associato al valore a dell’attributo A• (a,c) compare in r2, dunque tale valore è proprio c• (a,b) compare in r1, dunque il valore a può essere

associato in r al valore b• Si conclude che t = (a,b,c) ) r e quindi r è senza

perdita


52


• La condizione sufficiente data è verificata 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, quindi la condizione non è verificata


53


Proviamo a decomporre senza perditaProviamo a decomporre senza perdita

Impiegato ProgettoRossi MarteVerdi GioveVerdi VenereNeri SaturnoNeri Venere




54


• Abbiamo usato il buon senso, non il metodo usuale

• La decomposizione è soddisfacente, ma non è in BCNF


55

Un altro problemaUn altro problema

• Supponiamo di voler inserire una nuova ennupla che specifica la partecipazione dell'impiegato Neri, che opera a Milano, al progetto Marte





56



Neri Marte

Neri Milano


57

Impiegato Progetto SedeRossi Marte RomaVerdi Giove MilanoVerdi Venere MilanoNeri Saturno MilanoNeri Venere MilanoNeri Marte Milano


58

Conservazione delle dipendenzeConservazione 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


59

Qualità delle decomposizioniQualità 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


60

Una relazione non-normalizzataUna relazione non-normalizzata

Dirigente Progetto Sede

Rossi Marte RomaVerdi Giove MilanoVerdi Marte MilanoNeri Saturno MilanoNeri Venere Milano

Progetto Sede DirigenteDirigente Sede


61

La decomposizione è problematicaLa 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”


62

Una nuova forma normaleUna nuova forma normale

• Una relazione r è in terza forma normale (3NF) 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


63

Esempio 3NFEsempio 3NF

Telefoni(Prefisso,Numero, Località,Nome,Ind)

• Chiave Prefisso Numero• Altra chiave Località Numero• Dipendenze

• Prefisso Numero Nome• Prefisso Numero Località• Prefisso Numero Ind


64

EsempioEsempio

• Con queste dipendenze, la relazione è in 3NF

• Ridondanza: i prefissi sono ripetuti


65

BCNF e terza forma normaleBCNF 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”


66

Decomposizione in terza forma normaleDecomposizione 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


67

Una possibile strategiaUna 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


68

Strategia AlternativaStrategia Alternativa

• Riorganizzare la relazione data aggiungendo attributi

• Obiettivo: renderla decomponibile in BCNF• Metodo: i nuovi attributi creano nuove

dipendenze funzionali che soddisfano la condizione sufficiente• La decomposizione senza perdita è così

garantita• La conservazione delle dipendenze segue

in modo ovvio decomponendo sulle dipendenze stesse


69

Uno schema non decomponibile in BCNFUno schema non decomponibile in BCNF

Dirigente Progetto Sede

Rossi Marte RomaVerdi Giove MilanoVerdi Marte MilanoNeri Saturno MilanoNeri Venere Milano

Dirigente SedeProgetto Sede Dirigente


70

Una possibile riorganizzazioneUna possibile riorganizzazione

Dirigente Progetto Sede Reparto

Rossi Marte Roma 1Verdi Giove Milano 1Verdi Marte Milano 1Neri Saturno Milano 2Neri Venere Milano 2

Dirigente Sede RepartoSede Reparto DirigenteProgetto Sede Reparto


71

Decomposizione in BCNFDecomposizione in BCNF

Progetto Sede Reparto

Marte Roma 1Giove Milano 1Marte Milano 1

Saturno Milano 2Venere Milano 2

Dirigente Sede Reparto

Rossi Roma 1Verdi Milano 1Neri Milano 2


72

Progettazione e normalizzazioneProgettazione 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


73

Prodotto

Nome prodotto

Prezzo

Nome fornitore

Indirizzo

PartitaIVA

Codice

PartitaIVA NomeFornitore Indirizzo


74

Analisi dell’entitàAnalisi dell’entità

• L’entità viola la terza forma normale a

causa della dipendenza:

PartitaIVA NomeFornitore Indirizzo

• Possiamo decomporre sulla base di

questa dipendenza


75

Indirizzo

PartitaIVA

Nomefornitore

Nomeprodotto

Prezzo

Codice

FornituraProdotto Fornitore

(1,1) (0,N)


76

Professore Studente

Corso dilaurea

Tesi

(0,N) (0,1)

(0,N)

Dipartimento

(0,N)

Studente Corso di laureaStudente Professore

Professore Dipartimento


77

Analisi della relationshipAnalisi della relationship

• La relationship viola la terza forma

normale a causa della dipendenza:

Professore Dipartimento

• Possiamo decomporre sulla base di

questa dipendenza


78

Professore Studente

Corso dilaurea

Tesi

(0,N) (0,1)

(0,N)

DipartimentoAfferenza

(1,1)

(0,N)


79

Ulteriore analisi sulla base delle Ulteriore analisi sulla base delle dipendenzedipendenze

• La relationship Tesi è in BCNF sulla base

delle dipendenze

Studente CorsoDiLaurea

Studente Professore• le due proprietà sono indipendenti• questo suggerisce una ulteriore

decomposizione


80

Professore StudenteTesi

(0,N) (0,1)

Dipartimento

Afferenza

(0,N)

(1,1)

Corso dilaurea

(0,N)

Corso dilaurea

Iscrizione

(0,N)

(1,1)

S. Costantini 06/05/2006 (parte del materiale è tratto da slide del 2001 di Ceri-Atzeni)...

Documents

Transcript of S. Costantini 06/05/2006 (parte del materiale è tratto da slide del 2001 di Ceri-Atzeni)...