Appunti per l'esame orale di Databases

Normalizzazione

Capito Mastery

Fonte https://2022.aulaweb.unige.it/pluginfile.php/112449/mod_resource/content/1/ch7_RDBMS5

Ordine Alta Priorità Attenzione: → α β α, β

In questi appunti si vede spesso, è importante ricordare che sono intesi come insiemi di attributi.

Elementi di base e obiettivi

Dipendenza funzionale

Una dipendenza funzionale è una relazione tra due attributi all’interno di una relazione.

Dati due attributi A e B, si dice che A dipende funzionalmente da B se il valore di A è determinato da B.

Per esempio: se due righe della tabella hanno lo stesso valore dell’attributo B, allora devono avere lo stesso valore anche per A.

NB: La dipendenza funzionale è monodirezionale, non è detto che se B → A allora A → B.

Decomposizione

Decomposizione lossy

Quando una tabella viene “decomposta” in altre due, se si fa il join delle due tabelle “figlie” non si riottiene la tabella “madre”.

Vi è quindi una perdita di informazione.

Decomposizione lossless

Quando una tabella viene decomposta, il join delle tabelle figlie restituisce la tabella “madre”.

1NF

Uno schema relazionale R è in prima forma normale quando i domini di tutti gli attributi sono definiti “atomici”.

Dominio atomico

Un dominio di un attributo è definito atomico quando è costituito da unità indivisibili.

Un esempio di dominio non atomico è il seguente.

Evita la ridondanza.

Normalizzazione 1

Obiettivo: L’obiettivo della teoria della normalizzazione è il seguente:

Definire quando una relazione R è “ben normalizzata”.

Nel caso la relazione non fosse ben normalizzata posso applicare una decomposizione tale che:

• Sia lossless
• Le relazioni “figlie” sono ben normalizzate

La base della teoria della normalizzazione si basa su:

• Dipendenze funzionali
• Dipendenze multivalore

Dipendenze funzionali

La dipendenza funzionale è una generalizzazione del concetto di chiave.

Definizione generale: Il valore di un certo insieme di attributi di una relazione è determinato univocamente da un altro insieme di attributi nella tabella.

Esempio:

Nel caso soprastante, si può vedere che B → A ma non il contrario.

Superchiave e chiave candidata

Superchiave

K si dice superchiave dello schema R se e solo se K → R, ovvero se ogni valore di K identifica una ed una sola riga.

Chiave candidata: K è una chiave candidata di R se e solo se:

• K è chiave candidata di R
• K è irriducibile

Dipendenze banali

Una dipendenza funzionale è detta banale se soddisfa tutte le istanze della relazione.

α → β, β ⊆ α

In generale si ha una dipendenza funzionale banale quando.

Chiusura dell’insieme delle dipendenze funzionali

Un insieme F+ è definito come la chiusura di F e contiene tutte le dipendenze funzionali logicamente implicate da F.

Ad esempio, se A → B e B → C, in F+ ci sarà anche A → C.

BCNF

Normalizzazione 2

∀ α → β

Una tabella è normalizzata in BCNF se dipendenza funzionale in F+ nella forma con α ⊆ R, β ⊆ R vale almeno una delle seguenti condizioni:

• α → β è banale
• α è una superchiave di R

Attenzione: Una tabella è normalizzata in BCNF se ogni attributo della tabella dipende funzionalmente solo dalla chiave primaria della tabella.

Decomporre uno schema in BCNF

α → β

Supponiamo di avere uno schema R con una dipendenza funzionale che viola la BCNF.

Si decompone R in:

α ∪ β

R − (β − α)

Preservare le dipendenze

Per via delle varie decomposizioni, la BCNF non sempre permette di preservare tutte le dipendenze funzionali all’interno delle nuove tabelle (è necessario uno o più join per recuperarle), per permettere la preservazione delle dipendenze, vi è una forma normale più ridondante della BCNF, ovvero la 3NF.

A livello computazionale, la BCNF è più facile da computare rispetto alla 3NF.

3NF

α → β

Uno schema R è in 3NF se per ogni: in F+ vale almeno una delle seguenti informazioni:

• α → β ∈ β α è banale (i.e.)
• α è superchiave di R
• Ogni attributo A in β − α è contenuto in una chiave candidata di R

Se una tabella è in BCNF allora è anche in 3NF (non il contrario), questo perché la 3NF non è altro che una forma più estensiva, per preservare le dipendenze.

Attenzione: La 3NF si concentra sulla rimozione di dipendenze funzionali transitive, che non sono coperte dalla BCNF, che invece si concentra sul rimuovere le dipendenze funzionali non banali.

Normalizzazione 3

Normalizzazione

Gli obiettivi della normalizzazione sono i seguenti:

• Avere ogni relazione in forma normale
• Ogni decomposizione deve essere lossless
• Le decomposizioni devono preservare le dipendenze

Quando la BCNF non basta, 4NF

Vi sono casi in cui delle tabelle normalizzate in BCNF possono non essere sufficientemente normalizzate (motivo per il quale vi sono delle forme normali successive) a causa della presenza di dati ridondanti.

La tabella di sinistra può essere decomposta come nell’immagine sotto, con un grado di normalizzazione superiore, la 4NF, che si basa invece sulle dipendenze multivalore.

Dipendenze multivalore

Le dipendenze multivalore sono una forma di dipendenza in cui un insieme di attributi multivalore dipende da un insieme di attributi singolari. In altre parole, se un insieme di attributi singolari può determinare diversi valori per un insieme di attributi multivalore, allora esiste una dipendenza multivalore tra questi due insiemi di attributi. La normalizzazione può anche essere applicata alle dipendenze multivalore attraverso la quarta forma normale (4NF). La 4NF viene utilizzata per evitare la ridondanza dei dati quando ci sono dipendenze multivalore tra gli attributi di una tabella.

Teoria delle dipendenze funzionali

L’obiettivo di questa teoria è quella di:

• Comprendere quali dipendenze funzionali sono implicate da altre
• Sviluppare algoritmi ottimizzati per la decomposizione in BCNF e 3NF
• Sviluppare algoritmi per testare la conservazione delle dipendenze delle decomposizioni

Chiusura di un insieme di dipendenze funzionali

Attenzione: La chiusura di F, denotata da F+, è l’insieme delle dipendenze funzionali in F e quelle logicamente implicate da esse.

Per trovare F+ è necessario applicare gli assiomi di Armstrong:

• Riflessività: se β ⊆ α allora α → β
• Aumento: se α → β allora γα → γβ
• Transitività: se α → β e β → γ allora α → γ

Normalizzazione 4

Queste regole sono complete: perché generano solamente dipendenze funzionali che valgono e permettono di generare tutte quelle in F+.

Come individuare F+

Algoritmo di calcolo di F+:

• F = F+
• Repeat for each dipendenza funzionale in F+
• Applicare riflessività e aumento
• Aggiungere le DF ottenute ad F+
• For each coppia di DF f1, f2 in F+
• If f1 ed f2 possono essere combinate per transitività
• Then applicare la transitività e aggiungere la DF ad F+
• Until F+ non cambia più

Ulteriori proprietà per calcolare F+:

• Unione: α → β, α → γ allora α → βγ
• Decomposizione: α → βγ allora α → β, α → γ
• Pseudotransitività: α → β, γβ → δ allora αγ → δ

Chiusura di un insieme di attributi

La chiusura di un insieme di attributi denotata con α+ permette di:

• Testare una superchiave: infatti se la chiusura coincide con R allora α è superchiave
• Testare dipendenze funzionali: se una dipendenza α → β allora β ⊆ α+
• Calcolare F+: per ogni γ ⊆ R ne individuiamo γ+, e per ogni S ⊆ γ+ possiamo dire che γ → S

Algoritmo per calcolare la chiusura di un insieme di attributi:

Copertura canonica

La copertura canonica non è altro che una riduzione di F che mantiene le sue proprietà eliminando le ridondanze.

Attributi estranei:

Gli attributi estranei sono quelli che in una dipendenza funzionale possono essere “esclusi”.

Normalizzazione 5

Testing

Algoritmo per verificare se A ∈ α è estraneo in α:

• 1. Calcolare ({α} − A)+ usando le dipendenze contenute in F
• 2. Controllare se ({α} − A)+ contiene β, se lo contiene allora A è estraneo in α

Algoritmo per verificare se A ∈ β è estraneo in β:

• 1. Calcolare {α}+ usando solamente le dipendenze contenute in F′ = (F − {α → β}) ∪ {α → (β − A)}
• 2. Controllare se {α}+ contiene A, se lo contiene allora A è estraneo in β

Calcolo della copertura canonica

La copertura canonica Fc di F è quindi un insieme di D.F tali che:

• Fc implica logicamente tutte le dipendenze di F e viceversa
• Non ci sono dipendenze funzionali in Fc contenenti attributi estranei
• Ogni “lato” delle dipendenze funzionali in Fc è unico

Algoritmo per il calcolo della copertura canonica:

• Ripeti
• Utilizza la regola dell’unione per sostituire tutte le dipendenze in F
• Del tipo: α → β1, α → β2 con α → β1 β2
• Individua una dipendenza funzionale con α → β
• Un attributo estraneo in α o in β
• Se c’è un attributo estraneo rimuoverlo dalla DF
• Fino a che F non cambia più

Esempio.

Decomposizione lossless

Esempio = (R1, R2) R.

In un caso di decomposizione vorremmo che per tutte le possibili relazioni r dello schema R:

r = ΠR1(r) ⋈ ΠR2(r)

Una decomposizione di R in R1 ed R2 è lossless se e solo se vale almeno una delle seguenti affermazioni:

• R1 ∩ R2 → R1
• R1 ∩ R2 → R2

Normalizzazione 6

Preservare le dipendenze

Una decomposizione di R in Ri tabelle con le loro D.F. Ri preserva le dipendenze se e solo se:

(F1 ∪ F2 ∪ ... ∪ Fn)+ = F+

Esempio.

Algoritmo per verificare se la DF α → β è preservata dalla decomposizione di R in R1...Rn (con la chiusura degli attributi fatta rispetto a F):

• Result = α
• Finché: (risultato viene modificato) fai:
• R per ogni