DBMS - Normalizzazione

Dipendenza funzionale

La dipendenza funzionale (FD) è un insieme di vincoli tra due attributi in una relazione. La dipendenza funzionale dice che se due tuple hanno gli stessi valori per gli attributi A1, A2, ..., An, allora quelle due tuple devono avere gli stessi valori per gli attributi B1, B2, ..., Bn.

La dipendenza funzionale è rappresentata da un segno di freccia (→) cioè X → Y, dove X determina funzionalmente Y. Gli attributi del lato sinistro determinano i valori degli attributi sul lato destro.

Assiomi di Armstrong

Se F è un insieme di dipendenze funzionali allora la chiusura di F, denotata come F ⁺ , è l'insieme di tutte le dipendenze funzionali logicamente implicite da F. Gli assiomi di Armstrong sono un insieme di regole che, se applicate ripetutamente, genera una chiusura di dipendenze funzionali .

• Reflexive rule - Se alpha è un insieme di attributi e beta è_subset_of alpha, allora alpha contiene beta.

• Augmentation rule- Se a → b vale ey è un attributo impostato, vale anche ay → by. Ovvero l'aggiunta di attributi nelle dipendenze, non modifica le dipendenze di base.

• Transitivity rule- Come la regola transitiva in algebra, se vale a → b e b → c vale, allora vale anche a → c. a → b è chiamato come funzionalmente che determina b.

Banale dipendenza funzionale

• Trivial- Se vale una dipendenza funzionale (FD) X → Y, dove Y è un sottoinsieme di X, allora è chiamata FD banale. I banali FD valgono sempre.

• Non-trivial - Se vale un FD X → Y, dove Y non è un sottoinsieme di X, allora è chiamato FD non banale.

• Completely non-trivial - Se vale un FD X → Y, dove x interseca Y = Φ, si dice che è un FD completamente non banale.

Normalizzazione

Se la progettazione di un database non è perfetta, potrebbe contenere anomalie, che sono come un brutto sogno per qualsiasi amministratore di database. Gestire un database con anomalie è quasi impossibile.

• Update anomalies- Se gli elementi di dati sono sparsi e non sono collegati tra loro correttamente, potrebbe portare a situazioni strane. Ad esempio, quando proviamo ad aggiornare un elemento di dati con le sue copie sparse in più punti, alcune istanze vengono aggiornate correttamente mentre alcune altre vengono lasciate con valori precedenti. Tali istanze lasciano il database in uno stato incoerente.

• Deletion anomalies - Abbiamo provato a cancellare un record, ma parti di esso sono state lasciate non cancellate a causa dell'inconsapevolezza, i dati vengono salvati anche altrove.

• Insert anomalies - Abbiamo provato a inserire dati in un record che non esiste affatto.

La normalizzazione è un metodo per rimuovere tutte queste anomalie e portare il database a uno stato coerente.

Prima forma normale

La prima forma normale è definita nella definizione delle relazioni (tabelle) stessa. Questa regola definisce che tutti gli attributi in una relazione devono avere domini atomici. I valori in un dominio atomico sono unità indivisibili.

Riorganizziamo la relazione (tabella) come di seguito, per convertirla in Prima forma normale.

Ogni attributo deve contenere un solo valore dal proprio dominio predefinito.

Seconda forma normale

Prima di conoscere la seconda forma normale, dobbiamo capire quanto segue:

• Prime attribute - Un attributo, che fa parte della chiave candidata, è noto come attributo principale.

• Non-prime attribute - Un attributo, che non fa parte della chiave primaria, si dice che sia un attributo non primo.

Se seguiamo la seconda forma normale, allora ogni attributo non primo dovrebbe essere completamente funzionalmente dipendente dall'attributo chiave principale. Cioè, se X → A vale, allora non dovrebbe esserci alcun sottoinsieme appropriato Y di X, per il quale vale anche Y → A.

Vediamo qui nella relazione Student_Project che gli attributi della chiave principale sono Stu_ID e Proj_ID. Secondo la regola, gli attributi non chiave, ad esempio Stu_Name e Proj_Name, devono dipendere da entrambi e non da nessuno degli attributi della chiave principale individualmente. Ma troviamo che Stu_Name può essere identificato da Stu_ID e Proj_Name può essere identificato da Proj_ID indipendentemente. Questo è chiamatopartial dependency, che non è consentito nella seconda forma normale.

Abbiamo rotto la relazione in due come illustrato nella foto sopra. Quindi non esiste una dipendenza parziale.

Terza forma normale

Affinché una relazione sia nella terza forma normale, deve essere nella seconda forma normale e quanto segue deve soddisfare:

• Nessun attributo non primo dipende transitivamente dall'attributo chiave prime.
• Per qualsiasi dipendenza funzionale non banale, X → A, allora o -
  X è un superkey o,
  • A è un attributo principale.

Troviamo che nella relazione Student_detail sopra, Stu_ID è la chiave e l'unico attributo chiave principale. Troviamo che la città può essere identificata da Stu_ID così come da Zip stesso. Né Zip è un superkey né City è un attributo principale. Inoltre, Stu_ID → Zip → City, quindi esistetransitive dependency.

Per portare questa relazione nella terza forma normale, suddividiamo la relazione in due relazioni come segue:

Forma normale di Boyce-Codd

Boyce-Codd Normal Form (BCNF) è un'estensione della terza forma normale in termini rigorosi. BCNF afferma che -

• Per qualsiasi dipendenza funzionale non banale, X → A, X deve essere una superchiave.

Nell'immagine sopra, Stu_ID è la superchiave nella relazione Student_Detail e Zip è la superchiave nella relazione ZipCodes. Così,

Stu_ID → Stu_Name, Zip

e

CAP → Città

Il che conferma che entrambe le relazioni sono in BCNF.