Algoritmi di progettazione di basi di dati relazionali e …...Nella trattazione seguente, quando...

Algoritmi di progettazione di basi di dati relazionali e altre dipendenze

Nel Capitolo 11 è stata illustrata la tecnica di progettazione relazionale top-down e i relativi concetti che risultano ampiamente utilizzati negli attuali strumenti commerciali per la progettazione di basi di dati. La procedura prevede la progettazione di uno schema con-cettuale er o eer e la corrispondente traduzione in relazionale mediante un procedimen-to come quello descritto nel Capitolo 9. Le chiavi primarie sono assegnate a ogni relazio-ne sulla base delle dipendenze funzionali conosciute. Il processo successivo può essere denominato progettazione relazionale per analisi e prevede che le relazioni definite secondo l’approccio precedente o quelle ereditate da file, form o altre sorgenti precedenti vengano analizzate per identificare dipendenze funzionali indesiderate. Tali dipendenze vengono rimosse per mezzo di una successiva procedura di normalizzazione descritta nel Paragrafo 11.3 insieme con le definizioni delle relative forme normali, che permettono il miglioramento progressivo della qualità di progettazione di ogni singola relazione. Nel Paragrafo 11.3 è stato ipotizzato che le chiavi primarie fossero assegnate a ogni singola relazione, mentre nel Paragrafo 11.4 si è presentato un approccio di normalizzazione più generale in cui, per ogni relazione, venivano considerate tutte le chiavi candidate.

In questo capitolo partiremo dalla teoria delle forme normali e delle dipendenze funzionali, multivalore e di join con l’obiettivo di analizzare tre diversi punti. Per prima cosa discuteremo il concetto di inferenza di nuove dipendenze funzionali da un insieme dato e analizzeremo nuove nozioni tra cui la copertura, la copertura minimale e l’equi-valenza. Concettualmente è necessario comprendere la semantica degli attributi di una relazione in modo completo e conciso, e questo lo si può fare mediante il concetto di copertura minimale. Discuteremo quindi le proprietà desiderabili dei join non-additivi (senza perdita o lossless) e di conservazione delle dipendenze funzionali. Presenteremo un algoritmo generale per la verifica della non-additività dei join su un insieme di rela-zioni. In seguito, descriveremo un approccio relativo alla progettazione relazionale per sintesi delle dipendenze funzionali.

Si tratta di un approccio bottom-up alla progettazione in cui si ipotizza che le dipendenze funzionali conosciute tra gli insiemi di attributi dell’universo del discorso

Navathe_11OnLine.indd 1 02/04/11 10:05

2 Approfondimento Web

(UoD, universe of discourse) vengano fornite come input. Introdurremo algoritmi che permettono di ottenere le forme normali auspicabili, cioè la 3NF e la bCNF, e una o entrambe le proprietà di non-additività dei join e di conservazione delle dipendenze funzionali. Sebbene l’approccio per sintesi si riveli interessante come approccio forma-le, esso non viene impiegato nella pratica per la progettazione di basi di dati di grandi dimensioni a causa della difficoltà di fornire tutte le possibili dipendenze funzionali prima di cominciare la progettazione. Invece, seguendo l’approccio presentato nel Capi-tolo 11, le decomposizioni successive e i raffinamenti progressivi dello schema sono più gestibili e possono evolvere nel tempo. L’obiettivo finale di questo capitolo è discutere ulteriormente la nozione di dipendenza funzionale multivalore (MVD) introdotta nel Capitolo 11 e trattare brevemente gli altri tipi di dipendenze che sono state identificate.

Nel Paragrafo 1 vedremo le regole di inferenza per le unzionali e le useremo per illustrare i concetti di copertura, equivalenza e copertura minimale tra dipendenze fun-zionali. Nel Paragrafo 2 descriveremo prima le due auspicabili proprietà delle decom-posizioni, cioè la proprietà di conservazione delle dipendenze e la proprietà di join senza perdita, entrambe utilizzate dagli algoritmi di progettazione per ottenere delle decompo-sizioni auspicabili. È bene notare che per le forme normali superiori come la 2NF, la 3NF e la bCNF, non è sufficiente verificare gli schemi di relazione in modo indipenden-te l’uno dall’altro. Affinché si possa parlare di uno schema relazionale di buona qualità, le relazioni risultanti devono soddisfare collettivamente queste due ulteriori proprietà. Nel Paragrafo 3 tratteremo lo sviluppo di algoritmi di progettazione relazionale che iniziano con uno schema di relazione molto ampio chiamato relazione universale, ovvero un’ipotetica relazione contenente tutti gli attributi di interesse. Questa relazione viene decomposta (o, in altre parole, le dipendenze funzionali date vengono sintetizzate) in relazioni che soddisfano una certa forma normale come la 3NF o la bCNF e che soddisfano anche una o entrambe le proprietà auspicabili.

Nel Paragrafo 5 viene introdotto il concetto di dipendenza multivalore (MVD) segui-to dalle nozioni di inferenza ed equivalenza applicate alle MVD. Infine, nel Paragrafo 6 completeremo la discussione sulle dipendenze tra i dati introducendo le dipendenze di inclusione e le dipendenze modello. Le dipendenze di inclusione possono rappresentare vincoli di integrità referenziale e vincoli di classe/sottoclasse tra relazioni. Le dipenden-ze modello sono un modo per rappresentare qualunque vincolo generalizzato sugli attributi. Discuteremo inoltre alcune situazioni in cui, per stabilire e verificare una dipendenza funzionale tra attributi, è necessario definire una procedura o una funzione. Infine, discuteremo brevemente la forma normale dominio-chiave (DKNF, domain-key normal form), considerata la forma normale più generale.

1. Argomenti ulteriori sulle dipendenze funzionali: regole di inferenza, equivalenza e copertura minimale

Nel Paragrafo 11.2 (Capitolo 11) abbiamo introdotto il concetto di dipendenza funzio-nale (DF), l’abbiamo illustrata con alcuni esempi e definito una notazione per denotare DF multiple su una singola relazione. Abbiamo identificato e discusso le problematiche


Algoritmi di progettazione di basi di dati relazionali e altre dipendenze 3

relative alle dipendenze funzionali nei Paragrafi 11.3 e 11.4, mostrando come queste possono essere eliminate mediante una decomposizione appropriata della relazione. Nel Paragrafo 11.3 questo procedimento è stato descritto come normalizzazione e abbiamo mostrato come ottenere forme normali dalla prima alla terza (da 1NF a 3NF) partendo da chiavi primarie date. Nei Paragrafi 15.4 e 15.5 abbiamo illustrato alcuni test genera-lizzati per 2NF, 3NF e bCNF dato un qualunque numero di chiavi candidate in una relazione e abbiamo mostrato come ottenere queste forme normali. Ora torniamo allo studio delle dipendenze funzionali e mostriamo com’è possibile inferire nuove dipen-denze a partire da un insieme dato, discutendo i concetti di chiusura, equivalenza e copertura minimale che saranno necessari più avanti, quando illustreremo un approccio alla progettazione relazionale per sintesi dato un insieme di DF.

Regole di inferenza per dipendenze funzionaliSi indichi con F l’insieme di dipendenze funzionali specificate sullo schema di relazio-ne R. Generalmente il progettista dello schema specifica le dipendenze funzionali semanticamente evidenti; di solito, però, sussistono molte altre dipendenze funzionali in tutte le istanze di relazione valide che soddisfano le dipendenze in F. Queste altre dipen-denze possono essere inferite o dedotte dalle dipendenze funzionali presenti in F.

Per esempi tratti dalla vita reale è praticamente impossibile specificare tutte le dipen-denze funzionali che possono sussistere per la situazione data. Ad esempio, se ogni dipartimento ha un solo direttore, in modo che N_DIP determina univocamente SSN_DIRETTORE (N_DIP → SSN_DIR) e un Direttore ha un unico numero di telefono chia-mato TELEFONO_DIR (SSN_DIR → TELEFONO_DIR), queste due dipendenze insieme implicano la dipendenza N_DIP → TELEFONO_DIR. Questa è una DF inferita e non deve essere esplicitamente dichiarata in aggiunta alle due DF date. Formalmente, quindi, è utile definire il concetto di chiusura che comprende tutte le possibili dipendenze dedu-cibili dall’insieme F dato.

Definizione. Convenzionalmente, l’insieme di tutte le dipendenze formato da F e da tutte le dipendenze che possono essere dedotte da F è chiamato chiusura di F ed è indi-cato con F+.

Si supponga ad esempio di specificare il seguente insieme F di dipendenze funzio-nali ovvie sullo schema di relazione della Figura 11.3(a) (Capitolo 11):

F = {SSN → {NOME_I, DATA_N, INDIRIZZO, NUMERO_D},

NUMERO_D → {NOME_D, SSN_DIR_DIP} }

Alcune dipendenze funzionali che possiamo inferire da F sono le seguenti:

SSN → {NOME_D, SSN_DIR_DIP}

SSN → SSN

NUMERO_D → NOME_D

Una DF X → Y è inferita da un insieme di dipendenze F specificate su R se X → Y sussiste in ogni stato di relazione r di R; cioè ogni volta che r soddisfa tutte le dipenden-ze in F, in r sussiste anche X → Y. La chiusura F+ di F è l’insieme di tutte le dipenden-



ze funzionali che possono essere dedotte da F. Per determinare un modo sistematico per inferire dipendenze, occorre trovare un insieme di regole di inferenza che possono essere usate per inferire nuove dipendenze a partire da un insieme dato di dipendenze. Ora si considereranno alcune di queste regole di inferenza. Verrà usata la notazione F |= X→Y per indicare che la dipendenza funzionale X → Y è inferita dall’insieme di dipendenze funzionali F.

Nella trattazione seguente, quando verranno esaminate le dipendenze funzionali, si userà una notazione abbreviata. Le variabili di attributo verranno concatenate e le virgo-le omesse per comodità. Perciò la DF {X,Y} → Z è abbreviata in XY → Z, e la DF {X,Y,Z} → {U,V} è abbreviata in XYZ → UV. Le seguenti sei regole, da RI1 a RI6, sono note regole di inferenza per dipendenze funzionali:

RI1 (regola riflessiva)1: se X $ Y, allora X → Y;

RI2 (regola di arricchimento)2: {X → Y} |= XZ → YZ;

RI3 (regola transitiva): {X → Y, Y → Z} |= X → Z;

RI4 (regola di decomposizione, o di proiezione): {X → YZ} |= X → Y;

RI5 (regola di unione, o additiva): {X → Y, X → Z} |= X → YZ;

RI6 (regola pseudo-transitiva): {X → Y, WY → Z} |= WX → Z.

La regola riflessiva (RI1) afferma che un insieme di attributi determina sempre se stesso o uno qualsiasi dei suoi sottoinsiemi, il che è ovvio. Dato che RI1 genera dipendenze che sono sempre vere, tali dipendenze sono dette banali. Formalmente una dipendenza fun-zionale X → Y è banale se X $ Y; altrimenti è non-banale. La regola di arricchimento (RI2) sostiene che aggiungendo lo stesso insieme di attributi alla parte sinistra e alla parte destra di una dipendenza si ottiene un’altra dipendenza valida. Secondo la RI3 le dipendenze funzionali sono transitive. La regola di decomposizione (RI4) sostiene che si possono rimuovere attributi dalla parte destra di una dipendenza; l’applicazione ripetuta di questa regola può decomporre la DF X → {A1, A2, ... An} nell’insieme di dipendenze {X → A1, X → A2, ... X → An}. La regola di unione (RI5) consente di fare l’opposto: è possibile combinare un insieme di dipendenze {X → A1, X → A2, ... X → An} nella sin-gola DF X → {A1, A2, ... An}.

Un’avvertenza importante riguarda l’uso di queste regole. Anche se X → A e X → B implicano X → AB per la regola di unione dichiarata precedentemente, X → A, e Y → B non implica che XY → AB. Inoltre XY → A non implica necessariamente X → A o Y → A.

Ognuna delle precedenti regole di inferenza può essere dimostrata a partire dalla definizione di dipendenza funzionale, con prova diretta o per assurdo. Una prova per assurdo suppone che la regola non valga e mostra che ciò porta a una contraddizione. Verrà ora dimostrato che le prime tre regole, da RI1 a RI3, sono valide. La seconda prova è per assurdo.

1 La regola riflessiva può anche essere enunciata come X → X, ossia ogni insieme di attributi determina funzionalmente se stesso.2 La regola di arricchimento può anche essere enunciata come {X → Y} |= XZ → Y, ossia l’arricchimento degli attributi di parte sinistra di una DF produce un’altra DF valida.



PROVA DI RI1 Si supponga che X $ Y e che esistano due tuple t1 e t2 in una certa istanza di relazione r di R tali che t1[X] = t2[X]. Allora t1[Y] = t2[Y] perché X $ Y; perciò in r deve valere X → Y.

PROVA DI RI2 (PER ASSURDO)� Si supponga che in un’istanza di relazione r di R valga la X → Y, ma che non valga la XZ → YZ. Devono perciò esistere due tuple t1 e t2 in r tali che (1) t1[X] = t2[X], (2) t1[Y] = t2[Y], (3) t1[XZ] = t2[XZ], e (4) t1[YZ] ≠ t2[YZ]. Ciò non è possibile, perché da (1) e (3) si deduce (5) t1[Z] = t2[Z], e da (2) e (5) si dedu-ce (6) t1[YZ] = t2[YZ], contraddicendo (4).

PROVA DI RI3� Si supponga che in una relazione r sussistano sia (1) X → Y sia (2) Y → Z. Allora, per ogni coppia di tuple t1 e t2 in r tali che t1[X] = t2[X], si deve avere (3) t1[Y] = t2[Y], dall’ipotesi (1); perciò occorre anche avere (4) t1[Z] = t2[Z], dalla (3) e dall’ipotesi (2); quindi in r deve valere la X → Z.

Usando argomentazioni simili è possibile provare le regole di inferenza da RI4 a RI6 e ogni altra regola di inferenza valida. Però un modo più semplice per dimostrare che una regola di inferenza per dipendenze funzionali è valida consiste nel provarla usando regole di inferenza che sono già state dimostrate valide. Ad esempio si può provare le regole da RI4 a RI6 usando le regole da RI1 a RI3 come segue.

PROVA DI RI4 (USANDO DA RI1 A RI3�)�

1. X → YZ (data).

2. YZ → Y (usando RI1 e sapendo che YZ $ Y).

3. X → Y (usando RI3 su 1 e 2).


1. X → Y (data).

2. X → Z (data).

3. X → XY (usando RI2 su 1 arricchendo con X; si noti che XX = X).

4. XY → YZ (usando RI2 su 2 arricchendo con Y).

5. X → YZ (usando RI3 su 3 e 4).


1. X → Y (data).

2. WY → Z (data).

3. WX → WY (usando RI2 su 1 arricchendo con W).

4. WX → Z (usando RI3 su 3 e 2).

È stato dimostrato da Armstrong (1974) che le regole di inferenza da RI1 a RI3 sono corrette e complete. Per corrette si intende che, dato un insieme di dipendenze funzio-



nali F specificate su uno schema di relazione R, tutte le dipendenze che è possibile inferire da F usando le regole da RI1 a RI3 sussistono in ogni stato di relazione r di R che soddisfa le dipendenze in F. Per complete si intende che, usando ripetutamente le regole da RI1 a RI3 per inferire dipendenze finché non se ne possono più dedurre, si ottiene come risultato l’insieme completo di tutte le possibili dipendenze che possono essere dedotte da F. In altre parole, l’insieme di dipendenze F+, che è stato detto chiu-sura di F, può essere determinato da F usando solo le regole di inferenza da RI1 a RI3. Le regole di inferenza da RI1 a RI3 sono note come regole di inferenza di Armstrong.3

Generalmente i progettisti di basi di dati specificano dapprima l’insieme F delle dipendenze funzionali che possono essere facilmente determinate dalla semantica degli attributi di R; poi usano RI1, RI2 e RI3 per inferire ulteriori dipendenze funzionali, le quali saranno pure valide su R. Un modo sistematico per determinare queste dipendenze funzionali aggiuntive è quello di determinare prima di tutto ogni insieme X di attributi che appare come parte sinistra di qualche dipendenza funzionale in F, e poi di determi-nare l’insieme di tutti gli attributi che sono dipendenti da X.

Definizione. Per ogni insieme X di attributi di questo tipo, si calcola l’insieme X+ di attributi che sono determinati funzionalmente da X sulla base di F; X+ è detto chiusura di X rispetto a F. Per calcolare X+ si può usare l’Algoritmo 1.

Algoritmo 1. Determinazione di X+, chiusura di X rispetto a F.

X+ := X;repeat oldX+ := X+; for ogni dipendenza funzionale Y → Z in F do if X+ $ Y then X+ := X+ ∪ Z;until (X+ = oldX+);

Tale algoritmo inizia ponendo X+ uguale a tutti gli attributi in X. Da RI1 è noto che tutti questi attributi sono funzionalmente dipendenti da X. Servendosi delle regole di inferen-za RI3 e RI4 si aggiungono attributi a X+, usando tutte le dipendenze funzionali in F. Si continuano a considerare tutte le dipendenze in F (il ciclo repeat) finché non vengono più aggiunti attributi a X+ durante un ciclo completo (il ciclo for) sulle dipendenze in F. Ad esempio si consideri lo schema di relazione IMP_PROG della Figura 11.3(b) (Capi-tolo 11); dalla semantica degli attributi è possibile specificare il seguente insieme F di dipendenze funzionali che devono valere su IMP_PROG:

F = { SSN → NOME_I,

NUMERO_P → { NOME_P, SEDE_P},

{ SSN, NUMERO_P} → ORE}

3 A dire il vero, sono note come assiomi di Armstrong. Però, in senso matematico stretto, gli assiomi (fatti dati) sono le dipendenze funzionali in F, dato che si suppone che esse siano corrette, mentre le regole da rI1 a rI3 sono le regole di inferenza per inferire nuove dipendenze funzionali (nuovi fatti).



Usando l’Algoritmo 1 si possono calcolare i seguenti insiemi chiusura rispetto a F:

{ SSN} + = { SSN, NOME_I}

{ NUMERO_P} + = { NUMERO_P, NOME_P, SEDE_P}

{ SSN, NUMERO_P} + = { SSN, NUMERO_P, NOME_I, NOME_P, SEDE_P, ORE}

Intuitivamente, l’insieme di attributi nella parte destra di ogni riga rappresenta tutti gli attributi che dipendono funzionalmente dall’insieme di attributi nella parte sinistra, in base all’insieme F dato.

Equivalenza di insiemi di dipendenze funzionaliVediamo ora l’equivalenza di due insiemi di dipendenze funzionali. Innanzitutto diamo alcune definizioni preliminari.

Definizione. Si dice che un insieme F di dipendenze funzionali copre un altro insieme E di dipendenze funzionali, se ogni DF in E è presente anche in F+, cioè se ogni dipen-denza in E può essere inferita a partire da F; in alternativa possiamo dire che E è coper-to da F.

Definizione. Due insiemi E e F di dipendenze funzionali sono equivalenti se E+ = F+. Perciò l’equivalenza implica che ogni DF in E possa essere inferita da F, e ogni DF in F possa essere inferita da E; ossia E è equivalente a F se sussistono entrambe le condi-zioni E copre F e F copre E.

Si può determinare se F copre E calcolando X+ rispetto a F per ogni DF X → Y in E, e quindi verificando se questo X+ comprende gli attributi presenti in Y. Se è così per ogni DF in E, allora F copre E. Si determina se E e F sono equivalenti verificando se E copre F e F copre E.

Insiemi minimali di dipendenze funzionaliInformalmente, una copertura minimale di un insieme E di dipendenze funzionali è un insieme F di dipendenze funzionali che soddisfa la proprietà che ogni dipendenza in E è presente nella chiusura F+ di F. Inoltre questa proprietà si perde rimuovendo una dipendenza dall’insieme F; F non deve quindi contenere alcuna ridondanza e le dipen-denze in E devono essere in forma standard. Per soddisfare queste proprietà, possiamo stabilire formalmente che un insieme F di dipendenze funzionali è minimale se soddisfa le seguenti condizioni:

1. ogni dipendenza presente in F ha come parte destra un solo attributo;

2. non è mai possibile sostituire una dipendenza X → A di F con una dipendenza Y → A, dove Y è un sottoinsieme proprio di X, e avere ancora un insieme di dipen-denze equivalente a F;

3. non è mai possibile rimuovere una dipendenza da F e avere ancora un insieme di dipendenze equivalente a F.



Si può pensare a un insieme minimale di dipendenze come a un insieme di dipendenze in una forma standard o canonica e senza ridondanze. La condizione 1 assicura che ogni dipendenza si presenti in una forma canonica con un solo attributo nella parte destra.4 Le condizioni 2 e 3 assicurano che non ci siano ridondanze nelle dipendenze o per la presen-za di attributi ridondanti nella parte sinistra di una dipendenza (condizione 2) o per la presenza di una dipendenza che può essere inferita dalle altre DF in F (condizione 3).

Definizione. Una copertura minimale di un insieme E di dipendenze funzionali è un insieme minimale F di dipendenze che è equivalente a E. Possono esserci più coperture minimali per un dato insieme di dipendenze funzionali. Usando l’Algoritmo 2 si può sem-pre trovare almeno una copertura minimale F per qualunque insieme E di dipendenze.

Se parecchi insiemi di DF risultano essere coperture minimali di E sulla base della definizione precedente, è comune usare ulteriori criteri per la “minimalità”. Ad esempio si può scegliere l’insieme minimale sulla base del numero minimo di dipendenze oppure sulla base della lunghezza totale plain (la lunghezza totale di un insieme di dipendenze viene calcolata concatenando le dipendenze e trattandole come una lunga stringa di caratteri).

Algoritmo 2. Ricerca di una copertura minimale F per un insieme E di dipendenze funzionali.

1. Si imposti F := E.2. Si sostituisca ogni dipendenza funzionale X → { A1, A2, ..., An} in F con le n dipendenze

funzionali X → A1, X → A2, ..., X → An.3. Per ogni dipendenza funzionale X → A in F per ogni attributo B che è un elemento di X se { {F – {X → A} } ∪ { (X – {B} ) → A} } è equivalente a F, allora si sostituisca X → A con (X – {B} ) → A in F.4. Per ogni dipendenza funzionale rimanente X → A in F se {F – {X → A} } è equivalente a F, allora si rimuova X → A da F.

Illustriamo il precedente algoritmo con il seguente esempio.Sia dato E : {B → A, D → A, AB → D} come insieme di dipendenze funzionali.

Dobbiamo trovare la copertura minimale di E.

• Tutte le precedenti dipendenze sono in forma canonica; quindi il primo passo dell’Algoritmo 2 è completato e possiamo procedere con il secondo. Nel secondo passo dobbiamo determinare se AB → D contiene attributi ridondanti nella parte sinistra, cioè se la dipendenza è sostituibile da B → D o A → D.

• Poiché B → A, aggiungendo B da entrambe le parti della dipendenza (RI2), otteniamo BB → AB, cioè B → AB (i). Tuttavia abbiamo che AB → D come stabilito in (ii).

4 Questa è la forma standard per semplificare le condizioni e gli algoritmi che garantiscono che non esiste alcuna ridondanza in F. Usando la regola di inferenza rI4, si può convertire una singola dipendenza con più attributi nella parte destra in un insieme di dipendenze con singoli attributi nella parte destra.



• Per la regola transitiva (RI3), da (i) e (ii) otteniamo B → D. Dunque possiamo sosti-tuire AB → D con B → D.

• In questo modo, otteniamo un insieme Eʹ equivalente a quello E di partenza, così composto Eʹ : {B → A, D → A, B → D}. Poiché tutte le dipendenze funzionali hanno un singolo attributo nella parte sinistra non sono possibili ulteriori riduzioni nel secondo passo.

• Nel passo 3 verifichiamo la presenza in Eʹ di eventuali dipendenze funzionali ridon-danti. Applicando la regola transitiva su B → D e D → A deriviamo B → A. Dunque B → A è ridondante in Eʹ e può essere eliminata.

• Abbiamo quindi che la copertura minima di E è {B → D, D → A}.

2. Proprietà delle decomposizioni relazionaliConsideriamo il procedimento di decomposizione che è stato utilizzato in tutto il Capi-tolo 11 per decomporre relazioni ed eliminare dipendenze indesiderate ottenendo così forme normali superiori.

Decomposizione delle relazioni e insufficienza delle forme normaliGli algoritmi di progettazione di basi di dati relazionali che presenteremo qui prendono inizio da un unico schema di relazione universale R = {A1, A2, ..., An

} contenente tutti gli attributi della base di dati. Si farà implicitamente l’ipotesi di relazione universale, la quale stabilisce che ogni nome di attributo sia unico. L’insieme F di dipendenze fun-zionali che deve sussistere sugli attributi di R è specificato dai progettisti della base di dati ed è fornito agli algoritmi di progettazione. basandosi sulle dipendenze funzionali, gli algoritmi decompongono lo schema di relazione universale R in un insieme di sche-mi di relazione D = {R1, R2, ..., Rm

} che diventerà lo schema della base di dati relazio-nale; D è detto decomposizione di R.

È necessario assicurarsi che ogni attributo presente in R sia anche presente in almeno uno schema di relazione R

i nella decomposizione, così che non ci siano attributi “persi”;

formalmente si ha

m

∪i=1

Ri = R

Questa condizione è detta condizione di conservazione degli attributi di una decompo-sizione.

Un altro obiettivo è quello che ogni singola relazione Ri nella decomposizione D sia

in bCNF o in 3NF. Questa condizione non è però sufficiente a garantire di per sé una buona progettazione di basi di dati. Occorre infatti considerare la decomposizione nel complesso, oltre a esaminare le singole relazioni. Per illustrare questo punto, si conside-ri la relazione IMP_SEDI(NOME_I, SEDE_P) della Figura 11.5 (Capitolo 11), che è sia in



3NF sia in bCNF. In realtà ogni schema di relazione con due soli attributi è automatica-mente in bCNF.5 Anche se IMP_SEDI è in bCNF, essa dà comunque origine a tuple spurie quando viene unita tramite join con IMP_PROG1(SSN, NUMERO_P, ORE, NOME_P, SEDE_P), che non è in bCNF (si veda il risultato del join naturale nella Figu-ra 11.6). IMP_SEDI rappresenta perciò uno schema di relazione particolarmente mal definito, a causa della sua semantica contorta in cui SEDE_P fornisce la sede di uno dei progetti sui quali lavora un impiegato. L’unione tramite join di IMP_SEDI con PROGETTO(NOME_P, NUMERO_P, SEDE_P, NUM_D) della Figura 11.2 – che è in bCNF – dà pure origine a tuple spurie. Ciò evidenzia la necessità di altri criteri che, insieme con le condizioni di 3NF o bCNF, evitino progetti di cattiva qualità di questo tipo. Nei tre sottoparagrafi seguenti verranno esaminate le condizioni aggiuntive che devono sussistere su una decomposizione D considerata nel suo insieme.

Proprietà di conservazione delle dipendenze di una decomposizioneSarebbe utile che ogni dipendenza funzionale X → Y specificata in F apparisse direttamen-te in uno degli schemi di relazione R

i della decomposizione D, oppure potesse essere

inferita dalle dipendenze presenti in qualche Ri. Informalmente, quella enunciata è la con-

dizione di conservazione delle dipendenze: si desidera conservare le dipendenze perché ogni dipendenza in F rappresenta un vincolo sulla base di dati. Se una delle dipendenze non è rappresentata in una singola relazione R

i della decomposizione, non è possibile

imporre questo vincolo considerando una sola relazione; occorre piuttosto unire tramite join due o più relazioni della decomposizione e quindi verificare che nel risultato dell’ope-razione di JOIN sussistano le dipendenze funzionali.

Non è necessario che le dipendenze specificate in F si presentino esattamente nelle singole relazioni della decomposizione D. È sufficiente che l’unione delle dipendenze che sussistono sulle singole relazioni in D siano equivalenti a F. Si darà ora definizione formale di questi concetti.

Definizione. Dato un insieme di dipendenze F su R, la proiezione di F su Ri, denotata

con pRi

(F), dove Ri è un sottoinsieme di R, è l’insieme di dipendenze X → Y di F+ tali che gli attributi di X ∪ Y siano tutti contenuti in R

i. Perciò la proiezione di F su ogni schema di relazione R

i della decomposizione D è l’insieme delle dipendenze funzionali in F+, chiusura di F, tali che tutti i loro attributi di parte sinistra e di parte destra siano in R

i. Si dirà che una decomposizione D = {R1, R2, ..., Rm} di R conserva le dipendenze rispetto a F se l’unione delle proiezioni di F su ogni R

i in D è equivalente a F; cioè

((pR1

(F)) ∪ ... ∪ (pRm(F)))+ = F+

Se una decomposizione non conserva le dipendenze, qualche dipendenza viene persa nella decomposizione. Come detto prima, per verificare se una dipendenza persa sussiste comunque, occorre effettuare il JOIN di due o più relazioni presenti nella decomposizio-ne, fino a ottenere una relazione che presenti tutti gli attributi di parte sinistra e di parte

5 Il lettore è invitato a dimostrare, per esercizio, questa affermazione.



destra della dipendenza persa, e quindi verificare se nel risultato del JOIN sussiste la dipendenza, il che si presenta come un’opzione poco pratica.

Un esempio di decomposizione che non conserva le dipendenze è presentato nella Figura 11.12(a), in cui la dipendenza funzionale DF2 è persa quando LOTTI1A viene decomposta in {LOTTI1AX, LOTTI1AY}. Le decomposizioni della Figura 11.11, invece, conservano le dipendenze. Analogamente, per l’esempio nella Figura 11.13, indipenden-temente da quale delle tre decomposizioni mostrate venga scelta per la relazione INSEGNA(STUDENTE, INSEGNAMENTO, DOCENTE), una o entrambe le dipendenze originariamente presenti vengono perse. Si enuncia qui una proposizione relativa a tale proprietà senza darne la dimostrazione.

Proposizione 1. È sempre possibile trovare una decomposizione D che conserva le dipendenze rispetto a F e tale che ogni relazione R

i di D sia in 3NF.

Più avanti descriveremo l’Algoritmo 3, che crea, a partire da un insieme di dipendenze funzionali F, una decomposizione D = {R1, R2, ..., Rm

} di una relazione universale R, che conserva le dipendenze e tale che ogni R

i di D sia in 3NF.

Proprietà di join non-additivo (senza perdita)� di una decomposizioneUn’altra proprietà che una decomposizione D deve soddisfare è quella di join senza perdita o join non-additivo, che assicura che non vengano generate tuple spurie quando alle relazioni della decomposizione viene applicata un’operazione di JOIN NATURALE. Il problema è già stato illustrato nel Sottoparagrafo 11.1.4 (Capitolo 11) con l’esempio delle Figure 11.5 e 11.6. Dato che si tratta della proprietà di una decomposizione di schemi di relazione, la condizione di assenza di tuple spurie deve sussistere per ogni stato valido di relazione, cioè per ogni stato di relazione che soddisfa le dipendenze funzionali in F. La proprietà di join senza perdita è perciò sempre definita rispetto a un insieme specifico F di dipendenze.

Definizione. Formalmente, una decomposizione D = {R1, R2, ..., Rm} di R soddisfa la

proprietà di join senza perdita (non-additivo) rispetto all’insieme di dipendenze F di R se, per ogni stato di relazione r di R che soddisfa F, sussiste quanto segue, dove * è il JOIN NATURALE di tutte le relazioni in D:

*(pR1

(r), ..., pRm

(r)) = r

La parola perdita in senza perdita si riferisce a perdita di informazione, non a perdita di tuple. Se una decomposizione non soddisfa la proprietà di join senza perdita, è possibi-le che si presentino tuple spurie aggiuntive, dopo che sono state eseguite le operazioni di PROIEZIONE (p) e di JOIN NATURALE (*); queste tuple aggiuntive rappresentano un’informazione errata. Si preferisce qui la locuzione join non-additivo perché essa descrive più fedelmente la situazione. Sebbene il termine join senza perdita sia molto popolare in letteratura, d’ora in avanti useremo il termine join non-additivo, poiché risulta auto-esplicativo e non ambiguo. La proprietà di join non-additivo assicura che



non verranno generate tuple spurie nel risultato dell’esecuzione delle operazioni di PRO-IEZIONE e JOIN. A volte potremo comunque usare il termine schema lossy (con perdi-te) per indicare uno schema contenente perdite di informazione (Algoritmo 4).

Ovviamente la decomposizione di IMP_PROG(SSN, NUMERO_P, ORE, NOME_I, NOME_P, SEDE_P), della Figura 11.3, in IMP_SEDI(NOME_I, SEDE_P) e IMP_PROG1(SSN, NUMERO_P, ORE, NOME_P, SEDE_P), presente nella Figura 11.5, non soddisfa la proprietà di join non-additivo, come illustrato nella Figura 11.6. Per verifi-care se una decomposizione D di una relazione in n relazioni soddisfa la proprietà di join non-additivo rispetto a un insieme F di dipendenze funzionali date per la relazione use-remo una procedura generale, presentata nel seguente Algoritmo 3. Come vedremo più avanti, per verificare la proprietà di join senza perdita nel caso di decomposizioni bina-rie si può usare invece un test più semplice.

Algoritmo 3� Verifica della proprietà di join non-additivo.

Input. Una relazione universale R, una decomposizione D = {R1, R2, ..., Rm} di R, e un insieme F di dipendenze funzionali.

Nota: al termine di alcuni passi sono riportati commenti esplicativi nel seguente formato: (* commento *).

1. Si costruisca una matrice iniziale S con una riga i per ogni relazione Ri di D, e una colonna j per ogni attributo Aj di R.

2. Si ponga S(i, j) := bij per ogni elemento della matrice. (* ogni bij è un simbolo distinto associato agli indici (i, j) *)3. Per ogni riga i che rappresenta lo schema di relazione Ri

{ per ogni colonna j che rappresenta l’attributo Aj

{ se (la relazione Ri contiene l’attributo Aj) allora si ponga S(i, j) := aJ;} ;}; (* ogni aj è un simbolo distinto associato all’indice (j) *)4. Si ripeta il ciclo seguente finché l’esecuzione di un ciclo completo non dà luogo ad alcun

cambiamento in S { per ogni dipendenza funzionale X → Y in F { per tutte le righe di S che presentano gli stessi simboli nelle colonne corrispondenti

ad attributi presenti in X { si faccia sì che i simboli in ogni colonna corrispondente a un attributo di Y

siano gli stessi per tutte queste righe nel modo seguente: se una riga presenta un simbolo “a” in quella colonna, allora si pongano le altre righe uguali, nella colonna, allo stesso simbolo “a”. Se non esiste alcun simbolo “a” per l’attributo in alcuna riga, si scelga per l’attributo uno dei simboli “b” presenti in una delle righe e si ponga nelle altre righe lo stesso simbolo “b” per quella colonna;} ;} ;} ;

5. Se una riga è costituita per intero di simboli “a”, allora la decomposizione ha la proprietà di join non-additivo; altrimenti non ha questa proprietà.

Data una relazione R che è decomposta in un certo numero di relazioni R1,R2, ..., Rm, l’Algoritmo 3 definisce la matrice S che rappresenta uno stato di relazione r di R.

La riga i in S rappresenta una tupla ti (relativa alla relazione Ri) che ha simboli “a” nelle

colonne corrispondenti agli attributi di Ri e simboli “b” nelle altre colonne. L’algoritmo



quindi trasforma le righe di questa matrice (durante il ciclo del passo 4) in modo tale che esse rappresentino tuple che soddisfano tutte le dipendenze funzionali in F. Al termine del passo 4, ogni coppia di righe in S – che rappresentano due tuple di r – che si accordano sui valori degli attributi di parte sinistra X di una dipendenza funzionale X → Y di F, si accor-deranno anche sui valori degli attributi di parte destra Y. Si può dimostrare che se, dopo aver applicato il ciclo del passo 4, una qualsiasi riga di S termina con tutti simboli “a”, allora la decomposizione D soddisfa la proprietà di join non-additivo rispetto a F.

Se, d’altro lato, nessuna riga ha alla fine tutti simboli “a”, allora D non soddisfa la proprietà di join non-additivo. In quest’ultimo caso lo stato di relazione r rappresentato da S alla fine dell’algoritmo sarà un esempio di stato di relazione r di R che soddisfa le dipendenze in F, ma non soddisfa la condizione di join non-additivo; perciò questa rela-zione serve come controesempio che p250rova che D non ha la proprietà di join non-additivo rispetto a F. Si noti che i simboli “a” e “b” alla fine dell’algoritmo non hanno alcun significato particolare.

La Figura 1(a) mostra come si applica l’Algoritmo 3 alla decomposizione dello schema di relazione IMP_PROG della Figura 11.3(b) nei due schemi di relazione IMP_PROG1 e IMP_SEDI della Figura 11.5(a). Il ciclo al passo 4 dell’algoritmo non può cambiare alcun simbolo “b” in un simbolo “a”; perciò la matrice S risultante non ha una riga di soli sim-boli “a”, e quindi la decomposizione non gode della proprietà di join non-additivo.

La Figura 1(b) mostra un’altra decomposizione di IMP_PROG (in IMP, PROGETTO e LAVORA_SU) che gode della proprietà di join non-additivo, e la Figura 1(c) mostra come si può applicare l’algoritmo a questa decomposizione. Una volta che una riga consista solo di simboli “a”, si sa che la decomposizione gode della proprietà di join non-additivo, ed è possibile smettere di applicare le dipendenze funzionali (passo 4 dell’algoritmo) alla matrice S.

Verifica della proprietà di join non-additivo su decomposizioni binarieL’Algoritmo 3 ci consente di controllare se una specifica decomposizione D in n rela-zioni soddisfa la proprietà di join non-additivo rispetto a un insieme F di dipendenze funzionali. esiste un caso speciale di decomposizione chiamata decomposizione bina-ria, che consiste nella decomposizione di una relazione R in due relazioni. A questo proposito vedremo un test più semplice da applicare dell’Algoritmo 3, ma che è limita-to alle sole decomposizioni binarie.

Proprietà NJB (test di join non-additivo per decomposizioni binarie)� Una decomposizione D = {R1, R2} di R soddisfa la proprietà di join non-additivo rispetto a un insieme di dipendenze funzionali F di R se e solo se

• la DF ((R1 ∩ R2) → (R1 – R2)) è in F+, oppure

• la DF ((R1 ∩ R2) → (R2 – R1)) è in F+.

Si verifichi come questa proprietà sussista nei nostri esempi informali di normalizzazio-ne successiva dei Paragrafi 11.3 e 11.4 (Capitolo 11).

Nel Paragrafo 11.5 abbiamo decomposto LOTTI1A in due relazioni bCNF chiamate LOTTI1AX e LOTTI1AY e abbiamo decomposto la relazione INSEGNA della Figura 11.14



b11

b13

b14

a5

b16

a2

a1

a3

a4

a5

a6

b22

a1

b13

b14

b15

b16

a2

b21

a3

a4

a5

b26

b22

a1

a3 b34

b35

a6

b32

a1

b13

b14

b15

b16

a2

b21

a3

a4

a5

b26

b22

a1

a3

b34

b35

a6

b32

a2

a4 5

a

D={R1, R2}

D={R1, R2, R3}

(a)

(b)

(c)

R={SSN, NOME_I, NUMERO_P, NOME_P, SEDE_P, ORE}R1=IMP_SEDI={NOME_I, SEDE_P}R2=IMP_PROG1={SSN, NUMERO_P, ORE, NOME_P, SEDE_P}

R={SSN, NOME_I, NUMERO_P, NOME_P, SEDE_P, ORE}R1=IMP={SSN, NOME_I}R2=PROG={NUMERO_P, NOME_P, SEDE_P}R3=LAVORA_SU={SSN, NUMERO_P, ORE}

F={SSN�NOME_I;NUMERO_P�{NOME_P, SEDE_P}; {SSN,NUMERO_P}�ORE}

F={SSN�NOME_I;NUMERO_P�{NOME_P, SEDE_P}; {SSN,NUMERO_P}�ORE}

(nessun cambiamento alla matrice dopo aver applicato le dipendenze funzionali)

(matrice originale S all’inizio dell’algoritmo)

(matrice S dopo l’applicazione delle prime due dipendenze funzionali –l’ultima riga è costituita da tutti simboli “a”, e pertanto ci fermiamo)

SSN

IMP PROGETTO LAVORA_SU

NOME_I NUMERO_P NOME_P SEDE_P ORE

SSN NOME_I NUMERO_P NOME_P SEDE_P ORE

SSN NOME_I NUMERO_P NOME_P SEDE_P ORE

SSN SSNNOME_I NUMERO_P NUMERO_PNOME_P SEDE_P ORE

R1

R2

R1

R2

R3

R1

R2

R3

Figura 1 Test di join non-additivo per le decomposizioni n-arie. (a) Caso 1: la decomposizione di IMP_PROG in IMP_PROG1 e SEDI_IMP non soddisfa il test. (b) Una decomposizione di IMP_PROG che verifica la proprietà di join non-additivo. (c) Caso 2: la decomposizione di IMP_PROG in IMP, PROGETTO e LAVORA_SU soddisfa il test.



nelle due relazioni {DOCENTE, INSEGNAMENTO} e {DOCENTE, STUDENTE}. Queste sono decomposizioni valide, poiché sono non-additive in base al test sopra descritto.

Ulteriori decomposizioni non-additiveNei paragrafi precedenti abbiamo visto la decomposizione successiva di relazioni duran-te il processo di normalizzazione seconda e terza forma normale. Per verificare che queste decomposizioni non siano non-additive, dobbiamo verificare un’altra proprietà, come enunciato nella Proposizione 2.

Proposizione 2 (Conservazione della non-additività in decomposizioni suc-cessive)� Se una decomposizione D = {R1, R2, ..., Rm} di R soddisfa la proprietà di join non-additivo (senza perdita) rispetto a un insieme di dipendenze funzionali F su R e, se una decomposizione D

i = {Q1, Q2, ..., Qk} di Ri soddisfa la proprietà di join non-additivo rispetto alla proiezione di F su R

i, allora la decomposizione D2 = {R1, R2, ..., Ri-1, Q1, Q2, ..., Q

k, Ri+1, …, Rm} di R soddisfa la proprietà di join non-additivo rispetto a F.

3�. Algoritmi di progettazione di schemi di basi di dati relazionali

Forniamo ora tre algoritmi per creare una decomposizione relazionale. Ogni algoritmo, come vedremo nel seguito, ha proprietà specifiche.

Decomposizione in schemi 3�NF con conservazione delle dipendenzeL’Algoritmo 4 crea una decomposizione con conservazione delle dipendenze D = {R1, R2, ..., Rm

} di una relazione universale R basata su un insieme di dipendenze funzionali F, in modo che ogni R

i in D sia in 3NF. Garantisce solo la proprietà di conservazione

delle dipendenze; non garantisce la proprietà di join non-additivo. Il primo passo dell’Algoritmo 4 consiste nel trovare una copertura minimale G per F; a tale scopo si può usare l’Algoritmo 2. Si noti che, per un dato insieme F, possono esistere diverse coperture minime (come mostreremo in seguito nell’esempio successivo all’Algoritmo 4). In questi casi gli algoritmi possono anche produrre schemi alternativi diversi.

Algoritmo 4 Algoritmo di sintesi relazionale in 3NF con conservazione delle dipendenze.

Input. Una relazione universale R e un insieme di dipendenze funzionali F sugli attributi di R.

1. Si trovi una copertura minimale G per F (si usi l’Algoritmo 2);2. Per ogni parte sinistra X di una dipendenza funzionale che compare in G, si crei uno

schema di relazione in D con attributi {X ∪ {A1} ∪ {A2} ... ∪ {AK} }, dove X → A1, X → A2, ..., X → A

K sono le sole dipendenze in G con X come parte sinistra (X è la

chiave di questa relazione);3. Si pongano tutti gli attributi restanti (che non sono stati posti in alcuna relazione) in un

unico schema di relazione per assicurare la proprietà di conservazione degli attributi.



Esempio dell’Algoritmo 4. Si consideri la seguente relazione universale:

U(SSN_imp, N_P, Stip_I, Telefono_I, N_D, Nome_P, Sede_P)

SSN_imp, Stip_I, Telefono_I indicano, rispettivamente, codice della tessera sanitaria, sti-pendio e numero di telefono di un impiegato. N_P, Nome_P, Sede_P indicano, rispetti-vamente, numero, nome e sede di un progetto, mentre N_D è il numero di dipartimento.

Sono presenti le seguenti dipendenze funzionali:

DF1: SSN_imp → Stip_I, Telefono_I, N_D

DF2: N_P → Nome_P, Sede_P

DF3: SSN_imp, N_P → Stip_I, Telefono_I, N_D, Nome_P, Sede_P

In virtù della DF3, l’insieme di attributi {SSN_imp, N_P} rappresenta una chiave della relazione universale. Dunque, l’insieme F delle DF date comprende {SSN_imp → Stip_I, Telefono_I, N_D; N_P → Nome_P, Sede_P; SSN_imp, N_P → Stip_I, Telefono_I, N_D, Nome_P, Sede_P}.

Applicando l’Algoritmo 2 di copertura minima, al passo 3 osserviamo che N_P è un attributo ridondante in SSN_imp, N_P → Stip_I, Telefono_I, N_D. Inoltre, SSN_imp è ridondante in SSN_imp, N_P → Nome_P, Sede_P. Dunque la copertura minima è data da DF1 e DF2 (DF3 è totalmente ridondante) come segue (raggruppando gli attributi con la medesima parte sinistra in un’unica DF):

Copertura minima G: {SSN_imp → Stip_I, Telefono_I, N_D; N_P → Nome_P, Sede_P}

Applicando l’Algoritmo 4 alla precedente copertura minima G, otteniamo uno schema in 3NF composto da due relazioni con rispettive chiavi SSN_imp e N_P come segue:

R1(SSN_imp, Stip_I, Telefono_I, N_D)

R2(N_P, Nome_P, Sede_P)

Un lettore attento potrebbe facilmente notare che queste due relazioni hanno perso l’in-formazione originaria contenuta nella chiave della relazione universale U (cioè l’esisten-za di impiegati che lavorano su progetti con associazione molti-a-molti). Quindi, pur preservando le dipendenze iniziali, l’algoritmo non fornisce garanzia che tutte le infor-mazioni siano preservate. Dunque, lo schema risultante è lossy.

Proposizione 3� Ogni schema di relazione creato dall’Algoritmo 4 è in 3NF. (Qui non forniremo una dimostrazione formale;6 la dimostrazione dipende dal fatto che G sia un insieme minimale di dipendenze.)

È ovvio che tutte le dipendenze in G vengono conservate dall’algoritmo perché ogni dipendenza appare in qualche relazione R

i nella decomposizione D. Poiché G è equiva-lente a F, tutte le dipendenze in F vengono conservate direttamente nella decomposizio-ne oppure sono derivabili da quelle nelle relazioni risultanti, usando le regole di inferen-za presentate all’inizio di questo capitolo; in questo modo viene assicurata la proprietà

6 Per una dimostrazione si consulti Maier (1983) o Ullman (1982).



di conservazione delle dipendenze. L’Algoritmo 4 è chiamato algoritmo di sintesi rela-zionale, perché ogni schema di relazione R

i nella decomposizione è sintetizzato (costru-

ito) a partire dall’insieme di dipendenze funzionali in G aventi la stessa parte sinistra X.

Decomposizione non-additiva in schemi in BCNFL’algoritmo seguente decompone uno schema di relazione universale R = {A1, A2, ..., An

} in una decomposizione D = {R1, R2, ..., R

m}, in modo che ogni R

i sia in bCNF e la

decomposizione D goda della proprietà di join non-additivo rispetto a F. L’Algoritmo 5 utilizza la proprietà LJ1 e la proposizione 2 (conservazione di non-additività in decom-posizioni successive) per creare una decomposizione senza perdita D = {R1, R2, ..., Rm

} di una relazione universale R basata su un insieme di dipendenze funzionali F, in modo che ogni R

i in D sia in bCNF.

Algoritmo 5 Decomposizione relazionale in bCNF che verifica la proprietà di join non-additivo.


1. Si ponga D := {R} ;2. Finché c’è uno schema di relazione Q in D che non è in bCNF si esegua { si scelga uno schema di relazione Q in D che non sia in bCNF; si trovi una dipendenza funzionale X → Y in Q che violi bCNF; si sostituisca Q in D con due schemi di relazione (Q – Y) e (X ∪ Y); } ;

Ogni volta che attraversiamo il ciclo presente nell’Algoritmo 5 decomponiamo uno schema di relazione Q che non è in bCNF in due schemi di relazione. Secondo la pro-prietà LJ1 per le decomposizioni binarie e la proposizione 2, la decomposizione D verifica la proprietà di join non-additivo. Al termine dell’algoritmo, tutti gli schemi di relazione in D saranno in bCNF. Il lettore può verificare che l’esempio di normalizza-zione delle Figure 11.11 e 11.12 (Capitolo 11) segua sostanzialmente questo algoritmo. Le dipendenze funzionali DF3, DF4 e, più tardi, DF5, violano la bCNF, pertanto la relazione LOTTI viene decomposta in relazioni bCNF e inoltre la decomposizione sod-disfa la proprietà di join non-additivo. Analogamente, se applichiamo l’algoritmo allo schema di relazione INSEGNA della Figura 11.13, questo viene decomposto in INSEGNA1(DOCENTE, STUDENTE) e INSEGNA2(DOCENTE, CORSO) dato che la dipendenza DF2: DOCENTE → CORSO viola la bCNF.

Nel passo 2 dell’Algoritmo 5 è necessario determinare se uno schema di relazione Q è o meno in bCNF. Un metodo per fare ciò consiste nel testare, per ogni dipendenza funzionale X → Y in Q, se X+ non riesce a includere tutti gli attributi di Q, stabilendo quindi se X è una (super)chiave di Q. Un’altra tecnica si basa sull’osservazione che, ogni volta che uno schema di relazione Q viola la bCNF, esiste una coppia di attributi A e B di Q tale che {Q – {A, B} } → A; calcolando la chiusura {Q – {A, B} }+ per ogni coppia di attributi {A, B} di Q, e verificando se la chiusura comprende A (o B), possiamo deter-minare se Q è in bCNF.



Decomposizione con conservazione delle dipendenze e non-additiva (senza perdita)� in schemi in 3�NFFino a questo punto abbiamo mostrato come ottenere uno schema in 3NF con una pos-sibile perdita di informazione nell’Algoritmo 4 e come ottenere uno schema in bCNF con una perdita potenziale di certe dipendenze funzionali nell’Algoritmo 5. Ora sappia-mo che non è possibile assicurare tutte e tre le seguenti condizioni: (1) garanzia di schema senza perdite, (2) garanzia di conservazione delle dipendenze, (3) tutte le rela-zioni in bCNF. Come detto in precedenza, la prima condizione è obbligatoria e non può essere compromessa. La seconda condizione è auspicabile, ma non obbligatoria, e potrebbe dover essere rilassata qualora si insistesse per ottenere bCNF. Ora presentiamo un algoritmo alternativo mediante il quale si soddisfano le condizioni 1 e 2 e si garanti-sce soltanto la 3NF. Una semplice modifica all’Algoritmo 4, che produce l’Algoritmo 6, fornisce una decomposizione D di R con le seguenti proprietà:

• mantiene le dipendenze;

• soddisfa la proprietà di join non-additivo;

• è tale che ogni schema di relazione risultante nella decomposizione è in 3NF.

Poiché l’Algoritmo 6 garantisce entrambe le proprietà auspicabili, e non solamente la conservazione delle dipendenze funzionali come nel caso dell’Algoritmo 4, possiamo dire che si tratta di un algoritmo preferibile.

Algoritmo 6 Algoritmo di sintesi relazionale in 3NF con conservazione delle dipendenze e proprietà di join non-additivo.


1. Si trovi una copertura minimale G di F (si usi l’Algoritmo 2).2. Per ogni parte sinistra X di una dipendenza funzionale che compare in G, si crei uno

schema di relazione in D con attributi {X ∪ {A1} ∪ {A2} ... ∪ {AK} }, dove X → A1, X → A2, ..., X → AK sono le sole dipendenze di G con X come parte sinistra (X è la chiave di questa relazione).

3. Se nessuno degli schemi di relazione in D contiene una chiave di R, allora si crei un ulteriore schema di relazione in D contenente attributi che formano una chiave di R.7

4. Si eliminino le relazioni ridondanti dall’insieme di relazioni risultante nello schema relazionale della base di dati. Una relazione R è considerata ridondante se R è una proiezione di un’altra relazione S dello schema, oppure se R è sussunta da S.8

7 Il passo 3 dell’Algoritmo 4 non è necessario nell’Algoritmo 6 per la conservazione degli attributi, perché la chiave comprenderà tutti gli attributi non considerati; questi sono gli attributi che non partecipano ad alcuna dipendenza funzionale.8 Si noti che esiste un’ulteriore tipo di dipendenza: R è una proiezione del join di due o più relazioni dello schema. Questo tipo di ridondanza è considerata una dipendenza di join e viene successivamente discussa in Dipendenze di join e quinta forma normale pubblicato on-line su questo sito come Approfondimento Web al Capitolo 11. Dunque, tecnicamente, questa dipendenza può continuare a esistere senza interferire con la condizione di 3FN dello schema.



Il passo 3 dell’Algoritmo 6 comporta l’identificazione di una chiave K per R.

Esempio 1 dell’Algoritmo 6 Consideriamo nuovamente l’esempio illustrato alla fine dell’Algoritmo 4. Come nell’esempio precedente, facciamo riferimento alla copertura minima G e alle relazioni R1 e R2 prodotte al secondo passo dell’algoritmo. Ora, nel passo 3, generiamo una relazione corrispondente alla chiave {SSN_imp, N_P}. Dunque, lo schema risultante contiene:

R1 (SSN_imp, Stip_I, Telefono_I, N_D)

R2 (N_P, Nome_P, Sede_P)

R3 (SSN_imp, N_P)

Questo schema preserva entrambe le proprietà di conservazione delle dipendenze e di join non-additivo.

Esempio 2 dell’Algoritmo 6 (Caso X)�. Si consideri lo schema di relazione LOTTI1A mostrato nella Figura 11.13(a). Si assuma che questa sia fornita come relazione univer-sale con le seguenti dipendenze funzionali:

DF1: #id_proprietà → #lotto, Nome_contea, Area

DF2: #lotto, Nome_contea → Area, #id_proprietà

DF3: Area → Nome_contea

Nella Figura 11.13(a) queste erano indicate con DF1, DF2 e DF5. Il significato dei pre-cedenti attributi e le implicazioni delle precedenti dipendenze funzionali sono stati illustrati nel Paragrafo 11.4. Per semplicità, abbreviamo ogni attributo con la prima let-tera del nome (P per #id_proprietà, C per Nome_contea, A per Area, L per #lotto) rappre-sentando le dipendenze funzionali come l’insieme:

F: {P → LCA, LC → AP, A → C}

Se applichiamo a F l’Algoritmo 2 di copertura minima, (al passo 2) possiamo rappre-sentare l’insieme F come

F: {P → L, P → C, P → A, LC → A, LC → P, A → C}

Nell’insieme F, P → A può essere dedotta per transitività da P → LC e LC → A, ed è perciò ridondante. Quindi una possibile copertura minima è

Copertura minima GX: {P → LC, LC → AP, A → C}

Al passo 2 dell’Algoritmo 6 produciamo lo schema X (prima di eliminare le relazioni ridondanti) corrispondente a:

Schema X: R1(P, L, C), R2(L, C, A, P) e R3(A, C)

Al passo 4 dell’algoritmo, troviamo che R3 è sussunta da R2 (cioè R3 è sempre una pro-iezione di R2) e allo stesso modo R1 è una proiezione di R2. Dunque queste due relazio-ni sono entrambe ridondanti e lo schema in 3NF che preserva le proprietà auspicabili è (dopo aver eliminato le relazioni ridondanti):

Schema X: R2 (L, C, A, P)



In altri termini questo schema è identico alla relazione LOTTI1A(#lotto, Nome_contea, Area, #id_proprietà) che abbiamo stabilito essere in 3NF nel Paragrafo 11.4.2 (Capitolo 11).

Esempio 2 dell’Algoritmo 6 (caso Y)�. Partendo con LOTTI1A come relazione uni-versale e con il medesimo insieme di dipendenze funzionali, il secondo passo dell’Al-goritmo 2 di copertura minima produce come in precedenza

F: {P → C, P → A, P → L, LC → A, LC → P, A → C}

La DF LC → A può essere considerata ridondante, visto che può essere derivata per transitività da LC → P e P → A. Anche P → C è considerabile ridondante, essendo deri-vabile per transitività da P → A e A → C. Questo porta a coperture minime alternative come

Copertura minima GY: {P → LA, LC → P, A → C}.

Lo schema Y alternativo prodotto dall’algoritmo è ora:

Schema Y: S1 (P, A, L), S2 (L, C, P) e S3 (A, C)

Si noti che questo schema ha tre relazioni in 3NF, nessuna delle quali può essere consi-derata ridondante dalla condizione al passo 4. Tutte le DF nell’insieme F iniziale sono preservate. Il lettore noterà che delle tre relazioni, le relazioni S1 e S3 sono state prodot-te come schema in bCNF dalla procedura illustrata nel Paragrafo 11.5 (con l’implica-zione che S2 è ridondante in presenza di S1 e S3). Tuttavia, non si può eliminare la rela-zione S2 da questo insieme di tre relazioni in 3NF poiché essa non è proiezione né di S1 né di S3. Quindi, lo schema Y costituisce un possibile risultato finale dell’Algoritmo 6 applicato alla relazione universale, producendo relazioni in 3NF.

È importante notare che la teoria di decomposizione dei join non-additivi è basata sull’ipotesi che non siano ammessi valori nulli per gli attributi di join. Nel paragrafo seguente si discutono alcuni dei possibili problemi causati dai valori nulli nelle decom-posizioni relazionali.

4. Questioni relative a valori nulli, tuple dangling e progettazioni relazionali alternative

In questo paragrafo discuteremo alcune questioni relative ai problemi che sorgono quan-do la progettazione relazionale non è affrontata in modo opportuno.

Quando progettiamo uno schema di base di dati relazionale dobbiamo considerare attentamente i problemi associati ai valori nulli. Finora non c’è una teoria di progetta-zione relazionale pienamente soddisfacente che comprenda i valori nulli. Quando alcune tuple presentano valori nulli negli attributi che saranno usati per collegare via join sin-gole relazioni nella decomposizione si verifica un problema. Per illustrare ciò, si consi-deri la base di dati mostrata nella Figura 2(a), in cui vengono mostrate le due relazioni IMPIEGATO e DIPARTIMENTO. Le ultime due tuple impiegato, cioè berger e benitez, rappresentano impiegati appena assunti che non sono stati ancora assegnati a un dipar-timento (si dia per scontato che ciò non violi alcun vincolo d’integrità). Si supponga ora di voler reperire un elenco di valori di (NOME_I, NOME_D) per tutti gli impiegati. Se



eseguiamo l’operazione di JOIN NATURALE su IMPIEGATO e DIPARTIMENTO (si veda la Figura 2b), le due tuple prima menzionate non appariranno nel risultato. Questo pro-blema può essere affrontato usando l’operazione di JOIN ESTERNO. Si ricordi che, se consideriamo il JOIN ESTERNO SINISTRO di IMPIEGATO con DIPARTIMENTO, le tuple di IMPIEGATO che hanno un valore nullo per l’attributo di join appariranno ancora nel risultato, collegate via join con una tupla “immaginaria” di DIPARTIMENTO che ha valo-ri nulli per tutti gli attributi (si veda la Figura 2c).

In generale, ogni volta che viene progettato uno schema di basi di dati relazionale in cui due o più relazioni sono collegate tramite chiavi esterne, si deve dedicare particolare atten-zione alla ricerca di potenziali valori nulli nelle chiavi esterne. Questo, infatti, può causare un’imprevista perdita di informazioni nelle interrogazioni che implicano join su quella chia-ve esterna. Inoltre, se vi sono valori nulli in altri attributi, come STIPENDIO, il loro effetto su funzioni built-in, come SUM e AVERAGE, deve essere valutato attentamente.

Un problema collegato è quello delle tuple dangling (letteralmente “dondolanti”), che possono presentarsi se spingiamo troppo oltre una decomposizione. Si supponga di decomporre ulteriormente la relazione IMPIEGATO della Figura 2(a) nelle relazioni IMPIEGATO_1 e IMPIEGATO_2, mostrate nella Figura 3(a) e 3(b).9 Se applichiamo l’ope-razione di JOIN NATURALE a IMPIEGATO_1 e IMPIEGATO_2, otteniamo la relazione originale IMPIEGATO. Possiamo usare, però, la rappresentazione alternativa, mostrata nella Figura 3(c), in cui non inseriamo una tupla in IMPIEGATO_3 se all’impiegato non è stato assegnato un dipartimento (invece di inserire una tupla con un valore nullo per NUM_D come avviene in IMPIEGATO_2). Se usiamo IMPIEGATO_3 anziché IMPIEGA-TO_2 ed eseguiamo un’operazione di JOIN NATURALE tra IMPIEGATO_1 e IMPIEGA-TO_3, le tuple per berger e benitez non compariranno nel risultato; queste sono dette tuple dangling perché sono rappresentate in una sola delle due relazioni relative agli impiegati e quindi vanno perse se eseguiamo un’operazione di JOIN (INTERNO).

Analisi degli algoritmi di normalizzazione e progettazioni relazionali alternativeUno dei problemi con gli algoritmi di normalizzazione descritti è che il progettista della base di dati deve prima di tutto specificare tutte le dipendenze funzionali rilevanti tra gli attributi della base di dati. Questo non è un compito agevole per una grande base di dati con centinaia di attributi. Una dimenticanza nello specificare una o due dipendenze importanti può comportare un progetto inadeguato. Un altro problema è che questi algo-ritmi di solito sono non deterministici. Ad esempio gli algoritmi di sintesi (Algoritmi 4 e 6) richiedono la specificazione di una copertura minimale G per l’insieme di dipen-denze funzionali F. Poiché in generale possono esserci più coperture minimali corri-spondenti a F, l’algoritmo può dare diversi progetti a seconda della particolare copertu-ra minimale usata. Alcuni di questi progetti possono non essere soddisfacenti. L’algorit-mo di decomposizione (Algoritmo 5) dipende dall’ordine in cui le dipendenze funziona-

9 Questo accade talvolta quando applichiamo una frammentazione verticale a una relazione nel contesto di una base di dati distribuita (si veda il Capitolo 9 del volume di elmasri/Navathe Sistemi di Basi di Dati – Complementi).



Smith, John B.Wong, Franklin T.Zelaya, Alicia J.Wallace, Jennifer S.Narayan, Ramesh K.English, Joyce A.Jabbar, Ahmad V.Borg, James E.Berger, Anders C.Benitez, Carlos M.

123456789333445555999887777987654321666884444453453453987987987888665555999775555888664444

1965-01-091955-12-081968-07-191941-06-201962-09-151972-07-311969-03-291937-11-101965-04-261963-01-09

731 Fondren, Houston, TX638 Voss, Houston, TX3321 Castle, Spring, TX291 Berry, Bellaire, TX975 Fire Oak, Humble, TX5631 Rice, Houston, TX980 Dallas, Houston, TX450 Stone, Houston, TX6530 Braes, Bellaire, TX7654 Beech, Houston, TX

55445541

NULLNULL

RicercaAmministrazioneSede centrale

541

333445555987654321888665555

55445541

731 Fondren, Houston, TX638 Voss, Houston, TX3321 Castle, Spring, TX291 Berry, Bellaire, TX975 Fire Oak, Humble, TX5631 Rice, Houston, TX980 Dallas, Houston, TX450 Stone, Houston, TX

1965-01-091955-12-081968-07-191941-06-201962-09-151972-07-311969-03-291937-11-10

123456789333445555999887777987654321666884444453453453987987987888665555

Smith, John B.Wong, Franklin T.Zelaya, Alicia J.Wallace, Jennifer S.Narayan, Ramesh K.English, Joyce A.Jabbar, Ahmad V.Borg, James E.

RicercaRicerca

AmministrazioneAmministrazione

RicercaRicerca

AmministrazioneSede centrale

333445555333445555987654321987654321333445555333445555987654321888665555

55445541

NULLNULL


1965-01-091955-12-081968-07-191941-06-201962-09-151972-07-311969-03-291937-11-101965-04-261963-01-09

123456789333445555999887777987654321666884444453453453987987987888665555999775555888664444


RicercaRicerca

AmministrazioneAmministrazione

RicercaRicerca

AmministrazioneSede centrale

NULLNULL

333445555333445555987654321987654321333445555333445555987654321888665555

NULLNULL

NOME_I

NOME_D NUM_D SSN_DIR_DIP

SSN DATA_N INDIRIZZO NUM_D

NOME_I SSN DATA_N INDIRIZZO NUM_D NOME_D SSN_DIR_DIP

NOME_I SSN DATA_N INDIRIZZO NUM_D NOME_D SSN_DIR_DIP

IMPIEGATO

DIPARTIMENTO

(a)

(b)

(c)

Figura 2 Problemi relativi a join in presenza di valori nulli. (a) Alcune tuple di IMPIEGATO hanno un valore nullo per l’attributo di join NUM_D. (b) Risultato dell’applicazione dell’operatore di JOIN NATURALE alle relazioni IMPIEGATO e DIPARTIMENTO. (c) Risultato dell’applicazione dell’operatore di JOIN ESTERNO SINISTRO a IMPIEGATO e DIPARTIMENTO.

li vengono fornite all’algoritmo per verificare la violazione della bCNF. Anche in questo caso è possibile ottenere più progetti diversi relativi allo stesso insieme di dipendenze funzionali, a seconda dell’ordine in cui si considerano queste dipendenze per verificare la violazione della bCNF. Alcuni progetti che si ottengono possono essere significativa-mente superiori agli altri, mentre altri possono essere inadeguati.




123456789333445555999887777987654321666884444453453453987987987888665555999775555888664444

1965-01-091955-12-081968-07-191941-06-201962-09-151972-07-311969-03-291937-11-101965-04-261963-01-09


55445541

NULLNULL

123456789333445555999887777987654321666884444453453453987987987888665555999775555888664444

55445541

123456789333445555999887777987654321666884444453453453987987987888665555

(a)

(b) (c)

NOME_I SSN

SSN SSNNUM_D NUM_D

DATA_N INDIRIZZO

IMPIEGATO_1

IMPIEGATO_2 IMPIEGATO_3

Figura 3� Il problema della “tupla dangling”. (a) La relazione IMPIEGATO_1 (include tutti gli attributi di IMPIEGATO della Figura 11.2a a eccezione di NUM_D). (b) La relazione IMPIEGATO_2 (include l’attributo NUM_D con anche i valori nulli). (c) La relazione IMPIEGATO_3 (include l’attributo NUM_D ma non comprende tuple per le quali NUM_D ha valori nulli).

Non è sempre possibile trovare una decomposizione negli schemi di relazione che man-tenga le dipendenze e permetta a ogni schema di relazione nella decomposizione di essere in bCNF (invece di 3NF come nell’Algoritmo 6). Possiamo controllare gli sche-mi di relazione di 3NF nella decomposizione uno a uno per vedere se ciascuno soddisfa la bCNF. Se uno schema di relazione r

i non è in bCNF, possiamo decidere di decom-porlo ulteriormente o di lasciarlo così com’è in 3NF (con qualche possibile anomalia di aggiornamento).

Per illustrare i punti precedenti, consideriamo nuovamente la relazione LOTTI1A della Figura 11.13(a) (Capitolo 11). Si tratta di una relazione in 3NF e non in bCNF come discusso nel Paragrafo 11.5. Abbiamo anche mostrato che considerando le dipen-denze funzionali (DF1, DF2 e DF5 dalla Figura 11.13a), utilizzando l’approccio di progettazione bottom-up e applicando l’Algoritmo 6 è possibile ottenere sia la relazione LOTTI1A come schema in 3NF (in precedenza denominato schema X), sia uno schema alternativo Y composto da tre relazioni S1, S2, S3 (schema Y) ciascuna delle quali è in 3NF. Si noti che se analizziamo ulteriormente lo schema Y per verificare la bCNF, ognu-na delle relazioni S1, S2 e S3 risulta essere individualmente in bCNF. Al contrario, il test



di verifica della bCNF sullo schema X fallisce. Applicando l’Algoritmo 5, lo schema produce le due relazioni S1 e S3 (a causa della dipendenza funzionale non conforme A → C). Quindi la procedura di progettazione bottom-up, basata prima sull’Algoritmo 11.4 per definire relazioni in 3NF e ottenere entrambe le proprietà, e sull’Algoritmo 5 per ottenere relazioni in bCNF con la proprietà di join non-additivo (sacrificando la proprietà di conservazione delle dipendenze funzionali), produce uno schema finale in bCNF composto dalle relazioni S1, S2, S3 se si segue una certa via (la via dello schema Y) e uno schema composto dalle relazioni S1, S3 se se ne segue un’altra (quella dello schema X). Ciò è dovuto alle diverse coperture minime esistenti per l’insieme iniziale di dipendenze funzionali. Si noti che S2 è una relazione ridondante nello schema Y, tuttavia essa non viola il vincolo di join non-additivo. È facile vedere che S2 è un relazione vali-da e significativa che ha le due chiavi candidate (L, C) da un lato e l’attributo P dall’altro.

La Tabella 1 riassume le proprietà degli algoritmi analizzati finora in questo capitolo.

5. Discussione ulteriore sulle dipendenze multivalore e 4NF

In Dipendenze multivalore e quarta forma normale pubblicato on-line su questo sito come Approfondimento Web al Capitolo 11 abbiamo introdotto e definito il concetto di dipendenza multivalore e l’abbiamo usato per descrivere la quarta forma normale. Ora rivediamo le MVD per completare la trattazione su questo argomento specificando le regole di inferenza sulle MVD.

Regole di inferenza per dipendenze funzionali e multivaloreCome per le dipendenze funzionali, sono state sviluppate regole di inferenza per le dipendenze multivalore; tuttavia è meglio fornire un contesto unificato che includa le DF e le MVD così che ambedue i tipi di vincolo possano essere considerati insieme. Le regole di inferenza seguenti, da RI1 a RI8, formano un insieme completo e corretto per inferire le dipendenze funzionali e multivalore da un insieme di dipendenze dato. Si supponga che tutti gli attributi siano inclusi in uno schema di relazione “universale” R = {A1, A2, …, An} e che X, Y, Z e W siano sottoinsiemi di R.

RI1 (regola riflessiva per le DF): se X $ Y, allora X → Y. RI2 (regola di arricchimento per le DF): {X → Y} |= XZ → YZ. RI3 (regola transitiva per le DF): {X → Y, Y → Z} |= X → Z. RI4 (regola di complemento per le MVD): {X →→ Y} |= X →→ (R – (X ∪ Y))}. RI5 (regola di arricchimento per le MVD): Se X →→ Y e W $ Z, allora WX →→ YZ. RI6 (regola transitiva per le MVD): {X →→ Y, Y →→ Z} |= X →→ (Z – Y). RI7 (regola di replicazione per DF in MVD): {X → Y} |= X →→ Y. RI8 (regola di unione per le DF e le MVD): se X →→ Y ed esiste W con le proprietà

che (a) W ∩ Y è vuota, (b) W → Z e (c) Y $ Z, allora X → Z.

Le regole di inferenza di Armstrong per le DF sono quelle da RI1 a RI3, mentre le regole da RI4 a RI6 sono regole di inferenza che riguardano solo le MVD. Le RI7 e RI8 sono correlate



Tabella 1 Riepilogo degli algoritmi presentati nel capitolo.

Algoritmo Input Output Proprietà Osservazioni

1 Un attributo o un insieme di attributi X e un insieme F di DF

Un insieme di attributi nella chiusura di X rispetto a F

Trova tutti gli attributi che possono essere determinati funzionalmente da X

La chiusura di una chiave è l’intera relazione

2 Un insieme F di dipendenze funzionali

La copertura minimale di dipendenze funzionali

Per determinare la copertura minimale di un insieme F di dipendenze

Possono esistere coperture minimali multiple – dipende dall’ordine con cui le dipendenze funzionali vengono selezionate

3 Una decomposizione D di R e un insieme F di dipendenze funzionali

risultato booleano; sì e no per la proprietà di join non additivo

Test per la decomposizione non additiva

Si veda Verifica della proprietà di join non-additivo su decomposizioni binarie per un test più semplice per le decomposizioni binarie

4 Una relazione R e un insieme F di dipendenze funzionali

Un insieme di relazioni in 3NF

Conservazione delle dipendenze

Non garantisce la proprietà di join senza perdita


Un insieme di relazioni in bCNF

Decomposizione non-additiva

Non garantisce la conservazione delle dipendenze



Decomposizione non-additiva e conservazione delle dipendenze

Può non arrivare a bCNF, ma garantisce tutte le proprietà desiderabili e la 3NF

7 Una relazione R e un insieme di dipendenze funzionali e multivalore


Decomposizione non-additiva

Non garantisce la conservazione delle dipendenze

sia alle DF sia alle MVD. In particolare la RI7 afferma che una dipendenza funzionale è un caso speciale di una dipendenza multivalore; cioè ogni DF è anche una MVD perché soddi-sfa la definizione formale di una MVD. Questa equivalenza, però, sottende che: una DF X → Y è una MVD X →→ Y con l’ulteriore limitazione implicita che al massimo un valore di Y è associato a ogni valore di X.10 Dato un insieme F di dipendenze funzionali e multivalore specificato su R = {A1, A2, …, An}, possiamo usare le regole da RI1 a RI8 per inferire l’insie-me (completo) di tutte le dipendenze (funzionali o multivalore) F+ che sussisterà in ogni stato di relazione r di R che soddisfa F. Chiamiamo F+ la chiusura di F.

10 Cioè l’insieme di valori di Y determinato da un valore di X è limitato a essere un insieme con un solo elemento. Quindi, in pratica, non consideriamo mai una DF come una MVD.



(a) (b)IMP

NOME_I NOME_P NOME_D

SmithSmithSmithSmithBrownBrownBrownBrownBrownBrownBrownBrownBrownBrownBrownBrown

XYXYWXYZWXYZWXYZ

JohnAnnaAnnaJohnJimJimJimJimJoanJoanJoanJoanBobBobBobBob

PROGETTI_IMP

NOME_PNOME_I

XYWXYZ

SmithSmithBrownBrownBrownBrown

DIPENDENTI_IMP

NOME_DNOME_I

AnnaJohnJimJoanBob

SmithSmithBrownBrownBrown

Figura 4 Decomposizione di uno stato della relazione IMP che non è in 4NF. (a) La relazione IMP con ulteriori tuple. (b) Le due relazioni in 4NF corrispondenti PROGETTI_IMP e DIPENDENTI_IMP.

Quarta forma normale rivisitatarichiamiamo da Dipendenze multivalore e quarta forma normale pubblicato on-line su questo sito come Approfondimento Web al Capitolo 11 la definizione di quarta forma normale (4NF).

Definizione. Uno schema di relazione R è in 4NF rispetto a un insieme di dipendenze F (che include le dipendenze funzionali e multivalore) se, per ogni dipendenza multiva-lore non banale X →→ Y in F+, X è una superchiave di R.

Per illustrare l’importanza della 4NF, la Figura 4(a) mostra la relazione IMP in cui un altro impiegato, ‘brown’, ha tre dipendenti (‘Jim’, ‘Joan’ e ‘bob’) e lavora su quattro progetti diversi (‘W’, ‘X’, ‘Y’ e ‘Z’). Nella Figura 4(a) IMP ha 16 tuple. Se decomponiamo IMP in PROGETTI_IMP e DIPENDENTI_IMP, come mostrato nella Figura 4(b), dobbiamo memoriz-zare complessivamente solo 11 tuple, considerando entrambe le relazioni. Non solo la decomposizione porta a un risparmio di memoria, ma si evitano anche le anomalie di aggior-namento associate alle dipendenze multivalore. Ad esempio, se brown inizia a lavorare su un nuovo progetto P, dobbiamo inserire tre tuple in IMP, una per ogni dipendente. Se dimen-tichiamo di inserire una di queste, la relazione viola la MVD e diventa inconsistente per il fatto che implica in modo non corretto un’associazione tra progetto e dipendente.

Quando una relazione contiene MVD non banali, le operazioni di inserimento, elimina-zione e aggiornamento sulle singole tuple possono richiedere la modifica di ulteriori tuple, oltre a quella in questione. Se l’aggiornamento non è gestito in modo corretto, il significato della relazione può cambiare; tuttavia, dopo la normalizzazione in 4NF, queste anomalie scompaiono. Ad esempio, per aggiungere l’informazione che brown sarà assegnato al pro-getto P, si deve inserire solo una singola tupla nella relazione PROGETTO_IMP in 4NF.



La relazione IMP nella Figura 1 (a) di Dipendenze multivalore e quarta forma norma-le, pubblicato on-line su questo sito come Approfondimento Web al Capitolo 11, non è in 4NF, perché rappresenta due associazioni di tipo 1:N indipendenti: una tra gli impiegati e i progetti su cui lavorano e l’altra tra gli impiegati e i loro dipendenti. A volte abbiamo un’associazione tra tre entità che dipende da tutte e tre le entità partecipanti, come la relazione FORNITURA mostrata nella Figura 11.4(c). (Per il momento si considerino solo le tuple della Figura 1c in Dipendenze multivalore e quarta forma normale, pubblicato on-line su questo sito come Approfondimento Web al Capitolo 11, poste sopra la linea tratteggiata.) In questo caso ogni tupla rappresenta il fatto che un fornitore procura una parte specifica per un progetto particolare, quindi non ci sono MVD banali. La relazione FORNITURA è già in 4NF e non dovrebbe essere decomposta ulteriormente.

Decomposizione di join non-additivo in schemi in 4NFOgni volta che decomponiamo uno schema di relazione R in R1 = (X ∪ Y) e R2 = (R – Y) sulla base di una MVD X →→ Y che sussiste in R, la decomposizione gode della proprie-tà di join non-additivo. Si può dimostrare che questa è una condizione necessaria e sufficiente per decomporre uno schema in due schemi che hanno la proprietà di join non-additivo, come specificato dalla proprietà NJbʹ che è un’ulteriore generalizzazione della proprietà NJb mostrata precedentemente. La proprietà NJb è relativa solo alle DF, mentre NJbʹ gestisce sia le DF sia le MVD (si ricordi che una DF è anche una MVD).

PROPRIETÀ NJBʹGli schemi di relazione R1

e R2 costituiscono una decomposizione non-additiva di R rispetto a un insieme F di dipendenze funzionali e multivalore se e solo se

(R1 ∩ R2) →→ (R1 – R2)

oppure, per simmetria, se e solo se

(R1 ∩ R2) →→ (R2 – R1).

Con una piccola modifica dell’Algoritmo 5 si ottiene l’Algoritmo 7, che crea una decomposizione non-additiva che produce schemi di relazione che sono in 4NF (anziché in bCNF). Come con l’Algoritmo 5, l’Algoritmo 7 non produce necessariamente una decomposizione che conserva le DF.

Algoritmo 7 Decomposizione relazionale in relazioni in 4NF con la proprietà di join non-additivo.

Input. Una relazione universale R e un insieme di dipendenze funzionali e multivalore F.

1. Si ponga D:= {R};2. Fintantoché vi è uno schema di relazione Q in D che non è in 4NF; { si scelga uno schema di relazione Q in D che non è in 4NF; si trovi una MVD non banale X →→ Y in Q che viola la 4NF; si sostituisca Q in D con due schemi di relazione (Q – Y) e (X ∪ Y); } ;



6. Altre dipendenze e forme normaliIn Dipendenze di join e quinta forma normale, pubblicato on-line su questo sito come Approfondimento Web al Capitolo 11, abbiamo già introdotto un’altra definizione di dipendenza funzionale chiamata dipendenza di join (JD). essa si presenta quando una relazione è decomponibile in un insieme di relazioni proiettate che possono essere col-legate nuovamente per ottenere la relazione di partenza. Dopo aver definito la JD, abbia-mo introdotto la quinta forma normale che su di essa è basata. In questo paragrafo introdurremo altri tipi di dipendenze che sono state identificate.

Dipendenze di inclusioneLe dipendenze di inclusione sono state definite per formalizzare due tipi di vincoli inter-relazionali:

• il vincolo di chiave esterna (o di integrità referenziale) non può essere specificato come una dipendenza funzionale o multivalore, perché mette in relazione gli attribu-ti di relazioni diverse;

• il vincolo tra due relazioni che rappresentano un’associazione classe/sottoclasse (si vedano i Capitoli 8 e 9) non può essere definito formalmente in termini di dipenden-ze funzionali, multivalore e di join.

Definizione. Una dipendenza di inclusione R.X < S.Y tra due insiemi di attributi, X dello schema di relazione R e Y dello schema di relazione S, specifica il vincolo che, in qualunque istante, quando r è uno stato di relazione di R e s uno stato di relazione di S, dobbiamo avere:

pX(r( R )) p

Y (s(S))

La relazione (sottoinsieme) non deve essere necessariamente di sottoinsieme proprio. Naturalmente gli insiemi di attributi su cui è specificata la dipendenza di inclusione, X di R e Y di S, devono avere lo stesso numero di attributi. Inoltre i domini per ogni coppia di attributi corrispondenti dovrebbero essere compatibili. Ad esempio, se X = {A1, A2, …, A

n} e Y = {B1, B2, …, Bn}, una possibile corrispondenza è avere dom(Ai) compatibile con dom(B

i) per 1 ≤ i ≤ n. In questo caso diciamo che Ai corrisponde a Bi.Ad esempio possiamo specificare le seguenti dipendenze di inclusione sullo schema

di relazione della Figura 11.1:

DIPARTIMENTO.SSN_DIR_D < IMPIEGATO.SSN

LAVORA_SU.SSN < IMPIEGATO.SSN

IMPIEGATO.NUMERO_D < DIPARTIMENTO.NUMERO_D

PROGETTO.NUM_D < DIPARTIMENTO.NUMERO_D

LAVORA_SU.NUMERO_P < PROGETTO.NUMERO_P

SEDI_DIP.NUMERO_D < DIPARTIMENTO.NUMERO_D

Tutte le dipendenze di inclusione precedenti rappresentano vincoli di integrità referen-ziale. Possiamo usare anche dipendenze di inclusione per rappresentare associazioni



classe/sottoclasse. Ad esempio nello schema di relazione della Figura 9.6 possiamo specificare le seguenti dipendenze di inclusione:

IMPIEGATO.SSN < PERSONA.SSN

ALUNNO.SSN < PERSONA.SSN

STUDENTE.SSN < PERSONA.SSN

Come con altri tipi di dipendenze, ci sono delle regole di inferenza delle dipendenze di inclusione IDIr (inclusion dependency inference rules). ecco tre esempi:

IDIR1 (riflessività): R.X < R.X.

IDIR2 (corrispondenza degli attributi): se R.X < S.Y, dove X = {A1, A2, …, An} e

Y = {B1, B2, …, Bn} e A

i corrisponde a B

i, allora R.A

i < S.B

i per 1 ≤ i ≤ n.

IDIR3 (transitività): se R.X < S.Y e S.Y < T.Z, allora R.X < T.Z.

È stato mostrato che le regole di inferenza precedenti sono corrette e complete rispetto alle dipendenze di inclusione. Finora non sono state sviluppate forme normali basate sulle dipendenze di inclusione.

Dipendenze modelloLe dipendenze modello forniscono una tecnica per rappresentare i vincoli che general-mente non hanno definizioni semplici e formali. Indipendentemente dal fatto di definire varie tipologie di dipendenze, può manifestarsi la necessità di dover esprimere qualche vincolo basato sulla semantica degli attributi all’interno di relazioni che non può essere rappresentato da alcuna delle dipendenze definite. Lo scopo principale delle dipendenze modello è poter specificare un modello, o un esempio, in grado di definire ogni vincolo o dipendenza.

Ci sono due tipi di modelli: modelli che generano tuple e modelli che generano vinco-li. Un modello è formato da un certo numero di tuple ipotesi, che hanno lo scopo di mostrare un esempio di tuple che possono apparire in una o più relazioni. La seconda parte del modello è la conclusione. Per i modelli che generano tuple, la conclusione è costituita da un insieme di tuple che deve altresì esistere nelle relazioni se ci sono le tuple ipotesi. Per quanto riguarda i modelli che generano vincoli, la conclusione del modello è una con-dizione che deve essere verificata dalle tuple ipotesi. Usando i modelli che generano vin-coli, siamo in grado di specificare vincoli semantici, che vanno oltre lo scopo del model-lo relazionale rispetto al suo linguaggio di definizione dei dati e alla sua notazione.

La Figura 5 mostra come si possono definire dipendenze funzionali, multivalore e di inclusione tramite modelli. La Figura 6 mostra come si può specificare il vincolo che “lo stipendio di un impiegato non può essere superiore a quello del suo diretto supervisore” sullo schema di relazione IMPIEGATO della Figura 3.5.

Dipendenze funzionali basate su funzioni aritmetiche e procedureA volte gli attributi di una relazione sono collegabili per mezzo di una funzione aritme-tica o di un’associazione funzionale più complicata. Finché a ogni valore di X è associa-



Ipotesi

Conclusione

X = { A , B }

Y= { C }

X = { A , B }

Y = { C , D }Ipotesi

Conclusione

Ipotesi

Conclusione

Y = { E , F }

X = { C , D }

R = { A , B , C , D }

R = { A , B , C , D }

R = { A , B , C , D } S = { E , F , G }(c)

(b)

(a)

a1 b1 c1

c1 = c2 e 1 = d2

a1 b1 c2

a1 b1 c1 d1

a1 b1 c1 d1

c1 d1 g

a1 b1 c2 d2

a1 b1

c1

d1

a1 b1

c2

d2

d1

d2

d

Figura 5 Modelli per alcuni tipi comuni di dipendenze. (a) Modello per la dipendenza funzionale X → Y. (b) Modello per la dipendenza multivalore X →→ Y. (c) Modello per la dipendenza di inclusione R.X < S.Y.

to un valore univoco di Y possiamo ancora considerare l’esistenza di una DF X → Y. Ad esempio, nella relazione

RIGA_ORDINE(#Ordine, #Oggetto, Quantità, Prezzo_unitario, Prezzo_complessivo, Prezzo_scontato)

ogni tupla rappresenta un oggetto all’interno di un ordine con quantità e prezzo unitario di tale oggetto. In questa relazione (Quantità, Prezzo_unitario) → Prezzo_complessivo mediante la formula

Prezzo_complessivo = Prezzo_unitario * Quantità

Dunque, esiste un unico valore di Prezzo_complessivo per ogni coppia (Quantità, Prez-zo_unitario), in conformità con la definizione di dipendenza funzionale.

Inoltre, si potrebbe definire una procedura che considera, tra le altre cose, l’entità degli sconti e la tipologia dell’oggetto e così via, e che calcola il prezzo scontato per la quantità complessivamente ordinata di tale oggetto. Quindi possiamo affermare

(#Oggetto, Quantità, Prezzo_unitario) → Prezzo_scontato oppure

(#Oggetto, Quantità, Prezzo_complessivo) → Prezzo_scontato



IMPIEGATO = { NOME , SSN , ... , STIPENDIO , SSN_SUPERVISORE }

Ipotesi

Conclusione

a b c d

e d f g

c f<

Figura 6 Modello per il vincolo che lo stipendio di un impiegato deve essere inferiore a quello del superiore.

Per verificare le precedenti dipendenze si potrebbe definire una procedura più comples-sa CALCOLA_PREZZO_TOTALE. Sebbene le precedenti tipologie di DF siano tecnica-mente presenti in molte relazioni, non viene loro attribuita particolare attenzione duran-te la normalizzazione.

Forma normale dominio-chiaveStoricamente, i processi di normalizzazione e di individuazione delle dipendenze inde-siderate sono stati eseguiti fino alla 5NF, ma è stato possibile definire forme normali ancora più forti che tengono conto di altri tipi di dipendenze e di vincoli. L’idea che sta alla base della forma normale dominio-chiave dkNF (domain-key normal form) è quel-la di specificare (almeno dal punto di vista teorico) “la forma normale definitiva” che consideri tutti i tipi possibili di dipendenze e vincoli. Si dice che uno schema di relazio-ne è in dkNF se tutti i vincoli e le dipendenze che dovrebbero sussistere sugli stati di relazione validi possono essere realizzati imponendo semplicemente vincoli di dominio e i vincoli di chiave sulla relazione. Se una relazione è in DKNF, diventa molto sempli-ce imporre tutti i vincoli della base di dati controllando semplicemente che ogni valore di attributo in una tupla appartenga al dominio appropriato e che ogni vincolo di chiave sia stato imposto.

Tuttavia, a causa della difficoltà di inserire vincoli complessi in una relazione DKNF, la sua utilità pratica è limitata, poiché può risultare piuttosto difficile specificare vincoli di integrità generali. Si consideri ad esempio una relazione AUTOMOBILE(CASA_COSTRUTTRICE, NUM_TELAIO#) (dove NUM_TELAIO# è il numero identificativo del veicolo) e un’altra relazione PRODUTTORE(NUM_TELAIO#, PAESE) (dove PAESE è il luogo di produzione). Un vincolo generale può essere della seguente forma: “Se la CASA_COSTRUTTRICE è Toyota o Lexus, il primo carattere del NUM_TELAIO# è una “G” se il paese di produzione è il Giappone; se il PRODUTTORE è Honda o Acura, il secondo carattere del NUM_TELAIO# è una “G” se il paese di produzione è il Giappone”. Non esiste un modo semplice per rappresentare tali vincoli se non scrivendo una proce-dura (o asserzioni generali) per controllarli. La procedura CALCOLA_PREZZO_TOTALE vista in precedenza è un esempio di questo tipo di procedure che si rivelano necessarie per garantire il rispetto di un opportuno vincolo di integrità.



7. SommarioIn questo capitolo abbiamo presentato ulteriori argomenti sulle dipendenze funzionali, una discussione relativa alla decomposizione e numerosi algoritmi relativi a essa così come alla normalizzazione. Nel Paragrafo 1 abbiamo presentato le regole di inferenza per le dipendenze funzionali (DF), la nozione di chiusura di un attributo, di chiusura di un insieme di dipendenze funzionali, di equivalenza tra insiemi di dipendenze funziona-li e gli algoritmi per trovare la chiusura di un attributo (Algoritmo 1) e la copertura minimale di un insieme di DF (Algoritmo 2). Abbiamo quindi discusso due proprietà importanti delle decomposizioni: la proprietà di join non-additivo e la proprietà di con-servazione delle dipendenze. È stato descritto un algoritmo per verificare quando una decomposizione è non-additiva (Algoritmo 3) e un semplice test per verificare quando le decomposizioni binarie sono senza perdita (proprietà NJb). Abbiamo quindi discusso la progettazione relazionale per sintesi, basata su un insieme dato di dipendenze funzio-nali. Gli algoritmi di sintesi relazionale (come gli Algoritmi 4 e 6) generano relazioni 3NF da uno schema di relazione universale basato su un insieme di partenza di dipen-denze funzionali specificato dal progettista della base di dati. Gli algoritmi di decompo-sizione relazionale (come gli Algoritmi 5 e 7) generano relazioni bCNF (o 4NF) mediante successive decomposizioni non-additive di relazioni non-normalizzate in due relazioni-componente alla volta. Abbiamo visto che è possibile sintetizzare schemi di relazione 3NF che soddisfano entrambe le proprietà di cui sopra; tuttavia, in caso di bCNF, è possibile arrivare soltanto alla non-additività dei join – la conservazione delle dipendenze non può essere sempre garantita. Se il progettista deve ottenere una di queste due proprietà, si sappia che la condizione di join non-additivo è un obbligo assoluto. Nel Paragrafo 4 abbiamo mostrato come in una collezione di relazioni possono sorgere pro-blemi dovuti ai valori nulli che possono esistere nelle relazioni nonostante esse siano in 3NF o bCNF. A volte, quando la decomposizione è eseguita in modo scorretto, può accadere che certe “tuple dangling” non partecipino ai risultati dei join e quindi diven-tino invisibili. Abbiamo anche mostrato possibili progettazioni alternative che soddisfa-no una forma normale desiderata.

Nel Paragrafo 5 abbiamo rivisto le dipendenze multivalore (MVD) che possono pre-sentarsi a seguito di una combinazione scorretta di due o più attributi multivalore indi-pendenti all’interno della stessa relazione e che generano un’espansione combinatoria delle tuple usate per definire la quarta forma normale (4NF). Abbiamo presentato le regole di inferenza applicabili alle MVD e discusso l’importanza della 4NF. Infine, nel Paragrafo 6, abbiamo affrontato le dipendenze di inclusione usate per specificare vinco-li di integrità referenziale e vincoli di classe/sottoclasse, e le dipendenze modello usate per specificare tipi di vincoli arbitrari. Abbiamo sottolineato la necessità di funzioni aritmetiche e procedure più complesse per realizzare certi vincoli sulle dipendenze fun-zionali. Abbiamo concluso con una breve discussione sulla forma normale dominio-chiave (DKNF).



Questionario di verifica

1. Quale ruolo hanno le regole di inferenza di Armstrong (le tre regole di inferenza dalla RI1 alla RI3) nello svi-luppo della teoria della progettazione relazionale?

2. Che cosa si intende per completezza e correttezza delle regole di inferenza di Armstrong?

3. Che cosa si intende per chiusura di un insieme di dipendenze funzionali? Fate un esempio.

4. Quando si dice che due insiemi di dipendenze funzionali sono equivalenti? Come possiamo determinare la loro equivalenza?

5. Che cos’è un insieme minimale di dipendenze funzionali? Per ogni insieme di dipendenze esiste un insieme mi-nimale equivalente? È sempre unico?

6. Che cosa si intende per condizione di conservazione degli attributi in una decomposizione?

7. Perché le forme normali da sole non sono sufficienti come condizione di buona progettazione di schemi?

8. Che cos’è la proprietà di conservazione delle dipendenze per una decomposizione? Perché è importante?

9. Perché non è possibile garantire che gli schemi di relazione in bCNF vengano prodotti da decomposizioni che conservano le dipendenze di schemi di relazione non-bCNF? Si fornisca un controesempio per illustrare questo punto.

10. Che cos’è la proprietà di join non-additivo di una decomposizione? Perché è importante?

11. Tra le due proprietà di conservazione delle dipendenze e assenza di perdita, quale deve essere assolutamente soddisfatta? Perché?

12. Si discutano i problemi relativi ai valori nulli e alle tuple dangling.

13. Si mostri come il processo di creazione delle relazioni in prima forma normale possa portare a dipendenze multivalore. Come dovrebbe essere eseguita la normalizzazione in prima forma normale in modo da evitare MVD?

14. Quali tipi di vincoli sono in grado si rappresentare le dipendenze di inclusione?

15. Come differiscono le dipendenze modello dagli altri tipi di dipendenze che abbiamo analizzato?

16. Perché la forma normale di dominio-chiave è nota come forma normale definitiva?

esercizi

17. Si dimostri che gli schemi di relazione prodotti dall’Algoritmo 4 sono in 3NF.

18. Si dimostri che, se la matrice S risultante dall’Algoritmo 3 non ha una riga con tutti simboli “a”, la proiezione di S sulla decomposizione e la successiva riunione tramite join produrrà sempre almeno una tupla spuria.

19. Si dimostri che gli schemi di relazione prodotti dall’Algoritmo 5 sono in bCNF.

20. Si dimostri che gli schemi di relazione prodotti dall’Algoritmo 6 sono in 3NF.

21. Si specifichino le dipendenze modello per le dipendenze di join.

22. Si specifichino tutte le dipendenze di inclusione per lo schema di relazione della Figura 3.5.

23. Si dimostri che una dipendenza funzionale soddisfa la definizione formale di dipendenza multivalore.

24. Si consideri l’esempio di normalizzazione della relazione LOTTI dei Paragrafi 11.4 e 11.5. Si determini se la de-composizione di LOTTI in {LOTTI1AX, LOTTI1AY, LOTTI1B, LOTTI2} gode della proprietà di join non-addi-tivo, applicando l’Algoritmo 3 e anche usando il test presente nella proprietà NJb.



25. Si dimostri come le MVD NOME_I →→ NOME_P e NOME_I →→ NOME_D della Figura 1(a) (in Dipendenze multivalore e quarta forma normale, on-line) possono comparire durante la normalizzazione in 1NF di una rela-zione, dove gli attributi NOME_P e NOME_D sono multivalore.

26. Si applichi l’algoritmo di decomposizione (Algoritmo 5) alla relazione R e all’insieme di dipendenze F dell’Eser-cizio 11.19 Si ripeta il tutto per le dipendenze G dell’Esercizio 11.20 (Capitolo 11).

27. Si scrivano programmi che implementano gli Algoritmi 5 e 6.

28. Si considerino le decomposizioni seguenti per lo schema di relazione R dell’Esercizio 11.19 (Capitolo 11). Si determini se ogni decomposizione gode (i) della proprietà di conservazione delle dipendenze e (ii) della proprie-tà di join non-additivo, rispetto a F. Si determini anche in quale forma normale si trova ogni relazione della de-composizione.

a. D1 = {R1, R2, R3, R4, R5}; R1 = {A, B, C}, R2 = {A, D, E}, R3 = {B, F}, R4 = {F, G, H}, R5 = {D, I, J}.

b. D2 = {R1, R2, R3}; R1 = {A, B, C, D, E}, R2 = {B, F, G, H}, R3 = {D, I, J}.

c. D3 = {R1, R2, R3, R4, R5}; R1 = {A, B, C, D}, R2 = {D, E}, R3 = {B, F}, R4 = {F, G, H}, R5 = {D, I, J}.

29. Si consideri la seguente relazione FRIGORIFERO(#MODELLO, ANNO, PREZZO, STAB_PROD, COLORE), abbreviata in FRIGORIFERO(M, A, P, SP, C) e che ha il seguente insieme F di dipendenze funzionali: F = {M → SP, {M, A} → P, SP → C}.

a. Si valuti ciascuno dei seguenti insiemi come possibile chiave candidata per FRIGORIFERO, giustificando perché può essere o non può essere una chiave: {M}, {M, A}, {M, C}.

b. Sulla base di questa determinazione della chiave, si stabilisca se la relazione FRIGORIFERO è in 3NF e in bCNF, fornendone le opportune giustificazioni.

c. Si consideri la decomposizione di FRIGORIFERO in D = {R1(M, A, P), R2(M, SP, C)}. Questa decomposi-zione è senza perdita? Si dica perché. Si consulti il Paragrafo Verifica della proprietà di join non-additivo su de-composizioni binarie presente in questo capitolo.


Algoritmi di progettazione di basi di dati relazionali e …...Nella trattazione seguente, quando...

Documents

Transcript of Algoritmi di progettazione di basi di dati relazionali e …...Nella trattazione seguente, quando...