RICERCA ITALIANA     

Programma di ricerca

Nuove tecniche e strumenti per l'interrogazione di servizi di ricerca su Web

Università di riferimento

Politecnico di MILANO - ELETTRONICA E INFORMAZIONE - ()

Responsabile dell'Unità di ricerca

Stefano Ceri

Descrizione

Il progetto proposto si prefigge di progettare l’infrastruttura per i servizi di Ricerca di Nuova Generazione (Next Generation Search engines – NGS) ed è organizzato in 5 task.

T1: Progetto dell’infrastuttura, focalizzato sulla progettazione di un’infrastruttura per registrare Web Service e Wrapper. Le fonti dati vengono registrate con i loro schemi locali e i tag che descrivono i messaggi di input/output vengono mappati sui concetti dell’ontologia globale.

T2: Ambiente di esecuzione delle ricerche, focalizzato sull’esecuzione delle interrogazioni dell’utente, fornendo strumenti per sottomettere e rifinire le interrogazioni e per eseguire le strategie di join e la materializzazione dei risultati.

T3: Sviluppo di Wrapper, dedicato alla ricerca e estrazione di informazioni da fonti sul Web con un Web Service che espone un’interfaccia simile a un motore di ricerca convenzionale.

T4: Riformulazione delle interrogazioni, per determinare l’insieme dei servizi rilevanti per una certa interrogazione e le condizioni per ricombinare le risposte. La riformulazione deve tener conto dei vincoli espressi dall’ontologia globale, dagli schemi locali dei servizi e dal mapping tra schema locale e globale.

T5: Ottimizzazione della ricerca, per determinare la migliore strategia di join tra i frammenti XML restituiti dai motori di ricerca. Si dovranno inoltre definire metodi di join e metriche per misurare le prestazioni nei differenti scenari.

T1 e T2 saranno realizzati con un lavoro comune delle tre unità operative. I rimanenti task sono affidati a una singola unità. Questa unità è responsabile del task T5. Nel proseguo descriveremo T1, e T2, e (più in dettaglio) T5.

Task T1: Progetto dell’infrastruttura

Tutte le fonti dati considerate in questo progetto sono accedute attraverso Web Service. È ragionevole supporre che il risultato di una chiamata a Web Service sia un documento che non solo rispetta lo schema WSDL del servizio stesso, ma riflette le strategie appropriate per “rappresentare e pubblicare” efficacemente l’informazione estratta. Il WSDL descrive solo la sintassi ed è perciò inadeguato per la composizione: questa considerazione stimola la ricerca verso il cosiddetto “Semantic Web” con l’obiettivo di arricchire i Web Service con contenuti tratti da ontologie.

Di conseguenza, “registrare” un Web Service significa, essenzialmente, descrivere le proprietà concettuali che rappresentano il contenuto che può essere estratto dal servizio, e quindi descrivere il significato di ognuno degli “elementi restituiti” in termini dei suoi tag e in termini di “semantiche tipiche” di un elemento di output prodotto dal servizio. In particolare, durante la fase di registrazione, i Web Service sono mappati sullo schema globale dell’NGS, rappresentato da un’ontologia, che assumiamo sia formulato in uno standard W3C come OWL o uno delle sue varianti meno espressive. Questo è realizzato offrendo collegamenti tra elementi della specifica dell’input e dell’output a concetti dell’ontologia.

In questa ricerca ci proponiamo di definire uno schema generico per registrare Web Service che permettono la memorizzazione di metadati che descrivono: (a) la sintassi dei Web Service (richiesta/risposta), (b) la semantica dei tag nella richiesta, (c) la semantica dei tag nella risposta. Questi metadati sono quindi collegati ai concetti dell’ontologia che descrivono il dominio. L’aspetto importante è che, come risultato della registrazione, diventa possibile confrontare gli “elementi in output” prodotti da due diversi servizi (o da chiamate successive allo stesso servizio) estendendo il semplice test d’uguaglianza a più complicate analisi basate, ad esempio, su controlli di sussunzione tra concetti.

La “scalabilità” del nostro approccio (la capacità di gestire sorgenti multiple) dipende dalla facilità di registrare nuovi servizi. Quindi, mentre nella prima fase della ricerca l’enfasi sarà posta sulla registrazione manuale di pochi servizi (Google, Amazon, DBLP...), successivamente studieremo la possibilità di rendere semi-automatica la registrazione di servizi con strumenti basati su tecniche di ragionamento automatico. Data la necessità di adattare l’ontologia per nuove necessità, ci baseremo sulle esperienze acquisite nel campo dell’ “Information integration”, dove una buona scalabilità è raggiunta esprimendo gli schemi locali come interrogazioni sullo schema globale. Analogamente, nel contesto di NGS, si può, ad esempio, esprimere l’output di un certo servizio come un’interrogazione sui concetti dell’ontologia.

In questo contesto possiamo considerare due diverse politiche per adattare ed estendere l’ontologia: (1) un’estensione guidata dal servizio, che può essere usata quando il nuovo servizio da registrare può essere meglio rappresentato con concetti che non sono ancora rappresentati dall’ontologia; in questo caso l’ontologia dovrà essere accresciuta per rappresentare la conoscenza portata dal nuovo servizio. (2) Un’estensione guidata dall’interrogazione, che si utilizza quando le interrogazioni dell’utente richiedono informazioni che non hanno ancora una controparte semantica nell’ontologia; in questo caso noi possiamo decidere di aggiungere concetti all’ontologia allo scopo di venire incontro a queste nuove necessità, e di conseguenza mappare i servizi a un’ontologia il cui output soddisfa i nuovi concetti aggiunti.

In questa ricerca ci proponiamo di studiare queste politiche nel contesto degli NGS e come supportarle attraverso il ragionamento automatico.

Task T2: Ambiente di esecuzione delle ricerche

Questo task consiste nell’interrogare una fonte e memorizzare i suoi risultati per elaborazioni successive. L’interrogazione è eseguita invocando un servizio, gestendo la risposta e trovando i risultati come specificato da un’interfaccia che permette il caricamento parziale dei primi N elementi del risultato (con N un parametro fissato nel momento della chiamata). In generale ciò è semplice se i risultati vengono restituiti come semplici elementi XML e se l’interfaccia del servizio permette di controllare il numero di elementi restituiti (come Google o Amazon). In generale, i Web Service possono non essere forniti di funzioni avanzate di controllo e possono semplicemente restituire una quantità di dati impredicibile. In questo caso è necessario sfruttare in modo opportuno le risorse disponibili.

Questo task è anche responsabile di gestire le risposte che vengono fornite in formati diversi dal XML, e di allinearli al formato standard utilizzato nei passi successivi del processo, tenendo però traccia del riferimento tra l’elemento in linea con lo standard generato e l’elemento originale che era stato fornito dal servizio, che è probabilmente di interesse per l’utente.

Un esempio di questa funzionalità è la trasformazione richiesta per “leggere” una mappa, fornita in un formato grafico con annotazioni XML riguardanti punti della mappa stessa, e gestire le semantiche di interrogazioni specifiche come le richieste di luoghi che sono “a una certa distanza da un certo punto”. In questo caso, mentre l’interrogazione può essere espressa graficamente sulla mappa, il sistema deve poter rispondere non in termini di un grafico ma in termini di un insieme di elementi che sono nell’area di interesse e rappresentano luoghi (nomi di città o codici postali), in modo che sia possibile comporre questo risultato con altri. Inoltre, la “vicinanza” a un punto deve essere usata per dare un punteggio ai risultati prima di mostrarli.

Questo task è anche responsabile di descrivere l’interazione con l’utente per migliorare l’esecuzione iterativa di ricerche. L’interazione coi motori di ricerca è un processo tipicamente iterativo, dove gli utenti in genere eseguono dei passi in sequenza modificando i termini inseriti in base ai risultati dell’iterazione precedente, finché non sono soddisfatti; normalmente questo processo porta a un risultato migliore. Tecniche note dell’information retrieval possono permettere all’utente, sotto certe condizioni, di migliorare la ricerca specificando quali sono gli elementi più rilevanti del risultato.

L’input dell’utente può essere molto utile per migliorare le strategie di ricerca e per questo motivo dedicheremo il periodo finale del progetto alla sperimentazione di varie alternative di coinvolgimento dell’utente. Permettere all’utente di indicare quali dei concetti estratti meglio rappresentano le sue esigenze, utilizzando poi quest’informazione per modificare gli input presentati ai servizi, per ripetere le ricerche. Inoltre, l’interazione può essere usata per confermare i match ipotizzati dal sistema (ad esempio i match di concetti come “professore”, “ricercatore”, “autore”, se non esplicitamente supportati dal vocabolario).

Task T5: Ottimizzazione della ricerca

Il Task T5 consiste nell’estensione di classici paradigmi di esecuzione delle interrogazioni al nuovo compito di “join e match” di risultati parziali ottenuti dalle chiamate ai servizi. È noto che i join permettono combinazioni basate sul valore di risultati di sottointerrogazioni; il Task T5 adatta schemi di join molto noti (nested loop, merge-scan, hash based) a un contesto dove l’identità basata sul valore è sostituita da metodi di confronto più complessi. Il join avviene tra liste ordinate di frammenti XML, in cui ogni frammento rappresenta un descrittore di risorsa nel risultato della ricerca. La compatibilità tra frammenti è determinata combinando elementi XML; questi sono noti a priori, in quanto gli schemi di servizi sono conosciuti. Il match di due frammenti può essere “più forte” o “ più debole” a seconda se si usano operatori quali identità, prossimità, sussunzione e così via. Il match stesso produce un terzo punteggio che è combinato coi punteggi originali dei due elementi per produrre il punteggio complessivo del join.

In questo contesto costruire tecniche di ottimizzazione efficienti significa fornire i risultati di combinazioni col punteggio più alto. Nel semplice caso di join binari le metriche di costo per determinare il costo complessivo dipendono dalla cardinalità dei risultati prodotti dalle due ricerche e dal numero di operazioni di confronto; metodi efficaci possono essere progettati per particolari assunzioni sui costi dell’interrogazione, cioè assumendo che i costi dominanti sono correlati con l’esecuzione di richieste al servizio o invece col costo della combinazione basata sull’ontologia.

Data l’applicazione proposta – che presenta i risultati a un utente che sta interagendo con un motore di ricerca – ricerche esaustive non hanno senso, invece le “combinazioni migliori” devono essere cercate in modo efficiente, estraendole per prime con meccanismi che sono confrontabili con tecniche di esecuzione di interrogazioni per determinare in modo efficiente risultati con “punteggio massimo”. Questo “punteggio massimo” è definito in modo deterministico nelle interrogazioni relazionali, mentre nel nostro scenario è basato su complessi schemi di valutazione, e ciò rende il problema più complicato. I risultati restituiti agli utenti saranno ordinati in base al punteggio globale ottenuto durante l’operazione di join. Sospendere per lungo tempo le visualizzazioni di “buoni” risultati solo perché uno “migliore” potrebbe venire restituito successivamente è una strategia insoddisfacente; quindi, è necessario studiare e introdurre diversi gradi di approssimazione rispetto all’ordine di estrazione dei risultati (la cui bontà si valuta confrontandoli con l’ordine “teoricamente ottimo”).

Lo sviluppo di questo task consisterà inizialmente nel definire un formato astratto per le “strategie di interrogazione” e nello studiare le sue proprietà formali – più precisamente, trasformazioni standard di equivalenza, che sono conosciute nel contesto delle ottimizzazioni delle interrogazioni, e che possono essere adattate a questo nuovo scenario. Definiremo inoltre una varietà di operazioni di “match”; la loro efficacia e il loro costo saranno studiate in funzione del costo e della complessità di accedere a risorse “ontologiche” e di usare l’approssimazione e il contenimento al posto della semplice uguaglianza.

Quindi, metodi di join verranno definiti come una combinazione di (1) ordinamento delle operazioni di estrazione dei risultati dai servizi e (2) uso di opportune operazioni di match una volta acquisiti i risultati. Una tale descrizione “logica” dovrà essere completata da una strategia “fisica” per memorizzare i risultati intermedi e finali e per indicizzare tali risultati in accordo con il vocabolario dell’utente in modo di permettere un ulteriore utilizzo dei risultati in interrogazioni complesse o in future iterazioni dell’interrogazione. I metodi di join più promettenti saranno implementati e dimostrati.

Definiti dei metodi di join e delle strategie di interrogazione, continueremo la ricerca in questo task focalizzandoci su tecniche di ottimizzazione capaci di determinare l’ordine di join quando più di due fonti sono disponibili (basandoci su semplici euristiche), selezionando per ogni join in metodo più promettente, e gestendo il flusso dei dati e la loro struttura come richiesto per la memorizzazione di risultati parziali e finali.

Ogni metodo di join sarà associato a una metrica che permetterà di calcolare il suo costo approssimato e la sua efficacia attesa, cosicché un ottimizzatore sarà in grado di scegliere il metodo migliore. I costi dipendono da due fattori: l’interazione col servizio durante l’esecuzione delle richieste e l’esecuzione dei confronti tra frammenti XML. Questi fattori di costo richiamano quelli considerati dagli ottimizzatori di join: i costi di input/output (qui sostituito dal costo delle richieste al servizio) e il costo di cpu (qui sostituito dal costo necessario per confrontare coppie di frammenti XML, quando il confronto richiede analisi testuali o conoscenze specifiche del dominio). In linea di principio, i due costi si sommano; tuttavia, possiamo facilmente prevedere scenari dove il primo o il secondo fattore dominano, e si possono considerare questi casi estremi come i più significativi. L’efficacia complessiva della strategia è anche strettamente correlata a molti aspetti che difficilmente possono essere presi in considerazione, come la disponibilità delle fonti dei dati, la qualità stimata dei dati restituiti o il tempo medio di risposta. Alcuni di questi elementi saranno incrementalmente aggiunti alle metriche supportate.

Le strategie di accesso ai dati prodotte dal nostro metodo saranno rese pubbliche in un formato chiaro, e un intervento umano guidato dal progettista potrà essere richiesto al fine di rifinire le strategie di accesso per meglio capire e tarare i metodi. Come possibile seguito di questa ricerca immaginiamo un sistema in cui gli utenti posso sfruttare opportuni wizard per fornire indicazioni utili per le strategie di selezione.

Workplan

Il gruppo parteciperà ai seguenti deliverable:

D1.1. Stato dell’arte orientato alle tecnologie dei Web Service, comprensivo della scelta dei Web service da usare nel progetto e dei loro domini ontologici (M3)
D1.2. Definizione dell’architettura della piattaforma di registrazione dei Web Service (M6)
D2.1. Definizione dei protocolli per l’invocazione di Web Service e per la memorizzazione dei risultati parziali (M6)
D5.1. Risultati di ricerca preliminari che descrivono la notazione astratta per definire join tra due sorgenti e identificazione del principale algoritmo di join da usarsi nel progetto (M8)
D2.2. Primo prototipo funzionante che supporta due fonti, semplici metodi di join e nessuna interazione dell’utente (M12)
D5.2. Progetto di metodi di join avanzati e di ottimizzazioni di interrogazioni complesse (M18)
D2.3. Secondo prototipo in grado di gestire più sorgenti, molti metodi di join e l’interazione con l’utente (M22)
D1.3. Sperimentazione e valutazione (M24)