From The Blog, Page 19

Tema:

Dato il seguente schema relazionale R❬{A,B,C,D,E,F,G}, {AB→EG, EF→DA, B→C, CB→A}❭

1. dare una copertura canonica;
2. dare almeno una chiave;
3. dire se esistono almeno due chiavi;
4. dire se lo schema è in 3NF (giustificando la risposta), e se non lo è trasformarlo in 3NF specificando gli schemi delle relazioni risultanti.

Nota: il tema è stato sviluppato con la parte teorica qui: https://diario.softml.it/su-chiavi-superchiavi-e-terza-forma-normale/

Sviluppo:

1) calcolo le chiusure

AB⁺ = {AB} (banale)

AB⁺ = {ABEG} (per 1)

AB⁺ = {ABCEG} (per 3 - fine)

EF⁺ = {EF} (banale)

EF⁺ = {ADEF} (per 2 - fine)

B⁺ = {B} (banale)

B⁺ = {BC} (per 3)

B⁺ = {ABC} (per 4)

B⁺ = {ABCEG} (per 1 - fine)

CB⁺ = {ABCEG} (come B⁺)

2) espando la parte destra

AB→E

AB→G

EF→A

EF→D

B→C

BC→A

3) semplifico, se possibile, la parte sinistra

Siccome B→C, BC→A si può riscrivere come C→A.

Siccome B→C e C→A, AB→E e AB→G si può riscrivere come B→E e B→G.

B→E

B→G

EF→A

EF→D

B→C

C→A

4) creo le relazioni in 3NF:

R₁ = ❬{A,B,C,E,G}, {B→ACEG}❭

R₂ = ❬{A,D,E,F}, {EF→AD}❭

5) verifico di avere una chiave in una relazione o ne creo una nuova

dal punto 1 capisco che non ho una chiave.

BF sono attributi presenti solo a sinistra (determinanti), quindi provo a verificare se questo insieme fa da chiave.

BF⁺ = {BF} (banale)

BF⁺ = {BEF}

BF⁺ = {BEFG}

BF⁺ = {ABEFG}

BF⁺ = {ABDEFG}

BF⁺ = {ABCDEFG} (contiene tutti gli attributi quindi è chiave)

Creo una relazione contenente la chiave

R₃ = ❬{B,F}❭

Tema:

Dato il seguente schema relazionale R❬{A,B,C,D,E,F,G,H}, {DHC→AG, ED→C,
BD→EF, C→E}❭

1. dare una copertura canonica;
2. dare almeno una chiave;
3. dire se esistono almeno due chiavi;
4. dire se lo schema è in 3NF (giustificando la risposta), e se non lo è trasformarlo in 3NF specificando gli schemi delle relazioni risultanti.

Nota: il tema è stato sviluppato con la parte teorica qui: https://diario.softml.it/su-chiavi-superchiavi-e-terza-forma-normale/

Sviluppo:

1) calcolo le chiusure

1. DHC⁺ = {CDH}
2. DHC⁺ = {ACDGH}
3. DHC⁺ = {ACDEGH} (fine)

1. ED⁺ = {DE}
2. ED⁺ = {CDE} (fine)

1. BD⁺ = {BD}
2. BD⁺ = {BDEF}
   
3. BD⁺ = {BCDEF} (fine)

1. C⁺ = {C}
2. C⁺ = {CE} (fine)

Nessuna è superchiave.

2) espando la parte destra

DHC→G

DHC→A

ED→C

BD→E

BD→F

C→E

3) semplifico, se possibile, la parte sinistra

Siccome E è determinata da BD, nella dipendenza funzionale ED→C la D è ridondante e la posso togliere.

Calcoliamo la chiusura di BD per prova:

1. BD⁺ = {BD}
2. BD⁺ = {BDEF}
   
3. BD⁺ = {BCDEF} (fine)

Dal momento che la DF non è cambiata, abbiamo la prova che possiamo toglierla.

4) creo le relazioni in 3NF:

R₁ = ❬{ACDGH}, {DHC→AG}❭
R₂ = ❬{CE}, {E→C}❭
R₃ = ❬{BDEF}, {BD→EF}❭
R₄ = ❬{C}, {C→E}❭

posso accorpare la 2 e la 4: R₂ = ❬{CE}, {E→C, C→E}❭

5) verifico di avere una chiave in una relazione o ne creo una nuova

dal punto 1 capisco che non ho una chiave.

Sicuramente i termini che compaiono solo a sinistra faranno parte della chiave. Proviamo a calcolare la chiusura di questa:

1. BDH⁺ = {BDH}
2. BDH⁺ = {BDEFH}
3. BDH⁺ = {BCDEFH}
4. BDH⁺ = {ABCDEFGH} (fine)

La situazione finale quindi è:

R₁ = ❬{ACDGH}, {DHC→AG}❭
R₂ = ❬{CE}, {E→C, C→E}❭
R₃ = ❬{BDEF}, {BD→EF}❭
R₄ = ❬{BDH}❭ *chiave

Soluzione

1. dare una copertura canonica

Vedi sopra.

2. dare almeno una chiave

BDH

3. dire se esistono almeno due chiavi

No, esiste solo la chiave BDH, poiché corrisponde esattamente all'insieme di attributi esclusivamente determinanti (presenti solo a sinistra)

4. dire se lo schema è in 3NF (giustificando la risposta), e se non lo è trasformarlo in 3NF specificando gli schemi delle relazioni risultanti.

Lo schema non è in 3NF perché nessuna delle relazioni contiene la chiave.

Relazione

Una relazione è un insieme di attributi legati tra loro da dipendenze funzionali.

Dipendenza funzionale

La dipendenza funzionale implica che ci siano un determinante e un determinato. Se il determinante è uguale in due tuple, anche il determinato deve essere uguale.

Esempio: il codice fiscale determina il numero di telefono, significa che se in due righe contengono lo stesso CF, anche il numero di telefono è uguale.

Chiusura

Combinando più DF è possibile determinare anche le dipendenze non esplicite.

Esempio: R❬(A, B, C), {A→B, B→C}❭ significa "la relazione R ha attributi A, B, C e le dipendenze funzionali A determina B e B determina C. È evidente che A determina - sia pure in maniera indiretta - anche C.

La chiusura di un attributo o di un insieme di attributi rende espliciti tutti gli attributi che sono ricavabili esplicitamente o indirettamente. Si indica con un piccolo segno più dopo l'elenco degli attributi.

Esempio: R❬(A, B, C, D, E), {AB→B, BCD→DE, E→ABCD}❭

1. AB⁺ = {AB}
2. con la parte destra della chiusura, quali altri attributi posso determinare? Nessuno, quindi mi fermo.

 

1. BCD⁺ = {BCD}
2. Con BCD posso determinare DE (ma D ce l'ho già), quindi BCD⁺ = {BCDE}
3. Con BCDE posso determinare ABCD, quindi BCD⁺ = {ABCDE}
4. BCD è una superchiave

 

1. E⁺ = {E}
2. E⁺ = {ABCDE}
3. E è una superchiave

Superchiave

Una superchiave è un insieme di attributi che determinano tutti gli attributi.

Chiave

Una chiave è una superchiave minima, cioè una chiave a cui non posso togliere alcun attributo mantenendola chiave.

Esempio: R❬(A, B, C, D, E), {AB→B, BCD→DE, E→ABCD}❭

ABCD è una superchiave, perché posso determinare tutti gli attributi con questi quattro.

Però se tolgo A ottengo comunque una superchiave, quindi ABCD non è una chiave.

BCD è una superchiave solo se mantengo tutti e tre gli attributi (potrei provarlo calcolando la chiusura di BC, CD e BD e vedendo che non copro tutto l'insieme di attributi), quindi è una chiave.

Terza forma normale (solo algoritmo)

Per comodità mi riferirò al determinante come "parte sinistra" e al determinato come "parte destra", quindi per es. BCD→DE, dove BCD è il determinante e DE il determinato, mi riferirò a BCD chiamandolo "sinistra" e DE con "destra".

1. copertura canonica
   1. semplifico la parte destra
   2. verifico se posso eliminare attributi a sinistra
   3. verifico se ci sono DF comprese all'interno di altre DF
2. semplifico le DF: se la parte sinistra è identica, raggruppo
3. a questo punto creo tante relazioni quante sono le DF
4. se una relazione include tutti gli attributi di un'altra, le unisco (massimo comune tra gli attributi e riporto tutte le DF)
5. ci sono chiavi di R nelle relazioni che ho creato?
   1. gli attributi che stanno solo a sinistra sono sicuramente parte di una chiave
   2. se in nessuna delle relazioni è presente una chiave di R, allora aggiungo un attributo e provo a vedere se così diventa una chiave. Se sì, creo un'ulteriore relazione contenente la chiave

Esempio

R❬(A,B,C,D,E,F,G,H), {DHC→AG, ED→C, BD→EF, C→E}❭

Calcolo delle chiusure:

DHC⁺

1. DHC⁺ = {CDH}
2. DHC⁺ = {ACDGH}
3. DHC⁺ = {ACDEGH}
4. fine

CDH non è superchiave

ED⁺

1. ED⁺ = {DE}
2. ED⁺ = {CDE}
3. fine

ED non è superchiave

BD⁺

1. BD⁺ = {BD}
2. BD⁺ = {BDEF}
3. BD⁺ = {BCDEF}
4. fine

BD non è superchiave

C⁺

1. C⁺ = {C}
2. C⁺ = {CE}
3. fine

C non è superchiave

Semplificazione della parte destra

• DHC→AG
• ED→C
• BD→EF
• C→E

Meccanicamente, diventa:

• DHC→A
• DHC→G
• ED→C
• BD→E
• BD→F
• C→E

Semplificazione della parte sinistra

Se BD determina E e ED determina C, forse possiamo dire che la D in ED→C è ridondante.

Proviamo a calcolare la chiusura di BD cambiando ED→C in E→C:

BD⁺

1. BD⁺ = {BD}
2. BD⁺ = {BDEF}
3. BD⁺ = {BCDEF}
4. fine

non è cambiato niente, quindi possiamo semplificare le DF in:

• DHC→A
• DHC→G
• E→C
• BD→E
• BD→F
• C→E

Verifico che non ci siano DF comprese in altre: non ce ne sono

Creo le relazioni in 3nf:

R₁: ❬(ACDGH), {CDH→AG}❭

R₂: ❬(CE), {E→C, C→E}❭

R₃: ❬(BDEF), {BD→EF}❭

In una delle relazioni è presente una chiave? No.

Devo scoprire qual è una chiave e creare una relazione con quella.

BDH compaiono solo a sinistra, quindi fanno sicuramente parte della chiave. Calcoliamo la chiusura di BDH:

BDH⁺

1. BDH⁺ = {BDH}
2. BDH⁺ = {BDEFH}
3. BDH⁺ = {BCDEFH}
4. BDH⁺ = {ABCDEFGH}
5. fine

BDH è chiave.

R₄: ❬(BDH)❭