Progettazione logica

Nel secondo capitolo abbiamo visto i vari modelli dati che rappresentano il progetto di un database a livello concettuale. Per ogni modello a livello concettuale corrisponde un modello dati a livello logico della progettazione. In questo caso i modelli dati devono fornire oltre alla notazione per descrivere i dati anche un insieme di operazioni per manipolare i dati stessi.

In questo capitolo vedremo il modello dati relazionale, nel quale solitamente viene tradotto il "diagramma entità-relazione" progettato in precedenza, e l’algebra relazionale, un formalismo che ci permette di accedere ai dati. Inoltre, illustreremo uno strumento di analisi della qualità di un progetto, la teoria della normalizzazione.

Un modello dati a livello logico di progettazione è definito come un formalismo matematico composto da due parti: 

· una notazione per descrivere i dati,

· un insieme di operazioni per manipolare i dati.

Un modello matematico dei dati consente l’utilizzo di linguaggi e metodologie formali per l’accesso ai dati. In particolare le due metodologie su cui si basano i linguaggi di accesso ai dati di un database relazionale sono l’algebra relazionale e il calcolo relazionale. In seguito verrà introdotta la prima metodologia, in quanto costituisce la base del linguaggio SQL (Structured Query Language), ormai affermato come standard nell’accesso ai database relazionali.

La rappresentazione dei dati nel modello logico relazionale è basata su un unico concetto fondamentale, ovvero la relazione: questa va intesa in termini algebrici, e non va confusa con le relazioni tra i dati del modello concettuale.

Il concetto di relazione algebrica è quello secondo la teoria degli insiemi, cioè un sottoinsieme del prodotto cartesiano di una lista di domini.

Formalmente un dominio è semplicemente una lista di valori, non diverso da un tipo di dato.

Il prodotto cartesiano dei domini D1, D2, … , Dk che si scrive D1xD2x … xDk è l’insieme di tutte le k-tuple (v1, v2, … , vk) tali che v1 sia in D1, v2 in D2 e così via.

Ad esempio se k=2, D1={0,1} e D2={a, b, c}, allora:

                    D1xD2={(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}

Una relazione R è un qualunque sottoinsieme del prodotto cartesiano di uno o più domini.

Ad esempio, considerando il prodotto cartesiano precedente, {(0, a), (0, c), (1, b)} è una relazione così come l’insieme vuoto.

Gli elementi di una relazione si chiamano tuple o record. Ogni relazione che sia un sottoinsieme di qualche prodotto D1xD2x … xDk di k domini si dice che k è il grado (o arità) della relazione R. Una Progettazione database relazionali tupla (v1, v2, … , vk) ha k componenti e con vi indichiamo la i-esima componente. Una tupla con k componenti è anche chiamata k-tupla.

Vediamo un esempio più esemplificativo di relazione. Consideriamo i domini:

            Codice_Articolo = {T100, T200}

            Descriz_Articolo = {Tavolo quadrato, Tavolo tondo}

una possibile relazione tra essi è:

             Tavoli = {(T100, Tavolo tondo), (T200, Tavolo quadrato)}

Per comodità di rappresentazione è più conveniente descrivere una relazione algebrica come una tabella come fatto in figura 3.1.

Nella tabella che rappresenta la relazione algebrica, ogni riga è una tupla (o record) e a ogni colonna corrisponde una componente (o campo). Alle colonne si danno spesso dei nomi e sono gli attributi.

L’insieme dei nomi di attributi (delle colonne) di una relazione si chiama schema di relazione. Se denotiamo con REL una relazione e il suo schema di relazione ha gli attributi A1, A2, … , Ak si scrive spesso lo schema di relazione come:

                 REL(A1, A2, … , Ak)

per l’esempio precedente scriveremo:

                 Tavoli(Art_Cod, Art_Descriz)

L’insieme degli schemi di relazione usati per rappresentare informazioni viene chiamato schema di database (relazionale), e i valori correnti delle corrispondenti relazioni formano un’istanza del database o semplicemente il database (relazionale).

Nella definizione di relazione come insieme seguono due osservazioni fondamentali:

· in una tabella non possono esistere due righe uguali

· l’ordine tra le righe di una tabella non è significativo.

Da tali osservazioni deriva che è possibile, e necessario, individuare in ciascuna tabella un insieme di attributi (colonne) in base alle quali identificare le singole righe, che rappresentano quindi una chiave di accesso univoca alle informazioni contenute nella tabella stessa. Questo insieme di colonne, che va definito in fase di creazione dello schema logico, è detto chiave primaria

               (Primary Key - PK) della tabella.

Per la creazione di uno schema logico relazionale è necessario, partendo da uno schema concettuale definito in precedenza, in base al modello entità-relazione, applicare le seguenti regole.

1) Le entità dello schema concettuale diventano tabelle nello schema logico.

2) Le relazioni tra entità dello schema concettuale, vengono rappresentate nello schema logico, facendo uso delle cosiddette chiavi esterne. Una chiave esterna (Foreign Key - FK) di una tabella è un insieme di attributi che corrispondono a quelli che costituiscono la chiave primaria di un’altra tabella, e stabiliscono quindi, un riferimento tra le righe delle due tabelle (vincoli di integrità referenziale, vedi par. 3.5).

In particolare per rappresentare una relazione tra le tabelle T1 e T2 bisogna distinguere tra le relazioni 1:1, 1:N, N:N.

2.1) Relazione 1:1

      Agli attributi di T1 vanno aggiunti, come chiave esterna, gli attributi che                costituiscono la chiave primaria di T2, o alternativamente a T2 vanno aggiunti, come chiave esterna, gli attributi che costituiscono la chiave primaria di T1. Le due soluzioni sono del tutto equivalenti.

2.2) Relazione 1:N

Supponiamo che la relazione sia 1:N tra T1-T2. Agli attributi di T2 vanno aggiunti, come chiave esterna, gli attributi che costituiscono la chiave primaria di T1 (ma non il viceversa!).

2.3) Relazione N:N

In questo caso va definita una nuova tabella T3, che contiene, come chiavi esterne, le chiavi primarie sia di T1 che di T2; è da notare come in questo caso la chiave primaria della tabella T3 possa essere costituita dalla totalità dei suoi attributi.

Gli eventuali attributi della relazione vengono inclusi come attributi della tabella in cui è rappresentata la relazione (T3), quella che contiene le chiavi esterne.

Il modello relazionale non permette di rappresentare direttamente le gerarchie Isa del modello E-R quindi vanno eliminate ristrutturando entità e relazioni con tre alternative possibili che vediamo rispettivamente nella figura 3.2 b), c), d) in relazione alla generica gerarchia Isa della figura 3.2 a).

1) Accorpamento delle figlie della generalizzazione nel padre. Le entità E1 ed E2 vengono eliminate e le loro proprietà (attributi e partecipazione a relazioni e generalizzazioni) vengono aggiunte all’entità padre E0. A tale entità viene aggiunto un ulteriore attributo che serve a distinguere il "tipo" di una occorrenza di E0, cioè se tale occorrenza apparteneva a E1 o a E2 (fig. 3.2 b).

2) Accorpamento del padre della generalizzazione nelle figlie. 

L’entità padre E0 viene eliminata e, per la proprietà dell’ereditarietà, i suoi attributi, il suo identificatore e le relazione a cui tale entità partecipava, vengono aggiunti alle entità figlie E1 ed E2. Le relazioni R11 e R12 rappresentano rispettivamente la restrizione della relazione R1 sulle occorrenze delle entità E1ed E2 (fig. 3.2 c)).

3) Sostituzione della generalizzazione con relazioni 1:1. La generalizzazione si trasforma in due associazioni uno a uno che legano rispettivamente l’entità padre con le entità figlie E1 ed E2. Non ci sono trasferimenti di attributi o associazioni e le entità E1 ed E2 sono identificate esternamente dall’entità E0 (fig 3.2 d)). Nello schema ottenuto bisogna verificare, dopo ogni operazione di aggiornamento delle entità coinvolte nella generalizzazione, che per ogni occorrenza di E1 e di E2 esista una occorrenza di E0 collegata (e per le generalizzazioni totali, che per ogni occorrenza di E0 c’è una occorrenza collegata in E1 o E2).

3.4 Schema logico del database di esempio

Trasformiamo adesso lo schema concettuale del database Mobili Componibili, sviluppato nel capitolo precedente, nel corrispondente schema logico secondo il modello relazionale seguendo le regole sopra descritte.

I passi per tradurre lo schema concettuale nello schema logico corrispondente sono i seguenti.

1) Per ciascun insieme di entità dello schema concettuale, viene definita una tabella nello schema logico: Categorie, Articoli, Componenti, Laboratori, Negozi e Ordini (vedi figura 3.3). I nomi delle entità nello schema concettuale sono espressi al singolare (Categoria, Articolo,… ); nello schema logico sono stati resi al plurale, seguendo una convenzione spesso adottata (Categorie, Articoli,… ). Si sarebbe potuto comunque cambiare completamente i nomi o lasciare gli stessi; ciò che importa è avere come obiettivo la comprensibilità dello schema.  

2) Per ciascuna tabella viene definita una chiave primaria che ne identifica univocamente le righe (figura 3.4).

3) Vengono definite le chiavi esterne per la rappresentazione delle relazioni 1:N tra Categorie e Articoli, tra Negozi e Ordini e tra Laboratori e Componenti, figura 3.5. Alla tabella Articoli è stato aggiunto Cat_Cod, la chiave primaria della tabella Categorie; a Ordini è stata aggiunto Neg_Cod, la chiave primaria di Negozi; analogamente a Componenti è stato aggiunto Lab_Cod, la chiave primaria di Laboratori.

4) Vengono definite le nuove tabelle CompArt e OrdArt per la rappresentazione delle relazioni N:N tra Componenti e Articoli e tra Ordini e Articoli (figura 3.6). La tabella CompArt contiene le chiavi primarie di Componenti e Articoli, la tabella OrdArt contiene le chiavi primarie di Ordini e Articoli.

Si è poi aggiunto in CompArt l’attributo CompArt_Qta che specifica la quantità necessaria di un componente nella costruzione di un articolo. Per esempio, se l’articolo è una libreria e il Tabella Chiave primaria componente è uno scaffale, CompArt_Qta rappresenta il numero di scaffali necessari per costruire la libreria. Analogamente si procede per OrdArt.

In figura 3.7 viene mostrata una rappresentazione dello schema logico relazionale del database diesempio Mobili Componibili.

Le strutture del modello relazionale ci permettono di organizzare le informazioni di interesse per le nostre applicazioni. In molti casi, però, non è vero che qualsiasi insieme di tuple sullo schema rappresenti informazioni corrette per l’applicazione.

A tale scopo è stato introdotto il concetto di vincolo di integrità, come proprietà che deve essere soddisfatta dalle istanze che rappresentano informazioni corrette per l’applicazione.

E’ possibile classificare i vincoli a seconda degli elementi di una base di dati che ne sono coinvolti.

Distinguiamo due categorie, la prima delle quali ha alcuni casi particolari:

· Un vincolo è intrarelazionale se il suo soddisfacimento è definito rispetto a singole relazioni della base di dati:

· Un vincolo di tupla è un vincolo che può essere valutato su ciascuna tupla indipendentemente dalle altre.

· Come caso più specifico, un vincolo definito con riferimento a singoli valori viene detto vincolo su valori o vincolo di dominio, in quanto impone una restrizione sul dominio degli attributi. Ad esempio, se una componente di una tupla rappresenta il voto di un esame universitario in esso sono ammessi valori compresi tra 18 e 30.

· Un vincolo è interrelazionale se coinvolge più relazioni.

Ad esempio se abbiamo una tabella Esami e una Studenti possiamo richiedere che un numero di matricola compaia nella relazione Esami solo se compare nella relazione Studenti.

I vincoli di chiave sono i più importanti vincoli intrarelazionali. Nel modello relazionale ogni relazione deve possedere una chiave e tale chiave deve identificare univocamente tutte le tuple della relazione a cui afferisce. Anche se è permesso che delle tuple possano contenere valori nulli (NULL) che indicano l’assenza (o la non conoscenza) dell’informazione per il corrispondente componente, sulle chiavi delle relazioni è vietata la presenza dei valori nulli pena l’identificazione stessa delle tuple.

I vincoli di integrità referenziale sono la più importante classe di vincoli interrelazionali.

Vediamo alcune caratteristiche con un esempio: consideriamo la base di dati della figura 3.8. In essa la prima relazione contiene informazioni relative ad un insieme di infrazioni al codice della strada, la seconda agli agenti di polizia che le hanno rilevato e la terza ad un insieme di autoveicoli. Le informazioni della relazione INFRAZIONI sono rese significative e complete attraverso il riferimento alle altre due relazioni: alla relazione AGENTI, per il tramite dell’attributo Agente, che contiene i numeri di matricola di agenti corrispondenti alla chiave primaria della relazione AGENTI, e alla relazione AUTO per mezzo degli attributi Prov e Targa, che contengono gli omonimi attributi che formano la chiave primaria della relazione AUTO.

I riferimenti sono significativi in quanto i valori nella relazione INFRAZIONI sono uguali a valori effettivamente presenti nelle altre due: se un valore di Agente in INFRAZIONI non compare come valore della chiave di AGENTI, allora il riferimento non è efficace. Nell’esempio, tutti i riferimenti sono in effetti utilizzabili.

Un vincolo di integrità referenziale (foreign key o referential integrity constraint) fra un insieme di attributi X di una relazione R1 e un’altra relazione R2 è soddisfatto se i valori di X di ciascuna tupla dell’istanza di R1 compaiono come valori della chiave (primaria) dell’istanza R2.

Una istanza del database precedente che non rispetta i vincoli di integrità referenziale è mostrato in figura 3.9.

La relazione AGENTI non contiene nessuna tupla con valore Matricola uguale a 456, poi AUTO non contiene nessuna tupla con valore "RM" su Prov e 2F7643 su Numero.

Quindi i vincoli di integrità referenziale stabiliscono delle regole da seguire per salvare le relazioni definite tra tabelle durante l’immissione o l’eliminazione di record. Quando si applica l’integrità referenziale non è possibile aggiungere un record ad una tabella correlata se nella tabella primaria non esistono record associati, modificare valori contenuti nella tabella primaria che genererebbero record isolati in una tabella correlata ed infine eliminare record della tabella primaria se in una tabella correlata sono inclusi dei record correlati corrispondenti.

Non possiamo ad esempio cancellare un Agente dalla tabella AGENTI quando esistono ancora delle tuple corrispondenti nella tabella INFRAZIONI, e viceversa non possiamo inserire delle Infrazioni non correlati ad alcun record nella tabella AGENTI e AUTO.

Nel modello relazionale, come visto nei paragrafi precedenti, i riferimenti tra le varie relazioni (tabelle) vengono realizzate mediante l’utilizzo di campi con domini comuni, questo si indica dicendo che il modello relazionale è "basato su valori". Altri modelli logici, come il reticolare e il gerarchico, realizzano le corrispondenze in modo esplicito attraverso puntatori e vengono pertanto detti modelli "basati su record e puntatori". La figura 3.10 mostra un database relazionale, mentre nella figura 3.11 è rappresentato lo stesso database in un modello ideale basato su record e puntatori, dove sono stati utilizzati puntatori al posto dei riferimenti realizzati tramite valori (i numeri di matricola degli studenti e i codici dei corsi).

Rispetto ad un modello basato su record e puntatori, il modello relazionale, basato su valori, presenta diversi vantaggi:

· Esso richiede di rappresentare solo ciò che è rilevante dal punto di vista dell’applicazione (dell’utente); i puntatori sono qualcosa di aggiuntivi, legato ad aspetti realizzativi; nei modelli con puntatori, il programmatore delle applicazioni fa riferimento a dati che non sono significativi per l’applicazione;

· Essendo tutta l’informazione contenuta nei valori, è relativamente semplice trasferire i dati da un contesto ad un altro (per esempio se si deve trasferire una base di dati da un calcolatore ad un altro); in presenza di puntatori l’operazione è più complessa, perché i puntatori hanno un significato locale al sistema, che non sempre è immediato esportare;

· La rappresentazione logica dei dati (costituita dai soli valori) non fa alcun riferimento a quella fisica, che può anche cambiare nel tempo: il modello relazionale permette quindi di ottenere l’indipendenza fisica dei dati.

A titolo di inciso, vale la pena notare che anche in una base di dati relazionale, a livello fisico, i dati possono essere rappresentati secondo modalità che prevedono l’uso di puntatori. La differenza, rispetto ai modelli su puntatori è nel fato che qui i puntatori non sono visibili a livello logico.

Inoltre, da notare anche database moderni, come quelli orientati agli oggetti, vengono introdotti gli identificatori (di oggetti), che, pur ad un livello di astrazione più alto, presentano alcune delle caratteristiche dei puntatori.

Gli operatori dell’algebra relazionale permettono di eseguire le operazioni sui dati di un database relazionale. Essi definiscono le operazioni rilevanti nella gestione delle tabelle (relazioni algebriche) e possono essere classificati in operatori di base e operatori derivati.

I primi costituiscono un insieme funzionalmente completo, ovvero permettono di realizzare tutte le operazioni di dati all’interno di uno di schema relazionale. I secondi sono derivabili dai primi mediante opportune operazioni algebriche a volte complesse.

Gli operatori di base sono proiezione, selezione, prodotto, ridenominazione, unione e differenza. Gli operatori derivati sono intersezione, giunzione naturale e giunzione.

Tutti gli operatori relazionali hanno la caratteristica comune di avere come argomento delle relazioni (tabelle) e fornire come risultato altre relazioni (ancora tabelle). Nel seguito saranno usati come sinonimi i termini relazione e tabella.

Data una tabella e un insieme di attributi, la proiezione restituisce una tabella con tutte le righe di quella di partenza ma con alcune colonne (attributi) eliminati e/o risistemati nell’ordine desiderato (fig.3.12 c) e 3.13).

Data una tabella e una condizione logica sui suoi attributi, la selezione restituisce una tabella con gli stessi attributi di quella di partenza ma con le sole righe che soddisfano la condizione (fig. 3.12 d) e 3.13).

Date due tabelle, il loro prodotto restituisce una tabella le cui righe sono ottenute concatenando ogni riga della prima con tutte le righe della seconda (fig. 3.12 e)).

Data una tabella e una sequenza di attributi, la ridenominazione restituisce una tabella ottenuta dalla tabella di partenza cambiandone tutti gli attributi ordinatamente in quelli della sequenza data come argomento. Espressa in altri termini, la ridenominazione di una tabella in base a un insieme di nomi consente di ridenominarne le colonne assegnando loro tali nomi.

Date due tabelle con gli stessi attributi restituisce come risultato una tabella contenente tutte le righe delle due tabelle considerate (fig. 3.12 f)).

Anche in questo caso le tabelle devono avere la stessa struttura; il risultato è una tabella che contiene tutte le righe della prima escluse quelle contenute nella seconda. In altre parole la tabella restituita è uguale alla prima tabella epurata dalle righe uguali, cioè contenente gli stessi valori, a righe presenti nella seconda tabella (fig. 3.12 g)).

Date due tabelle con gli stessi attributi, restituisce come risultato una tabella contenente tutte le righe comuni alle due tabelle considerate. L’intersezione può essere espressa con due operazioni di differenza:

                                        R Ç S = R – (R – S)

Date due tabelle con un dominio in comune, restituisce una tabella ottenuta mediante il seguente procedimento:

1) viene effettuato il prodotto cartesiano tra le due tabelle;

2) sulla tabella così risultante viene eseguita la selezione delle righe in cui gli attributi appartenenti al dominio comune sono uguali;

3) vengono infine ridenominati gli attributi comuni con uno stesso nome, in modo che compaiono una sola volta.

E’ possibile definire il natural join anche tra tabelle aventi più domini in comune. Se le tabelle non hanno domini in comune il natural join si riduce al prodotto cartesiano.

Date due tabelle con un dominio in comune, ed una condizione nella forma

Dove A1 e A2 sono gli attributi delle due tabelle corrispondenti al dominio in comune e op è un operatore di confronto (>, <, £, ecc.), la join restituisce una tabella ottenuta mediante il seguente procedimento:

1) viene effettuato il prodotto cartesiano tra le due tabelle:

2) sulla tabella così risultante viene eseguita la selezione delle righe in cui gli attributi appartenenti al dominio comune soddisfano la condizione:

3) vengono infine ridenominati gli attributi comuni con lo stesso nome, in modo che compaiono una volta sola.

Se op è l’operazione di = la join viene chiamata equijoin.

Il semijoin della relazione R con la relazione S è la proiezione sugli attributi di R del natural join di R e S (fig. 3.14 h)).

Una volta impostato uno schema logico relazionale è necessario effettuare una serie di verifiche sulla correttezza del procedimento svolto. Queste potranno portare a modificare la struttura dello schema stesso, al fine di renderlo corretto ed evitare il verificarsi, nella gestione dei dati, di errori difficilmente ovviabili a posteriori.

Tale processo è detto normalizzazione dello schema relazionale ed è effettuabile mediante procedimenti di tipo algebrico, basati sui concetti di dipendenza e di scomposizione.

Esistono cinque forme normali di cui le prime due sono molto semplici mentre quelle più significative sono la terza e quella di Boyce-Codd che hanno certe proprietà desiderabili:

· assenza o quasi di ridondanza nelle relazioni

· eliminazione delle anomalie

· conservazione delle dipendenze

· ricostruzione della relazione di partenza a partire da quelle scomposte

· mantenimento dei vincoli di integrità del progetto originale.

Vediamo dei comportamenti poco desiderabili di uno schema di relazione tramite un esempio.

Supponiamo di avere la relazione:

                  INFO_FORN(NOME_FORN, INDIR_FORN, NOME_PROD, PREZZO)

che comprende tutte le informazioni di un fornitore di un particolare prodotto.

In questo schema si possono riscontrare diversi problemi.

· Ridondanza. L’indirizzo del fornitore è ripetuto una volta per ogni prodotto venduto.

· Inconsistenza potenziale (anomalie di aggiornamento). Come conseguenza della ridondanza potremmo aggiornare l’indirizzo del fornitore in una tupla, lasciandolo inalterato in un’altra. Non avremmo allora un unico indirizzo per ogni fornitore, come invece ci si aspetterebbe.

· Anomalie di inserimento. Non possiamo registrare un indirizzo di un fornitore, se questo attualmente non fornisce almeno un prodotto. In una tupla potremmo porre dei valori nulli nelle componenti NOME_PROD e PREZZO per quel fornitore, ma allora, quando per esso si introducesse un prodotto, ci ricorderemmo di cancellare la tupla dei valori nulli? E ancora peggio, NOME_PROD e NOME_FORN insieme formano una chiave per la relazione, e non è ammissibile che si inseriscono dei valori nulli in una chiave.

· Anomalie in cancellazione. L’inverso del problema precedente è che se cancellassimo tutti i prodotti di un fornitore, involontariamente perderemmo traccia del suo indirizzo.

Nell’esempio mostrato tutti i problemi precedenti svaniscono se sostituiamo la relazione INFO_FORN con i due schemi di relazione seguenti:

                      FORNITORI(NOME_FORN, INDIR_FORN)

                      FORNISCE(NOME_FORN, NOME_PROD, PREZZO)

In tal caso FORNITORI contiene l’indirizzo di ogni fornitore esattamente una volta, quindi non vi è ridondanza. Inoltre possiamo introdurre l’indirizzo di un fornitore anche se attualmente non fornisce prodotti.

Adesso però abbiamo lo svantaggio di dover eseguire una join tra le due relazione per ottenere gli indirizzi dei fornitori di un certo prodotto.

Quello che abbiamo appena eseguito non è altro che una normalizzazione della relazione INFO_FORN scomponendo tale relazione in altre due relazioni che conservano tutti i dati e le dipendenze di partenza.

Vediamo adesso brevemente i concetti dipendenze e di scomposizione che sono alla base delle forme normali.

La prima cosa da notare è che le dipendenze e la ridondanza sono strettamente legate tra di loro. Nel caso in cui le dipendenze siano funzionali, la forma della ridondanza è ovvia. Se nella precedente relazione INFO_FORN vedessimo le due tuple della figura 3.15:

potremmo fare l’ipotesi che Nome_Forn determini funzionalmente Indir_Forn per dedurre che ??? sta per Via "Roma 16". Quindi la dipendenza funzionale fa si che per un fornitore, tutti i campi Indir_Forn, escluso il primo, siano ridondanti. Se però non sono valide le nostre ipotesi sulla dipendenza funzionale sopraddetta quest’ultimo campo non sarebbe ridondante.

Quando abbiamo dei tipi di dipendenza più generali di quelle funzionali, la forma assunta dalla ridondanza diventa meno chiara. In tutti i casi però sembra che la causa e la cura della ridondanza vadano mano nella mano. Cioè la dipendenza, come quella tra Indir_Forn e Nome_Forn, non solo dà origine alla ridondanza, ma permette anche, la scomposizione della relazione Info_Forn in Fornitori e Fornisce, in modo tale che la relazione originale Info_Forn possa essere recuperata dalle due relazioni.

Come evidenziato un tipo di dipendenza è quella funzionale, un’altra importante che analizzeremo è quella a molti valori.

Le dipendenze funzionali descrivono legami di tipo funzionale tra gli attributi di una relazione.

Se ad esempio un attributo ne determina un altro in modo unico, come potrebbe essere che Nome_Fornitore determina Indirizzo_Fornitore diciamo che vi è una dipendenza funzionale di Indirizzo_Fornitore da Nome_Fornitore, o anche che Nome_Fornitore determina funzionalmente Indirizzo_Fornitore, e si indica come segue:

                     {Nome_Fornitore} - {Indirizzo_Fornitore}

Il significato delle dipendenze funzionali è che se abbiamo una relazione dove un certo insieme di attributi formano una chiave per tale relazione, possiamo dire che, gli altri attributi (anche un sottoinsieme della chiave) sono determinati funzionalmente dalla chiave. La chiave quindi determina funzionalmente una relazione.

Un’ altra dipendenza funzionale dello schema di relazione Info_Forn è:

                     {Nome_Forn, Nome_Prod} - {Prezzo}

che ritroviamo nella seconda tabella della scomposizione.

Introduciamo il concetto di dipendenza a molti valori con un esempio.

Supponiamo di avere il seguente schema di relazione INFO_CORSO(CORSO, INSEGNANTE, ORA, AULA, STUDENTE, VOTO). In figura 3.16 abbiamo una possibile relazione per tale schema.

In questo semplice esempio vi è un solo corso con due studenti, ma vediamo parecchi fatti importanti che ci aspetteremmo fossero validi in qualunque relazione di questo schema. Un corso può avere luogo ogni volta a ore diverse in aule diverse. Ogni studente ha una tupla per ogni corso seguito e per ogni sessione di quel corso. Il voto per il corso è ripetuto per ogni tupla.

Perciò ci aspettiamo che valga in generale la dipendenza a molti valori di Ora e Aula da Corso e si indica

                      {Corso} - {Ora, Aula}

cioè che esista un insieme di coppie ore-aula associate ad ogni corso e non associate agli altri attributi.

Adesso se consideriamo le tuple:

           u1 = Cs101 Chiarissimo 9-11 222 Rossi 30

           u2 = Cs101 Chiarissimo 11-13 333 Verdi 28

ossia la prima e la quinta tupla della relazione in fig 3.16. Adesso, vista la dipendenza precedente, possiamo pensare di scambiare la coppia ore-aula delle tuple precedenti ed ottenere le tuple seguenti:

          u3 = Cs101 Chiarissimo 11-13 333 Rossi 30

          u4 = Cs101 Chiarissimo 9-11 222 Verdi 28

Se controlliamo la relazione in figura 3.16 vediamo che queste tuple sono effettivamente nella relazione: rispettivamente la seconda e la quarta.

La dipendenza molti valori sopra detta non vale perché le tuple si trovano nella relazione, ma essa vale perché qualunque corso c se si tiene alle ore h1 nell’aula r1 con insegnante t1 e studente s1 che ha voto g1 e se si tiene anche alle ore h2 nell’aula r2 con insegnante t2 e studente s2 che ha voto g2, allora si terrà alle ore h1 nell’aula r1 con insegnante t2 e studente s2 che ha voto g2.

Esiste un algoritmo per controllare se sussistono dipendenze a molti valori tra due insiemi di attributi di una relazione, ma non ci dice come trovarle, per potere applicare regole di scomposizione.

Per individuare tutte le dipendenze di uno schema di relazione non è plausibile andare a vedere le tuple della relazione per dedurre le dipendenze valide.

Il solo modo per determinare le dipendenze funzionali che valgono per uno schema di relazione è quello di considerare con attenzione il significato degli attributi.

La scomposizione di uno schema di relazione R={A1, A2, … , An} consiste, nella sua sostituzione, con un insieme S={R1, R2, … , Rk} di sottoinsiemi di R tali che:

                                        R = R1 È R2 È … È Rk

Non è richiesto che i diversi Ri siano disgiunti.

Il motivo per eseguire una scomposizione è che essa permette di eliminare alcuni problemi visti nel paragrafo 3.8.1. Abbiamo anche visto in tale paragrafo che gli schemi di relazioni FORNITORI e FORNISCE sono una scomposizione per lo schema di relazione INFO_FORN, e risolvono i problemi riscontrati.

Ma adesso sorge un dubbio, noi ci aspettiamo che le relazioni correnti degli schemi scomposti siano la proiezione sui rispettivi attributi della relazione dello schema di partenza. Un modo per controllarlo è quello di prendere il natural join delle relazioni scomposte e vedere se riotteniamo la relazione dello schema di partenza. Se però il natural join non permette di ricostruire la relazione originale, non vi è alcun modo di ripristinarla in modo univoco.

Se R è uno schema relazionale scomposto negli schemi R1, R2, … , Rk e D è un insieme di dipendenze, diciamo che la scomposizione possiede un lossless join (rispetto a D) o è una scomposizione lossless join (rispetto a D), se per ogni relazione r (istanza attuale) di R che soddisfa D, r è il natural join delle sue proiezioni sugli Ri.

La proprietà di lossless join è necessaria se la relazione scomposta deve essere ricostruita a partire dai suoi costituenti (si esegue tra questi ultimi un natural join), di conseguenza interrogando le relazioni scomposte otteniamo gli stessi risultati della relazione originale.

Facciamo un esempio di scomposizione che non è lossless join.

Supponiamo di avere la relazione della figura 3.17.

tale relazione soddisfa le dipendenze funzionali:

                   Impiegato - Sede

                   Progetto - Sede

che sostanzialmente specificano il fatto che ciascun impiegato opera presso un’unica sede e che ciascun progetto è sviluppato presso un’unica sede. Si osservi che impiegato può partecipare a più progetti anche se, sulla base delle dipendenze funzionali, debbono essere tutti progetti assegnati alla sede a cui afferisce.

L’idea generale delle scomposizioni è quella di scomporre la relazione di partenza sulla base delle dipendenze. Allora saremmo portati a decomporre la relazione in due parti:

· Una relazione sugli attributi Impiegati e Sede, in corrispondenza alla dipendenza Impiegato à Sede.

· L’altra sugli attributi Progetto e Sede, in corrispondenza alla dipendenza funzionale Progetto - Sede.

L’istanza in figura 3.17 verrebbe decomposta, per mezzo di proiezioni sugli attributi coinvolti, nelle due relazioni in figura 3.18.

Adesso eseguiamo un natural join di queste ultime due tabelle con l’unico attributo comune, cioè Sede, ed otteniamo la relazione della figura 3.19.

Osservando la relazione ottenuta notiamo che non abbiamo ricostruito tutte e sole le informazioni della relazione originaria: ad esempio l’impiegato Verdi lavora a Milano così come il progetto Saturno viene svolto presso la sede di Milano, ma in effetti Verdi non lavora a tale progetto.

Abbiamo ottenuto una relazione che contiene due tuple in più, dette spurie, rispetto a quella di partenza, quindi, la scomposizione non è lossless.

La definizione iniziale di scomposizione lossless join si adatta a qualunque numero di schemi relazionali. Però, per le scomposizioni in due schemi si può fornire un controllo molto più semplice dato dalla seguente definizione:

Sia r una relazione su X e siano X1 e X2 sottoinsiemi di X tali che X1 È X2 = X. Inoltre, sia X0 = X1 Ç X2. Se r soddisfa la dipendenza funzionale X0àX1 oppure la dipendenza funzionale X0àX2, allora r ha una scomposizione lossless join su X1 e X2.

In modo intuitivo possiamo dire che una relazione si decompone senza perdita su due relazioni se l’insieme degli attributi comuni alle due relazioni è chiave per almeno una delle due relazioni scomposte.

Nell’esempio precedente, possiamo vedere che l’intersezione degli insiemi degli attributi su cui abbiamo effettuato le due proiezioni è costituita dall’attributo Sede, che non è primo membro di alcuna dipendenza funzionale.

Esiste un algoritmo che dato uno schema relazionale, un insieme di dipendenze funzionali e una scomposizione permette di dire se la scomposizione è lossless join.

Un’altra proprietà importante di una scomposizione di uno schema di relazione è che essa mantenga le dipendenze.

Diciamo che una scomposizione di uno schema di relazione conserva l’insieme delle dipendenze se l’unione di tutte le dipendenze nello schema scomposto implica logicamente tutte le dipendenze iniziali.

Il motivo per cui è desiderabile che una scomposizione mantenga le dipendenze è che le dipendenze si possono considerare come vincoli di integrità (correttezza dei valori che si trovano nelle componenti delle tuple) per lo schema di relazione.

Facciamo un esempio partendo dalla relazione della figura 3.17. Volendo rimuovere le anomalie, potremmo pensare, per ottenere una decomposizione lossless join, di sfruttare la dipendenza:

                           Impiegato - Sede

(potremmo procedere anche utilizzando l’altra dipendenza, Progetto à Sede) ottenendo due relazioni, una sugli attributi Impiegato e Sede e l’altra sugli attributi Impiegato e Progetto. L’istanza in figura 3.17 verrebbe così decomposta nelle relazioni in figura 3.20.

Il natural join delle due relazioni in figura 3.20 produce effettivamente la relazione in figura 3.17, per cui possiamo dire che la relazione in figura 3.17 ha una decomposizione lossless join su Impiegato, Sede e Impiegato, Progetto. In effetti Impiegato è chiave per la prima relazione, per cui la proprietà sopra discussa garantisce la decomposizione senza perdita. Però la decomposizione non mantiene le dipendenze funzionali. Infatti, supponiamo di voler realizzare un inserimento corrispondente all’inserimento di una tupla che specifica la partecipazione dell’impiegato Neri, che opera a Milano, al progetto Marte (svolto a Roma). Sulla relazione originaria, cioè quella in figura 3.17, un tale aggiornamento verrebbe immediatamente individuato come illecito, perché porterebbe ad una violazione della dipendenza Progetto à Sede. Sulle relazioni decomposte, non è possibile rilevare alcune violazione di dipendenza (a meno di considerare le due relazioni contemporaneamente, ma in tal caso si verrebbero a perdere molti dei benefici della decomposizione stessa): sulle relazione avente per attributi Impiegato e Progetto non è infatti possibile definire alcuna dipendenza funzionale e quindi non ci possono essere violazioni da rilevare, mentre la tupla con i valori Neri e Milano già appartiene alla relazione su Impiegato e Sede.

Possiamo quindi notare come non sia possibile effettuare alcuna verifica sulla dipendenza Progetto - Sede, perché i due attributi Progetto e Sede sono stati separati: uno in una relazione e l’altro nell’altra.

In modo intuitivo possiamo dire che una decomposizione conserva le dipendenze se in ogni decomposizione, ciascuna delle dipendenze funzionali dello schema originario coinvolga attributi che compaiono tutti insieme in uno degli schemi decomposti.

In questo modo, è possibile garantire, sullo schema decomposto, il soddisfacimento degli stessi vincoli il cui soddisfacimento è garantito dallo schema originario.

E’ opportuno osservare che una scomposizione può possedere un lossless join rispetto ad un insieme di dipendenze F, pur non conservando F. L’esempio precedente in figura 3.20 è un esempio di tale possibilità. Inoltre una scomposizione potrebbe conservare F, pur non possedendo un lossless join.

Esiste un algoritmo che dato uno schema di relazione, una scomposizione e un insieme di dipendenze funzionali permette di dire se la scomposizione conserva le dipendenze.

Una nota a sfavore delle scomposizioni è quella che aumentano i tempi di risposta delle interrogazioni sul database quindi è apprezzabile nel momento in cui sia necessario  risolvere problemi come quello della ridondanza, ma non in altri casi.

La prima forma normale (First Normal Form – 1NF) stabilisce che in una tabella (relazione) non possono esistere colonne (attributi) definite per contenere una molteplicità di valori. Una tabella quindi non può contenere una struttura vettoriale o array, al contrario di quanto consentito in linguaggi di programmazione tradizionali.

Le tabelle che contengono una colonna non rispondente a questa condizione vanno trasformate, creando per ciascuna riga della tabella di partenza tante righe quanti sono i valori multipli presenti nelle colonne della riga considerata, figura 3.21 a), oppure scomponendo in due tabelle come in figura 3.21 b).

Nelle tabelle non normalizzate viene assegnato comunque spazio di memorizzazione ai "campi ripetuti" anche se in essi non sono specificati valori. Inoltre il numero dei "campi ripetuti", è fisso, ad esempio nella prima tabella della figura 3.21 b) per ogni persona sono ammessi al più tre figli, ma ci sono persone con quattro o più figli. In ultimo, ma non per importanza, se vogliamo ricercare un figlio nella tabella suddetta lo dobbiamo fare per tutte e tre le colonne di ogni riga.

Tutti questi problemi sono stati risolti scomponendo la tabella di partenza in due tabelle in cui in una (tabella Figli) sono stati spostati le colonne ripetute. L’associazione tra le due tabelle è stabilita con la combinazione della primary key e foreign key (fig. 3.21 b)).

La seconda forma normale (Second Normal Form – 2NF) riguarda le tabelle in cui la chiave primaria sia composta da più attributi e stabilisce che, in questo caso, tutte le colonne corrispondenti agli attributi dipendano dall’intera chiave primaria e non da una parte di essa. Naturalmente è richiesto che la tabella sia già in 1NF. Se la tabella è dotata di chiave primaria mono attributo è già in 2NF.

Nella prima parte della figura 3.22 è mostrata una tabella che non risponde a questo requisito; infatti la chiave primaria è composta da Codice_città e Codice_via; la colonna Città dipende solo da Codice_città; la colonna Via dipende invece da Codice_città e Codice_via: la colonna Città quindi non dipende da tutta la chiave, ma solo da una sua parte.

Per ricondurre una tabella con questa caratteristica alla seconda forma normale è necessario scomporla in due tabelle. Nella seconda parte della figura 3.22 entrambe le tabelle, che rappresentano globalmente la stessa realtà della precedente, rispettano la seconda forma normale.

Convertendo il progetto di un database in 2NF si eliminano buona parte dei problemi visti nel paragrafo 3.8.1.

Delle successive forme normali diamo anche una definizione formale e per fare questo ci servono alcune definizioni.

Una relazione può avere più attributi o insieme di attributi che possono formare una chiave. Con il termine chiave candidata si indica un qualsiasi insieme minimale di attributi che funzionalmente li determina tutti, mentre il termine chiave (primaria) è riservato per una particolare chiave candidata (la "principale"). Con il termine superchiave si indica un qualunque superinsieme (è una chiave o contiene una chiave) di una chiave.

Si definisce primario un attributo A in una relazione R se A è membro di una qualunque chiave di R. Se A non e membro di alcuna chiave, allora A è non primario.

Uno schema di relazione R è in terza forma normale (Third Normal Form - 3NF) se ogni volta che in R vale X à A e A non è in X, allora X è una superchiave per R, oppure A è primario, cioè la 3NF stabilisce che non esistono dipendenze tra colonne di una tabella se non basate sulla chiave primaria, o se esistono, l’attributo determinato è primario. Naturalmente è richiesto che la tabella sia già in 2NF.

Nella prima parte della figura 3.23 sono mostrate due tabelle che non rispondono a questo requisito: le dipendenze funzionali individuate per la prima tabella sono:

                      {N_Protocollo} - {Mittente, Tipo}

                      {Tipo} - {Urgenza}

per la seconda:

                      {Tipo} - {Descrizione}

la violazione è data dal fatto che nella prima tabella la chiave primaria è N_Protocollo; la colonna Urgenza non dipende da N_Protocollo, bensì, dalla chiave primaria della seconda tabella, ovvero Tipo. Quindi la dipendenza funzionale:

                      {Tipo} - {Urgenza}

viola la 3NF in quanto Tipo non è superchiave per la prima tabella e Urgenza non è primario.

Anche in questo caso la dipendenza va ricondotta alla tabella opportuna, creandone eventualmente una ad hoc. Nel nostro esempio le modifiche da apportare allo schema logico rappresentato sono le seguenti:

1) eliminare la colonna urgenza dalla prima tabella,

2) aggiungere la colonna Urgenza alla seconda tabella, ottenere così la terza tabella della figura 3.23.

Si scompone in modo che a ciascuna dipendenza corrisponde una diversa relazione la cui chiave è proprio il primo membro della dipendenza stessa. In tale modo, il soddisfacimento della 3NF è garantito, per la definizione stessa della 3NF.

Nell’esempio precedente, la separazione delle dipendenze (e quindi dei concetti da essa rappresentati) è stata facilitata dalla struttura delle dipendenze stesse, "naturalmente" separate e indipendenti l’una dall’altra. In effetti in molti casi pratici, la decomposizione può essere effettuata producendo tante relazioni quante sono le dipendenze funzionali definite (o meglio, le dipendenze funzionali con diverso primo membro).

In generale, purtroppo, le dipendenze possono avere una struttura complessa: può non essere necessario (possibile) basare la decomposizione su tutte le dipendenze e può essere difficile individuare quelle su cui si deve basare la decomposizione.

Vediamo un esempio semplicissimo, esaminando il quale capiamo subito quale sarebbe la natura della decomposizione, ma che, al tempo stesso, ci permette di individuare il problema.

Consideriamo la relazione della figura 3.24.

Notiamo che soddisfa la dipendenza:

                      {Impiegato, Categoria} - {Stipendio}

ma anche le dipendenze:

                      {Impiegato} - {Categoria}

                      {Categoria} - {Stipendio}

Procedendo come in precedenza, potremmo facilmente ottenere una base di dati con due relazioni entrambe in 3NF.

D’altra parte, per la stessa relazione, avremmo potuto individuare, insieme alla dipendenza funzionale:

                       {Categoria} - {Stipendio}

anche la dipendenza:

                       {Impiegato} - {Categoria, Stipendio}

anziché {Impiegato} - {Categoria}, che avrebbe descritto il frammento di realtà con la stessa accuratezza (o quasi). In questo secondo caso, non avremmo avuto strumenti per generare una naturale decomposizione in 3NF, perché ovviamente la dipendenza {Impiegato} - {Categoria, Stipendio} ricopre tutti attributi e quindi non suggerisce alcuna relazione decomposta.

Da notare come in un esempio così semplice l’individuazione delle dipendenze possa produrre difficoltà nella decomposizione; si può immaginare che cosa possa succedere quando la relazione è complessa e su di essa sono definite diverse dipendenze funzionali, fra loro interconnesse.

In tal caso non si può fare a meno di trattare la normalizzazione in modo formale che però esula dagli scopi di questo documento.

1) Partire dalle tabelle non normalizzate

2) Individuare le chiavi primarie, ed eventuali altre dipendenze funzionali.

3) Individuare e risolvere le violazioni della 1NF rimuovendo tutti gli attributi ripetuti.

· Se esistono attributi ripetuti trasformare la tabella in questione creando per ciascuna riga della tabella di partenza tante righe quanti sono i valori multipli presenti nelle colonne della riga considerata oppure spostando le colonne ripetute in un’altra tabella dove la chiave primaria della prima tabella diventa chiave esterna in quest’ultima (fig 3.21 a) e b)).

4) Individuare e risolvere le violazioni della 2NF assicurando che ciascun attributo dipenda dall’intera chiave.

· Se alcuni attributi non dipendono dall’intera chiave (dipendenze funzionali in cui il termine a sinistra non è l’intera chiave) creare una nuova tabella con gli altri attributi che dipendono da parte di questa.

· Definire in questa nuova tabella la chiave primaria coincidente con la parte determinante della chiave originale.

· Eliminare dalla tabella originale gli attributi (non chiave) spostati nella nuova tabella (fig. 3.22).

5) Individuare e risolvere le violazioni della 3NF assicurando che non esistano attributi non chiave che dipendano da altri attributi non chiave.

· Se esiste un tale attributo, rimuoverlo dalla tabella originale insieme da tutti gli altri che dipendono dallo stesso determinante (dipendenze funzionali tra attributi non chiave), e creare una nuova tabella che li contenga.

· Gli attributi determinanti diventano chiave primaria nella nuova tabella e permangono nella precedente tabella in qualità di chiavi esterne.

· (Eliminare gli attributi che sono dipendenti dai determinanti dalla tabella di partenza (fig. 3.23)).

Il processo precedente permette di verificare la qualità delle relazioni, a volte non occorre fare nessuna trasformazione, perché lo schema del database si trova gia in 3NF, in questo contesto, la teoria della normalizzazione costituisce un utile strumento di analisi della qualità di un progetto.

Il motivo per cui a volte non necessita fare alcuna trasformazione sullo schema del database è perché la metodologia di progettazione (concettuale, logica) porta a schemi di database già in 3NF, tramite l’individuazione e la separazione dei concetti fondamentali della realtà da modellare creando entità e/o associazioni distinte.

Per la maggior parte delle situazioni quando un progetto di schema di database si trova in terza forma normale è più che ottimo.

Nei successivi paragrafi, per completezza, illustreremo la forma normale di Boyce-Codd e brevemente, la quarta forma normale (nella pratica poco usata).

La forma normale di Boyce-Codd è una condizione molto forte, nel senso che non è sempre possibile portare in questa forma uno schema relazionale tramite scomposizione, senza perdere la capacità di mantenere le dipendenze. Mentre la terza forma normale fornisce la maggior parte dei vantaggi della forma normale di Boyce-Codd, per quanto riguarda l’eliminazione delle anomalie, però è una condizione che possiamo raggiungere per uno schema arbitrario di database, senza perdere la conservazione delle dipendenze o la proprietà di lossless-join.

Uno schema di relazione R con dipendenze F, si dice essere in forma normale Boyce-Codd (Boyce-Codd Normal Form – BCNF) se ogni volta in R vale XàA, e A non è in X, allora X è una superchiave di R, cioè X è una chiave o contiene una chiave.

Ovvero, la BCNF stabilisce che non esistono dipendenze tra attributi di una relazione se non basate sulla chiave primaria.

Si consideri lo schema relazionale (CITTA’, VIA, CAP), abbreviato con CSZ, con le dipendenze CS-Z e Z-C. Si può dimostrare che le chiavi di questo schema relazionale sono CS e SZ. Lo schema CSZ con queste dipendenze non si trova in BCNF, dato che in CSZ vale Z-C, però Z non è una chiave di CSZ e neppure contiene una chiave. La scomposizione però in 3NF poiché C è primario e CS è chiave.

L’esempio della figura 3.23 è in BCNF.

La ragione che sta alla base della BCNF è quella di eliminare le ridondanze che possono essere introdotte dalle dipendenze funzionali e non eliminate dalle precedenti forme normali. In tale forma normale, facendo uso solo delle dipendenze funzionali, non è possibile prevedere nessun valore dati gli altri.

Naturalmente dato che la 3NF è più debole della BCNF, non può eliminare tutte le ridondanze.

L’esempio canonico è quello CSZ precedente, che è in 3NF e si possono avere coppie di tuple come in figura 3.25:

in cui dalla dipendenza Z-C possiamo dedurre che il valore incognito è c. Si osservi che queste tuple non possono violare l’altra dipendenza CS-Z perché altrimenti sarebbero la stessa tupla.

Le due più importanti proprietà per schemi di database sono il lossless join e la conservazione delle dipendenze e sono viste come un tutt’uno.

I risultati a cui si è giunti sono che per qualunque schema relazionale vi è una scomposizione lossless join in forma normale Boyce-Codd e una in terza forma normale che ha un lossless join e conserva anche le dipendenze. Tuttavia può non esserci una scomposizione di uno schema relazionale in forma normale Boyce-Codd che conservi le dipendenze.

Si può quindi affermare che, talvolta, la forma normale di Boyce-Codd non è raggiungibile.

Esiste un algoritmo che dato uno schema relazionale e un insieme di dipendenze funzionali trova una scomposizione lossless join per la BCNF .

Esiste un algoritmo che dato uno schema relazionale e un insieme di dipendenze funzionali trova una scomposizione lossless join che conserva le dipendenze per la 3NF (algoritmo 7.5 e teorema 7.8 pagg. 465-466 Ullman).

Spesso la non raggiungibilità della BCNF di uno schema di database può essere dovuta ad una analisi non sufficientemente accurata dell’applicazione.

Facciamo un esempio. Consideriamo la relazione in figura 3.26.

Su tale relazione possiamo supporre che siano definite le seguenti dipendenze:

· {Funzionario} - {Sede}: ogni funzionario opera presso una sede;

· {Progetto, Sede} - {Funzionario}: ogni progetto ha più responsabili, ma in sedi diverse, e ogni funzionario può essere responsabile di più progetti, però, per ogni sede, un progetto ha un solo responsabile.

La relazione non è in BCNF, perché il primo membro della dipendenza {Funzionario}-{Sede} non è superchiave. Al tempo stesso, possiamo notare come non sia possibile alcuna buona decomposizione di questa relazione; infatti, la dipendenza {Progetto, Sede} - {Funzionario} coinvolge tutti gli attributi e quindi nessuna decomposizione è in grado di conservarla.

Se però esaminiamo meglio le specifiche, possiamo arrivare alla conclusione che avremmo potuto descrivere il frammento di realtà di interesse in maniera più appropriata introducendo un ulteriore attributo Reparto, che partiziona (sulla base dei responsabili) le singole sedi, vedi figura 3.27.

Le dipendenze possono, in questo caso, essere così definite:

· {Funzionario}-{Sede, Reparto}: ogni funzionario opera presso una sede e dirige un reparto;

· {Sede, Reparto}-{Funzionario}: per ogni sede e reparto c’è un solo funzionario;

· {Progetto, Sede}-{Reparto}: per ogni sede, un progetto è assegnato ad un solo reparto (e, di conseguenza, ha un solo responsabile); la dipendenza funzionale {Progetto,Sede}-{Funzionario} è quindi ricostruibile.

Per questo schema, esiste una buona decomposizione, come mostrato dall’istanza in figura 3.28.

· la decomposizione è senza perdita, perché gli attributi comuni Sede e Reparto formano una chiave per la prima relazione;

· le dipendenze sono conservate, perché per ciascuna dipendenza esiste una relazione decomposta che ne contiene tutti gli attributi;

· entrambe le relazioni sono in BCNF, perché tutte le dipendenze hanno il primo membro costituito da una chiave.

Esiste una generalizzazione della forma normale di Boyce-Codd, che si applica a schemi di relazione con dipendenze a molti valori, e che permette di eliminare le ridondanze provocate da queste dipendenze e non eliminate dalle precedenti forme normali.

La definizione formale è data di seguito.

Sia R uno schema di relazione e D l’insieme di dipendenze applicabili a R. Diciamo che R è in quarta forma normale (Fourth Normal Form – 4NF) se ogni volta che nella chiusura di D esiste una dipendenza a molti valori X-Y, dove Y non è sottoinsieme di X e X unione Y non contiene tutti gli attributi di R, si verifica che X sia superchiave di R.

Notiamo che il significato di una superchiave (chiave) è quello di un insieme di attributi che determina funzionalmente R.

Mentre la chiusura di un insieme di dipendenze F, è l’insieme delle dipendenze funzionali logicamente implicato da F.

Si osservi che se R è in quarta forma normale, allora è anche in forma normale di Boyce-Codd, cioè la condizione di quarta forma normale è più forte della forma normale di Boyce–Codd.

La 4NF possiede una scomposizione lossless join rispetto ad un insieme di dipendenze D.

Ricapitolando, il corretto progetto di una base di dati relazionale dovrebbe partire dalla definizione dello schema derivato dall’esame della realtà di interesse, per arrivare alla definizione di uno schema logico relazionale normalizzato.

Esistono strumenti informatici detti CASE (Computer Aided Software Engineering) che aiutano l’analista in questo processo; esempio di questa classe di strumenti è Bachman della Cayenne Software Inc.

Lo schema relazionale deve essere tradotto utilizzando un RDBMS (Relational Database Management System); tra i più diffusi troviamo Oracle, Informix, DB2 e Microsoft Access.

Un RDBMS, tramite il suo DDL, permette di implementare lo schema logico attraverso la creazione di tabelle, chiavi primarie e esterne, indici, viste e così via, fa rispettare i vincoli di tupla, di dominio, di unicità, di Not Null, di integrità referenziale, ecc.

Nella pratica, nella progettazione dello schema logico, per ragioni di efficienza si deve compiere spesso un ulteriore passo detto di denormalizzazione in cui, in parziale contrasto con la teoria relazionale, si ammette una certa ridondanza dei dati in cambio di migliori prestazioni del sistema in termini di tempi di risposta.