Costruzione dei risultati

Vediamo ora il problema che giustifica la necessità di avere una fase di costruzione dei risultati ed in seguito descriviamo le operazioni che vengono effettuate in questa fase.

Ogni vettore di posizioni è partizionato logicamente in gruppi. Una posizione appartiene ad un gruppo piuttosto che ad un altro in base alla posizione del nodo padre che la include.

Gruppi creati a partire dalla stessa posizione del padre sono legati tra loro.

Ad esempio, con riferimento alla figura 3.7, il vettore di posizioni del nodo B è suddiviso in 2 gruppi, il primo B1 contenente le posizioni {[2,10], [11,40]} e il secondo B2

contenente la posizione {[52,56]} poiché incluse rispettivamente nella posizione [1,50] e [51,70] del nodo padre A. Allo stesso modo il vettore di posizioni del nodo C contiene nel primo gruppo C1 la posizione {[41,49]} e nel secondo gruppo C2 le posizioni {[57,63],[64,69]} anch’esse incluse rispettivamente nella posizione [1,50] e [51,70] del nodo padre A. In conclusione i gruppi legati tra loro sono B1e C1, e B2e C2.

Questi legami impediscono di considerare in modo indipendente le posizioni di figli diversi. Quindi, lo scopo di questa fase è quello di riempire la tabella dei risultati, introdotta nel paragrafo [3.1.4] sfruttando le informazioni sui Pivot contenute nella tabella hash, introdotta nel paragrafo [3.1.3], e tendendo conto di tali legami, rendendo così possibile la fase successiva di visualizzazione dei risultati.

Il riempimento della tabella richiede un’ulteriore visita bottom-up. Durante tale visita in ogni nodo viene costruita una tabella temporanea per ogni posizione del padre contenente i risultati relativi a quella posizione. La tabella costruita nei nodi foglia ha un numero di righe pari al numero di posizioni contenute nell’intervallo associato alla posizione corrente del nodo padre ed un numero di colonne fissato a priori e pari al doppio del numero di Pivot. Questo perché per ogni Pivot viene memorizzata la posizione di apertura e chiusura della finestra di testo da visualizzare. Ogni posizione viene inserita nella corrispondente riga e nella colonna j-esima dove j è l’indice del Pivot, recuperato dalla tabella hash [3.1.3], associato al nodo. Procedendo con la visita in ogni nodo interno si fondono le tabelle dei nodi figli per generarne una nuova con un numero di righe pari al prodotto tra i numeri di righe delle tabelle temporanee dei nodi figli. Le righe della nuova tabella vengono riempite combinando tra loro le righe di ciascuna tabella dei figli (vedi figura 3.8). Inoltre, se il nodo corrente è un Pivot, la posizione corrente per la quale si stanno calcolando i risultati si inserisce nella colonna corrispondente all’indice associato al nodo Pivot. Un caso particolare si verifica in presenza del nodo speciale <xml_or>. In tal caso la tabella del nodo si ottiene facendo l’unione delle righe delle tabelle dei nodi figli.

NodoA {[1,50], [51,70]}

NodoC NodoB

{[2,10], [11,40], [52,56]} {[41,49], [57,63], [64,69]}

Figura 3.7 – Esempio di partizionamento in gruppi delle posizioni

Alla fine della visita la tabella costruita nel nodo radice sarà la tabella dei risultati finali.

Lo spazio occupato dalla tabella è proporzionale al prodotto del numero di risultati che soddisfano l’interrogazione e delnumero di Pivot presenti nella clausola RETURN.

La presenza della clausola RANGE nell’interrogazione potrebbe ridurre il numero di risultati da visualizzare. Questo però non implica una riduzione proporzionale anche del tempo di risposta e dello spazio occupato dalla struttura dati poiché i risultati vengono comunque generati tutti. Il notevole aumento di complessità che si sarebbe avuto facendo costruire solamente i risultati richiesti ci ha portato a rinunciare a tale funzionalità. L’aumento di complessità è dovuto all’esistenza di una relazione tra le posizioni di nodi differenti, che a priori, senza aver effettuato la completa visita dell’albero, non permette di stabilire qual è l’i-esimo risultato. Ma come già osservato, la completa visita dell’albero ha generato l’intera tabella dei risultati.

3.4.1 Memorizzazione dei risultati nel file system

La libreria XCDEv2.0 per consentire una visualizzazione dei risultati di un’interrogazione anche in un momento successivo a quello di risoluzione della stessa, consentendo la memorizzazione di questi in un file. In tale file vengono memorizzate, secondo lo schema in figura 3.9, la tabella dei risultati e la tabella hash. Essendo la tabella dei risultati costituita da numeri interi, abbiamo scelto di memorizzare tali informazioni in maniera compressa. Il file è in formato binario e la tabella è memorizzata per righe, e al suo interno le righe della tabella sono memorizzate in maniera sequenziale. Per garantire una maggiore efficienza nel recupero di un sottoinsieme dei risultati dal file ogni dieci righe (costituenti un blocco) viene memorizzato nel file un indice del blocco, cioè un puntatore alla sua prima riga. In testa al file viene memorizzata la dimensione della tabella dei risultati e il numero di variabili presenti nella clausola RETURN. Seguono il vettore dei puntatori ai blocchi, e per ogni risultato la lunghezza della lista delle posizioni e la lista delle posizioni fisiche memorizzate con il Continuation bit, e infine le informazioni relative alla tabella hash.

30 51 52 56

57 63 64 69

30 51 57 63 30 51 64 69 52 56 57 63 52 56 64 69

Figura 3.8 – Esempio di combinazione di righe

Per problemi legati alla codifica dello zero i valori codificati con il Continuation bit vengono incrementati di uno. In sede di decompressione i valori saranno opportunamente decrementati.

3.4.2 Recupero dei risultati dal file system

La possibilità di memorizzare i risultati di un’interrogazione in un file introduce la necessità di disporre di un meccanismo di recupero degli stessi.

La libreria offre due tipi di recupero: un recupero totale dei risultati ed uno parziale. Il recupero totale prevede la lettura dal file di tutti i risultati presenti. Quello parziale, invece, permette di recuperare un intervallo specifico di risultati. Quest’ultimo sfrutta la presenza dei puntatori ai blocchi per evitare la scansione sequenziale dei risultati.

dim. tabella

Figura 3.9 – Struttura del file che contiene i risultati