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.