Next: Proiezione sugli schema graph
Up: Rappresentazione formale degli schemi
Previous: Schema graph
Indice
Indice analitico
Schema graph ridotto
Confrontato con gli schema graph generali, la classe degli schema graph canonici ha l'importante vantaggio di fornire una rappresentazione non ridondante e compatta. D'altra parte, allo scopo di ottenere dei risultati univoci per le operazioni di modifica degli schemi, dobbiamo assicurarci di lavorare su rappresentazioni univocamente determinate. Questa sezione dimostra come sia possibile ottenere uno schema determinato univocamente, chiamato Schema Graph Ridotto.
Per gli insiemi aciclici di FD semplici, le coperture canoniche sono determinate univocamente e possono essere calcolate attraverso una riduzione transitiva:
Per illustrare le differenze tra la chiusura transitiva
e la chiusura
delle dipendenze funzionali
, osserviamo che la definizione di
contiene solo FD semplici. Se le FD in F coinvolgono due o più attributi allora
contiene delle dipendenze funzionali non semplici addizionali che sono implicite in
.
Esempio 3
Per
abbiamo:
Come visto in [AGU72], nel caso dei grafi aciclici la riduzione transitiva
è univocamente determinata ed
. Oltre a questo, ricordiamo che
è una copertura canonica di
, da [Lec04], quindi se
è aciclico lo schema graph ridotto per
è
.
D'altra parte, negli scenari reali l'aciclicità delle dipendenze funzionali può non essere soddisfatta, dal momento che i cicli si presentano in almeno due casi:
- Proprietà Descrittive. Sebbene nella quasi totalità dei casi le associazioni tra le proprietà di un data warehouse abbiano una molteplicità molti-a-uno, in alcuni casi possono avere una molteplicità uno-ad-uno. Questo accade tipicamente con le proprietà descrittive, che permettono di descrivere un oggetto attraverso diverse nomenclature (per esempio i codici dei prodotti ed il loro nome).
- Misure Derivate. Due misure derivate possono essere calcolabili l'una a partire dall'altra, se la funzione di derivazione è invertibile. Questo accade, per esempio, nel caso della conversione dei prezzi da una valuta all'altra, semplicemente applicando dei fattori costanti di conversione.
L'esempio seguente dimostra che le coperture canoniche non sono più univoche quando l'insieme delle dipendenze funzionali è ciclico.
Esempio 4
Consideriamo le misure
ed
i cui valori sono derivabili l'una dell'altra. Avremo quindi un ciclo di dipendenze funzionali composto da
e
. Consideriamo ora una misura
che può essere derivata da
e da
. A questo punto, abbiamo un insieme
di dipendenze funzionali
, ed è facilmente dimostrabile che
e
sono entrambe coperture canoniche di
.
E' necessario quindi dimostrare la possibilità di determinare in maniera univoca la forma ridotta per gli schema graph anche in presenza di dipendenze funzionali cicliche [Lec04].
Consideriamo uno schema graph
, dove
non è né ciclica né canonica. La relazione
su
, definita come:

se
per
è una relazione di equivalenza.
viene utilizzata per denotare l'insieme delle classi di equivalenza indotte da
su
. Consideriamo quindi il grafo aciclico orientato dove ciascun nodo è una classe di equivalenza
ed un arco va da
ad
, con
, se esistono degli attributi
tali che
.
La riduzione transitiva di questo grafo è lo schema graph aciclico equivalente per S e denominato da
.
è aciclico (data la sua costruzione) ed univocamente determinato (dato che la riduzione transitiva è univoca per i grafi aciclici). Sia ora
un ordinamento totale su
(specificato dall'utente o generato dal sistema su alcuni criteri di ordinamento come il timestamp di creazione dell'attributo o il nome dell'attributo).
Definizione 17 (Schema Graph Ridotto)
Sia
uno schema graph ed
sia lo schema graph aciclico equivalente per
.
Lo schema graph ridotto per
è il grafo orientato
, dove
Da [AGU72,Lec04] sappiamo che lo schema graph ridotto
per
è una riduzione transitiva univocamente determinata per
, ed
è una copertura canonica per
. D'ora in avanti, dato un insieme F di dipendenze funzionali semplici, useremo
per denotare l'operatore di riduzione che produce la copertura canonica univocamente determinata
di
, secondo la definizione 17.
Esempio 5
Consideriamo lo schema graph
nella figura 4.6, dove Part ha una proprietà equivalente PartDescr ed i costi di spedizione sono espressi in Euro, Lire e Marchi. La forma ridotta per
, basata sull'ordinamento totale indotto dai nomi degli attributi, è mostrato nella figura 4.7.
Figura 4.7:
Forma ridotta per lo schema schema graph
|
Next: Proiezione sugli schema graph
Up: Rappresentazione formale degli schemi
Previous: Schema graph
Indice
Indice analitico
Alessandro Ronchi
2005-07-16