Compito 27/05/2014 - Esercizio C

Posted by On Filed under Basi di dati

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:

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

Posted by On Filed under Basi di dati

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:

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:

  1. BDH+ = {BDH}
  2. BDH+ = {BDEFH}
  3. BDH+ = {BCDEFH}
  4. 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

  1. dare una copertura canonica

Vedi sopra.

  1. dare almeno una chiave

BDH

  1. 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)

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

Posted by On Filed under Basi di dati

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:

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+

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

BDH è chiave.

R4: ❬(BDH)❭

Trovare le chiavi in una relazione

Posted by On Filed under Basi di dati

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

Posted by On Filed under Basi di dati

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:

  1. Gli attributi di R1 ⋃ gli attributi di R2 = gli attributi di R
  2. La join naturale R1 ⨝ R2 è la proiezione di R
  3. 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

  1. Calcolare le chiavi di R
  2. Ripetere finché tutte le relazioni non sono in BCNF:
    1. Prendere ogni R' con A→B che viola la BCNF
    2. Decomporre R' in R1(A, B), R2(A, resto). La join tra le relazioni deve restituire R
    3. Calcolare le dipendenze funzionali di R1 e R2
    4. 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

Posted by On Filed under Basi di dati

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

Posted by On Filed under Basi di dati

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.