next up previous contents index
Next: Versioni Up: Un approccio al versioning Previous: Proiezione sugli schema graph   Indice   Indice analitico


Algebra delle modifiche degli schemi

Come abbiamo visto nelle soluzioni presentate fino ad oggi per la gestione del versioning nei data warehouse, è necessario prima di tutto stabilire un'algebra delle operazioni di modifica, affinché si possano calcolare sulla base di questo insieme di operazioni di base tutte le operazioni possibili. L'introduzione di una rappresentazione dei cubi multidimensionali basata su grafi orientati ci permette di semplificare considerevolmente l'insieme delle operazioni di base: $ \mathtt{Add_A}, \mathtt{Del_A}, \mathtt{Add_F}, \mathtt{Del_F}$, rispettivamente per aggiungere un attributo ed eliminarlo, aggiungere una dipendenza funzionale semplice ed eliminarla. Per ognuna di queste operazioni definiremo gli effetti sullo schema graph, che d'ora in avanti considereremo sempre nella sua forma ridotta, utilizzando i termini schema graph ed schema graph ridotto indistintamente.

In aggiunta alle quattro operazioni appena introdotte, assumiamo che ci sia una operazione per creare uno schema iniziale $ S = (\{E\}, \emptyset)$, che contiene solo il fact node, ed una che permette di cancellare uno schema esistente.

Sia $ S=(\hat{U}, F)$ uno schema graph. Per ciascuna operazione di modifica $ M(Z)$ (dove $ M$ è $ \mathtt{Add_A}$ o $ \mathtt{Del_A}$ e $ Z$ è un attributo, oppure $ M$ è $ \mathtt{Add_F}$ o $ \mathtt{Del_F}$ e $ Z$ è una dipendenza funzionale. Definiamo il nuovo schema $ \mathtt{New}(S,M(Z))$ ottenuto applicando $ M(Z)$ sullo schema corrente $ S$.

Definizione 18   Sia $ S=(\hat{U}, F)$ uno schema graph ridotto, ed $ A$ un attributo. Allora:

$\displaystyle \mathtt{New}(S,\mathtt{Add_A}(A)) := (\hat{U}\cup \{A\}, (F \cup \{E \to A\})^-)$

Nella definizione 18 non distinguiamo i casi in cui $ A$ sia già presente o meno in $ S=(\hat{U}, F)$. Infatti se $ A$ è già presente in $ S$ lo schema risultante rimarrà invariato, mentre se non lo è verrà direttamente connesso attraverso un arco al fact node $ E$. 4.2

Al momento dell'inserimento il progettista dovrà specificare se questo attributo è una proprietà o una misura. Queste informazioni verranno registrate nei meta-dati.

Definizione 19   Sia $ S=(\hat{U}, F)$ uno schema graph ridotto, e sia $ A \in U$ un attributo. Allora:

$\displaystyle \mathtt{New}(S,\mathtt{Del_A}(A)) :=
(\hat{U}\setminus \{A\}, \pi_{\hat{U}\setminus \{A\}}(F)^-)$

Quindi, secondo il teorema 1 la cancellazione di una attributo $ A$ è definita rimuovendo $ A$ e mantenendo le dipendenze funzionali che non coinvolgono $ A$ attraverso la proiezione $ \pi$

Definizione 20   Sia $ S=(\hat{U}, F)$ uno schema graph ridotto, ed $ f = A_1 \to A_2$ una dipendenza funzionale che coinvolge almeno un attributo in $ U$. Allora avremo:

$\displaystyle \mathtt{New}(S,\mathtt{Add_F}(f)) := (\hat{U}, (F \cup \{f\})^-)$

Bisogna notare che l'introduzione di una nuova dipendenza funzionale può introdurre ridondanze, che vengono rimosse attraverso la riduzione ``$ -$''.

Definizione 21   Sia $ S=(\hat{U}, F)$ uno schema graph ridotto, ed $ f = A_1 \to A_2$ una dipendenza funzionale già esistente in $ F$, dove $ A_1 \neq E$. Sia
$\displaystyle F'$ $\displaystyle =$ $\displaystyle F \setminus \{f\}$  
    $\displaystyle {}\cup \{A_0 \to A_2 \: \mid \:{} (\exists A_0 \in \hat{U}) \;
A_0 \to A_1 \in F\}$  
    $\displaystyle {}\cup \{A_1 \to A_3 \: \mid \:{} (\exists A_3 \in U) \;
A_2 \to A_3 \in F\}$  

Allora:

$\displaystyle \mathtt{New}(S,\mathtt{Del_F}(f)) := (\hat{U}, (F')^-)$

La definizione 21 afferma che la dipendenza funzionale $ f = A_1 \to A_2$ viene eliminata attraverso la differenza degli insiemi. Successivamente vengono inserite in $ F$ tutte le dipendenze funzionali che determinano $ A_1$ e tutte le dipendenze funzionali che partono da $ A_1$. Questa definizione permette di gestire qualsiasi operazione di cancellazione di dipendenze funzionali semplici, senza nessuna perdita di informazioni importanti implicitamente connesse a quella che stiamo eliminando dallo schema.

Esempio 6   La sequenza delle operazioni applicate ad $ S_0$ per arrivare ad $ S_1$ è $ \mathtt{Del_A}(\texttt{Date}),\\
\mathtt{Add_A}(\texttt{SubCategory}),
\matht...
...ct}\to\texttt{Nation}),\\
\mathtt{Del_F}(\texttt{Terms}\to\texttt{Incentive})
$ In particolare, gli schema graph ridotto risultanti per la gerarchia della dimensione Part dopo ciascuna operazione nella seconda linea sono mostrate nella figura 4.8: (a) mostra lo schema graph dopo l'inserimento del nuovo attributo SubCategory, (b) dopo l'inserimento del nuovo arco Type $ \to$ SubCategory, e (c) dopo l'inserimento del nuovo arco SubCategory $ \to$ Category

Figura 4.8: Schema Graph ridotto per la gerarchia della dimensione Part dopo le operazioni di modifica.
La sequenza delle operazioni applicate ad $ S_1$ per arrivare ad $ S_2$ è: $ \mathtt{Add_A}(\texttt{PartDescr}),
\mathtt{Add_F}(\texttt{Part}\to\texttt{Pa...
...LIT}),\\
\mathtt{Add_F}(\texttt{ShippingCostsLIT}\to\texttt{ShippingCostsDM})
$

Possiamo quindi dimostrare che le definizioni 18-21 formalizzano il risultato atteso per le modifiche degli schemi, ed in particolare che queste operazioni di modifica sono chiuse sugli schema graph.

Teorema 2   Sia $ S=(\hat{U}, F)$ uno schema graph ridotto.
  1. Sia $ (\hat{U}', F') = \mathtt{New}(S,\mathtt{Add_A}(A))$. Allora $ A \in \hat{U}'$.
  2. Sia $ (\hat{U}', F') = \mathtt{New}(S,\mathtt{Del_A}(A))$. Allora $ A \notin \hat{U}'$.
  3. Sia $ (\hat{U}', F') = \mathtt{New}(S,\mathtt{Add_F}(f))$. Allora $ f \in F'^+$.
  4. Sia $ (\hat{U}', F') = \mathtt{New}(S,\mathtt{Del_F}(f))$. Allora $ f \notin F'^+$.
In aggiunta, in tutti questi casi $ (\hat{U}', F')$ è uno schema graph ridotto.

Dimostrazione:La (1), (2), e la (3) sono dirette conseguenze delle definizioni 18, 19, e 20, rispettivamente. La (4) è conseguente dalla definizione 21, osservando che $ F$ è canonica e quindi in particolare è non ridondante. Rimane da dimostrare che $ (\hat{U}', F')$ è uno schema graph ridotto, cioè che: (a) $ F'$ è un insieme di dipendenze funzionali semplici (b) $ E$ ha solo archi in uscita ed esiste un percorso da $ E$ a ciascun attributo di $ \hat{U}'$ (c) $ (\hat{U}', F')$ è in forma ridotta. Per $ \mathtt{Add_A}$, $ \mathtt{Add_F}$, e $ \mathtt{Del_F}$, (a) e (b) sono banali. Per $ \mathtt{Del_A}$, (a) e (b) sono conseguenti dal teorema 1. Per tutte le quattro operazioni, (c) dipende direttamente dalla definizione dell'operatore di riduzione ``$ -$''.

Questo teorema è necessario per dimostrare che le operazioni di modifica che abbiamo appena definito portano a schemi validi e viene garantita la produzione di risultati non ridondanti ed univocamente determinati.


next up previous contents index
Next: Versioni Up: Un approccio al versioning Previous: Proiezione sugli schema graph   Indice   Indice analitico
Alessandro Ronchi 2005-07-16