06 Normalizzazione
-
Upload
guestbe916c -
Category
Business
-
view
1.531 -
download
0
Transcript of 06 Normalizzazione
Verifiche di qualita` per schemi relazionali
1
La qualita` di schemirelazionali
Il concetto di qualita` per uno schema relazionale si riferisce alla possibilita` di
generare comportamenti anomali durante le operazioni di aggiornamento, dovuti alla
presenza di dati ridondanti
2
La qualita` di schemirelazionali
Lo schema soddisfadeterminate proprieta’?
SI
No anomalie Applicare teoriaNormalizzazione
Nuovo schemaequivalente a quello iniziale,
senza anomalie
NO
Schema relazionaleVincoli di integrita`
(dipendenze funzionali)
3
La qualita` di schemirelazionali
Se utilizziamo le metodologie di progettazione presentate in precedenza, gli schemi relazionali generati spesso soddisfanouna forma normale (terza forma normale)
non presentano anomalieIn questo caso, la teoria della normalizzazione rappresenta un utile strumento di verifica, che puo` suggerire modifiche nel casoin cui vogliamo ottenere forme normali differenti, magari piu` restrittive
forma normale di Boyce-CoddLa normalizzazione e` inoltre utile in fasi di revisione successivadegli schemi relazionali
vincoli di integrita` sorti da nuovi requisiti applicativi possonogenerare nuove anomalienuovi schemi normalizzati
4
Ridondanza
Chiave = colloc
ridondanza
stesso Film
5
RidondanzaVideo
Film
No ridondanza
6
Anomalia di modificaLa valutazione del film Pulp Fiction di Quentin Tarantino cambia
Se non modifichiamo tale valore in tutte le tuple in cui appare il film da aggiornare, dopo la modifica, tuple relative allo stesso film
potrebbero avere valutazioni diverse
anomalia di modifica
444
7
Anomalia di cancellazioneTutti i video relativi a “Pulp fiction” di Quentin Tarantino hannodei problemi e devono essere sostituiti
Ogni informazione sul film “Pulp fiction” viene persa
anomalia di cancellazione
8
Anomalia di inserimentoVogliamo inserire l’elenco dei film per i quali verranno resi disponibilialcuni video a partire dal prossimo mese
Poiche’ la collocazione del video e` chiave di FilmInVideo, le informazionirelative ad un film non possono essere inserite finche’ non e` nota la
collocazione di almeno un video relativo a quel film
anomalia di inserimento
mediterraneo gabriele salvatores 1991 commedia 3.80?
9
Ridondanza e anomalie
Il problema legato alla presenza di anomaliedipende dall’avere utilizzato un’unicarelazione per memorizzare informazionirelative a film e video
concettualmente rappresentano due entita` distinte che condividono un’associazione
Tali anomalie non si verificano se utilizziamole relazioni Film e Video
10
Teoria della normalizzazione –obiettivi
Identificare situazioni che possono generare anomalie, partendodall’analisi di alcuni tipi di vincoli di integrita` validi per lo schema dipartenza
dipendenze funzionaliIdentificare quali proprieta`, rispetto alle dipendenze funzionali, unoschema deve soddisfare affinche` non sia soggetto ad anomalie
definizione di forme normali per gli schemi relazionaliFornire strumenti per trasformare lo schema relazionale di partenzain uno schema equivalente al precedente che soddisfi una forma normale
scomposizioneprevede la sostituzione di una relazione che presenta anomalie con un insieme di relazioni, che non presentano tale problemail processo di scomposizione e` guidato dalle dipendenze funzionaliidentificate
11
Teoria della normalizzazione –osservazione
La normalizzazione puo` portare ad inefficienze nelleprestazioni, nel caso in cui le interrogazioni richiedanofrequentemente di combinare i dati suddivisi in relazionidistinteDeterminare la valutazione del film corrispondente ad un certo video
FilmInVideo (non normalizzata) interrogazione su singolatabellaFilm + Video (normalizzate) join
Il processo di normalizzazione deve essere applicato con le dovute cautele
12
Dipendenze funzionaliLa presenza di ridondanza in uno schema dipende daproprieta` del dominio applicativo che possono essererappresentate tramite vincoli di integrita`
dipendenze funzionali
Le dipendenze funzionali, come ogni altra tipologia divincoli, devono essere identificate durante la fase diprogettazione concettuale, a partire dal documento dispecifica dei requisiti
13
Dipendenze funzionali –concetti di base
Una dipendenza funzionale descrive un legame di tipo funzionaleesistente tra gli attributi di una singola relazione
dati il titolo ed il regista di un film, l’anno di produzione, il genere e la valutazione assegnati al film sono unici
titolo e regista determinano funzionalmente i valori degli attributianno, genere e valutaz
14
Dipendenze funzionali –definizione
R(A1,A2,....An) schema di relazioneX e Y sottoinsiemi di UR
r istanza di R(A1,A2,....An)
r soddisfa X Y se, per ogni coppia di tuplet1 e t2 in r, vale
se t1[X] = t2[X] allora t1[Y] = t2[Y]
15
Dipendenze funzionali –definizione
X determina funzionalmente Y in R(A1, A2, ...., An), indicato con X →R(A1,...,An) Y (o con X → Y , in assenza di ambiguita`) se qualunqueistanza r di R(A1,A2,....,An) soddisfa X → Y
X →R(A1,...,An) Y (X → Y ) e` chiamatadipendenza funzionale su UR
16
Dipendenze funzionali –notazione
A1A2 . . .An denota l’insieme {A1,A2, . . . ,An}
dati X e Y insiemi di attributi, XY denota X U Y
17
Dipendenze funzionali –esempio
a) titolo regista → annob) titolo regista → valutazc) titolo regista → registad) colloc → titolo registae) colloc → valutazf) titolo → regista
titolo → colloc
VALGONO NON VALE
18
Dipendenze funzionali – tipi (a), (b), (d) dipendono dalla semantica dei dati
sono vincoli di integrita`devono essere determinati durante la fase di progettazioneconcettuale
(f) dipende dalla specifica istanza consideratanon e` un vincolo di integrita`
(c) sempre validadipende dalla definizionedipendenza funzionale banale
(e) implicata dalle dipendenze (b) e (d)dipendenza funzionale derivata
19
Dipendenze funzionali derivate
Formalizzabili tramite la nozione diimplicazione logica di un insieme didipendenze funzionaliL’implicazione logica permette di determinarel’insieme massimale di dipendenze funzionaliderivabili a partire da un insieme didipendenze funzionali dato
chiusura di un insieme di dipendenzefunzionali
20
Dipendenze funzionali derivateR(A1, ...,An) schema di relazioneF insieme di dipendenze funzionali su URX → Y dipendenza funzionale su UR
F implica logicamente X → Y , denotato con F |= X → Y , se qualunque istanza r di R(A1, ...,An) che soddisfa tuttele dipendenze in F, soddisfa anche X → Y
La chiusura di F, denotata con F+, e` l’insieme delledipendenze funzionali logicamente implicate da F
F+ = {X → Y | F |= X → Y }
21
Dipendenze funzionali derivate – esempio
F = titolo regista → annotitolo regista → valutaztitolo regista → registacolloc → titolo registacolloc → valutaztitolo → regista
F |= colloc → annoF |= colloc → titoloF |= colloc → regista
Escludendo le dipendenze banali e ridondanti:F+ = F U {colloc → anno, colloc → titolo, colloc → regista}
22
Regole di ArmstrongIl calcolo di F+ e` fondamentale per applicare la teoriadella normalizzazioneA questo proposito, e` stato definito un insieme di regoledi inferenza che permette di calcolare F+
regole di ArmstrongOgni regola di Armstrong ha la forma:
se G allora X → Ydove G e` un insieme (eventualmente vuoto) didipendenze funzionali (le premesse) e X → Y e` unadipendenza funzionale (la conclusione)
23
Regole di ArmstrongD insieme di attributi
A1: riflessivita`. Sia Y ⊆ X ⊆ D. Allora X → Y
A2: additivita`. Sia Z ⊆ D. Se X → Y, allora XZ → Y Z
A3: transitivita`.Se X → Y e Y → Z, allora X → Z
24
Regole di Armstrong derivateNon aumentano il potere espressivo
A4: unione.Se X → Y e X → Z, allora X → Y Z
A5: pseudotransitivita`.Se X → Y e WY → Z, allora XW → Z
A6: scomposizione. Sia Z ⊆ Y. Se X → Y , allora X → Z
25
Regole di Armstrong –derivazione
Le regole di Armstrong possono essere concatenate in modo che le conclusioni di un certo insieme di regolediventino le premesse di un’altra regola
Derivazione
Dato un insieme di dipendenze funzionali F, X → Y e` derivabile da F, indicato con F ⊢ X → Y , se esiste unaderivazione le cui premesse sono contenute in F e la cui conclusione coincide con X → Y
26
Regole di Armstrong –proprieta`
Le regole di Armstrong sono corretteogni derivazione con premesse in F puo` derivare solo conclusioni in F+
Le regole di Armstrong sono completeogni dipendenza funzionale in F+ puo` essere derivata a partire da F, applicandotali regole
27
Regole di Armstrong –proprieta`
F insieme di dipendenze funzionali su un insieme di attributi DX ⊆ D, Y ⊆ D
F ⊢ X → Y se e solo se F |= X → Y
28
Chiusura di un insieme diattributi
La computazione di F+ e` molto costosaesponenziale nel numero di dipendenze
Spesso non e` necessario calcolare F+ ma e` sufficiente stabilire se una certadipendenza funzionale appartiene ad F+
algoritmo semplice ed efficiente basato sullanozione di chiusura di un insieme di attributirispetto ad un insieme di dipendenze
29
Chiusura di un insieme diattributi
Contiene tutti gli attributi che possono esserederivati da quelli di partenza, utilizzando le dipendenze funzionali date
F insieme di dipendenze funzionali su un insieme diattributi DX ⊆ D
La chiusura di X rispetto ad F, denotata con X+, e` l’insieme {A ∈ D | F ⊢ X → A}
30
Chiusura di un insieme diattributi – proprieta`
F insieme di dipendenze funzionali
F ⊢ X → Y se e solo se Y ⊆ X+, con X+
calcolata rispetto ad F
31
Chiusura di un insieme diattributi – algoritmo
Attributi funzionalmentedeterminati da X(i)
32
Chiusura di un insieme diattributi – esempioa) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipo
X = collocX(0) = collocX(1) = colloc tipo titolo registaX(2) = colloc tipo titolo regista anno genere valutazX(3) = X(2) = X+ = U FilmInVideo
33
Chiavi
Il concetto di chiave puo` essere definito in termini di dipendenze funzionaliUtile per
determinazione delle forme normaliverificare se le chiavi identificate durante la progettazione logica sono correttamente definite rispetto alle dipendenze funzionali
34
Chiavi
R(A1, ...,An) schema di relazioneF insieme di dipendenze funzionali su UR
X ⊆ UR
X e` chiave di R(A1, ...,An) se verifica le seguenti condizioni:1. X → A1 A2 . . . An ∈ F+
2. non esiste Y ⊆ X tale che Y → A1 A2 . . . An ∈ F+
35
ChiaviX e` chiave per uno schema di relazione R(A1, ...,An)
rispetto ad un insieme di dipendenze funzionali F
F |= X → A1 A2 . . . An
F ⊢ X → A1 A2 . . . An
A1 A2 . . . An ⊆ X+
36
Chiavi – osservazione
Se un attributo non compare mai a destra diuna dipendenza funzionale in F, questoattributo fara` certamente parte della chiaveIn caso contrario, non sarebbe possibilederivarlo applicando le regole di Armstrong
37
Chiavi – esempio
R(C,S,Z)F = {CS → Z, Z → C }CS+ = SZ+ = CSZ
CS e SZ sono chiavi per R
38
Chiavi – esempioFilmInVideo(colloc titolo regista anno genere valutaz tipo)
a) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipo
Sappiamo che colloc e` chiave della relazioneLe dipendenze funzionali ci permettono di verificare che questovincolo e` correttoInfatti:
colloc+ = UFilmInVideocondizione di minimalita` soddisfatta
39
Chiavi – esempioSupponiamo di non conoscere la chiave diFilmInVideo e di volerla determinare
colloc non compare mai a destra in una dipendenzafunzionale
colloc appartiene alla chiave
colloc+ = UFilmInVideocolloc e` chiavecolloc e` l’unica chiave
40
Forme normaliLe forme normali sono state introdotte per stabilire condizioni che, se soddisfatte da unoschema relazionale, garantiscono l’assenzadelle anomalie discusse in precedenzaEsistono vari tipi di forme normali
differiscono per il tipo di anomalie che permettonodi evitare
Forme normali piu` note:forma normale di Boyce-Codd (BCNF)terza forma normale (3NF)
41
Forme normaliBCNF
Permette di evitare un insieme molto ampio dianomaliePiu` restrittiva di 3NFPoco usata nellapratica
3NF
Permette di evitare un insieme piu` ristretto dianomalieMeno restrittiva diBCNFMolto usata nellapratica
42
Forme normali – osservazioneFilmInVideo(colloc titolo regista anno genere valutaz tipo)Le dipendenze
{titolo regista→anno titolo regista→genere titolo regista → valutaz} generano ridondanza:
molti video possono corrispondere allo stesso film, quindi avere lo stessotitolo e stesso registain base alle dipendenze, molti video avranno anche lo stesso valore per anno, genere e valutaz
La dipendenza colloc → titolo regista non genera ridondanzacolloc e` chiave per FilmInVideonon e` possibile che due tuple abbiamo lo stesso valore per colloc
X → Y , con X chiave o super-chiave per la relazione considerata, non potra` mai generare ridondanze e quindi anomalie
43
Forme normali – BCNF
R(A1, ...,An) schema di relazioneF insieme di dipendenze funzionali su UR
R(A1, ...,An) e` in forma normale di Boyce-Codd (BCNF) rispetto ad F se per ognidipendenza funzionale X → Y ∈ F, con Y ⊆X, allora X e` una chiave o super-chiave di R
44
Forme normali – BCNF –esempio
FilmInVideo(colloc titolo regista anno genere valutaz tipo)
a) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipo
Sappiamo che l’unica chiave di tale relazione e` collocLo schema non e` in BCNF in quanto le dipendenze
titolo regista → anno, titolo regista →genere e titolo regista → valutaznon soddisfano la condizione di BCNF
titolo regista non e`chiave o super-chiave della relazione
45
Forme normali – BCNF –esempio
Video(colloc,tipo,titoloFilm,registaFilm)Film(titolo,regista,anno,genere,valutaz)Dipendenze funzionali:
colloc → tipo titolo regista per Videotitolo regista → anno genere valutaz per Film
Sono in BCNFle uniche dipendenze funzionali sono quelle chehanno la chiave sul lato sinistro
46
Forme normali – 3NFLa BCNF impone una condizione molto forte
permette di evitare ogni tipo di anomalia, in quanto evita ogni tipodi ridondanzapotrebbe non permettere di modellare alcuni vincoli rilevanti per ildominio applicativo (tutti quelli che a sinistra non contengono unachiave od una superchiave)come vedremo successivamente, se una relazione non soddisfala BCNF non sempre e` possibile decomporla per ottenere unoschema equivalente in BCNF per il quale valgano tutte le dipendenze funzionali di partenza
Alcune delle precedenti restrizioni si possono superare con la 3NF
Forma normale piu` deboleGli schemi in 3NF ammettono una certa ridondanza, benche’ limitata
47
Forme normali – 3NF –attributo primo
R(A1, ...,An) schema di relazione
Ai, 1 ≤ i ≤ n, e` un attributo primo per R(A1, ...,An) se Ai e` elemento di una qualchechiave di R
48
Forme normali – 3NF
R(A1, ...,An) schema di relazioneF insieme di dipendenze funzionali su UR
R(A1, ...,An) e` in terza forma normale (3NF) rispetto ad F se per ogni dipendenzafunzionale X → Y ∈ F, con Y ⊆ X, allora:
X `e una chiave o super-chiave di R oppure∀ A ∈ Y , A e` un attributo primo per R(A1, ...,An)
49
Forme normali – 3NF
BCNF 3NF
BCNF 3NF
50
Forme normali – 3NF –esempio
R(C,S,Z)F = {CS → Z, Z → C }CS+ = SZ+ = CSZ
Attributi primi = CSZLo schema e` in 3NFPoiche` Z non e` ne’ chiave ne’ super-chiave, lo schema non e` in BCNF
51
Forme normali – 3NF –esempio
FilmInVideo(colloc titolo regista anno genere valutaz tipo)
a) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipo
Attributi primi = collocLo schema non e` in 3NF
52
ScomposizioneUna volta scelta una forma normale, la base di datiottenuta tramite la progettazione logica non necessariamente soddisfa le proprieta` imposte datale forma normale
E` necessario trasformare lo schema di ogni relazionein uno o piu` schemi di relazioni che soddisfino tale forma normale
scomposizione
53
Scomposizione
La scomposizione di uno schema di relazioneR(A1, ...,An)
e` la sua sostituzione con un insieme dischemi relazionali Σ = {R1,R2, . . . ,Rk} non necessariamente disgiunti tali che
UR = UR1 ∪ UR2 ∪ . . . ∪ URk
54
Scomposizione – proprieta`
Lossless join (join senza perdite)Preservazione delle dipendenze funzionali
55
Scomposizione lossless joinSe una relazione viene scomposta, e` importante chesia possibile riottenere esattamente la stessarelazione eseguendo il join naturale delle relazioni in cui e` stata scomposta
R(A1, ...,An) schema di relazioneF insieme di dipendenze funzionali su UR
Σ = {R1,R2, . . . ,Rk} scomposizione di R(A1, ...,An)
Σ e` lossless join rispetto ad F se per ogni istanza r di R(A1, ...,An) che soddisfa F, vale:
r = ΠR1 (r) ΠR2 (r) . . . ΠRk (r)
56
Scomposizione lossless join -esempio
R(A,B,C,D,E,G,H,I) F = {A → HI, B → DE}Le istanze di R non sono scomponibili senza perdite rispetto ad ABDEI ed ACGH
r
ΠABDEI (r) ΠACGH (r)
ΠABDEI (r) ΠACGH (r)
57
Scomposizione lossless join
Esiste un algoritmo generale per determinarese una data scomposizione verifica la proprieta` di lossless join
non lo vediamoIntroduciamo invece un semplice test applicabile nel caso in cui la scomposizionecontenga solo due schemi
58
Scomposizione lossless joinΣ = {R1,R2} scomposizione per R(A1, ...,An)F insieme di dipendenze funzionali su UR
Σ ha la proprieta` di lossless join rispetto ad F se e solo se F implica logicamente una delle seguentidipendenze funzionali: 1. (UR1 ∩ UR2) → (UR1 − UR2 )2. (UR1 ∩ UR2) → (UR2 − UR1 )
59
Scomposizione lossless join –esempio
R(A,B,C,D,E,G,H,I) F = {A → HI, B → DE}Le istanze di R sono scomponibili senza perditerispetto ad ABDEI ed ABCGHInfatti
ABDEI ∩ ABCGH = ABABDEI \ ABCGH = DEIAB → DEI ∈ F+
60
Scomposizione lossless join –esempio
FilmInVideo(colloc titolo regista anno genere valutaz tipo)a) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipo
R1(colloc,tipo,titoloR2,registaR2)R2(titolo,regista,anno,genere,valutaz)soddisfa la proprieta` di lossless join
UR1 ∩ UR2 = {titolo, regista}UR2 − UR1 = {anno, genere, valutaz}F |= titolo regista→anno genere valutaz
61
Scomposizione lossless join -esempio
FilmInVideo(colloc titolo regista anno genere valutaz tipo)a) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipo
R1(colloc,tipo)R2(titolo,regista,anno,genere,valutaz)non soddisfa la proprieta` di lossless join
UR1 ∩ UR2 = { }UR2 − UR1 = UR2→ UR2 ovviamente non vale in F+
Una scomposizionecon schemi disgiuntinon e` mai lossless join
62
Scomposizione che preservale dipendenze
Un’altra importante proprieta` di una scomposizionedi uno schema R in Σ = {R1, ...,Rk} e` che l’insiemedelle dipendenze funzionali F definito per R siaimplicato dalle proiezioni di F sugli schemi R1, . . ., Rk
La nozione di proiezione permette di restringere un insieme di dipendenze funzionali ad un sottoinsiemedi attributi dello schema per il quale sono state definite
63
Scomposizione che preservale dipendenze
D insieme di attributiF insieme di dipendenze funzionali su DZ ⊆ D
La proiezione di F su Z, denotata con Π Z(F), e` l’insieme {X → Y |X → Y ∈ F+ | XY ⊆ Z}
64
Scomposizione che preservale dipendenze
R(A1, ...,An) schema di relazioneΣ = {R1, . . . ,Rk} scomposizione per R(A1, ...,An)F insieme di dipendenze funzionali su UR
Σ preserva le dipendenze in F se ∪ i=1,...,k ΠRi (F) |= F
Se vengono verificate le dipendenze locali ad ogni schema, alloraanche le dipendenze globali (che coinvolgono schemi diversi)
sono verificate
65
Scomposizione che preservale dipendenze - esempio
R(C,S,Z) F = {CS → Z, Z → C}. Σ = { R1, R2 } R1(S,Z) R2(C,Z) Σ ha la proprieta` di lossless join
{S, Z} ∩ {C, Z} → {C, Z} − {S, Z} ∈ F+
ΠR1(F) = { S → S, Z → Z}ΠR2(F) = { C → C, Z → Z, Z → C}CS → Z non e` preservata
66
Scomposizione che preservale dipendenze – esempio
FilmInVideo(colloc titolo regista anno genere valutaz tipo)a) titolo regista → annob) titolo regista → generec) titolo regista → valutazd) colloc → titolo registae) colloc → tipof) anno → tipo
Σ = { R1, R2 } R1 = colloc titolo regista tipoR2 = titolo regista anno genere valutaz
ΠR1(F) = { (d), (e) }ΠR2(F) = { (a), (b), (c) }
ΠR1(F) U ΠR2(F) |= (f) anno+ = anno
Σ non preserva le dipendenze
67
Scomposizione che preservale dipendenze – algoritmi
Dalla definizione discende algoritmo per determinare se una scomposizione Σ = {R1, . . . ,Rk} preserva un insieme di dipendenzefunzionali F
basato sul calcolo di Fesponenziale nella dimensione di F
Esistono altri algoritmi polinomiali, che non presentiamo, basati sul concetto di chiusuradi un insieme di attributi
68
Scomposizione che preservale dipendenze – osservazione
Dato X ⊆ Ri, la dipendenza funzionale ottenuta da X → X+ (con X+ calcolato rispetto ad F) eliminando gliattributi a destra che non compaiono in Ri appartienea ΠRi (F)
Ogni dipendenza funzionale che appartiene a ΠRi (F) puo` essere calcolata in questo modo
69
Scomposizione che preservale dipendenze – esempio
R(A,B,C,D) F = {A → B, B → C, C → D, D → A}Σ = {AB, BC, CD}A+ = B+ = C+ = D+ = ABCDΠAB(F) = {A → B, B → A}ΠBC(F) = {B → C, C → B} ΠCD(F) = {C → D, D → C}G = ΠAB(F) U ΠBC(F) U ΠCD(F)
Stabiliamo se D → A e` preservata da ΣD+ = ABCD calcolato rispetto a GD → A `e preservata da Σ
70
Scomposizione in BCNFQualsiasi schema di relazione ammette unascomposizione BCNF che soddisfa la proprieta` dilossless joinE` possibile che non esista, per un dato schema direlazione, una scomposizione in BCNF che preservi le dipendenze
Il prezzo da pagare per ottenere una forma normale cheelimini completamente le anomalie, come la BCNF, e`
una potenziale perdita di vincoli di integrita`
71
Scomposizione in BCNF –algoritmo
Scomposizione lossless join di SComplessita` dipende dallacomplessita`calcoloproiezioni
72
Scomposizione in BCNF –esempio
R(C,S,Z) F= {CS → Z, Z → C}Chiavi CS e SZNon e` in BCNF
Σ = {S1, S2} non preserva CS → Z
Z → C viola la BCNF
S1(C, Z) ΠS1(F)= {Z → C}Chiave ZBCNF
Π
S2(S, Z) ΠS2(F) = { }Chiave SZBCNF
73
Scomposizione in BCNF –esempio
FilmInVideo(colloc titolo regista anno genere valutaz tipo)F = { (a) titolo regista → anno genere valutaz,
(b) colloc → titolo regista tipo}Chiave collocNon e` in BCNF
Σ = {R1, R2} preserva le dipendenze
titolo regista → anno genere valutazviola la BCNF
R1(titolo,regista,anno,genere,valutaz)ΠR1(F)= { (a) }Chiave titolo registaBCNF
ΠR2(colloc,titolo,regista, tipo)ΠR2(F)= { (b) }Chiave collocBCNF
74
Scomposizione in 3NF
L’algoritmo che vedremo puo` essereapplicato solo sotto opportune ipotesiSe queste ipotesi sono soddisfatte, l’algoritmo genera una scomposizione in 3NF lossless join che preserva le dipendenzeL’insieme di dipendenze funzionali deveessere minimale
l’insieme non deve quindi contenere ridondanze
75
Scomposizione in 3NF –minimalita` 1. Unicita` degli attributi a destra
1. Il lato destro di ogni dipendenza in F corrisponde ad un singoloattributo
2. Assenza di dipendenze funzionali ridondantiPer nessuna dipendenza X → A ∈ F, l’insieme di dipendenze G = F − {X → A} e` equivalente ad F, cioe` vale F+ = G+
Per determinare se questa condizione e` soddisfatta, si calcolaX+ rispetto a F − {X → A}
se A e` in X+, allora F+ = G+ e quindi X → A e` ridondante3. Assenza di attributi a sinistra ridondanti
Per nessuna dipendenza X → A ∈ F e nessun sottoinsieme Z diX, l’insieme di dipendenze G = F − {X → A} U {Z → A} e` equivalente ad F, cioe` vale F+ = G+
Z e` ridondante in X → A se (X − Z)+, calcolata rispetto ad F, contiene A
76
Scomposizione in 3NF –minimalita`
Per la regola di scomposizione e` sempre possibilericondursi alla forma richiesta dalla condizione (1)E` possibile dimostrare che per ogni insieme didipendenze funzionali F esiste un insieme didipendenze funzionali minimale G tale che F+ = G+
L’insieme G puo` essere calcolato applicando le regole precedenti in sequenza, considerando unadipendenza funzionale alla voltaL’ordine in cui le varie dipendenze sono esaminatepuo` generare insiemi minimali diversi
77
Scomposizione in 3NF –esempio
R(A,B,C,D)F = {AB → D, A → B, A → C, B → C, C → B}Unicita` attributi a destra soddisfattaDipendenze ridondanti
A → BA+ = ABCD rispetto ad F − {A → B}A → B e` ridondanteF3 = F − {A → B}Nessun’altra dipendenza puo` esseeliminata
Attributi ridondanti a sinistraAB → D
A+ = ABCD calcolata rispetto adB puo` essere eliminata da AB F4 = {A → D, A → C, B → C, CB} minimale
A → CA+ = ABCD rispetto ad F −{A → C} A → C e` ridondante
F1 = F −{A → C}Nessun’altra dipendenza puo` essereeliminata
Attributi ridondanti a sinistraAB → D
A+ = ABCD calcolata rispetto ad F1 B puo` essere eliminata da AB → D
F2 = {A → D, A → B, B → C, C → B} minimale
78
Scomposizione in 3NF –algoritmo
79
Scomposizione in 3NF –esempio
R(A,B,C,D)F = {A → D, A → B, B → C, C → B} minimaleA+ = ABCD A e` l’unica chiaveLo schema non e` in 3NF
C → B e B → C non soddisfano condizioneGeneriamo gli schemi R1(A,D), R2(A,B) ed R3(B,C)Gli schemi R1(A,D) e R2(A,B) possono essere combinatiottenendo il nuovo schema R1,2(A,B,D)
R1,2(A,B,D) R3(B,C)R1,2 contiene la chiave
R1,2(A,B,D) R3(B,C) 3NF lossless join e preserva le dipendenze
80
Scomposizione in BCNF –esempio
R(A,B,C,D)F = {A → D, A → B, B → C, C → B} Chiave ANon e` in BCNF
Σ = {R1, R2} preserva anche A → BA+ = ABCD calcolato rispetto a ΠR1(F) U ΠR2(F)
C → B viola la BCNF
R1(B,C) ΠR1(F)= {B → C, C → B}Chiavi B e CBCNF
R2(A,D,C) ΠR2 (F) = {A → D, A → C }Chiave aBCNF
81
OsservazioneLa progettazione logica, insieme alla normalizzazione, permette di generare schemi relazionali di qualita`, a partire da schemi ERSe utilizziamo le metodologie di progettazione basatesui diagrammi ER gli schemi relazionali ottenuti sonogia` in 3NF
82
OsservazioneLa normalizzazione rappresenta comunque un utile strumento di verifica di qualita`
non sempre le basi di dati esistenti sono state progettateseguendo i criteri propostilo schema di una base di dati puo` evolvere nel tempo
a questa evoluzione non sempre si affianca un raffinamentodella documentazionemodifiche applicate a schemi normalizzati, se effettuate con scarsa attenzione, possono portare alla generazione diridondanze
utile strumento per verificare la scelta degli identificatori, e diconseguenza delle chiavi, determinate nelle fasi diprogettazione concettuale e logica