Appunti per l'esame orale di Databases

Normalizzazione

Capito

Mastery

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

5

Ordine Alta

Priorità

⚠ →

α β α, β

In questi appunti si vede spesso , è imporante 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 attributi è definito atomico quando è costituito da unità indivisibili

Un esempio di dominio non atomico è il seguente

Modello Colore

Ford Fiesta Rosso, Nero, Grigio, Blu

Tesla Model X Rosso, Bianco, Nero

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 di 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:

A B

1 4

1 5

3 7

Nel caso soprastante, si può vedere che B→A ma non i 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 → , 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

⚠ 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 decomposizione, 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 attributi 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.

⚠ 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 Ch

Chiusura di un insieme di dipendenze funzionali

⚠ 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

+ +

⊆ ⊆ →

γ R γ S γ γ

calcolare F+: per ogni ne individuiamo , e per ogni 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:

⚙ ∈

A α α

Algoritmo per verificare se è estraneo in

+

({α} − A)

1. calcolare usando le dipendenze contenute in F

+

({α} − A) β α

2. controllare se contiene , se lo contiene allora A è estraneo in

⚙ ∈

A β β

Algoritmo per verificare se è estraneo in

+ ′ = (F − {α → ∪ {α →

α F β})

1. calcolare usando solamente le dipendenze contenute in

(β − 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 isnieme 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: con

1 1 1 2 1 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

= (R , )

R R

In un caso di decomposizione vorremmo che per tutte le

1 2

possibili relazioni r dello schema R

= Π (r) ⋈ Π (r)

r R R

1 2

Una decomposizione di R in R1 ed R2 è lossless se e solo se vale

almeno una delle seguenti affermazioni

∩ →

R R R

1 2 1

Normalizzazione 6

∩ →

R R R

1 2 2

Preservare le Dipendenze

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

se: + +

(F ∪ ∪ ... ∪ ) =

F F F

1 2 n

⚙ esempio

→

α β

Algoritmo per verificare se la DF è preservata

ddalla decomposizione di R in R1...Rn (con la chiusura

degli attributi fatta rispetto a F)

α

result =

finchè: (risultato viene modificato) fai:

R

per ogni