Compito 27/05/2014 - Esercizio C
Tema:
Dato il seguente schema relazionale R❬{A,B,C,D,E,F,G}, {AB→EG, EF→DA, B→C, CB→A}❭
- dare una copertura canonica;
- dare almeno una chiave;
- dire se esistono almeno due chiavi;
- 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:
R1 = ❬{A,B,C,E,G}, {B→ACEG}❭
R2 = ❬{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
R3 = ❬{B,F}❭
Compito 09/09/2014 - Esercizio C
Tema:
Dato il seguente schema relazionale R❬{A,B,C,D,E,F,G,H}, {DHC→AG, ED→C,
BD→EF, C→E}❭
- dare una copertura canonica;
- dare almeno una chiave;
- dire se esistono almeno due chiavi;
- 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
- DHC+ = {CDH}
- DHC+ = {ACDGH}
- DHC+ = {ACDEGH} (fine)
- ED+ = {DE}
- ED+ = {CDE} (fine)
- BD+ = {BD}
- BD+ = {BDEF}
- BD+ = {BCDEF} (fine)
- C+ = {C}
- 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:
- BD+ = {BD}
- BD+ = {BDEF}
- BD+ = {BCDEF} (fine)
Dal momento che la DF non è cambiata, abbiamo la prova che possiamo toglierla.
4) creo le relazioni in 3NF:
R1 = ❬{ACDGH}, {DHC→AG}❭
R2 = ❬{CE}, {E→C}❭
R3 = ❬{BDEF}, {BD→EF}❭
R4 = ❬{C}, {C→E}❭
posso accorpare la 2 e la 4: R2 = ❬{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:
- BDH+ = {BDH}
- BDH+ = {BDEFH}
- BDH+ = {BCDEFH}
- BDH+ = {ABCDEFGH} (fine)
La situazione finale quindi è:
R1 = ❬{ACDGH}, {DHC→AG}❭
R2 = ❬{CE}, {E→C, C→E}❭
R3 = ❬{BDEF}, {BD→EF}❭
R4 = ❬{BDH}❭ *chiave
Soluzione
- dare una copertura canonica
Vedi sopra.
- dare almeno una chiave
BDH
- 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)
- 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.
Su chiavi, superchiavi e terza forma normale
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}❭
- AB+ = {AB}
- con la parte destra della chiusura, quali altri attributi posso determinare? Nessuno, quindi mi fermo.
- BCD+ = {BCD}
- Con BCD posso determinare DE (ma D ce l'ho già), quindi BCD+ = {BCDE}
- Con BCDE posso determinare ABCD, quindi BCD+ = {ABCDE}
- BCD è una superchiave
- E+ = {E}
- E+ = {ABCDE}
- 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".
- copertura canonica
- semplifico la parte destra
- verifico se posso eliminare attributi a sinistra
- verifico se ci sono DF comprese all'interno di altre DF
- semplifico le DF: se la parte sinistra è identica, raggruppo
- a questo punto creo tante relazioni quante sono le DF
- se una relazione include tutti gli attributi di un'altra, le unisco (massimo comune tra gli attributi e riporto tutte le DF)
- ci sono chiavi di R nelle relazioni che ho creato?
- gli attributi che stanno solo a sinistra sono sicuramente parte di una chiave
- 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+
- DHC+ = {CDH}
- DHC+ = {ACDGH}
- DHC+ = {ACDEGH}
- fine
CDH non è superchiave
ED+
- ED+ = {DE}
- ED+ = {CDE}
- fine
ED non è superchiave
BD+
- BD+ = {BD}
- BD+ = {BDEF}
- BD+ = {BCDEF}
- fine
BD non è superchiave
C+
- C+ = {C}
- C+ = {CE}
- 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+
- BD+ = {BD}
- BD+ = {BDEF}
- BD+ = {BCDEF}
- 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:
R1: ❬(ACDGH), {CDH→AG}❭
R2: ❬(CE), {E→C, C→E}❭
R3: ❬(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+
- BDH+ = {BDH}
- BDH+ = {BDEFH}
- BDH+ = {BCDEFH}
- BDH+ = {ABCDEFGH}
- fine
BDH è chiave.
R4: ❬(BDH)❭
Trovare le chiavi in una relazione
Troviamo le chiavi nella relazione
R(A, B, C)
F={A→B, B→C}
A è prima, perché si trova solo a sinistra di una relazione, B e C sono non prime.
Facciamo uno schemino con tre colonne: nella prima ci sono gli attributi che compaiono solo a sinistra, nella terza gli attributi che sono presenti sia a sinistra sia a destra di una DF, in mezzo gli attributi presenti sia a destra sia a sinistra di qualche DF.
S | E | D ---+---+--- A | B | C ---+---+---
Altro esempio:
R(ABCD)
F={AB→C, C→B, C→D}
S | E | D ---+---+--- A | B | D | C | ---+---+---
A+ è dato da A, ma ora dobbiamo trovare la chiusura di AB+, che è ABCD e la chiusura di AC+, che è ACBD.
La chiave primaria è data da ABC.
Altro esempio:
R(ABC)
F={A→B, B→C, C→A}
S | E | D ---+---+--- | A | | B | | C | ---+---+---
"Really sticky situation".
La chiave è (ABC) e la superchiave è - ovviamente - ABC
Boyce Codd FN
Una relazione R(A1, A2, ... An)può essere scomposta in due relazioni:
R1(B1, B2, ... Bk)
R2(C1, C2, ... Ck)
e le relazioni risultanti sono di Boyce Codd se:
- Gli attributi di R1 ⋃ gli attributi di R2 = gli attributi di R
- La join naturale R1 ⨝ R2 è la proiezione di R
- Ogni attributo in comune tra R1 e R2 è una chiave
Per esempio:
Studenti(CodiceFiscale, Nome, Indirizzo, CodiceScuola, NomeScuola, NomeCittà, Punteggio, Priorità)
ha le seguenti DF:
CodiceFiscale → Nome, Indirizzo, Punteggio
Punteggio → Priorità
CodiceScuola → NomeScuola, NomeCittà
è in forma Boyce-Codd?
Le chiavi sono: CodiceFiscale, CodiceScuola.
Ogni DF ha una chiave contenente CodiceFiscale e Scuola? NO! Quindi la relazione non è in BCFN.
Altro esempio:
Iscritto(CodiceFiscale, Nome, Stato, Data, Maggiorenne
La DF è: CodiceFiscale, Nome, Stato → Data, Maggiorenne
è quindi in BCNF.
Algoritmo per decomporre una relazione in BCNF
Input: relazione + dipendenze funzionali
Output: decomposizione di R in relazioni che rispettano la BCNF senza perdita di join
- Calcolare le chiavi di R
- Ripetere finché tutte le relazioni non sono in BCNF:
- Prendere ogni R' con A→B che viola la BCNF
- Decomporre R' in R1(A, B), R2(A, resto). La join tra le relazioni deve restituire R
- Calcolare le dipendenze funzionali di R1 e R2
- Calcolare le chiavi di R1 e R2
Esempio:
Studenti(CodiceFiscale, Nome, Indirizzo, CodiceScuola, NomeScuola, NomeCittà, Punteggio, Priorità)
ha le seguenti DF:
CodiceFiscale → Nome, Indirizzo, Punteggio
Punteggio → Priorità
CodiceScuola → NomeScuola, NomeCittà
Come sopra, la chiave è CodiceFiscale, CodiceScuola
Creiamo due relazioni
S1(CodiceScuola, NomeScuola, NomeCittà)
S2(CodiceFiscale, Nome, Indirizzo, CodiceScuola, Punteggio, Priorità)
Ora S1 è in BCNF
Invece S2 non è in BCNF, quindi la decomponiamo in:
S3(Punteggio, Priorità)
S4(CodiceFiscale, Nome, Indirizzo, CodiceScuola, Punteggio)
Ora S3 è in BCNF.
Invece S4 non è in BCNF, quindi la decomponiamo in:
S5(CodiceFiscale, Nome, Indirizzo, Punteggio)
S6(CodiceFiscale, CodiceScuola)
Finalmente abbiamo S1, S3, S5, S6 che rappresentano la BCNF della relazione senza perdita di join.
Terza forma normale e Boyce-Codd
Alcuni esempi, redatti con l'aiuto di http://dblab.dsi.unive.it:8080/
Attributi | Dipendenze funzionali | Chiavi | Attributi primi | Boyce-Codd | 3NF | Commento |
---|---|---|---|---|---|---|
a | - | {(a)} | (a) | R<(a){}> | R<(a){}> | Nessuna d.f. |
a | a→a | {(a)} | (a) | R<(a){}> | R<(a){}> | D.f. banale, non si riporta |
a, b | a→b | {(a)} | (a) | R<(a,b){a→b}> | R<(a,b){a→b}> | |
a, b | a→b, b→a | {(a), (b)} | (a b) | R<(a,b){a→b,b→a}> | R<(a,b){b→a}> | Differenza tra BC e 3NF: nel primo caso sono esplicite entrambe le d.f., nella 3NF solo una |
a, b, c | a→b, b→c | {(a)} | (a) | R1<(a,b){a→b}>, R2<(b,c){b→c}> | R1<(a,b){a→b}>, R2<(b,c){b→c}> | In entrambi i casi, si "estrae" una relazione. Dipendenze preservate. |
Nota bene: b non è una chiave, ma diventa la chiave di una nuova relazione sia secondo BC sia secondo 3NF
a, b, c | a→b, ab→c | {(a)} | (a) | R<(a,b,c){a→b,a→c}> | R<(a,b,c){a→bc}> | b è determinato da a, quindi c è determinato dalla sola a (secondo Boyce-Codd) oppure in ogni caso da ab (secondo 3NF) |
a, b, c | a→b, ab→c, bc→a | {(a),(bc)} | (abc) | R<(a,b,c) {a→b, a→c, bc→a}> | R<(a,b,c) {bc→a}> | |
a, b, c, d, e, g, h, i | adg→gi ach→adg bc→ad ce→ach |
{(bce)} | (bce) | R<(a,b,c) {a→b, a→c, bc→a}> | R<(a,b,c) {bc→a}> |
Transazioni e concorrenza
Transazione
Atomicità: un'operazione può essere o completata o annullata, non può essere completata parzialmente
Persistenza: se una transazione termina con successo, le modifiche devono essere mantenute sui dati
Serializzabilità: non possono essere eseguite due transazioni che interferiscono tra loro (ved. esempio due prelievi bancomat contemporanei)
Problemi / giornale
- La transazione fallisce
- C'è un problema esterno temporaneo (es. caduta della corrente elettrica)
- C'è un disastro (rottura di un disco)
La garanzia per tutti e tre i tipi di problema è il giornale, cioè un log delle transazioni.
Il giornale è compilato con il contenuto delle transazioni e ogni tanto avviene un allineamento con la base dati. L'allineamento può avvenire tramite una sospensione di tutte le transazioni, ma esistono anche tecniche che riducono i tempi di attesa.
Disfare le transazioni
Se un'operazione fallisce la transazione si deve DISFARE.
Se un'operazione riesce ma non siamo sicuri che il dato sia scritto nel disco, occorre RIFARE.
Il giornale NON è soggetto a buffering, quindi le informazioni sono sempre scritte direttamente sul disco.