next up previous contents index
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:

Definizione 14 (Chiusura Transitiva)   Sia $ U$ un insieme di attributi, ed $ F$ un insieme di FD semplici su $ U$. La chiusura transitiva di $ F$, denominata $ F^*$, è definita in maniera induttiva come segue:
  1. $ f \in F \Longrightarrow f \in F^*$
  2. $ A \to B \in F^* \: \wedge \:B \to C \in F^* \Longrightarrow A \to C \in F^*$

Definizione 15 (Riduzione Transitiva)   Sia $ U$ un insieme di attributi, ed $ F$ un insieme di FD semplici su $ U$. La riduzione transitiva di $ F$ è l'insieme minimo $ F^-$ di FD semplici su $ U$ tale che $ F^* = (F^-)^*$.

Per illustrare le differenze tra la chiusura transitiva $ F^*$ e la chiusura $ F^+$ delle dipendenze funzionali $ F$, osserviamo che la definizione di $ F^*$ contiene solo FD semplici. Se le FD in F coinvolgono due o più attributi allora $ F^+$ contiene delle dipendenze funzionali non semplici addizionali che sono implicite in $ F^*$.

Esempio 3  

Per $ F = \{ A \to B, B \to C \}$ abbiamo:

$\displaystyle F^*$ $\displaystyle =$ $\displaystyle \{ A \to B, B \to C, A \to C \}$  
$\displaystyle F^+$ $\displaystyle =$ $\displaystyle \{ A \to B, B \to C, A \to C,$  
    $\displaystyle \; A \to A, AB \to A, AC \to A, ABC \to A,$  
    $\displaystyle \; B \to B, AB \to B, AC \to B, BC \to B, ABC \to B,$  
    $\displaystyle \; C \to C, AB \to C, AC \to C, BC \to C, ABC \to C
\}$  

Come visto in [AGU72], nel caso dei grafi aciclici la riduzione transitiva $ F^-$ è univocamente determinata ed $ F^- \subseteq F$. Oltre a questo, ricordiamo che $ F^-$ è una copertura canonica di $ F$, da [Lec04], quindi se $ F$ è aciclico lo schema graph ridotto per $ S=(\hat{U}, F)$ è $ S^-=(\hat{U}, F^-)$.

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:

L'esempio seguente dimostra che le coperture canoniche non sono più univoche quando l'insieme delle dipendenze funzionali è ciclico.

Esempio 4   Consideriamo le misure $ A_1$ ed $ A_2$ i cui valori sono derivabili l'una dell'altra. Avremo quindi un ciclo di dipendenze funzionali composto da $ A_1 \to A_2$ e $ A_2 \to A_1$. Consideriamo ora una misura $ A_3$ che può essere derivata da $ A_1$ e da $ A_2$. A questo punto, abbiamo un insieme $ F$ di dipendenze funzionali $ \{A_1 \to A_2, A_2 \to A_1, A_1 \to A_3, A_2 \to A_3\}$, ed è facilmente dimostrabile che $ \{A_1 \to A_2, A_2 \to A_1, A_1 \to A_3\}$ e $ \{A_1 \to A_2, A_2 \to A_1, A_2 \to A_3\}$ sono entrambe coperture canoniche di $ F$.

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 $ S=(\hat{U}, F)$, dove $ F$ non è né ciclica né canonica. La relazione $ \equiv_F$ su $ \hat{U}$, definita come:

$\displaystyle A \equiv_F B$       se     $\displaystyle A \to B \in F^+ \: \wedge \:B \to A \in F^+$

per $ A,B \in \hat{U}$ è una relazione di equivalenza. $ \hat{U}/_{\equiv_F}$ viene utilizzata per denotare l'insieme delle classi di equivalenza indotte da $ \equiv_F$ su $ \hat{U}$. Consideriamo quindi il grafo aciclico orientato dove ciascun nodo è una classe di equivalenza $ X \in \hat{U}/_{\equiv_F}$ ed un arco va da $ X$ ad $ Y$, con $ X \neq Y$, se esistono degli attributi $ A \in X, B \in Y$ tali che $ A \to B \in F$. La riduzione transitiva di questo grafo è lo schema graph aciclico equivalente per S e denominato da $ S^a=(\hat{U}/_{\equiv_F}, F^a)$. $ S^a$ è aciclico (data la sua costruzione) ed univocamente determinato (dato che la riduzione transitiva è univoca per i grafi aciclici). Sia ora $ <_S$ un ordinamento totale su $ \hat{U}$ (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 16 (Dipendenze Funzionali Implicite)   Sia $ \hat{U}$ un insieme di attributi per i quali esiste un ordinamento totale $ <_S$, $ F$ un insieme (eventualmente ridondante e/o ciclico) di dipendenze funzionali semplici su $ \hat{U}$, ed $ X = \{A_1, \ldots, A_n\} \in \hat{U}/_{\equiv_F}$, $ n \geq 1$. Sia $ A_1 <_S A_2 <_S \ldots <_S A_n$ l'ordinamento degli attributi in $ X$ ottenuti con $ <_S$. Le dipendenze funzionali implicite (dato $ <_S$) sono date da $ F_X = \{A_1 \to A_2, A_2 \to A_3, \ldots, A_{n-1} \to A_n, A_n \to A_1\}$.

Definizione 17 (Schema Graph Ridotto)   Sia $ S=(\hat{U}, F)$ uno schema graph ed $ S^a=(\hat{U}/_{\equiv_F}, F^a)$ sia lo schema graph aciclico equivalente per $ S$. Lo schema graph ridotto per $ S$ è il grafo orientato $ S^-=(\hat{U}, F^-)$, dove

$\displaystyle F^- = \bigcup_{X \to Y \in F^a} \left\{ \min X \to \min Y \right\}
\cup \bigcup_{X \in \hat{U}/_{\equiv_F}} F_X.$

Da [AGU72,Lec04] sappiamo che lo schema graph ridotto $ S^-=(\hat{U}, F^-)$ per $ S$ è una riduzione transitiva univocamente determinata per $ S$, ed $ F^-$ è una copertura canonica per $ F$. 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 $ F^-$ di $ F$, secondo la definizione 17.

Esempio 5   Consideriamo lo schema graph $ S_2$ 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 $ S_2$, basata sull'ordinamento totale indotto dai nomi degli attributi, è mostrato nella figura 4.7.

Figura 4.7: Forma ridotta per lo schema schema graph $ S_2$


next up previous contents index
Next: Proiezione sugli schema graph Up: Rappresentazione formale degli schemi Previous: Schema graph   Indice   Indice analitico
Alessandro Ronchi 2005-07-16