Progetto e realizzazione di un linguaggio di interrogazione visuale per dati multidimensionali

 6
nasceva la necessità di aggregare i dati per analizzare meglio la situazione 
in esame e per eseguire, di conseguenza, le analisi. 
Per tale motivo esiste una forte correlazione tra dati, informazioni, 
conoscenza e decisioni; il problema, dunque, si può esprimere chiedendosi 
come passare dai dati alle informazioni, ottenere la conoscenza, per poi 
arrivare alle decisioni; il tutto attraverso un processo d’aggregazione degli 
stessi dati. Il Data Warehousing insieme alle applicazioni On-Line 
Analytical Processing (OLAP) ed alle tecniche di Data Mining rappresenta 
la soluzione a tutto ciò, nel senso che il data warehousing rappresenta la 
soluzione più idonea per arrivare alle decisioni, cosa che i tradizionali 
DBMS supportano con maggiore difficoltà. Tale transizione, se si fa 
riferimento a [Mar90], si può schematizzare attraverso il diagramma, 
mostrato in figura 1.1, dove il data warehousing supporta l’utente, nella 
fattispecie il decision maker, nelle fasi centrali dell’elaborazione del dato 
che si trasforma in un’informazione proficua. 
Se alle informazioni si associano delle regole, si riescono a realizzare 
processi inferenziali attraverso i quali si può costruire la conoscenza. Le 
informazioni e la conoscenza, a loro volta, possono essere associate a 
modelli computazionali dai quali é possibile trarre comprensione. La 
comprensione associata a modelli valutativi può supportare la decisione. 
 7
  
 
Figura 1.1. Processo decisionale partendo da dati disaggregati 
 
L’ambiente data warehouse è, essenzialmente, destinato ai decision 
makers che, come sappiamo non hanno profonda familiarità con 
l’information technology, e che quindi necessitano di essere assistiti sia 
attraverso un modello di dati semplici ed intuitivo, sia con un linguaggio di 
interrogazione naturale e soprattutto non procedurale. 
Molte delle problematiche che hanno dato origine al data warehousing 
erano presenti, già, dai primi anni ’80, e caratterizzavano l’ambiente dei 
database statistici e scientifici; la notorietà del data warehouse è stata 
dovuta, principalmente, all’utilizzo di questi ultimi in altri ambienti che 
non erano quelli per cui i database statistici erano stati destinati ed 
utilizzati, ovvero per studi socio-economici, per studi di censimento, 
Dati
Conoscenza
Comprensione
Decisioni
Aggregazione 
Regole 
Modelli Valutativi 
Modelli Computazionali 
Data 
Warehousing 
OLAP 
Data Mining 
Informazioni
 8
modelli di consumo, e così via. Quando si ebbe la necessità di trasformare 
un tradizionale DBMS in un sistema più complesso, come quello di un data 
warehouse, si ci rese conto che molto della ricerca effettuata sui database 
statistici era decisamente valida per il problema del data warehousing. 
Quindi possiamo dire, se ci è concesso, che il “padre” del data 
warehouse è il database statistico (SDB); per gli SDB, bisogna dire che ci 
sono, fondamentalmente, tre aree di ricerca in cui sono coinvolti i database 
statistici: 

Area del modeling logico e concettuale, nonché 
dell’interrogazione; 

Area dell’organizzazione fisica; 

Area della sicurezza. 
A loro volte queste aree possono suddividersi in sottoaree, ma il mio 
obiettivo è presentare lo studio sugli SDB in maniera sintetica senza entrare 
troppo nel dettaglio.  
Il lavoro, in questa tesi, si focalizzerà sul primo punto, in modo 
particolare, sull’area dell’interrogazione. La tesi si compone di cinque 
capitoli.  
Il nostro studio si occuperà, nel secondo capitolo, di esporre lo stato 
dell’arte dei database statistici che, a mio avviso, rappresentano un ottimo 
background per affrontare il problema del data warehousing; infatti, in 
questo capitolo, si descrivono le peculiarità e gli aspetti più rilevanti, 
facendo riferimento a diversi articoli, tra i quali [Sho82] e [ShoWon85] ne 
costituiscono il riferimento più importante. La differenza principale tra le 
basi di dati statistiche e quelle tradizionali sta principalmente nella 
differenziazione del tipo di dato (categoria, sommario). Vengono 
presentati, poi, in rassegna diversi modelli logici e concettuali, quelli più 
rappresentativi, che hanno caratterizzato le basi dati statistiche. Due diversi 
metodi hanno distinto, principalmente, l’evoluzione di tali modelli, quello 
 9
relativo all’estensione dei modelli esistenti e quello relativo alla creazione 
di nuovi modelli, tipicamente grafici. La descrizione dei modelli si 
conclude con ADAMO [BeRT96b] che risulta essere quello più completo 
dal punto di vista semantico ed, inoltre, costituisce la base sul quale 
formalizzeremo il nostro modello. Inoltre, in questo capitolo vengono 
presentati i principali metodi relativi all’organizzazione fisica dei dati 
statistici, in modo particolare verrà affrontato il problema della 
materializzazione delle viste ed oggetto, tuttora, di accurati studi 
[GupMun95].  
Il capitolo si conclude lo studio delle analogie e delle differenze tra 
una base dati statistica e l’OLAP che può essere definito come 
l’elaborazione di dati strutturati in forma statistica, ma quando essi fanno 
riferimento a dati descriventi concetti di natura business (vendite, 
produzione, …) e con la presentazione dei modelli multidimensionali, 
essenzialmente modelli concettuali, che a differenza dei modelli 
tradizionali (ad esempio E-R), permettono di descrivere in modo più 
completo gli oggetti presenti in una base dati destinata ad essere utilizzata 
in un ambiente data warehouse. 
Il terzo capitolo costituisce la parte più importante del lavoro, infatti 
viene presentato il modello ADaS+ e la sua algebra, sul quale, poi, si 
baserà il prototipo descritto nell’ultimo capitolo; tale modello rappresenta 
un’evoluzione del modello ADaS [BeRT96] e rispetto ai modelli 
multidimensionali si differenzia da questi, perché è caratterizzato da 
macrodati ed effettua una distinzione tra dimensioni e misure, elementi che 
hanno luogo da processi molto diversi. Viene, inoltre, mostrato il rapporto 
tra il nostro modello ed il data warehouse, in modo particolare, la sua 
collocazione in un’architettura data warehousing. 
Nel quarto capitolo viene presentato il linguaggio associato al modello 
ADaS+ ed ai suoi operatori definito Multidimensional Query Language; 
 10
tale linguaggio può essere classificato come uno pseudo-SQL, 
caratterizzato da un insieme ridotto di istruzioni e da una sintassi semplice, 
adatto, soprattutto, nel supportare l’OLAP, anche se nell’effettiva 
implementazione tutti i controlli relativi alla sintassi sono gestiti, 
automaticamente, dal prototipo. 
Nell’ultimo capitolo viene presentato il prototipo, realizzato con un 
linguaggio object-oriented come Java, che si interfaccia con una base dati 
creata e mantenuta attraverso il DBMS Oracle, nella quale sono contenuti i 
dati (gli oggetti multidimensionali) destinati alle interrogazioni. La parte 
più importante del prototipo è quella che permette la creazione ed 
esecuzione delle interrogazioni (query), infatti queste ultime sono realizzate 
tramite un’interfaccia molto intuitiva, mentre l’effettiva esecuzione avviene 
nel “motore” (engine) scritto in linguaggio PL/SQL ed eseguito all’interno 
del server di Oracle attraverso quelle che si chiamano store procedures. 
La tesi si conclude con un capitolo in cui si propongono sviluppi 
futuri, anche, alla luce di ciò che è stato fatto nella ricerca nei modelli 
multidimensionali, nell’OLAP e nelle tecniche di data warehousing. 
 
 
 
 
 
 
 
 
 
 
 
 
 11
 
 
2.1 Le Basi di Dati Statistiche 
 
Le basi di dati statistiche (SDB), [Sho82] [ShoWon85], possono 
essere descritte in termini del tipo di dato che esse contengono e dal loro 
uso. Esse contengono sia dati descrittivi (attributi di categorie) che dati di 
misura (variabili) associati a tali attributi. Gli SDB sono spesso utilizzati 
per analisi statistiche; infatti, un processo d’analisi coinvolge la selezione 
di tuple utilizzando delle condizioni sugli elementi descrittivi, poi avviene 
la selezione di diverse variabili per effettuare, appunto, l’analisi. 
Quest’ultima può coinvolgere sia operazioni statistiche elementari (Min, 
Max, Media, Somma, Conta) che operazioni complesse (Regressione 
Multipla, Deviazione Standand, Covarianza). 
Il processo di analisi statistica si può dividere in tre fasi: la prima fase 
corrisponde ad un’operazione di controllo o checking, caratterizzata 
dall’individuazione di probabili errori o di valori atipici che, ad ogni modo, 
risultano essere validi, attraverso il controllo di istogrammi e la verifica di 
integrità dei vincoli sui parametri; la seconda fase corrisponde ad 
un’operazione di esplorazione, nella quale si determinano le distribuzioni 
delle variabili e le loro relazioni, ciò avviene attraverso la scelta di 
campioni di dati, la selezione di record e la creazione di insieme di dati 
temporanei; la terza ed ultima fase corrisponde ad un’operazione di 
conferma nella quale l’analista controlla le distribuzioni ipotizzate (che 
sono basate sulle osservazioni fatte nella fase precedente) sulla base dati e 
2. Lo stato dell’arte 
 12
sulle relazioni tra le variabili. Questo processo può essere eseguito molte 
volte finché non si ottengono dei risultati soddisfacenti. 
Ci sono tre principali ragioni per cui i tradizionali sistemi di gestione 
dei dati sono inadeguati alla gestione degli SDB, anche se, a prima vista, 
questa problematica non sembra apparire. Per mostrare l’inadeguatezza si 
pensi ad un database contenente le informazioni relative ad un censimento; 
questo database sarà caratterizzato da una mole enorme di dati (migliaia di 
megabyte) e le tradizionali operazioni, se questo database fosse realizzato 
con le tecniche convenzionali (relazionale), sarebbero, in sostanza, 
inapplicabili nel momento in cui si effettua un semplice join, questo perché 
il tempo necessario all’esecuzione dell’operazione sarebbe, sicuramente, 
inaccettabile per l’analista. Quindi, la prima ragione è dovuta al fatto che 
sono necessarie grandi quantità di memoria di massa per conservare i dati 
in un SDB, da cui discende l'inefficienza delle tecniche di accesso per 
questi database. Inoltre questi database hanno un alto grado di ridondanza e 
contengono dati sparsi (di solito addensati lungo la diagonale principale di 
una matrice multidimensionale) e potranno, quindi, beneficiare di tecniche 
di compressione e/o di metodi di organizzazione delle informazioni più 
idonei.  
Il secondo motivo legato all’inadeguatezza dei sistemi tradizionali alla 
gestione di un SDB deriva dall’osservazione che i sistemi attuali sono 
realizzati per supportare un alto volume di transazioni tipiche dei sistemi 
OLTP (On Line Transactional Processing) caratterizzati, quasi sempre, 
dalla possibilità di accedere in modo concorrente ai dati (la gestione della 
concorrenza, in un ambiente OLTP, è un fattore fondamentale, si pensi, ad 
esempio, ad un sistema per la prenotazione di biglietti aerei). 
Il terzo motivo discende dall’osservazione che i sistemi attuali di 
gestione dei dati presentano una funzionalità analitica ridotta, dovuta, 
principalmente, al fatto che tali sistemi presentano funzioni statistiche 
 13
molto limitate, come ad esempio somma, max e media ed, inoltre, 
impongono l’utilizzo di complessi linguaggi di interrogazione.  
Un SDB, invece, è caratterizzato da funzioni statistiche complesse e 
da un overhead, comunque, inferiore a quello di un sistema OLTP, 
soprattutto per ciò che riguarda la concorrenza. 
Vi sono poi altre problematiche non meno importanti come la gestione 
dell’eterogeneità delle basi di dati, quando queste ultime sono 
implementate su diversi DBMS (relazionale, gerarchico, reticolare ed 
multidimensionale) con la conseguenza che non si adotta una convenzione 
comune per la scelta dei nomi (il problema del naming), per il formato dei 
dati, per la descrizione e la strutturazione degli stessi dati ed, infine, per la 
presenza di linguaggi d’interrogazione diversi. 
La caratteristica predominante negli SDB è, come abbiamo visto, 
quella delle suddivisione delle informazioni in due tipi di dati: categorie e 
misure, cosa che non accade nei tradizionali sistemi di gestione dei dati 
dove il dato è rappresentato, ad esempio, da relazioni le cui colonne 
rappresentano gli attributi (modello relazionale). Sia i dati di categoria che i 
dati di misura sono descritti in termini di attributi. La ragione per questa 
distinzione è dovuta al fatto che gli attributi di categoria rappresentano la 
descrizione dei dati misurati, mentre gli attributi di misura, spesso indicati 
come attributi di sommario, contengono i dati ai quali sono applicate le 
operazioni statistiche. 
Bisogna notare, in primo luogo, che per ogni valore degli attributi di 
sommario vi è una combinazione d’attributi di categoria, cioè gli attributi 
di categoria sono utilizzati come chiave composita per gli attributi di 
sommario. In secondo luogo, emerge, chiaramente, una notevole 
ridondanza per i valori degli attributi di categoria ed in alcuni casi, quando 
esistono tutte le possibili combinazioni degli stessi, ogni valore di un 
attributo di categoria deve essere ripetuto tante volte quanto il prodotto 
 14
della cardinalità dei rimanenti attributi. Una terza considerazione nasce dal 
fatto che la cardinalità del dominio caratterizzante gli attributi di categoria 
è tipicamente piccola, in contrasto con gli attributi di sommario che, 
spesso, hanno un intervallo molto più ampio dovuto al fatto che, quasi 
sempre, rappresentano misure di tipo numerico. 
Una diretta conseguenza nell’adottare la caratterizzazione dei due tipi 
di attributi porta qualche volta, nel momento in cui si realizza un SDB, 
visto per semplicità in forma di matrice, a combinazioni degli attributi di 
categoria che non hanno un corrispettivo elemento negli attributi di 
sommario; ciò dà origine a matrici sparse. In questo caso si utilizzano 
particolari tecniche di compressione, oppure si rimuovono dal database gli 
elementi associati solo ai valori nulli. 
Un’operazione molto comune nell’analisi e nell’elaborazione dei 
valori di sommario di un SDB è quella di ridurre il numero di attributi di 
categoria aggregando i valori di sommario associati alle istanze di quegli 
attributi che non sono di interesse per l’analisi statistica. Inoltre, in 
corrispondenza di quegli stessi valori di sommario oggetto 
dell’aggregazione i restanti attributi di categoria presentano i valori 
medesimi. In questo modo si riduce la cardinalità della tabella statistica. 
Tra le caratteristiche da considerare, ancora, vi è quella della stabilità, 
infatti la maggior parte degli SDB sono statici, nel senso che un database di 
questo genere non è soggetto ad operazioni di aggiornamento. Ciò significa 
che una volta che il dato è raccolto esso verrà solo utilizzato per eseguire 
analisi, ma raramente sarà oggetto di aggiornamenti che potrebbero 
modificare la struttura delle tabelle con il relativo ricalcolo da parte del 
sistema per i valori di sommario. La staticità degli SDB è un beneficio dal 
momento che molti problemi che caratterizzano le normali basi di dati 
nascono da numerosi aggiornamenti, che richiedono algoritmi per il 
controllo della concorrenza e che in tale contesto possono essere evitati. 
 15
L’ultima caratteristica dei database statistici, comune anche in altri tipi 
di basi di dati, si presenta quando un database è caratterizzato da un  
numero elevato di attributi (dell’ordine delle centinaia). Infatti, in questi 
casi, quando si formula un’interrogazione, l’utente, oltre a tenere conto 
della sintassi del linguaggio d’interrogazione, dovrà considerare, anche, i 
nomi degli insiemi di dati (o relazioni), i nomi degli attributi, i possibili 
valori legati a tali attributi ed anche il formato dei valori. Questo fenomeno 
viene definito proliferazione dei termini. A tal proposito si presenta la 
necessità di un tool che permetta di gestire un numero così elevato di 
attributi in modo che l’analista sia facilitato nel processo di analisi. 
Inoltre le difficoltà, legate alla gestione di un numero elevato di 
attributi, sono più evidenti negli SDB perché, in primo luogo, la definizione 
delle categorie, spesso, è oggetto di modifiche od alterazioni molto più che 
nelle basi dati tradizionali; si pensi, ad esempio, alle contee negli Stati 
Uniti che pur cambiando i loro confini mantengono i loro nomi. In secondo 
luogo, la creazione di nuovi valori di sommario, comporta introduzione di 
nuove categorie oppure l’uso di categorie esistenti, ma con nuovi 
significati; è necessario, quindi, controllare questa proliferazione di nomi e 
tenere traccia di quelli già presenti nel sistema. 
Di tutte le caratteristiche finora presentate, quella più evidente, di un 
database statistico, è la proprietà della multidimensionalità, che influisce 
sulle considerazioni di progetto sia per la gestione fisica sia per quella 
logica dei dati. Mentre in altre applicazioni il concetto di un’entità, cioè di 
qualcosa che esiste ed è distinguibile (ad esempio: impiegati, dipartimenti, 
conti correnti), è comune, negli SDB è più conveniente pensare le entità 
come “casi” che rappresentano le istanze di una simulazione o di un esame, 
e che vengono comunemente rappresentati da un insieme di categorie o 
parametri. Per esempio, i dati sul commercio possono essere identificati in 
termini di paese esportatore, paese importatore, merce, anno e mese; quindi 
 16
si determinano cinque attributi di categoria ed un attributo di sommario. 
Questo dà origine ad un ipercubo di cinque dimensioni. 
La multidimensionalità gioca un ruolo fondamentale sia a livello 
fisico, dove è necessaria la presenza di speciali strutture dati e di metodi 
d’accesso e di compressione particolari, sia a livello logico, dove sono 
necessari speciali modelli, per rappresentare l’aspetto multidimensionale 
del dato, e le corrispondenti interfacce utenti per esprimere in maniera 
corretta le interrogazioni. 
La difficoltà di elaborare lo spazio multidimensionale è ulteriormente 
aggravata dal fatto che ogni dimensione, associata ad una categoria, può 
avere essa stessa una complessa struttura, di solito gerarchica. 
 
2.1.1 Organizzazione fisica e metodi d’accesso. 
 
È evidente che un database statistico necessita di una diversa 
organizzazione fisica e di metodi d’accesso efficienti. Le tecniche più 
importanti, come in [OlRS86], per migliorare sia l’organizzazione sia 
l’accesso vanno da tecniche di compressione sofisticate (che tengono conto 
della particolare distribuzione dei valori non nulli all’interno 
dell’ipercubo), a particolari strutture multidimensionali, quad-tree, K-D 
tree, ad organizzazioni alternative dei file, come i file trasposti, ed infine ad 
una migliore gestione dei buffer nelle operazioni di input/output (I/O). 
 
2.1.2 Operatori caratteristici di un SDB. 
 
Un SDB presenta la necessità di creare nuovi operatori per la sua 
particolare struttura e per le informazioni che contiene. Infatti, gli operatori 
nei tradizionali sistemi di gestione dei dati non hanno quelle proprietà che 
 17
risultano essere indispensabili ad un SDB. Esempi sono il campionamento 
e gli operatori (per strutture dati multidimensionali) come la trasposizione e 
l’aggregazione. Se questi operatori non sono direttamente supportati dal 
DBMS, ciò costringe l’utente a servirsi di quelli disponibili per effettuare 
l’operazione voluta, con una conseguente inefficienza. Ad esempio, se il 
dato è aggregato, allora l’operatore dovrebbe essere applicato direttamente 
sul dato senza compiere alcun processo di disaggregazione, per poi 
riaggregare il tutto una volta che si sono ottenuti i risultati. 
L’operatore più importante è quello di aggregazione applicato quando 
si devono generare dati di sommario da microdati (dati con il livello di 
granularità più basso) oppure quando si devono ridurre le dimensioni di una 
struttura multidimensionale. Oltre, alle funzioni di aggregazione più 
comuni come Max, Min, Somma, Media, Conta, il sistema di gestione degli 
SDB dovrebbe avere anche funzioni più complesse come Mediana, Moda, 
Varianza, Covarianza, implementandole direttamente sui dati aggregati al 
fine di aumentare l’efficienza del sistema. 
Ci sono altri operatori che caratterizzano un database statistico, anche 
se in questo contesto non assumono un’importanza rilevante come quella 
dell’aggregazione, dato che sono destinati maggiormente per database 
scientifici. 
Il primo operatore è quello del campionamento (sampling), anche se, 
spesso, tale operazione viene eseguita a livello di applicazione attraverso 
un package di analisi statistica. In ogni modo, è più efficiente eseguire il 
campionamento dei dati attraverso delle routine d’accesso, dato che solo il 
dato campionato è passato al programma applicativo. Inoltre, 
quest’operazione dovrebbe essere eseguita il più vicino possibile allo stadio 
d’elaborazione delle query.  
Un altro operatore è la ricerca degli elementi più vicini (nearest 
neighbor), per determinare il matching d’eventi statistici. Ci sono, 
 18
principalmente, due tipi di ricerche nearest neighbor. La prima determina il 
punto (o i punti) che sono più vicini rispetto ad un punto dato (riferimento); 
il concetto di vicinanza si esprime tramite la distanza minima tra i punti 
oggetto dell’esame e quello utilizzato come riferimento. La seconda ricerca 
determina tutti i punti all’interno di una circonferenza con centro il punto di 
riferimento ed il raggio fissato a priori; anche in questo caso sono 
necessarie delle tecniche per determinare gli elementi nelle celle 
multidimensionali, e criteri di selezione sugli attributi di categoria.  
Il terzo operatore per l’analisi di un SDB è quello della stima e 
dell’interpolazione, dovuto al problema di determinare stime di valori di 
dati non esistenti. Un esempio nasce dall’utilizzo di dati scientifici che 
descrivono fenomeni fisici, perché in questo caso abbiamo a disposizione 
solo un numero finito di dati discreti, e tali dati non sempre sono presenti 
negli istanti desiderati. In questo caso si necessita di routine di stima ed 
interpolazione che dovrebbero essere inglobate nei meccanismi d’accesso 
ai dati.  
L’ultimo operatore è quello della trasposizione, che si utilizza in 
quanto, molto spesso, l’output dei dati statistici richiede una propria 
trasposizione (i dati sono memorizzati lungo certe dimensioni e 
necessitano, in output, di essere visualizzate lungo altre). In questo caso, 
infatti, i dati memorizzati secondo certe dimensioni, necessitano per la 
visualizzazione di essere disposti lungo altre dimensioni. 
C’è da considerare, inoltre, che devono, comunque, essere disponibili 
tutti quegli operatori utilizzati dai tradizionali sistemi di gestione dei dati, 
come gli operatori relazionali. Solo che, in questo caso, si lavora con una 
mole di dati notevolmente superiore rispetto ai database tradizionali e con 
l’aggravio di gestire il metadato associato al dato che si va ad elaborare. 
In aggiunta, i tradizionali metodi di ordinamento e di join annidati 
sono inadatti sugli SDB proprio per la quantità di dati che caratterizzano le 
 19
basi di dati statistiche. In questi casi conviene utilizzare metodi di join hash 
che costituiscono un’alternativa, dato che hanno una complessità lineare 
rispetto alle operazioni di I/O. Questi metodi, essenzialmente, partizionano 
i due insiemi di dati, su cui si deve effettuare il join, con una funzione hash 
sugli attributi oggetto del join, per poi fare il join delle partizioni in 
relazione alle coppie. 
 
2.1.3 Modelli logici. 
 
In questa sezione si vuole tracciare in linea di massima la 
rappresentazione logica dell’informazione, dato che sarà ripresa in seguito. 
I sistemi convenzionali di gestione dei dati sostengono il concetto 
d’insieme d’istanze di un’entità in svariate forme. I modelli esistenti come 
quello relazionale, gerarchico, reticolare e quello entità-relazione 
supportano solo semplici tipi di dato per gli attributi delle entità. Negli 
SDB, invece, vi è bisogno si gestire complessi tipi di dati, come vettori, 
matrici, serie temporali, con la possibilità, per ognuno dei valori, che essi 
contengono, di essere a loro volta dati complessi. 
I SDB sono un valido esempio per l’utilizzo di una gran diversità di 
dati, che vanno dai soliti caratteri e numeri, anche in virgola mobile, a 
vettori e matrici o più complesse tabelle per la rappresentazione di spazi 
multidimensionali. Inoltre, grafici e istogrammi sono i risultati comuni di 
molte analisi statistiche. Sorge, così, la difficoltà di realizzare un singolo 
sistema in grado di gestire tutti questi tipi di dati in maniera corretta ed 
efficace.