Date post: | 02-May-2015 |
Category: |
Documents |
Upload: | abelie-colonna |
View: | 215 times |
Download: | 1 times |
Forma normale di Boyce e Forma normale di Boyce e CoddCodd
Definizione
22
Le DF di DipartimentoLe DF di DipartimentoImpiegato
StipendioProgetto
Bilancio Funzione
Rossi 20 Marte 2 tecnico
Verdi 35 Giove 15 progettista
Verdi 35 Venere 15 progettista
Neri 55 Venere 15 direttore
Neri 55 Giove 15 consulente
Neri 55 Marte 2 consulente
Mori 48 Marte 2 direttore
Mori 48 Venere 15 progettista
Bianchi 48 Venere 15 progettista
Bianchi 48 Giove 15 direttore
Impiegato StipendioProgetto Bilancio
Impiegato Progetto Funzione
33
Impiegato Stipendio
La Df riporta che lo stipendio di ciascun impiegato dipende solo dall’impiegato stesso indipendentemente dai progetti a cui partecipa e quindi presenta
Ridondanza Anomalia di aggiornamento Anomalia di cancellazione Anomalia di inserimento
44
Progetto Bilancio
La DF riporta che il bilancio di ciascun progetto dipende solo dal progetto stesso indipendentemente dalla partecipazione degli impiegati ai progetti e quindi presenta
Ridondanza Anomalia di aggiornamento Anomalia di cancellazione Anomalia di inserimento
55
Impiegato Progetto Funzione
La DF riporta che in ogni progetto ogni impiegato svolge una ed una sola funzione.
Si noti che, essendo (Impiegato, Progetto) chiave di Dipartimento
non esistono due tuple con stessa chiave e Funzione (non esistono ridondanze)
La modifica interviene su una sola tupla La cancellazione non comporta perdita di
informazioni che potrebbero essere ancora utili L’inserimento è possibile anche attribuendo valori
nulli agli attributi diversi da Impiegato e Progetto
66
DF ed anomalieDF ed anomalieLe anomalie viste si riconducono alla presenza delle DF:
Impiegato → Stipendio Progetto → Bilancio
Viceversa la FD Impiegato, Progetto → Funzione
non causa problemi
Le anomalie sono causate dalla presenza di concetti eterogenei:
proprietà degli impiegati (lo stipendio) proprietà dei progetti (il bilancio) proprietà della chiave Impiegato Progetto
77
La causa delle anomalieLa causa delle anomalieLe prime due FD non corrispondono a chiavi e causano anomalie
La terza FD corrisponde ad una chiave e non causa anomalie
Impiegato Stipendio Impiegato non è chiave
Progetto Bilancio Progetto non è chiave
Impiegato Progetto Funzione Impiegato Progetto è chiave
88Forma Normale di Boyce e Forma Normale di Boyce e CoddCodd
Uno relazione r è in forma normale di Boyce e Codd se:
per ogni dipendenza funzionale (non banale)
X → Y definita su R(T),
X contiene una chiave K di r Ossia X è una superchiave di r
99
NormalizzazioneNormalizzazione
La normalizzazione è il processo di trasformazione che
data una relazione che non soddisfa una forma normale
la scompone in altre relazioni che invece soddisfano la forma normale
Nel caso della forma normale di Boyce e Codd la trasformazione si basa su un semplice criterio:
Individuazione dei diversi concetti riportati insieme nella relazione
Decomposizione della relazione in relazioni più semplici, una per ogni concetto.
1010Un esempio di Un esempio di normalizzazionenormalizzazione
Impiegato
Progetto
Funzione
Rossi Marte tecnico
Impiegato
Stipendio
Verdi Gioveprogettista
Rossi 20 Verdi Venereprogettista
Progetto
Bilancio
Verdi 35 Neri Venere direttore Marte 2
Neri 55 Neri Giove consulente Giove 15
Mori 48 Neri Marte consulente Venere 15
Bianchi 48 Mori Marte direttore
Mori Venereprogettista
Bianchi Venereprogettista
Bianchi Giove direttore
1111
Non sempre così facileNon sempre così facileImpiegato
Progetto
Sede
Rossi Marte Roma
Verdi Giove Milano
Verdi Venere Milano
Neri Saturno Milano
Neri Venere Milano
Impiegato
SedeProgetto
Sede
Rossi Roma Marte Roma
Verdi Milano Giove Milano
Neri Milano Saturno Milano
Venere Milano
Impiegato Sede
Progetto Sede
1212
Proviamo a ricostruireProviamo a ricostruire
Impiegato
SedeProgetto
Sede
Rossi Roma Marte Roma
Verdi Milano Giove Milano
Neri Milano Saturno Milano
Venere Milano
Impiegato
Progetto
Sede
Rossi Marte Roma
Verdi Giove Milano
Verdi Saturno Milano
Verdi Venere Milano
Neri Giove Milano
Neri Saturno Milano
Neri Venere Milano
Diversa dalla relazione di partenza!
1313Decomposizione senza Decomposizione senza perditaperdita
La decomposizione non deve assolutamente alterare il contenuto informativo del DB
Si introduce pertanto il seguente requisito Decomposizione senza perdita (lossless)
Uno schema R(X) si decompone senza perdita negli schemi R1(X1) e R2(X2) se, per ogni istanza legale r su R(X), il join naturale delle proiezioni di r su X1 e X2 è uguale a r stessa
X1(r) X2
(r) = r
1414Decomposizione senza Decomposizione senza perditaperdita
Una decomposizione con perdita può generare tuple spurie
Per decomporre senza perdita è necessario e sufficiente che il join naturale sia eseguito su una superchiave di uno dei due sottoschemi, ovvero che valga X1 ∩ X2 → X1 oppure X1 ∩ X2 → X2
La decomposizione senza perdita è garantita se gli attributi comuni contengono una chiave per almeno una delle relazioni decomposte
1515Decomposizione senza Decomposizione senza perditaperdita
Impiegato
Progetto
Sede
Rossi Marte Roma
Verdi Giove Milano
Verdi Venere Milano
Neri Saturno Milano
Neri Venere Milano
Impiegato
SedeImpiegato
Progetto
Rossi Roma Rossi Marte
Verdi Milano Verdi Giove
Neri Milano Verdi Venere
Neri Saturno
Neri Venere
1616
Un altro problema (1/3)Un altro problema (1/3)Supponiamo di voler inserire una nuova ennupla che specifica la partecipazione dell'impiegato Neri, che opera a Milano, al progetto Marte
Ricordiamo che le dipendenze sullo schema originario sono
Impiegato Sede Progetto Sede
Ossia un impiegato deve operare su una sola sede e anche i progetti devono insistere su una sola sede
1717
Un altro problema (2/3)Un altro problema (2/3)
Impiegato
SedeImpiegato
Progetto
Rossi Roma Rossi Marte
VerdiMilano
Verdi Giove
NeriMilano
Verdi Venere
Neri Saturno
Neri Venere
Neri Marte
1818
Un altro problema (3/3)Un altro problema (3/3)Proviamo a ricostruire
Impiegato
Progetto
Sede
Rossi Marte Roma
Verdi Giove Milano
Verdi Venere Milano
Neri Saturno Milano
Neri Venere Milano
Neri Marte Milano
La dipendenza Progetto Sede non è preservata
1919Conservazione delle Conservazione delle dipendenzedipendenze
Una istanza legale nello schema decomposto genera sullo schema ricostruito una soluzione non ammissibile
Ogni singola istanza è (“localmente”) legale, ma il DB (“globalmente”) non lo è
Infatti il progetto “Marte” risulta essere assegnato a due sedi, in violazione del vincolo Progetto Sede
Problemi di consistenza dei dati si hanno quando la decomposizione “separa” gli attributi di una FD. Per verificare che la FD sia rispettata si rende necessario far riferimento a entrambe le relazioni.
2020Conservazione delle Conservazione delle dipendenzedipendenze
Una decomposizione preserva le dipendenze se ciascuna delle dipendenze funzionali dello schema originario coinvolge attributi che compaiono tutti insieme in uno degli schemi decomposti Nell’esempio la dipendenza Progetto Sede non
è conservata
Se una FD non si preserva diventa più complicato capire quali sono le modifiche del DB che non violano la DF stessa
2121Alcune definizioni: attributo Alcune definizioni: attributo primoprimo
Un attributo di uno schema di relazione R è detto attributo primo di R se esso è membro di una qualche chiave candidata di R.
Un attributo è detto non primo se non è un attributo primo, cioè se non è membro di nessuna chiave candidata.
2222
1 Forma Normale1 Forma Normale
La 1FN è parte integrante della definizione formale di relazione nel modello relazionale di base.
La 1FN impone che il dominio di un attributo comprenda solo valori atomici.
La 1FN non consente quindi di usare attributi multivalore, composti o una loro qualsiasi combinazione.
2323
2 Forma normale2 Forma normale
La 2FN si basa sul concetto di dipendenza funzionale completa.
Una dipendenza funzionale X->Y è una dipendenza funzionale completa se la rimozione di un qualsiasi attributo A da X fa decadere la DF. Una DF è parziale se è possibile rimuovere da X attributi senza che essa venga meno.
Uno schema di relazione R è in 2FN se ogni attributo non primo A di R dipende funzionalmente in modo completo dalla chiave primaria di R
2424
2 Forma normale: considerazioni2 Forma normale: considerazioni
Uno schema di relazione è in 2FN se ogni attributo non primo A di R non è parzialmente dipendente da nessuna chiave di R.
La verifica comporta l’esame delle DF i cui attributi della parte sinistra fanno parte della chiave primaria.
Se la chiave primaria è fatta da un sol attributo (il che stabilisce che le DF sulla chiave sono complete) allora lo schema di relazione è già in 2FN.
2525
3 Forma Normale3 Forma Normale
La 3FN si basa sul concetto di DF transitiva.
Una DF X->Y definita sullo schema di relazione R è transitiva se esiste un insieme Z, che non è né chiave candidata né appartiene ad una chiave di R, per cui valgono contemporaneamente X->Z e Z->Y
Uno schema di relazione R è in 3FN se soddisfa la 2FN e nessun attributo non primo di R dipende in modo transitivo dalla chiave primaria (definizione originaria di Codd).
26263 Forma Normale: 3 Forma Normale: generalizzazionegeneralizzazione
Uno schema di relazione R è in 3FN se ogni volta che sussiste in R una DF non banale
X->Ao X è una superchiave di Ro A è un attributo primo di R
Quindi uno schema di relazione R non è in 3FN quando viola entrambe le condizioni. Da cui si ricava:
Uno schema di relazione R è in 3FN se ogni attributo non primo di R è funzionalmente dipendente in modo completo da ogni chiave di R e non è dipendente in modo transitivo da alcuna chiave di R.
2727
3FN e BCNF3FN e BCNF
La forma normale di Boyce e Codd è stata proposta come una forma più semplice di 3FN ma difatti è più restrettiva.
Ogni relazione in BCNF è anche in 3FN.
Le relazioni in 3FN non necessariamente sono in BCFN
2828
Ancora anomalieAncora anomalieLo schema
TEL(Prefisso,Numero,Località,Abbonato,Indirizzo) ha vincoli Prefisso,Numero → Località,Abbonato, Indirizzo Località → Prefisso
Lo schema è in 3NF, in quanto Prefisso è primo (non c’è dipendenza transitiva)
Nella seguente istanza legale l’informazione sul prefisso viene replicata per ogni abbonato
Prefisso
Numero
LocalitàAbbonato
Indirizzo
051 457856 Bologna Rossi Via Roma 8
059 452332 Modena Verdi Via Bari 16
051 987856 Bologna Bianchi Via Napoli 77
051 552346 Castenaso Neri Piazza Borsa 12
059 387654 Vignola Mori Via Piave 65
2929
Decomposizione in BCNFDecomposizione in BCNFUna soluzione consiste nel decomporre lo schema in
NUM_TEL(Numero,Località,Abbonato,Indirizzo) PREF_TEL(Località, Prefisso)
La decomposizione è lossless perché (NUM_TEL PREF_TEL) = TEL
Numero
LocalitàAbbonato
IndirizzoPrefisso
Località
457856 Bologna Rossi Via Roma 8 051 Bologna
452332 Modena Verdi Via Bari 16 059 Modena
987856 Bologna Bianchi Via Napoli 77 051 Castenaso
552346 Castenaso Neri Piazza Borsa 12 059 Vignola
387654 Vignola Mori Via Piave 65
3030
OsservazioniOsservazioniBenché gli schemi in 3NF non siano esenti da
problemi, tale livello di normalizzazione è comunemente accettato nella pratica
Nel caso generale, problemi di complessità computazionale rendono improponibile affrontare l’attività di normalizzazione mediante tecniche di “analisi”. Tutti i seguenti problemi sono NP-completi: Determinare se un attributo è primo Verificare se esiste una chiave di grado minore di
k Verificare se uno schema è in 3NF
3131
OsservazioniOsservazioniL’approccio adottato è di tipo costruttivo,
ovvero anziché verificare se uno schema è al livello di normalizzazione richiesto, si progettano schemi che siano a tale livello di normalizzazione.
Qualità di una decomposizione (ottenibile con algoritmi di normalizzazione): deve essere senza perdita, per garantire la
ricostruzione delle informazioni originarie dovrebbe conservare le dipendenze, per
semplificare il mantenimento dei vincoli di integrità originari
3232
Decomposizione in 3NFDecomposizione in 3NFL’idea alla base dell’algoritmo che produce una
decomposizione in 3NF è creare una relazione per ogni gruppo di FD che hanno lo stesso lato sinistro (determinante) e inserire nello schema corrispondente gli attributi coinvolti in almeno una FD del gruppo Esempio: Se le FD individuate sullo schema
R(ABCDEFG) sono: AB→ CD, AB →E, C → F, F → G
si generano gli schemi: R1(ABCDE), R2(CF), R3(FG)
3333
Se 2 o più determinanti si determinano reciprocamente, si fondono gli schemi (più chiavi alternate per lo stesso schema)
Esempio: Se le FD su R(ABCD) sono: A →BC, B → A, C →D
si generano gli schemi R1(ABC), R2(CD)
Decomposizione in 3NFDecomposizione in 3NF
3434
Alla fine si verifica che esista uno schema la cui chiave è anche chiave dello schema originario (se non esiste lo si crea)
Esempio: Se le FD su R(ABCD) sono: A →C, B →D
si generano gli schemi R1(AC), R2(BD), R3(AB)
Decomposizione in 3NFDecomposizione in 3NF
3535Una limitazione non Una limitazione non superabilesuperabile
Dirigente
Progetto
Sede
Rossi Marte Roma
Verdi GioveMilano
Verdi MarteMilano
Neri SaturnoMilano
Neri VenereMilano
Progetto Sede DirigenteDirigente Sede
3636Una limitazione non Una limitazione non superabilesuperabile
Nell’esempio la dipendenza Progetto,SedeDirigente coinvolge tutti gli attributi e quindi nessuna decomposizione può preservare tale dipendenzaQuindi, in funzione del pattern di FD, potrebbe non essere possibile decomporre in BCNF e preservare le FD
3737
In pratica…In pratica…Se la relazione non è normalizzata si decompone
in terza forma normaleSi verifica se lo schema ottenuto è anche in
BCNF Si noti che se una relazione ha una sola chiave
allora le due forme normali coincidono
Se uno schema non è in BCNF si hanno 3 alternative: Si lascia così com’è, gestendo le anomalie
residue (se l’applicazione lo consente) Si decompone in BCNF, predisponendo opportune
query di verifica (per verificare le dipendenze originarie vengano violate)
Si cerca di rimodellare la situazione iniziale, al fine di permettere di ottenere schemi BCNF
3838
BCNF e 3BCNF e 3aa Forma Normale 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”
3939
Uno schema non in BCNFUno schema non in BCNF
Dirigente
Progetto
Sede
Rossi Marte Roma
Verdi GioveMilano
Verdi MarteMilano
Neri SaturnoMilano
Neri VenereMilano
Progetto Sede DirigenteDirigente Sede
4040Una possibile Una possibile riorganizzazioneriorganizzazione
Dirigente
Progetto
SedeReparto
Rossi Marte Roma 1
Verdi GioveMilano
1
Verdi MarteMilano
1
Neri SaturnoMilano
2
Neri VenereMilano
2
Dirigente Sede RepartoSede Reparto DirigenteProgetto Sede Reparto
4141
Decomposizione in BCNFDecomposizione in BCNF
Progetto
SedeReparto
Dirigente
SedeReparto
Marte Roma 1
Rossi Roma 1 Giove Milano 1
Verdi Milano 1 Marte Milano 1
Neri Milano 2 Saturno Milano 2
Venere Milano 2
4242Progettazione e Progettazione e normalizzazionenormalizzazione
La teoria della normalizzazione può essere usata nella progettazione logica per verificare lo schema relazionale finaleSi può usare anche durante la progettazione concettuale per verificare la qualità dello schema concettuale
4343
Es.: entità non normalizzataEs.: entità non normalizzata
Prodotto
Nome prodotto
Prezzo
Nome fornitore
Indirizzo
PartitaIVA
Codice
PartitaIVA NomeFornitore Indirizzo
4444
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
4545
DecomposizioneDecomposizione
Indirizzo
PartitaIVA
Nomefornitore
Nomeprodotto
Prezzo
Codice
FornituraProdotto Fornitore(1,1) (0,N)
4646Es.: associazione non Es.: associazione non normalizzatanormalizzata
Professore Studente
Corso dilaurea
(0,N) (0,1)
(0,N)
Dipartimento
(0,N)
Tesi
Studente Corso di laurea
Studente Professore
Professore Dipartimento
4747
Analisi dell’associazioneAnalisi dell’associazione
L’ associazione viola la terza forma normale a causa della dipendenza:
Professore Dipartimento
Possiamo decomporre sulla base di questa dipendenza
4848
DecomposizioneDecomposizione
Afferenza
(1,1)
(0,N)
Professore Studente
Corso dilaurea
(0,N) (0,1)
(0,N)
Dipartimento
Tesi
4949Ulteriore analisi sulla base delle Ulteriore analisi sulla base delle dipendenzedipendenze
L’associazione Tesi in BCNF sulla base delle dipendenze
Studente CorsoDiLaurea Studente Professore
Le due proprietà sono indipendentiQuesto suggerisce una ulteriore decomposizione
5050
Ulteriore decomposizioneUlteriore decomposizione
Afferenza
(1,1)
(0,N)
Professore Studente
Corso dilaurea
(0,N) (0,1)
Dipartimento
Tesi
Iscrizione
(1,1)
(0,N)
5151Normalizzazione vs. Normalizzazione vs. performances performances
Potremmo voler utilizzare schemi non normalizzati per aumentare la performancesAd es. collegare e mostrare informazioni memorizzate in due tabelle differenti richiede il join delle tabelle
5252Normalizzazione vs. Normalizzazione vs. performancesperformances
Alternativa 1: usare schemi denormalizzati che contengono gli attributi di entrambe le relazioni accesso più veloce spazio e tempo di esecuzione superiore per
gestire le modifiche maggiore sforzo di programmazione per
gestire la ridondanza, con conseguente maggiore incidenza degli errori di programmazione
Alternativa 2: usare una vista materializzata stessi vantaggi e svantaggi della alternativa
1, eccetto il maggiore sforzo di programmazione
5353
RiferimentiRiferimentiAtzeni, Ceri, Paraboschi, Torlone – Basi di dati – McGraw-
Hill, 1999Cabibbo, Torlone, Batini – Basi di dati: progetti ed esercizi
svolti – Pitagora editrice, Bologna, 1995Atzeni, Batini, De Antonellis – Teoria relazionale dei dati –
Boringhieri, Torino, 1985