next up previous contents index
Next: Schema graph ridotto Up: Rappresentazione formale degli schemi Previous: Dipendenze funzionali semplici   Indice   Indice analitico


Schema graph

Per analizzare il problema del versioning nei data warehouse, dobbiamo introdurre una rappresentazione per gli schemi sulla quale definire le operazioni di modifica. Nel capitolo precedente abbiamo visto alcune rappresentazioni delle dimensioni, chiamate rispettivamente schema delle dimensioni [LHV02] (figura 3.6) e versione di struttura [EK01] (figura 3.7). Queste due rappresentazioni grafiche hanno il limite di non modellare il fatto e le misure (semplici o derivate), e per definizione rappresentano solamente dimensioni i cui grafi sono aciclici. Introduciamo quindi una nuova rappresentazione basata sui grafi, chiamata Schema Graph, che cattura le informazioni chiave dei modelli multidimensionali (come ad esempio il DFM). In maniera intuitiva, in coerenza con [LV03], uno schema data warehouse è un grafo orientato, dove i nodi sono attributi (sia proprietà che misure), e gli archi rappresentano le dipendenze funzionali semplici di una copertura canonica. La rappresentazione degli schemi dei data warehouse in termini di grafi ci permette di definire le modifiche agli schemi attraverso le quattro operazioni di modifica dei grafi:

  1. Aggiunta di un nodo (attributo)
  2. Rimozione di un nodo (attributo)
  3. Aggiunta di un arco (dipendenza funzionale)
  4. Rimozione di un arco (dipendenza funzionale)

Questo modello ci permette di semplificare l'analisi degli schemi, grazie ad una visualizzazione intuitiva e confortevole.

Definiamo quindi in maniera formale gli Schema Graph:

Definizione 13 (Schema Graph)   Uno schema graph è un grafo orientato $ S=(\hat{U}, F)$ con nodi $ \hat{U}=\{E\} \cup U$ ed archi $ F$, dove
  1. $ E$ è chiamato fact node e rappresenta il fatto di interesse. Le sue istanze sono i singoli eventi che sono stati registrati, cioè le singole tuple della tabella del fatto (fact table);

  2. $ U$ è un insieme di attributi (incluse le proprietà e le misure);

  3. $ F$ è un insieme di FD semplici definite su $ \{E\} \cup U$ nello schema del data warehouse;

  4. $ E$ ha solo archi in uscita, ed esiste un percorso che parte da $ E$ e termina in ciascun attributo in $ U$.
$ S$ è chiamato schema graph canonico se $ F$ è canonico.

Gli schema graph canonici per il fatto shipment della figura 4.1 sono mostrati nelle figure 4.44.54.6. Come possiamo vedere anche dagli esempi, ogni schema graph rappresenta una versione, a differenza delle versioni di struttura introdotti in [EK01]. Archi e nodi, quindi, non vengono etichettati con gli intervalli di validità, perché questi sono già determinati dalla definizione della versione corrispondente al grafo, che vedremo successivamente.

Figura 4.4: Schema graph $ S_0$

Figura 4.5: Schema graph $ S_1$

Figura 4.6: Schema graph $ S_2$

Gli schema graph così definiti soddisfano l'Universal Relation Schema Assumption (URSA) [Mai83], che è una assunzione standard nella progettazione dei database relazionali. L'URSA connette il nome di un attributo alla sua semantica, cioè stabilisce che all'interno dell'insieme degli schema graph che descrivono lo schema del data warehouse tutte le occorrenze del nome di un attributo hanno obbligatoriamente lo stesso significato. Nel nostro esempio, quindi, i due differenti concetti rappresentati dal tipo di componenti e dal tipo di vendita sono dichiarati attraverso due nomi distinti (Type ed SType). D'altra parte è possibile che un attributo appaia con lo stesso nome in versioni diverse dello stesso schema o in schemi diversi, se modella lo stesso concetto.

Infine dobbiamo far notare che, in riferimento al modello multidimensionale, una dipendenza funzionale $ f \in F$ ha un impatto sulla semantica degli attributi, nella maniera seguente:

  1. $ f = E \to A$

  2. $ f= B \to A$

Detto questo, risulta chiaro che dalla rappresentazione grafica appena introdotta non sia possibile stabilire se un attributo sia (1) una dimensione o una misura, oppure (2) una proprietà o una misura derivata. Sarà quindi necessario salvare queste informazioni nel deposito dei meta-dati, come vedremo in seguito.


next up previous contents index
Next: Schema graph ridotto Up: Rappresentazione formale degli schemi Previous: Dipendenze funzionali semplici   Indice   Indice analitico
Alessandro Ronchi 2005-07-16