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.

code:

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

code:

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

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

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

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

code:

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

code:

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

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 

code:

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

code:

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

f1 U f2 = f 

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? :D

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?

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)

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)

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

-si crea una relazione per ogni gruppo di attributi coinvolti in una dipendenza funzionale

-si verifica che alla fine una relazione contenga una chiave della relazione originaria

4) se la chiave non é presente in nessuna relazione, si accorpano più relazioni in modo di avere la chiave in una relazione sola

Originally posted by karplus
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.

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

Originally posted by karplus
Formula? :?
Sei fuori strada di abbastanza. :D

Al passo x0 (il primo passo) ci sono solo gli attributi di partenza che stai testando, ti devi chiedere se al passo x1 se ne aggiungono altri.
Dato che nè B nè C compaiono mai a sx delle dipendenze funzionali, ovvero non implicano mai niente, al passo x(1) hai ancora bc, ovvero le stesse di partenza.

Ergo bc non é chiave perchè come risultato finale non hai avuto ABCD.

Mi rendo conto che ti avrò confuso le idee, ma la spiegazione é questa, devi digerire ancora un po' la procedura.

Es 2
Si consideri R(A,B,C,D); per ciascuno dei seguenti gruppi di dipendenze
funzionali

Originally posted by Voodoo
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 :D.

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

Originally posted by karplus
Ho sbagliato a ricopiare io sul dsy una cosa ma il risultato é cmq quello che avevo riportato, ora lo ricopio esattamente come l'aveva trascritto il prof

ABD->E qui la B é ridondante perchè c'è già AD->B, quindi diventa AD -> E . Ergo le R vengono:

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

LA decomposizione risultante quindi é R3,4(A,B,C,D) R1(..) R2(..) R5(..)

I puntini di sospesione sono per evitare di ricopiare ciò che é già noto presumo. Grazie al passaggio che avevo dimenticato, R3 non é più dentro R1.

Resta però il dilemma, perchè cavolo non ha accorpato R4 e R5 se a ricevimento una sett fa mi ha detto che é la prima cosa da fare??

Originally posted by karplus
Ho sbagliato a ricopiare io sul dsy una cosa ma il risultato é cmq quello che avevo riportato, ora lo ricopio esattamente come l'aveva trascritto il prof

ABD->E qui la B é ridondante perchè c'è già AD->B, quindi diventa AD -> E . Ergo le R vengono:

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

LA decomposizione risultante quindi é R3,4(A,B,C,D) R1(..) R2(..) R5(..)

I puntini di sospesione sono per evitare di ricopiare ciò che é già noto presumo. Grazie al passaggio che avevo dimenticato, R3 non é più dentro R1.

Resta però il dilemma, perchè cavolo non ha accorpato R4 e R5 se a ricevimento una sett fa mi ha detto che é la prima cosa da fare??