1

Il raffinamento dello schema e Il raffinamento dello schema e la normalizzazione nei la normalizzazione nei database relazionalidatabase relazionali

Eugenio Di Sciascio

2

Introduzione Introduzione

La modellazione E-R ci ha consentito di descrivere schemi relazionali

Lo strumento base per la modellizzazione è stato finora “la ragionevolezza”

Esistono però metodi formali per assicurare la scelta di “buoni” schemi relazionali.

Tali metodi verranno essenzialmente utilizzati per verificare e raffinare lo schema.

3

Linee guida informaliLinee guida informali

Scelta degli attributi: Progettare lo schema in modo che sia

semplice descrivere il suo significato, prestare cioè attenzione alla semantica degli attributi.

Evitare di riunire in uno schema di relazione attributi propri di entità diverse del mondo reale.

4

Linee guida informali (2)Linee guida informali (2)

Ridurre la ridondanza: Ha un duplice scopo: ridurre la “storage

area” e evitare le anomalie da aggiornamento

Anomalie da aggiornamento:1. Anomalie da inserimento2. Anomalie da modifica3. Anomalie da cancellazione

5

Linee guida informali (3)Linee guida informali (3)

1. Anomalie da inserzione: Inserimento di un nuovo impiegato -> inserimento dati dipartimento oppure nulls.Inserimento dati nuovo dipartimento -> almeno 1 impiegato (Id_imp è PK, non null)

2. Anomalie da cancellazione: Eliminazione dell’ultimo dipendente di un dipartimento -> perdita delle informazioni sul dipartimento

3. Anomalie da modifica: Nuovo direttore dipartimento -> modifica di tutte le tuple relative a impiegati di quel dipartimento.

Nome Cognome Superio_id Id_dipData_n indirizzoCF Stip_annuoImpiegato_dipartimento

DipNome Dir_dipData_ino

6

Linee guida informali (4)Linee guida informali (4) Ridurre il numero di valori null nelle tuple: Valori null possono essere variamente interpretati: non

applicabile, sconosciuto, non inserito In molti casi conviene creare nuove relazioni per ridurre i

null. Esempio:

Se solo il 5% degli impiegati ha un fax personale avremo il 95% di null.

Nome Cognome Superio_id Id_dipData_n indirizzoCF Stip_annuoImpiegato_fax

Tel. Fax.

Nome Cognome Superio_id Id_dipData_n indirizzoCF Stip_annuoImpiegato

Tel.

Fax.Id_dip

Fax_imp

7

Linee guida informali (5)Linee guida informali (5)

Evitare le tuple spurie:Una tupla spuria (cioè con informazioni

non corrette) può essere generata a seguito di un join naturale

E’ necessario realizzare schemi che consentano di effettuare join con condizioni di uguaglianza su attributi che siano o chiavi primarie o chiavi esterne, così da garantire l’assenza di tuple spurie.

8

Dipendenze funzionaliDipendenze funzionali

Una dipendenza funzionale è un vincolo tra due insiemi di attributi di una base di dati e dipende dalla semantica dello schema.

Data uno schema relazionale R e due sottoinsiemi non vuoti di attributi X e Y esiste una dipendenza funzionale XY se per ogni istanza r di R:t1 r,t2 r, x(t1) = x(t2) y(t1) = y(t2)i.e., date due tuple in r se i valori su X coincidono, anche i valori su Y coincidono.

9

Dipendenze funzionali (2)Dipendenze funzionali (2)

Notare che:o Se un vincolo su uno schema R indica che

X sia una chiave candidata di R ciò implica che X Y per ogni sottoinsieme Y di attributi di R.

o Non vale la proprietà : X Y Y X.

10

Dipendenze funzionali (3)Dipendenze funzionali (3)

Sia F l’insieme delle FD che sono specificate su uno schema R.

In generale ci saranno comunque altre FD non specificate esplicitamente.

Chiamiamo F+ , chiusura di F, l’insieme delle FD implicate da F.

Esistono regole, corrette e complete, per determinare le FD, detti assiomi di Armstrong.

11

Dipendenze funzionali (4)Dipendenze funzionali (4)

Assiomi di Armstrong:Riflessività: X Y X YIncremento: X Y XZ YZTransitività: X Y , Y Z X ZPossono essere anche determinate altre utili

regole:Unione: X Y , X Z X YZDecomposizione: X YZ X Y

12

Dipendenze funzionali (5)Dipendenze funzionali (5)

Un insieme F di dipendenze funzionale è minimo se: Ogni FD ha 1 solo attributo alla sua destra Non è possibile rimuovere alcuna FD da F ed avere

ancora un insieme equivalente ad F. La parte sinistra di ogni dipendenza funzionale è

minima. In tal modo otterremmo sicuramente schemi privi di

ridondanza Problemi: il calcolo della F+ è pesante e in genere va

accettata una certa quantità di ridondanza per motivi di efficienza.

13

Forme normaliForme normali

Un metodo formale per analizzare le relazioni Consente una eventuale decomposizione di

relazioni in schemi che godono di migliori proprietà.

E’ in generale necessario che anche altre proprietà siano verificate per garantire un buon progetto:

Lossless join (join non additivo) Conservazione delle dipendenze

14

1 Forma normale1 Forma normale

Coincide in pratica con la definizione di relazione:

Il dominio di ciascun attributo deve consistere di valori atomici e il valore di un attributo in una tupla deve essere un valore singolo del dominio

Il metodo di decomposizione è quello già descritto per il mapping ER relazionale

15

2 Forma Normale2 Forma Normale

Uno schema R è in questa forma se ogni attributo non primo ha una FD piena dalla PK di R.

Nome Cognome Superio_idindirizzoCF Stip_annuo

Impiegato_progNome_progN_prog Sede Ore_lav

Nome Cognome Superio_idindirizzo

CF

Stip_annuo

Impiegato_prog

Nome_prog

N_prog

Sede

Ore_lav

CF N_prog

Impiegato Progetto

16

3 Forma Normale3 Forma Normale

Uno schema R è in questa forma se per ogni FD X Y, X è una superchiave di R oppure Y è un attributo primo.

Nome Cognome Superio_id Id_dipData_n indirizzoCF Stip_annuoImpiegato_dipartimento

DipNome Dir_dipData_ino

Nome Cognome Superio_id Id_dipData_n indirizzoCF Stip_annuoImpiegato

DipNome Dir_dipData_inoId_Dip

Dipartimento

17

Forma Normale di Boyce-CoddForma Normale di Boyce-Codd Uno schema R è in questa forma se per ogni FD

X Y, X è una superchiave di R In altre parole R è in BCNF se le uniche FD non

ovvie sono vincoli di chiave. Se R è in BCNF è ovviamente anche in 3NF. Se

una R è in 3NF, ma non in BCNF è ancora possibile ridondanza.

3NF è comunque accettabile ed è sempre possibile decomporre una R in 3NF relazioni che godano anche del lossless-join e preservino le dipendenze.

18

Problemi delle decomposizioniProblemi delle decomposizioni

Interrogazioni più costose a causa dei joinPerdita di informazione (tuple spurie)

dovuta a join.Controllo delle dipendenze può richiedere

l’effettuazione di join.

19

Decomposizione senza perditeDecomposizione senza perdite La decomposizione di uno schema R(X) in due

sottoinsiemi di attributi X1 e X2 tali che X1X2=X e X1X2=X0 è lossless join se è soddisfatta la FD X0 X1 oppure X0 X2

La decomposizione è lossless se l’insieme degli attributi comuni alle due relazioni risultanti è chiave per almeno 1 delle 2 relazioni.

La condizione è sufficiente, non necessaria Data R con FD F, se XY viola la BCNF possiamo

sempre decomporre in R-Y e XY ottenendo relazioni BCNF e lossless join, ma non è assicurata la conservazione delle dipendenze.

20

Conservazione delle dipendenzeConservazione delle dipendenze

E’ in generale importante mantenere i vincoli espressi nelle FD in singole relazioni, così da poterli verificare.

Qs. Può essere in contrasto con la normalizzazione

Esiste un algoritmo che garantisce il lossless join e la conservazione delle dipendenze con decomposizione in 3NF (non in BCNF)

21

Conservazione delle Conservazione delle dipendenze (2)dipendenze (2) Esempio: R(impiegato, progetto,sede) FD: impiegato sede (un impiegato lavora in

una sede); progetto-sede impiegato (ogni progetto ha più impiegati, in sedi diverse, ogni impiegato può gestire più progetti, ma in ciascuna sede un progetto ha un responsabile)

Non in BCNF: impiegato sede e impiegato non è superchiave, ma non è decomponibile xchè progetto-sede impiegato include tutti gli attributi e quindi non è decomponibile.

22

Riassumendo..Riassumendo..Relazioni in BCNF sono prive di

ridondanzaSe non è possibile ottenere una

decomposizione BCNF, lossless join e con conservazione delle dipendenze possiamo accontentarci di una 3NF.

Soprattutto considerare ciò che desideriamo, cioè tenere comunque in conto le prestazioni e le interrogazioni probabili.