Caricare documenti e articoli online 
INFtube.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.
Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

PROGETTAZIONE DELLE BASI DI DATI

tecnica


Inviare l'articolo a Facebook Inviala documento ad un amico Appunto e analisi gratis - tweeter Scheda libro l'a yahoo - corso di

Progettazione delle Basi di Dati


Problematiche legate ad una progettazione non opportuna

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.

Definizione di dipendenza funzionale

a b se t1[a]=t2[a] allora t1[b]=t2[b




banalmente: a a

a b con b a

Chiusura di un insieme di dipendenze funzionali

È 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:

Assiomi di Armstrog

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.

Chiusura di un attributo

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.

Forma Canonica o Copertura Canonica

È 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

Decomposizione priva di perdite

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

Mantenimento delle dipendenze

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.


Algoritmo teorico per testare il mantenimento delle 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.

Definizione degli attributi

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;

Definizione di 1NF

Uno schema si trova in 1NF se ogni suo attributo è semplice, cioè caratterizzato solo da valori atomici.

Definizione di 2NF

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.

Dipendenze transitive

Dipendenza transitiva generale o debole: a b g g a b

Dipendenza transitiva ristretta o forte: a b g g a b

Definizione di 3NF

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)

Definizione di BCNF

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.

Definizione di Dipendenza Multivalore

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

Chiusura di un Insieme di dipendenze 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

Decomposizione priva di perdite

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.

Mantenimento delle dipendenze

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.

Definizione di 4NF

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;

Dipendenze di Join

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.

Definizione di 5NF o PJNF (project join normal form)

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!

Definizione di DKNF (domain key normal form)

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

Denormalizzazione

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


Hits: 1927
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI

E 'stato utile?



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2020