Generazione dell’albero di ricerca

Nell’albero di ricerca generato dall’approccio olistico, alla radice sono collegate

tutte le possibili baseline. Ogni livello successivo `e invece associato ad uno degli at-

tributi dimensionali presenti nel group by set della query e contiene i nodi che rap- presentano i refinement ottenuti combinando tutti i possibili valori dell’attributo con i fattori in grado di quantificare una variazione relativa.

Come spiegato nella Sezione 4.3.2, la prima differenza tra l’approccio originale

e la versione implementata `e costituita dal fatto che quest’ultima genera solamente

una baseline e un refinement per ogni membro della gerarchia dimensionale. Essi

vengono calcolati a partire dalla cache e, in questo modo, il sistema sviluppato `e

in grado di eseguire interrogazioni su un qualsiasi cubo multidimensionale.

La prima implementazione realizzata prevedeva una struttura dell’albero di ri- cerca coerente con quanto previsto dall’approccio ma, a seguito di alcune prove

sperimentali, `e emerso chiaramente un limite. Infatti, dato che ogni livello del-

l’albero `e associato ad un certo attributo dimensionale, pu`o essere emesso un solo

refinement che descrive uno dei suoi valori. Al contempo, `e necessario restituire

un refinement per ogni attributo dimensionale presente nel group by set. Di conse- guenza, se le variazioni presenti nei dati non sono distribuite tra le varie dimensioni ma si concentrano in alcune di esse, i refinement scelti dall’approccio non sono in grado di offrire all’utente il massimo contenuto informativo possibile.

Si consideri, ad esempio, la query che richiede di calcolare il salario medio raggruppando i dati per regione di provenienza del lavoratore e per salario iniziale.

Assumendo che il discorso in grado di massimizzare la qualit`a percepita dall’utente

contenga i refinement “Il valore aumenta del 20% per i laureati provenienti dal Northeast” e “Il valore diminuisce del 30% per i laureati provenienti dal South”, la strategia originale non sarebbe in grado di selezionare questo output.

L’implementazione presentata propone quindi un approccio alternativo, a cui si fa riferimento con il termine completo. Esso prevede che, in tutti i livelli dell’albero, a ciascun nodo venga collegato un figlio per ogni refinement relativo ad un possibile

valore di un attributo dimensionale presente nel group by set della query. `E per`o

(Root) The averagemid-career salary is 80K

Values decrease by 30% for graduates from the South Values increase by 20% for

graduates from the Northeast.

Values decrease by 10% for start salaries of less

than 50 K. Values increase by 5% for start salaries of at least

50 K.

(Root) The averagemid-career salary is 80K

Values decrease by 30% for graduates from the

South

Values increase by 20% for graduates from the

Northeast. Values decrease by 10%

for start salaries of less than 50 K. Values increase by 5% for start salaries of at least

50 K.

Values decrease by 30% for graduates from the South Values increase by 20% for

graduates from the Northeast. Values decrease by 10%

for start salaries of less than 50 K. Values increase by 5% for start salaries of at least

50 K.

Figura 4.4: Esempio di albero di ricerca completo

La Figura 4.4 riporta il confronto tra l’albero di ricerca generato dall’approc- cio originale e quello ottenuto con la variante completa, nel caso in cui la query

corrisponda a quella indicata nell’esempio precedente. Si pu`o notare che il secon-

do albero `e caratterizzato da una maggiore espressivit`a, in quanto cattura tutti i

discorsi codificati dal primo aggiungendone altri. Il secondo albero viene definito

completo, perch´e rappresenta tutte le combinazioni tra i possibili refinement.

Nell’implementazione presentata `e possibile, tramite un apposito parametro,

scegliere se generare l’albero di ricerca coerente con l’approccio originale o quello completo. Questo ha permesso, come illustrato nel Capitolo 5, di confrontare le due strategie e di verificare i vantaggi ottenuti grazie ad un albero completo.

Gestione della complessit`a computazionale

Generare un albero completo, che considera tutte le possibili combinazioni di re-

finement, pu`o consentire all’approccio olistico di ottenere risultati migliori. Uno

spazio di ricerca di dimensione maggiore pu`o per`o causare un overhead computa-

Fissato il numero di refinement a n e data una query caratterizzata da un group by set contenente n attributi dimensionali, ognuno dei quali prevede m possibili valori, il numero dei nodi foglia dell’albero generato dall’approccio olistico

`e pari a mn. Considerando invece l’albero completo, il numero di foglie `e (m ∗ n)n

perch´e ad ogni livello sono disponibili tutti i refinement (ad eccezione di quelli gi`a

selezionati). La dimensione dell’albero aumenta quindi di un fattore nn _{che, pur}

essendo n limitato dalla scarsa memoria degli utenti [32], non `e trascurabile.

`

E stata dunque adottata una tecnica euristica per contenere la dimensione dello spazio di ricerca, indipendentemente dal cubo multidimensionale interrogato e dal-

la query formulata. Secondo il principio di uniformit`a descritto nella Sezione 3.2.2,

in assenza di informazioni l’utente tende ad assumere una distribuzione uniforme

dei dati. Perci`o i refinement pi`u interessanti risultano essere quelli che indicano

un maggiore scostamento dalla distribuzione uniforme precedentemente percepita.

Ad esempio, data una query che calcola una media, i refinement pi`u interessanti

sono caratterizzati da una variazione maggiore in valore assoluto.

La strategia descritta `e usata per ordinare tutti i refinement generati, vengono

poi selezionati i primi N (parametro che indica il massimo numero di figli di un nodo dell’albero) ed essi, a loro volta, sono utilizzati per generare l’albero di

ricerca completo. Quest’ultimo `e caratterizzato da una complessit`a nell’ordine di

grandezza di O(mk), che pu`o essere controllata grazie a questa tecnica. Infatti,

m e k corrispondono rispettivamente al massimo numero di figli di un nodo e al numero dei livelli dell’albero e sono entrambi parametri dell’approccio.