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)❭