Forme Normali

Dipendenze funzionali, prima, seconda e terza forma normale (1NF, 2NF, 3NF) e forma normale di Boyce-Codd; decomposizione senza perdita per eliminare ridondanza e anomalie.

Una forma normale è una proprietà che deve essere soddisfatta dagli attributi di ogni schema di relazione in un database, esse garantiscono la "qualità" di un database, perchè quando non nomralizzato, un database può contenere ridondanza e crea problemi in fase di aggiornamento dei dati

Le principali problematiche sono date dalla Ridondanza, che da anomalie di aggiornamento, cancellazione e inserimento.

Dipendenza funzionale

Per scoprire e rimuovere le anomalie in uno schema del modello logico si devono scoprire le relazioni dette Dipendenze Funzionali (DF) che fissano ulteriori vincoli di integrità di uno schema di relazione R(X)R(X)

Lo si nota tramite la sintassi Y→ZY \rightarrow Z che indica una dipendenza funzionale da Y a Z, dove Y e Z sono attributi di una relazione. Si legge come Y determina Z oppure Z dipende funzionalmente da Y

Consideriamo una relazione r su R(X)r \ su \ R(X) e due sottoinsiemi non vuoti Y,Z⊆XY,Z \subseteq X, esiste una Dipendenza Funzionale da Y a Z (Y→ZY \rightarrow Z) se per ogni coppia di tuple t1,t2t_{1}, t_2 di r, che hanno gli stessi valori su Y, risulta che t1,t2t_{1}, t_{2} hanno gli stessi valori anche in Z, cioè che:

∀t1,t2∈r:t1[Y]=t2[Y]→t1[Z]=t2[Z]\Large{\forall t_{1},t_{2} \in r : t_{1}[Y]=t_{2}[Y] \rightarrow t_{1}[Z] = t_{2}[Z]}

Esempio:

PROGETTAZIONI

ImpiegatoStipendioProgettoBilancioFunzione
Rossi20Marte2tecnico
Verdi35Giove15progettista
Verdi35Venere15progettista
Neri55Venere15direttore
Neri55Giove15consulente
Neri55Marte2consulente
Mori48Marte2direttore
Mori48Venere15progettista
Bianchi48Venere15progettista
Bianchi48Giove15direttore
  • Lo stipendio dipende dall'impiegato
  • Il bilancio dipende dal progetto

Chiavi e attributi

Tutti gli attributi che sono parte di almeno una chiave R(X)R(X) si dice Attributo primo, mentre uno che non fa parte di alcuna chiave è detto Attributo non primo.

Se KK è una chiave dello schema R(X)R(X) allora ogni attributo non primo ZZ dipende funzionalmente da KK, quindi il vincolo di DF K→ZK \rightarrow Z, dove X⊇K∪ZX \supseteq K \cup Z, generalizza il vincolo di chiave K→XK \rightarrow X

Se Y→ZY \rightarrow Z e risulta che anche Z→YZ \rightarrow Y, e Y è una chiave per uno schema R, allora anche Z è una chiave. Una dipendenza funzionale Y→ZY \rightarrow Z è detta completa se Z non dipende da nessun altro sottoinsieme di Y, cioè che se Y è una chiave, se la dipendenza funzionale è completa, Z deve dopendere da tutta la chiave e non anche da parte di essa

Prima forma normale (1NF)

Uno Schema di relazione R(X)R(X) è detto essere in prima forma normale se ogni attibuto di XX è un attributo semplice. Nel modello relazionale, R(X)R(X) è per definizione in 1NF. Quindi ne segue che ogni attributo di R(X)R(X) non primo dipende funzionalmente da una chiave di R(X)R(X)

Un esempio di relazione non in 1NF è quando contiene un attributo multivalore, come una lista, per esempio, Corsi e Indirizzo sono dati multivalore e strutturati, quindi non in 1NF

StudenteCorsiFasciaIndirizzo
MoscatoBasi di Dati, InformaticaIVia: Roma; Num: 30
CAP: 80125; Città: Napoli
PentaBasi di Dati, Sistemi InformativiIVVia: Duomo, Num: 29
CAP: 80100; Città: Napoli

E può essere trasformato in 1NF normalizzando la colonna Corsi e Indirizzo

StudenteCorsiFasciaViaNumCAPCittà
MoscatoBasi di DatiIRoma3080125Napoli
MoscatoInformaticaIRoma3080125Napoli
PentaBasi di DatiIVDuomo2980100Napoli
PentaSistemi InformativiIVDuomo2980100Napoli

Seconda forma normale (2NF)

Uno schema di relazione R(X)R(X) è detto in 2NF, se è in 1NF e ogni attributo non primo dipende completamente da ogni chiave di R(X)R(X), cioè ogni dipendenza funzionale dipende solo da un attributo primo, ed in generale, se ogni chiave di R(X)R(X) ha un solo attributo, allora R(X)R(X) è in 2NF

ArticoloMagazzinoQuantitàCittà
scarpeNA12500Napoli
scarpeRM14500Roma
pantaloniNA13000Napoli

DF1: {Articolo,Magazzino}→Cittaˋ\{Articolo, Magazzino\} \rightarrow Città DF2: Magazzino→CittaˋMagazzino \rightarrow Città

In DF1, città dipende funzionalmente da Articolo e Magazzino

Uno schema che non soddisfa la 2NF può essere normalizzato decomponendo le relazioni che non soddisfano la 2NF, cioè viene decomposta in base agli attributi non comuni in modo tale che le relazioni ottenute soddisfino la 2NF e che il contenuto informativo del database sia uguale.

Articoli_Magazzini

ArticoloMagazzinoQuantità
scarpeNA12500
scarpeRM14500
pantaloniNA13000

Città_Magazzini

MagazzinoCittà
NA1Napoli
RM1Roma

Decomposizione senza perdita

Si dice decomposizione senza perdita se uno schema R(X)R(X) si decompone in R1(X1)R_{1}(X_{1}) e R2(X2)R_{2}(X_{2}) se per ogni istanza legale r di R(X)R(X), il JOIN naturale delle proiezioni di r su X1X_1 e X2X_2 è uguale a r, cioè che:

πx1(r)▹◃πx2(r)=r\Large{\pi_{x_{1}}(r) \triangleright \triangleleft \pi_{x_{2}(r)}= r}

oppure che valga che X1∩X2→X1X_{1} \cap X_{2} \rightarrow X_1, oppure, X1∩X2→X2X_{1} \cap X_{2} \rightarrow X_2, cioè che una decomposizione è garantita essere senza perdita se gli attributi comuni contengono una chiave per almeno una delle relazioni decomposte

ImpiegatoProgettoSede
RossiMarteRoma
VerdiGioveMilano
VerdiVenereMilano
NeriSaturnoMilano
NeriVenereMilano

Decomposizione su attributo comune Impiegato

ImpiegatoSede
RossiRoma
VerdiMilano
NeriMilano
ImpiegatoProgetto
RossiMarte
VerdiGiove
VerdiVenere
NeriSaturno
NeriVenere

Terza forma normale (3NF)

Dato uno schema di relazione R(X)R(X), un attributo AA dipende transitivamente dall'insieme di attributi YY se esiste un altro insieme di attributi ZZ tale che:

  • Y→ZY \rightarrow Z e ZZ -/-> YY
  • Z→AZ \to A e AA -/-> ZZ
  • A∉Y∪ZA \notin Y \cup Z

Uno schema di relazione R(X)R(X) è in 3NF se è in 2NF e ogni attributo non primo di R(X)R(X) dipende in modo non transitivo da ogni chiave di RR, cioè che dipende solo dalle chiavi.

Un altro modo per definirlo è che R(X)R(X) è in 3NF se per ogni DF Y→ZY \to Z definita su R(X)R(X)

  • Y è una superchiave di R(X)R(X). Ogni dipendenza funzionale è completa
  • Z è un attributo primo. Se YY è un attributo non primo, Z deve essere un attributo primo

Riassumendo

  • 1NF: ogni attributo non primo dipende dalla chiave
  • 2NF: ogni attributo non primo dipende da tutta la chiave
  • 3NF: ogni attributo non primo dipende solo dalla chiave

Forme normale di Boyce e Codd

Uno schema di relazione R(X)R(X) è in forma normale di Boyce e Codd se ogni dipendenza funzionale Y→ZY \to Z definita su R(X)R(X), YY è una superchiave.

Se uno schema di relazione è in forma normale di Boyce e Codd, allora è anche in 3NF, ma non viceversa