Lo stato dell’arte

In questo paragrafo sar`a presentato un breve excursus sullo stato dell’arte per quanto riguarda l’interrogazione approssimata dei documenti XML e la riscrittura delle query, problema accennato all’interno del paragrafo precedente.

Abbiamo visto, parlando del linguaggio di interrogazione per documenti XML XQuery, come la risoluzione di un interrogazione su un archivio di dati semistrut-turati possa essere ricondotta al confronto fra due struttura ad albero: sia le query che i documenti XML (o i loro schemi), infatti, possono essere rappresentati per mezzo di gerarchie ad albero. A partire da questa assunzione sono stati sviluppati una serie di lavori per permettere il confronto approssimato fra due differenti strutture ad albero, per poter trovare tutti i documenti di un archivio che sono in grado soddisfare suffi-cientemente ’l’albero’ della query. In [43] viene proposto un metodo per il confronto di due alberi per mezzo di un algoritmo basato sul concetto di edit distance. In questo lavoro si afferma che la distanza fra due alberi (di cui uno pu`o essere l’espressione della struttura richiesta da una query ed il secondo della struttura di un documento formato da dati semistrutturati) pu`o essere misurata in base al costo della sequenza di operazioni necessarie per tramutare il primo albero nel secondo. Le operazioni identificate a questo scopo sono tre:

• Inserimento di un nodo • Cancellazione di un nodo

In base a queste tre operazioni siamo in grado di trasformare la struttura di un albero (qualunque essa sia) in quella di qualsiasi altro. Ad ognuna delle tre oper-azioni citate viene assegnato un costo (espresso da un valore reale positivo). Dalla somma di tutti i costi di una sequenza di operazioni in grado di cambiare la strut-tura dell’albero T₁ in quella dell’albero T₂, si evince la distanza che intercorre fra i due. Sfortunatamente, per`o, gli stessi autori del metodo hanno dimostrato che con-frontare in questo modo due strutture ad albero `e un problema NP-completo. La complessit`a computazionale dell’algoritmo impiegato `e, quindi, notevolmente elevata e diviene, per i mezzi attuali, proibitiva se il confronto viene effettuato su un archivio di documenti molto ampio.

Il lavoro che viene presentato in [41] tratta la ricerca approssimata in alberi non ordinati in maniera nettamente differente. L’approccio discusso pu`o essere utilizzato al fine di ritrovare informazioni interessanti in strutture che possono essere rappre-sentate tramite alberi (eg. XML e dati semistrutturati in generale). La query viene vista anch’essa come un albero formato dai path elencati all’interno della richiesta stessa. IL problema, chiamato in gergo approximate nearest neighbor search (ANN), `e il seguente: dato un numero intero DIFF un’albero descritto dalla query, detto Q, ed un database di alberi di dati(estratti, ad esempio, da un archivio di documenti XML)

D, trovare tutti gli alberi appartenenti a D che contengono un sottoalbero D’ la cui

distanza da Q risulti essere inferiore a DIFF. Si consideri la Figura ():

L’albero rappresentato dalla query, Q, `e contenuto completamente all’interno di

D1 (l’area tratteggiata rappresenta D’), ma solo il percorso dall’elemento a

all’ele-mento c si ritrova sia in Q che in D2. La distanza fra la query ed il docuall’ele-mento la cui struttura `e rappresentata da D1 sar`a nulla (pari a 0), la distanza, invece, fra la query e l’altro albero `e pari a 1. Tale distanza, infatti, viene calcolata contando i percor-si (path) presenti in Q e non nell’albero dei dati; se questa distanza supera l’intero

DIFF, l’albero dei dati selezionato non `e ritenuto interessante per la query. Questo

metodo, in pratica, definisce la distanza fra una query ed uno schema come il numero di percorsi presenti all’interno della richiesta ma non all’interno dello schema. Questo metodo, pur essendo computazionalmente molto pi`u leggero del precedente, non trat-ta la semantica delle query e dei documenti, non potranno, quindi, essere identificati come simili documenti che trattano gli stessi concetti, ma con termini differenti.

Un’altro interessante lavoro, pi`u simile a quello che verr`a sviluppato in questa tesi, `e quello descritto ad Torsten Schlieder in [38]. Le fondamenta su cui si basa tale lavoro sono riassunte perfettamente dalla frase -Un motore per risolvere query XML

dovrebbe trovare il miglior risultato possibile: se non si ritrova un matching esatto con i documenti, i risultati simili dovrebbero essere cercati e presentati in ordine di importanza all’utente -. L’utente, per poter formulare in modo corretto una query,

deve conoscere perfettamente la struttura di tutti i documenti presenti in archivio, compito quanto mai complesso. Per facilitare il compito dell’utente la query deve essere trasformata e adattata agli alberi rappresentanti i documenti nel repository (si tratta esattamente del problema di riscrittura delle query citato in precedenza). A tal fine, Schlieder propone un nuovo linguaggio per l’interrogazione di documenti XML chiamato ApproXQL[37]. ApproXQL `e un semplice linguaggio di pattern-matching che non distingue fra elementi ed attributi, ed un esempio `e fornito da:

cd[ title [”piano” and ”concerto” ] and composer[”rachmaninov”]]

in cui si richiedono tutti i cd di Rachmaninov il cui titolo sia concerto o piano. Ap-proXQL non tratta in modo differente attributi ed elementi XML, rendendo la sintassi delle interrogazioni notevolmente pi`u semplice. Non basta, per`o, semplicemente cer-care una corrispondenza diretta fra l’albero fornito dalla query e gli alberi dei dati: per trovare risultati similari (ad esempio titoli come ’pianoforte’) si usano le basic query

trasformations. Queste trasformazioni, che vengono effettuate sull’albero della query,

schema della query a quelli dei documenti dell’archivio. Ad ogni documento ritrovato in questo modo viene associato, quindi, un costo detto di trasformazione. Sono ritenu-ti interessanritenu-ti solamente i documenritenu-ti per i quali il costo di trasformazione della query non supera una certa soglia. Un costo di trasformazione basso rappresenta una buona similarit`a fra la query ed il documento considerato. Il procedimento di trasformazione di una query `e computazionalmente pesante (il numero di trasformazioni possibili, soprattutto se l’archivio `e grande, pu`o essere elevatissimo) e pu`o essere aiutato dalla presenza di schemi rappresentanti la struttura dei documenti XML.

Un approccio differente `e quello descritto in [9] dai professori P.Ciaccia e W.Penzo dell’Universit`a di Bologna. In questo lavoro si parla del rilassamento dei requisi-ti posrequisi-ti in una query come un ’must’, nel caso si srequisi-tia lavorando con un insieme di documenti molto grande e vario, al fine di evitare risultati inconsistenti. Il risulta-to ottenurisulta-to , allo scopo di trovare e classificare similitudini fra l’albero della query con quelli dei documenti, consiste in una funzione di similarit`a detta SATES (Scored

Approximate Tree Embedding Set). SATES fornisce come risultato, per ogni query,

un insieme di alberi di dati (classificati a seconda della similarit`a) che approssimano quello della query. Il risultato `e ottenuto sfruttando eventuali affinit`a semantiche pre-senti fra i nomi delle foglie e dei nodi degli alberi della query e dei documenti. Sfrut-tando questo approccio, anche se computazionalemnte pesante, si possono ritrovare informazioni desiderate ma immagazzinate in archivio tramite termini simili, ma non uguali, a quelli espressi dalla query.

Un importante lavoro che, invece, sfrutta l’utilizzo di un sistema mediatore per la riscrittura delle query viene offerto dal progetto MIX [1] (Mediation of Information using XML) sviluppato presso il Supercomputer Center di San Diego (SDSC). La tecnologia MIX `e stata impiegata per lo sviluppo di una parte della California Digital Library i cui documenti possono essere richiesti ponendo una query usando un’inter-faccia grafica (chiamata BBQ). La BBQ fornisce le risposte utilizzando il query pro-cessor MIX in grado di processare le richieste e fornire le risposte basandosi su viste madiate in XMAS (un linguaggio di interrogazione basato su XML) degli oggetti in archivio.

L’ultimo lavoro accennato in questa sede al fine di risolvere il problema della riscrittura della query, prima di descrivere l’approccio utilizzato nell’ambito della tesi, `e quello presentato da S.Melnik, H.Garcia-Molina ed E.Rahm in [32]. Gli autori pre-sentano un algoritmo di matching in grado di trovare le corrispondenze fra i nodi di

due alberi (che possono essere schemi di documenti o altre strutture di questo tipo). L’algoritmo descritto prende il nome di Similarity Flooding Algorithm ed usa un ap-proccio basato sulla considerazione che il concetto di similarit`a si propaga da un nodo a quelli vicini (eg. se un nodo appartenente ad un albero detto T1risulta essere sim-ile ad un nodo appartenente ad un albero T<sub>2</sub> `e probabile che anche fra i nodi ad essi vicini esista un certo grado di somiglianza). La prima cosa da fare `e ottenere valori di similarit`a iniziali fra i nodi dei due alberi (in [32] si parla, ad esempio, di operatori che utilizzino procedimenti di confronto fra stringhe); nel passo successivo entra in gioco il vero e proprio algoritmo di Similarity Flooding che iterativamente modifica il grado di silarit`a fra i nodi (alterando quindi il mapping iniziale fra la due strutture ad albero) propagando i pi`u alti gradi di similitudine dai nodi che li posseggono a quelli strettamente connessi con loro. L’algoritmo viene eseguito fino a quando i valori di similarit`a fra i nodi (visti come numeri compresi fra zero e uno) si stabilizzano o, in caso contrario, un numero prefissato di volte.