.dsy:it. - Esempi di Normalizzazione e decomposizione lossless join

Pages (3): [1] 2 3 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Basi di dati ~ comunicazione digitale (http://www.dsy.it/forum/forumdisplay.php?forumid=108)
-- Esempi di Normalizzazione e decomposizione lossless join (http://www.dsy.it/forum/showthread.php?threadid=31355)

Posted by Voodoo on 01-07-2007 17:38:

Esempio Normalizzazione

Posto un esercizio di normalizzazione,presente sul sito del prof nel pdf es_misti.pdf. Li ha risolti e commentati Svarions,io giro il tutto perchè possa essere utile a tutti e raccogliere il materiale necessario:

code:
Es 2
Si consideri R(A,B,C,D); per ciascuno dei seguenti gruppi di dipendenze
funzionali
1.  ABC -> D, D->A;
2.  AB->C, AB->D, C->A, D->B;
determinare:
a)  Tutte le chiavi di R.
b)  Se R è in 3NF.
c)  Se R è in BCNF; nel caso in cui non lo fosse, discutere l’esistenza
(ed eventualmente proporre) di una decomposizione 
che preservi le dipendenze funzionali.

Prima di tutto cominciamo con la prima f {abc ->d e d -> a}

Dobbiamo trovare le chiavi allora si guarda quali attributi (lettere) non compaiono mai a destra delle dipendenze funzionali, nel nostro caso bc. Partiamo con bc perché non compaiono mai a destra nelle dipendenze funzionali.
A questo punto sappiamo che bc sono sicuramente attributi primi cioè o sono chiave o fanno parte di una chiave (avendoli calcolati in questo modo faranno minimo parte di tutte le chiavi). Per vedere se sono chiavi si calcola la chiusura. Ricordiamo che per la chiusura vale che quando x(n-1) = x(n) allora si ha finito di calcolare la chiusura per quel determinato attributo:

code:
bc* x(o) = bc 	x(1) = bc

quindi non sono chiave, se lo fossore stati allora sarebbero stati anche l'unica chiave per quello detto prima (cioè che ogni chiave li deve contenere) dato che non sono chiavi ci resta da provare abc e bcd:

code:
abc* x(0) = abc 	x(1) = abcd
bcd* x(0) = bcd	x(1) = abcd

quindi sono entrambi chiavi. Deriviamo che le chiavi sono abc e bcd. Non esistendo altre combinazioni che contengono bc e che non contengono ne a ne b (anche singolarmente) allora sono le uniche chiavi (tutte le altre combinazioni sarebbero SUPER CHIAVI).
Abbiamo provato queste 2 combinazioni perché so che bc deve essere compreso nella chiave e che da solo non è chiave quindi la più piccola combinazione di attributi che contiene bc è bc più un attributo e dato che gli attributi sono abcd ci resta solo da provare bc + a e bc + d per capirci se ipoteticamente lo schema fosse stato abcde avremmo testato anche bc + e (bce).

Trovate le chiavi passiamo alla domanda 2. per vedere se è in 3nf deve essere che per ogni dipendenza funzionale:

o a sinistra abbiamo una chiave o superchiave della f
o a destra abbiamo un attributo primo

siccome nel nostro caso abbiamo che gli attributi primi (quelli che
compaiono in una o più chiavi) sono abcd (cioè tutti) allora è sicuramente in 3nf (a destra avremo per forza solo attributi primi).

Ora passiamo alla domanda 3. per vedere se è in bcnf deve essere per ogni dipendenza funzionale deve essere verificato che

a sinistra abbiamo una chiave o superchiave della f

abc -> d essendo abc chiave va bene ma d -> a essendo che d non è ne chiave ne superchiave ma solo un attributo primo ci fa affermare che non è in bcnf.

Ora passiamo all'ultima domanda cioè fare una scomposizione che sia bcnf e che preservi tutte le dipendenze funzionali. Cominciamo con il dire che una scomposizione che preserva tutte le dipendenze funzionali è quando l'unione delle dipendeze funzionali delle scomposizione coincide alle dipendenze funzionali dello schema prima della scomposizione (la nostra f).
Dato che quello che non ci va bene è d -> a (non mi va bene d -> a perchè è la dipendenza che rende lo schema non in BCNF e d -> a essendo che d non è ne chiave ne superchiave ma solo un attributo
primo ci fa affermare che non è in bcnf) proviamo a scomporla in
s1(a,d) con f1(d -> a) e non ci vuole un genio a capire che in questa
scomposizione la chiave è d ed è quindi in bcnf, quello che ci rimane è s2(b,c,d) con f2().
Per calcolare la seconda scomposizione dobbiamo prendere tutti gli attributi nello schema di partenza meno gli attributi utilizzati nella prima scomposizione + una chiave della prima scomposizione (quindi s(a,b,c,d) togliamo (d,a) di S1 e aggiungiamo (d) che è la chiave della di f1 cioè appunto s2(b,c,d)). Cioè S – S1 +(unione) CHIAVE DI S1 [in teoria questo che abbiamo scritto è sbagliato formalmente, dovremmo mettere u di S e u di S1]. per vedere che dipendenze ci sono nelle scomposizioni basta vedere di quali dipendenze in F hai gli attributi in una scomposizione, quindi si la seconda non ha nessuna dipendenza funzionale in
quanto manca la a. Che io sappia non esiste un algoritmo per la
scomposizione, ma se proprio ne vuoi uno devi provare tutte le scomposizioni possibili. È banale capire che non esiste una scomposizione in bcnf vedendo la prima dipendenza funzionale (abc -> d) che non potrà mai essere preservata indipendentemente da come scompongo in quando ha tutti gli attributi dello schema. Devi cercare di capire bene come si scompone, poi si vede a occhio cosa vale la pena di tentare e se è scomponibile.

Facendo f1 U f2 viene fuori f3 (d -> a) che NON coincide con f perché manca abc -> d. si potrebbero provare altre scomposizioni ma questa è la più intelligente e le altre darebbero un risultato simile se non peggiore, quindi possiamo affermare che NON ESISTONO
SCOMPOSIZIONI IN BCNF CHE MANTENGONO TUTTE LE DIPENDENZE FUNZIONALI.

Un furbone potrebbe pensare che potremmo scomporre in s1(d,a) f1(d -> a) e s2(a,b,c,d) con f2(abc->d) ma questa chiaramente è una scomposizione sbagliata perché non usa il metodo di scomposizione di cui ho parlato prima e inoltre è inlogico avere un s1 che è un sottoinsieme di s2 e per concludere è illogico anche avere una scomposizione che coincide come schema con lo schema iniziale. Sarebbe come dire in uno schema reale di esempio
cliente(nome, cognome, telefono) scomposto in clienteScomposto1(nome,cognome, telefono) e clienteScomposto2(cognome, telefono) che chiaramente è un assurdo.

--------------------------------------------------------------------------

Passiamo al secondo gruppo di dipendenze.
Troviamo le chiavi di R.
PRIMO PASSAGGIO: se esistono elementi che non sono mai a dx nelle dipendenze funzionali allora questi elementi sono elementi primi E PARTECIPERANNO A TUTTE LE CHIAVI. Tutti gli elementi sono almeno una volta a dx quindi niente.
SECONDO PASSO: provo le chiavi. Tramite l'osservazione precedente si potrebbe dedurre quali sono le chiavi ma diciamo che noi non ci arriviamo allora passiamo con i tentativi:
- siccome il passo 1 non ha dato risultati dobbiamo provare le chiavi
composte da 1 solo attributo:

code:
A*	x(0) = A	X(1) = A			A* = A
B*	X(0) = B	X(1) = B			B* = B
C*	X(0) = C	X(1) = CA 	X(2) = CA	C* = CA
D*	X(0) = D	X(1) = DB	X(2) = DB 	D* = DB

- non ci sono chiavi qua, allora proviamo con 2 attributi tutte le
combinazioni:

code:
AB* X(0) = AB	X(1) = ABCD	X(2) = ABCD	AB* = ABCD
AC* X(0) = AC	X(1) = AC	X(2) = AC	AC* = AC
AD* X(0) = AD	X(1) = AD	X(2) = ABD	X(3) = ABCD	AD* = ABCD
BC* X(0) = BC	X(1) = BC	X(2) = ABC	X(3) = ABCD	BC* = ABCD
BD* X(0) = BD	X(1) = BD	X(2) = BD	BD* = BD
DC* X(0) = DC	X(1) = DC	X(2) = ABCD	DC* = ABCD

Riassumendo le chiavi sono AB, AD, BC, DC. Gli attributi primi sono A,B,C,D (cioè tutti gli attributi). Abbiamo trovato qualche chiave ora dobbiamo vedere se è utile (e nel caso provare) fare la chiusura di 3 attributi. Partiamo dagli attributi che non sono chiavi testati nel passaggio prima cioè AC e BD.
- Le combinazioni possibili per AC sono ABC ACD ma AB è chiave
quindi ABC è sicuramente una superchiave e CD è chiave quindi anche ACD è sicuramente superchiave quindi qua non dobbiamo provare niente.
Le combinazioni possibili per BD sono ABD (ma AB è chiave) e BCD
(ma BC è chiave). Quindi nemmeno qua non dobbiamo provare niente.
Dato che il passaggio precedente non ha dato SOLO SUPERCHIAVI è inutile provare con 4 attributi inquanto otterremmo solo super chiavi.
Nota bene:Questo è il sistema completo per trovare le chiavi adesso proverò a darvi qualche dritta per ridurre il numero di passi:
- osservando l'insieme delle dipendenze funzionali notiamo che a occhio si poteva evitare di fare i calcoli con un attributo solo
- notiamo anche subito a occhio che AB è chiave quindi per trovare le altre chiavi era sufficiente mettere A + qualcosa che punta a B (se c'è e se ce ne sono più di uno creiamo una chiave per ogni attributo) e nel nostro caso è D e B + qualcosa che punta a A (se c'è e se ce ne sono più di uno creiamo una chiave per ogni attributo) e nel nostro caso era C per finire qualcosa che punta ad A più qualcosa che punta a B cioè CD.
- in generale un'osservazione accurata semplifida di molto i calcoli,
cercate però se avete tempo di usare l'algoritmo proposto prima.

SECONDA DOMANDA:

è ovviamente in 3NF in quanto tutti gli attributi sono primi.

TERZA DOMANDA:

PRIMO PASSO: per essere in BCNF a sinistra di tutte le dipendenze funzionali deve esserci una chiave o una super chiave della relazione. Nel nostro caso abbiamo AB->C, AB->D, C->A, D->B di cui

code:
- AB->C va bene perché AB è chiave
- AB->D va bene perché AB è chiave
- C->A non va bene perché C non è ne chiave ne super chiave
- D->B non va bene perché D non è ne chiave ne super chiave

Siccome non è in BCNF proviamo a vedere se esitono delle scomposizioni in grado di renderla tale.
SECONDO PASSO: proviamo qualche scomposizione.

PRIMO TENTATIVO: prendiamo la prima dipendenza che nn ci va bene e mettiamola da parte evito di riscrivere le regole per determinare il restante di una scomposizione (l'S2 per intenderci)

code:
S1 (C,A) F1 (C->A)
S2 (BCD) F2 (D->B)

Unendo f1 con f2 non ottengo la f iniziali quindi il primo tentativo ha
fallito
SECONDO TENTATIVO: prendiamo la seconda dipendenza funzionale con non ci va bene

code:
S1 (D,B) 	F1 (D -> B)
S2 (A,C,D)	F2 (C -> A)

Unendo f1 con f2 non ottengo la f iniziali quindi il primo tentativo ha
fallito.

ALTRI TENTATIVI: Lascio a voi testare altri tentativi come per esempio S1(A,B,C) S2(D) tanto tutti daranno lo stesso risultato cioè negativo. Possiamo concludere che non esiste una decomposizione che preservi le dipendenze funzionali.
OSSERVAZIONI: si poteva capire che non esisteva una decomposizione che preservi le dipendenze funzionali dal fatto che AB va in tutti gli attributi. Inoltre da quello che ho potuto vedere dagli esami passati non è mai stata proposta un insieme di dipendenze funzionali decomponibile perciò se all'esame vi viene una decomposizione se fossi in voi ci darei un occhio

.

Spero di essere stato utile, ho cercato di sviluppare tutti i passaggi anche quelli + stupidi in ogni caso resto a disposizione per maggiori chiarimenti.

__________________
GET DROPBOX
# il grado di lentezza è direttamente proporzionale all'intensità della memoria;il grado di velocità è direttamente proporzionale all'intensità dell'oblio (Kundera) #
BLOG: Byte Strike
ChRiS :ciao:

Posted by Voodoo on 02-07-2007 19:34:

code:
Si consideri lo schema di relazione R = (A,B,C,D) e il seguente insieme di
dipendenze funzionali:  
1.  A -> B 
2.  BC -> D 
3.  A -> C 
Rispondere ai seguenti quesiti motivando le risposte date: 
a)  Determinare la chiave o le chiavi dello schema di relazione R. 
b)  Determinare se R e’ in 3NF o BCNF. 
c)  Produrre eventuali decomposizioni e discutere 
la preservazione dei dati e delle dipendenze 
funzionali

a) come al solito osserviamo innanzitutto quali sono gli elementi che non compaiono a destra: solo A in questo caso quindi possiamo dire che A è sicuramente attributo primo.
Calcoliamo la chiusura di A:

code:
A*  x(0) = A   x(1) = ABC  x(2) = ABCD

Quindi A è chiave,l'unica chiave in quanto le chiusure degli altri attributi non portano a riavere lo schema R.

b) Per essere in 3NF ciascuna dipendenza deve avere a sinistra una chiave o una superchiave oppure a destra un attributo primo (cioè facente parte della chiave).
Poichè BC -> D e BC non è chiave e D non è attributo primo,non è in 3NF. Poichè per esser in BCNF lo schema dev'esser in 3NF,concludiamo che non è nemmeno in BCNF.

c) la dipendenza che mi crea problemi perchè mi rende lo schema non in BCNF/3NF è BC -> D quindi scomponiamo:

code:
s1 (BCD)  f1(BC -> D)
s2 (ABC)  f2(A -> B,A -> C)

f1 U f2 = f

Quindi esiste una scomposizione in BCNF che mi preservi le dipendenze.

Posted by Pupino on 24-07-2007 11:07:

In riferimento a quest' ultimo esercizio...

La domanda che poneva era Produrre eventuali decomposizioni e discutere la preservazione dei dati e delle dipendenze funzionali.

La preservazione dei dati come la discuti?

__________________

PUPINO'S VIDEO
FRANK JAY :!:

UN BLOG :look:

Posted by Voodoo on 24-07-2007 11:53:

Originally posted by Pupino
In riferimento a quest' ultimo esercizio...

La domanda che poneva era Produrre eventuali decomposizioni e discutere la preservazione dei dati e delle dipendenze funzionali.

La preservazione dei dati come la discuti?

In riferimento a quell'esercizio,la presenrvazione dlle dipendenze si mantiene se f1 U f2 = f,quella dei dati se vi è un lossless join fra gli insiemi scomposti.

Posted by dc671228 on 08-02-2008 11:55:

Scomposizione

Ciao! C'è una cosa che non ho capito nella scomposizione:

Ho capito come scegli i 2 gruppi, ma le relative relazioni in f1 e f2 come le trovi?

Posted by Voodoo on 08-02-2008 12:16:

Re: Scomposizione

Originally posted by dc671228
Ciao! C'è una cosa che non ho capito nella scomposizione:

Ho capito come scegli i 2 gruppi, ma le relative relazioni in f1 e f2 come le trovi?

Ho dato l'esame a luglio e l'ho verbalizzato di recente. La normalizzazione l'ho capita a stento e quel che ho capito è scritto qua. Confida nei tuoi compagni di corso per farti spiegare la cosa,io ho resettato il cervello per quanto concerne quest'argomento

Posted by dc671228 on 08-02-2008 13:21:

ok, grazie cmq!
Ciao!

Posted by altin on 21-02-2008 17:14:

per quanto ne so io le f1 e f2 gli scegli in base ai sottoinsiemi S che tu hai.
per scegliere le S si fa cosi::
si vede la d.f. che nn ti verifica uno delle forme della normalizazzione. metti dentro a S2 tutti gli attributi che si trovano nella tua d.f. che vuoi modificare. e vedi tutte le d.f. che puoi carvarne da questi attributi o dalla lora combinazione. la f2 sara fatta da queste.
La S1 sara fatta dagli attributti rimanenti + un attributo della S2 (xke alla fine ti servira per fare join).

Posted by altin on 21-02-2008 17:24:

prendo quest esempio
Si consideri lo schema di relazione R = (A,B,C,D) e il seguente insieme di
dipendenze funzionali:
1. A -> B
2. BC -> D
3. A -> C

1)sappiamo che la chiave è la A
2)vediamo le d.f. in che forma saranno
in quest esempio nn sono ne in BCNF ne in 3NF xke la d.f. BC-->D
nn si verifica per nessuna delle due forme.

allora la tua S2 sara fatta da tutti gli attributi di questa d.f. cioè BCD...
S2(B,C,D).
per calcorale la f2 vedi le d.f. che puoi caverne da B,C,D.(per vedere devi guardare anche la freccia --> le tue dip devono avere la direzione della dip.
cioè tu da B nn trovi niente xke hai A->B;A->C; BC->D
La stessa cosa vale per C(cioè nn puoi trovare nessuna d.f.
mentre BC ti da la dip funz BC->D..
per questo la tua f2(BC->D).
la S1 avra come attributi quelli rimanenti piu uno della S2 che servira per fare join("questo penso che la scegli te a caso")
S1(A,B).
la f1 sara fatta dalle dip funz che posso ricavare da queste due.
A->B
A->C
quindi f1(A->B;A->C)
per preservare le dipendeze funzionali dobbiamo avere.
f1 U f2 = f

Posted by karplus on 14-12-2008 14:44:

Ringrazio chi ha iniziato e/o proseguito questa discussione che mi ha permesso di capire la normalizzazione, qui di seguito elenco uno "schemino" dei passi da seguire per effettuare la normalizzazione:

1) Verificare che l'insieme delle dipendenze funzionali date sia minimale, ovvero cercare e rimuovere eventuali dip. funz. o attributi ridondanti.
2) Stabilire quali attributi sono primi, ovvero quali non compaiono mai a destra delle dip funz.
3) Trovare le chiavi, ovvero un insieme di attributi primi e non, che "passando" dalle varie dip funz portano ad avere un insieme di attributi uguale a quello dato dal testo dell'esercizio
4) Controllare se l'insieme R delle dip. funz. é 3NF o BCNF. É BCNF se a sinistra delle dip funz ci sono solo chiavi o superchiavi (attributi che contengono una chiave), 3NF se é BCNF tutto o in parte, o se a destra ci sono solo attributi primi.
5) Effettuare la decomposizione lossless join richiesta (3NF o BCNF). Nel caso che sia BCNF si parte dalla dip funz che la viola e si calcola S2 cioè S2=(S-S1)+CHIAVE S1. Poi si uniscono F1 e F2 e se non danno F non esiste una decomposizione lossless join che preservi le dip funz.

Anche se differisce dal metodo adottato dal prof questo metodo di decomposizione lossless join BNCF é cmq valido, me l'ha confermato lui stesso correggendo un mio esame.

Nei post precedenti al mio viene spiegato come fare la decomposizione lossless join, ma attenzione perchè viene spiegato solo il caso in cui la decomposizione richiesta sia in BCNF, lo svolgimento di una scomposizione 3NF é totalmente diverso.

[EDIT 01-02-09]
Venerdì sono stato a ricevimento dal prof e mi sono fatto spiegare la decomposizione 3nf.

I passaggi da fare sono 4:
1) scrivere le relazioni di ogni dipendenza funzionale
2) accorpare le relazioni che hanno la stessa chiave
3) cercare se é presente una relazione che ha come chiave la chiave "totale" dell'esercizio, ovvero quella trovata calcolando la chiusura all'inizio dell'esercizio.
4) se la chiave non é presente in nessuna relazione, si accorpano più relazioni in modo da avere la chiave in una relazione sola. Ci sono più relazioni da cui é possibile derivare la chiave, che io sappia non c'è un criterio che impone di prendere una piuttosto che l'altra relazione, l'importante é ritrovarsi con una nuova relazione che contiene la chiave "totale" dell'esercizio.

Nella fattispecie il prof mi ha corretto la scomposizione 3nf capitata all'esame del 20 Gennaio. La chiave TOTALE dell'esercizio, é quella trovata calcolandone la chiusura (prima parte di un esercizio della normalizzazione), cosa che ho dato per scontato e di cui non ho ricopiato lo svolgimento. La chiave in questione é AC.

Prima di iniziare l'esercizio bisogna controllare che siano verificate queste 3 condizioni: unicità attributi a destra, assenza di dipendenze funzionali ridondanti, assenza di attributi ridondanti a sinistra.

Le dipendenze funzionali erano (svolgiamo già il passaggio 1):

AD->E R1(A,D,E)
A->F R2(A,F)
AC->B R3(A,C,B)
C->D R4(C,D)
C->F R5(C,F)

la chiave é AC.

passaggio 2:
si combinano R4 e R5 in R6 perchè hanno la stessa chiave cioè C, si compie cioè il famigerato accorpamento.

passaggio 3:
R3 contiene AC, cioè la chiave totale dell'esercizio

passaggio 4:
visto che il passaggio 3 é verificato, non occorre creare una relazione R7 che abbia AC come chiave.

La decomposizione lossless join in 3nf quindi é:
R6(C,D,F)R3(A,C,B)R2(A,F)R1(A,D,E)

Faccio un piccolo addendum al passaggio 4:
supponiamo che R3 sia R3(A,E,D), R3 non contiene la chiave AC. Quindi dovremmo creare una relazione R7 partendo R2+R6, R7 alla fine sarebbe (A,C,D,F).
Nulla ci vieta però di comporre R7 a partire da R1+R6, otterremmo R7(A,D,E,C,F), tuttavia secondo me é meglio partire da R che hanno meno attributi possibili, ma é un parere personale.

Posted by Jaky on 21-01-2009 15:26:

Originally posted by karplus

A questo punto bisogna trovare due insiemi R che contengano gli attributi primi della chiave trovata precedentemente, la chiave in questo caso é AC, quindi si combinano R3 e R4:

R3,4(A,B,C,D)

Ciao, non è che potresti spiegare + dettagliatamente questo passaggio?

non capisco perchè scegli proprio R3 e R4

E la parte finale da scrivere per dimostrare che la combinazione di questi due insiemi porta a una decomposizione lossless join é così:

R3,4(A,B,C,D)R1(A,D,E)R2(A,E,F)R5(C,F)

Anche questo non mi è tanto chiaro.

Ciao e grazie :-D

Posted by karplus on 21-01-2009 19:24:

guardate il mio post precedente, lì c'è la procedura spiegatami dal prof per la scomposizione in 3nf.

L'algoritmo viene spiegato bene dal prof qui alla pagina 79.
Viene spiegato anche qui alle pagine 418-420.

Posted by Jaky on 04-02-2009 11:20:

in aggiunta a quanto hai spiegato, è meglio chiarire una cosa.
se avessimo avuto

AD->E R1(A,D,E)
A->F R2(A,F)
AC->D R3(A,C,D)
C->D R4(C,D)
C->F R5(C,F)

in questo caso, non bisogna unine R4 con R5, ma inserire la dip.funz di R4 in R3.
Era per precisare che non sempre bisogna unire i gruppi con stessa chiave

Posted by karplus on 04-02-2009 11:26:

grandissimo, questo era un dubbio che mi era rimasto, e in effetti anche ora non me lo spiego.
R4 va in R3 perchè ha sia la C che la D già presenti in R3, giusto?

E questo passaggio ha la "precedenza" sull'accorpare le dip funz con la stessa chiave perchè in R3 é presente la chiave generale di tutto l'esercizio, giusto?

Posted by alfoguasta on 04-02-2009 16:47:

Originally posted by Jaky
Ciao, non è che potresti spiegare + dettagliatamente questo passaggio?
non capisco perchè scegli proprio R3 e R4

Anche questo non mi è tanto chiaro.

Ciao e grazie

<<<<NN TROVO LA TRACCIA DI QUESTO QUOTE....DEVO TRALASCIARE QUESTE CONSIDERAZIONI O COSA?? GRAZIE>>>>

All times are GMT. The time now is 16:15.

Pages (3): [1] 2 3 »
Show all 38 posts from this thread on one page