 |  | |
|
| | |
|
| |
Ridondanza dell'informazione: la medesima informazione è ripetuta molte volte senza che ce ne sia la necessità.
Erronea rappresentazione dell'informazione: non si possono inserire certe informazioni se non se ne inseriscono anche altre logicamente distinte.
Perdita di informazione: si ha quando si opera una divisione di uno schema in più schemi e il join tra questi ultimi non restituisce esattamente lo schema originario.
a b se t1[a]=t2[a] allora t1[b]=t2[b
banalmente: a a
a b con b a
È l'insieme di tutte le dipendenze funzionali F+ che si possono ricavare partendo da un insieme dato di dipendenze F applicando esaustivamente i seguenti assiomi:
Riflessività a a
se b a allora a b
Arricchimento se a b allora ga gb
Transitività se a b e a g allora a g
Estendendo gli assiomi:
Unione se a b e a g allora a bg
Decomposizione se a bg allora a b e a g
Pseudotransitività se a b e gb d allora ga d
Il calcolo di F+ è esponenziale.
Dato un insieme di attributi a si definisce chiusura di a l'insieme a dove
se a B F+ allora B a
Algoritmo per ottenere a
result := a
while (result cambia) do
for each b g in F
begin
if b result then result := result g
end
il calcolo di a va con il quadrato del numero delle dipendenze funzionali.
È l'insieme Fc ricavato da F meno tutte le dipendenze ridondanti.
f F è ridondante se ( F - )+ F+
Fc è un insieme di dipendenze tali che F implica logicamente tutte le dipendenze di Fc ed Fc implica logicamente tutte le dipendenze di F, cioè F+ Fc+ (i due insiemi sono equivalenti). Fc deve soddisfare le seguenti proprietà:
ogni a b in Fc non contiene attributi estranei in a cioè:
F ( F - )
ogni a b in Fc non contiene attributi estranei in b cioè:
F ( F - )
ogni a in Fc è unico
Algoritmo per ottenere F +
repeat
applicare l'unione in ogni dipendenza di F per sostituire ogni
a b e a b con a b b
cercare in ogni dipendenza funzionale a b gli attributi estranei in a o in b
eliminare gli attributi estranei;
until F non cambia
Dato lo schema R, sia F l'insieme delle dipendenze funzionali definite su R. Siano R1 e R2 due schemi derivati dalla decomposizione di R. Questa decomposizione è priva di perdite se vale almeno una delle seguenti affermazioni:
R1 R2 R1
R1 R2 R2
Sia F l'insieme delle dipendenze funzionali definite su R e sia R1, R2, ., Rn una decomposizione di R. La restrizione di F su Ri è l'insieme Fi delle dipendenze funzionali di F+ che includono solo attributi di Ri. Sia F'=F1 F2 Fn. In generale F F' ma se (F')+=F+ allora la decomposizione mantiene tutte le dipendenze.
Calcolare F+
for each schema Ri in do
begin
Fi := restrizione di F+ su Ri
end
F' := 0
for each restrizione Fi do
begin
F' := F' Fi
end
Calcolare F'+
if (F'+= F+) then return true; else return false;
Ma richiede il calcolo di due chiusure, quindi è troppo pesante. Si usano, in alternativa dei metodi che possono semplificare il test
1° Metodo
Verificare se tutte le dipendenze funzionali di F si proiettano nei sottoschemi, in tal caso infatti ( Fi )+ F+. Questo è il caso più semplice, se non si verifica non posso dire niente perché le dipendenze che non si sono proiettate esplicitamente possono comunque essere rispettate implicitamente.
2° Metodo
Verifichiamo che l'insieme Fi ed F siano equivalenti. Si verifica cioè che ogni insieme di dipendenze appartenga alla chiusura dell'altro.
Fi F+ e questo è verificato per costruzione;
2. F Fi)+ per ogni dipendenza a b di F che non si proietta esplicitamente: se a UFi b allora a b Fi)+
3° Metodo
Si utilizza quando fallisce il primo metodo.
F = dove
F' è l'insieme di dipendenze che si proiettano esplicitamente su F
F'' è l'insieme di dipendenze che non si proiettano esplicitamente su F
e non accade che F' determina F''.
Occorre dimostrare che F'' Fi
Devo capire se manca F''' tale che
(F F''') (F''' Fi )
in tal caso le dipendenze sono mantenute.
In tutti i casi, se trovo delle dipendenze che non si proiettano nei sottoschemi devo assolutamente reinserile per assicurare la legalità delle inserzioni nella base di dati. Quindi se una dipendenza non è mantenuta va aggiunto uno schema che la mantenga esplicitamente oppure va integrato uno dei sottoschemi esistenti.
Attributo Primo: se appartiene almeno ad una chiave candidata;
Attributo Semplice: se il suo dominio è caratterizzato da valori atomici;
Attributo Multivalore: se il suo dominio è caratterizzato da una lista;
Attributo Strutturato: se il suo dominio è divisibile in un certo numero di sottocampi;
Uno schema si trova in 1NF se ogni suo attributo è semplice, cioè caratterizzato solo da valori atomici.
Uno schema si trova in 2NF se è in 1NF e non esistono dipendenze parziali di attributi non primi dalla chiave (da ogni chiave candidata).
oppure
Uno schema si trova in 2NF se è in 1NF e, per ogni attributo A in R si ha almeno una delle seguenti condizioni:
a. A appare in una chiave candidata;
b. A non dipende parzialmente da nessuna chiave candidata.
Dipendenza transitiva generale o debole: a b g g a b
Dipendenza transitiva ristretta o forte: a b g g a b
Uno schema si trova in 3NF se è in 1NF e non ci sono dipendenze transitive (in forma generale) di alcun attributo non primo da alcuna chiave.
oppure
Uno schema si trova in 3NF se è in 1NF e, per ogni dipendenza funzionale non banale a b, vale almeno una delle seguenti:
a. a è superchiave;
b. ogni attributo in b è primo.
Algoritmo per una decomposizione in 3NF
(mantiene sempre le dipendenze)
Sia Fc la copertura canonica dell'insieme delle dipendenze funzionali F;
i:=0;
for each dip. funzionale a b in Fc do
if nessuno schema Rj, j=1,2.i contiene ab
then begin
i:=i+1;
Ri:= ab
end
if nessuno degli schemi Rj, j=1,2.i contiene una chiave candidata per R
then begin
i:=i+1;
Ri:= una qualsiasi chiave candidata per R;
end
return (R1, R2, . Ri)
Uno schema si trova in BCNF se è in 1NF e, per ogni dipendenza funzionale non banale a b, con b non in a e a R, a è superchiave.
oppure
Uno schema si trova in BCNF se è in 1NF e non ci sono dipendenze transitive dalla chiave.
Algoritmo per una decomposizione in BCNF
(può non mantenere le dipendenze!)
result := ;
done := false;
compute F+;
while (not done) do
if (esiste uno schema Ri in result che non è in BCNF)
then begin
sia a b una dipendenza funzionale non banale su Ri tale che a Ri non è in F+ e a b
result :=(result - Ri) (Ri - b a b
end
else done := true;
Se le dipendenze non sono mantenute ci accontentiamo della 3NF, che è sempre raggiungibile mantenendo contemporaneamente le dipendenze.
Se in uno schema R si riconosce un insieme di attributi a, un insieme di attributi b e il resto dello schema R - a b per cui per uno stesso valore degli attributi a ci sono più valori degli attributi b che non dipendono da R - a b allora diciamo:
a b
cioè che a multidetermina b
oppure
a b se in ogni relazione legale r e per ogni coppia di tuple t1,t2 in r si ha:
(t1[a t2[a [ t1[a] = t2[a
t3, t4 ( t3[a] = t4[a] = t1[a
t3[b] = t1[b t4[b] = t2[b
t3[R-a b] = t2[R-a b
t4[R-a b] = t1[R-a b
cioè graficamente:
|
|
|
|
|
|
A |
|
|
|
W |
|
|
|
A |
|
|
|
W |
|
oppure
Sia R(a b g) uno schema tutto chiave dove r sia una relazione legale in R
dove: r1 = ab(r) e r2 = ag(r).
a b e a g se e solo se r1 >< r2 = r
Nota: Le dip. funzionali sono un caso particolare delle dip. multivalore
Sia D l'insieme delle dipendenze funzionali e multivalore. La chiusura D+ di D è l'insieme delle dipendenze multivalore e funzionali implicate logicamente da D. Gli assiomi che ci servono sono quelli di Armstrong e in più:
Complementazione: se a b allora a R - a b
Arricchimento multivalore: se a b g R e d g allora ga db
Transitività multivalore: se a b e b g allora a ->-> g b
Da cui possiamo dedurre le seguenti due regole inferenziali:
Replica: se a b allora a b
Coalescenza: se a b g b, ed esiste d g e d g=0 e d g allora a g
inoltre:
Unione Multivalore: se a b e a g allora a bg
Intersezione: se a b e a g allora a b g
Differenza: se a b e a g allora a b g e a g b
Sia dato uno schema R e sia D l'insieme delle dipendenze funzionali e multivalore su R. Siano R1 e R2 una decomposizione di R. Questa decomposizione è priva di perdite se e solo se vale almeno una delle seguenti dipendenze multivalore in D+:
R1 R2 R1
R1 R2 R2
Si noti l'analogia con le dipendenze funzionali, in questo caso però l'implicazione è un se e solo se e non un semplice se. allora.
Sia dato uno schema R e sia R1, R2, . Rn una decomposizione di R. Consideriamo l'insieme D di tutte le dipendenze multivalore e funzionali. La restrizione di D in Ri dell'insieme Di consiste in:
Tutte le dipendenze funzionali di D+ che includono solo attributi di Ri
Tutte le dipendenze multivalore della forma
a b Ri
dove a Ri e a b è in D+.
La decomposizione dello schema R negli schemi R1, R2, . Rn è una decomposizione che mantiene le dipendenze se, per ogni insieme di relazioni r1(R1), r2(R2) . rn(Rn), con ri legale in Di, esiste una relazione r(R) che soddisfa D e per la quale ri = Ri(r) per ogni i.
Uno schema è in 4NF se è in 1NF e, per ogni dipendenza multivalore a b con a R e b R vale almeno una delle seguenti:
a. a b è una dipendenza multivalore banale;
b. a è superchiave per lo schema R.
Algoritmo per una decomposizione in 4NF
result := ;
done := false;
compute D+;
while (not done) do
if (esiste uno schema Ri in result che non è in 4NF)
then begin
sia a b una dipendenza multivalore non banale su Ri tale che
a Ri non è in D+ e a b
result :=(result - Ri) (Ri - b a b
end
else done := true;
Supponiamo di avere una relazione r di tre attributi, del tipo (A,B,C) quindi uno schema tutto chiave, e supponiamo che i campi siano riempiti come da figura. Possono esistere delle realtà particolari i cui valori osservati rispecchiano questa organizzazione e queste realtà godono della proprietà che è possibile decomporle senza perdere informazione. Osserviamo attentamente la struttura e le caratteristiche della nostra istanza:
|
A |
B |
C |
|
|
|
|
|
a1 |
b1 |
c2 |
|
a2 |
b1 |
c1 |
|
a1 |
b2 |
c1 |
|
a1 |
b1 |
c1 |
Notiamo i valori a1 e b1 per la prima tupla, sulla seconda tupla abbiamo b1, c1, sulla terza abbiamo c1, a1. In questo percorso abbiamo utilizzato i valori a1, b1, c1 e l'ultima tupla è proprio a1, b1, c1! Una struttura di questo genere descrive una realtà detta dipendenza di join e si scrive come:
*((A, B), (B, C), (A, C))
e significa che lo schema di partenza è decomponibile senza perdite nei tre sottoschemi indicati. Nota: Le dip. multivalore sono un caso particolare del dip. di join.
Uno schema R è in 5NF se e solo se ogni dipendenza di join presente è conseguenza di una chiave candidata.
oppure
Uno schema R è in 5NF se e solo se per ogni dipendenza di join vale almeno una delle seguenti affermazioni:
la dipendenza è banale (quando uno dei due sottoschemi è lo schema di partenza)
ogni Ri delle dipendenza di join è superchiave
Ma quest'ultima definizione fallisce in alcuni casi, ad esempio: *((A, C), (B, D)), infatti ogni schema è superchiave, ma il vincolo sussiste!
Non si può raggiungere con la decomposizione, ma solo mediante la rielaborazione del significato e del numero degli attributi. Dati:
D: insieme di vincoli di dominio del tipo PAi(r) dom (Ai);
K: insieme delle chiavi per cui Kj R;
G: insieme di tutti gli altri vincoli esistenti;
Uno schema è in DKNF se D K G
Se G è composto solo da vincoli del tipo: dipendenze funzionali, dipendenze multivalore, dipendenze di join allora la 5NF gode di questa proprietà;
Se G è composto solo da vincoli del tipo: dipendenze funzionali, dipendenze multivalore, allora la 4NF gode di questa proprietà;
Se G è composto solo da dipendenze funzionali, allora la BCNF gode di questa proprietà.
Significa fare un analisi critica della decomposizione operata sugli schemi, alla luce delle future e più frequenti interrogazioni che saranno fatte. Sarà quindi necessario riorganizzare gli schemi, riportandoli magari a forme normali meno sofisticate per garantire una certa efficienza nell'elaborazione delle interrogiazioni.
|
Privacy |
Articolo informazione
Commentare questo articolo:Non sei registratoDevi essere registrato per commentare ISCRIVITI |
Copiare il codice nella pagina web del tuo sito. |
Copyright InfTub.com 2024
