Decomposizione senza perdita
Data una relazione r su X, se X1 e X2 sono due sottoinsiemi di X la cui unione è X stesso, allora il join delle due relazioni ottenute per proiezione di r su X1 e X2 è una relazione che contiene tutte le tuple di r più eventualmente alcune altre che si possono definire
“spurie”.
La decomposizione di r su X1 e X2 è senza perdita se il join delle due proiezioni è uguale ad r stessa, cioè non contiene tuple spurie.
Se si deve fare una decomposizione ai fini della normalizzazione, è essenziale che sia senza perdita.
Sia r una relazione su X e X1 e X2 tali che X1 U X2 = X e X0 = X1 X2 .
Se r soddisfa la dipendenza funzionale X0->X1 oppure X0 -> X2 allora la decomposizione è senza perdita.
Cioè la decomposizione è senza perdita se gli attributi comuni sono superchiave per una delle relazioni decomposte.
Decomposizione senza perdita
La decomposizione in più relazioni può creare casi in cui un inserimento di dati illecito per la relazione originaria (per la violazione di una dipendenza funzionale) possa non essere rilevato nel caso della relazione decomposta.
Una proprietà fondamentale delle decomposizioni deve essere quella di conservare le dipendenze.
Essa può essere garantita se ciascuna delle dipendenze funzionali dello schema originario coinvolge attributi che compaiono tutti insieme in uno degli schemi decomposti.
Conservazione delle dipendenze
Impiegato Progetto Sede Rossi Marte Roma
Verdi Giove Milano Verdi Venere Milano Neri Saturno Milano Neri Venere Milano
Impiegato Progetto Rossi Marte
Verdi Giove Verdi Venere
Neri Saturno Neri Venere Impiegato Sede
Rossi Roma Verdi Milano
Neri Milano
Impiegato Sede Progetto Sede
Supponiamo di voler inserire una nuova tupla che specifica la partecipazione dell'impiegato Neri, che opera a Milano, al progetto Marte
Conservazione delle dipendenze
Impiegato Progetto Rossi Marte
Verdi Giove Verdi Venere
Neri Saturno Neri Venere Impiegato Sede
Rossi Roma Verdi Milano
Neri Milano
Neri Marte
Neri Milano
Impiegato Progetto Sede Rossi Marte Roma
Verdi Giove Milano Verdi Venere Milano Neri Saturno Milano Neri Venere Milano Neri Marte Milano Progetto Sede non è conservata
Conservazione delle dipendenze
Qualità di una decomposizione
Una decomposizione deve avere la proprietà di decomposizione senza perdita e conservare le dipendenze.
• La decomposizione senza perdita garantisce che le informazioni nella relazione originaria siano ricostruibili con precisione a partire da quelle decomposte. In questo caso, la stessa interrogazione dà gli stessi risultati sulla relazione originaria e su quelle decomposte.
• La conservazione delle dipendenze garantisce che, nelle relazioni decomposte, i vincoli di integrità di quelle originarie siano ancora validi. Ogni aggiornamento (non) valido su quella originaria corrisponde a un aggiornamento (non) valido su quelle decomposte. Queste ultime possono accettare anche aggiornamenti leciti impossibili su quella originaria, a causa delle anomalie rimosse con la decomposizione.
Una relazione non normalizzata
Dirigente Progetto Sede
Rossi Marte Roma
Verdi Giove Milano Verdi Marte Milano Neri Saturno Milano Neri Venere Milano
Progetto Sede Dirigente Dirigente Sede
La decomposizione è problematica
Progetto Sede Dirigente coinvolge tutti gli attributi e quindi nessuna decomposizione può preservare tale dipendenza
Quindi, in alcuni casi, la forma normale di Boyce &
Codd non è raggiungibile
Terza forma normale
Esistono schemi che violano la forma normale di Boyce e Codd che non sono decomponibili ai fini della normalizzazione.
Es. se è presente una dipendenza funzionale in cui un membro sinistro non è superchiave o se una d.f.
coinvolge già tutti gli attributi e quindi non è decomponibile conservando le dipendenze.
In questi casi si ammette una condizione meno restrittiva, che a sua volta non ammette ridondanze o anomalie pur ammettendo situazioni come quelle viste.
Tale condizione si chiama terza forma normale.
Si dice che una relazione r è in terza forma normale se, per ogni dipendenza funzionale X Y definita su di essa è verificata almeno una delle seguenti condizioni:
• X contiene una chiave K di r
• ogni attributo in Y è contenuto in almeno una chiave di r
La terza forma normale è meno forte della forma normale di Boyce e Codd ma è sempre ottenibile.
Terza forma normale
Uno schema non decomponibile in BCNF
Dirigente Progetto Sede
Rossi Marte Roma
Verdi Giove Milano Verdi Marte Milano Neri Saturno Milano Neri Venere Milano
Dirigente Sede
Progetto Sede Dirigente
Una possibile riorganizzazione
Dirigente Progetto Sede Reparto
Rossi Marte Roma 1
Verdi Giove Milano 1
Verdi Marte Milano 1
Neri Saturno Milano 2
Neri Venere Milano 2
Dirigente Sede Reparto
Sede Reparto Dirigente
Progetto Sede Reparto
Decomposizione in BCNF
Progetto Sede Reparto
Marte Roma 1 Giove Milano 1 Marte Milano 1 Saturno Milano 2 Venere Milano 2 Dirigente Sede Reparto
Rossi Roma 1 Verdi Milano 1 Neri Milano 2
Progettazione e normalizzazione
• la teoria della normalizzazione può essere usata nella progettazione logica per verificare lo schema relazionale finale
• si può usare anche durante la progettazione
concettuale per verificare la qualità dello schema concettuale
Prodotto
Nome prodotto
Prezzo Nome
fornitore Indirizzo
Partita IVA
Codice
PartitaIVA Nomefornitore Indirizzo
Si suppone che ogni prodotto abbia un solo fornitoreAnalisi dell’entità
• L’entità viola la terza forma normale a causa della dipendenza:
PartitaIVA NomeFornitore Indirizzo
• Possiamo decomporre sulla base di questa dipendenza
Indirizzo Partita
IVA
Nome fornitore Nome
prodotto
Prezzo
Codice
Fornitura
Prodotto Fornitore
(1,1) (0,N)
Relatore Studente
Corso di laurea
Tesi
(0,N) (0,1)
(0,N) Dipartimento
(0,N)
Studente Corso di laurea Studente Relatore
Relatore Dipartimento
Analisi della associazione
•
L’associazione viola la terza forma normale a causa della dipendenza:
Relatore Dipartimento
•
Possiamo decomporre sulla base di questa
dipendenza
Relatore Studente
Corso di laurea
Tesi
(0,N) (0,1)
(0,N)
Dipartimento Afferenza
(1,1)
(0,N)
Ulteriore analisi sulla base delle dipendenze
•
La associazione Tesi è in BCNF sulla base delle dipendenze
Studente CorsoDiLaurea Studente Relatore
•
le due proprietà sono indipendenti
•
questo suggerisce una ulteriore decomposizione
Relatore Tesi Studente
(0,N) (0,1)
Dipartimento Afferenza
(0,N) (1,1)
Corso di laurea
(0,N)
Corso di laurea Iscrizione
(0,N) (1,1)
