MINISTERO DELL

Coordinatore	LENZERINI Maurizio
Università	Universita' degli Studi di ROMA "La Sapienza"
Titolo del Programma	D2I: Integrazione, warehousing e mining di sorgenti eterogenee di dati
Costo originale del Progetto	881.000.000
Quota Cofinanziamento MURST	564.000.000
Quota Cofinanziamento ATENEO	254.000.000
Totale finanziamento	818.000.000
Fondi complessivi utilizzati nel primo anno	380.255.684

L'obiettivo generale del progetto e' la definizione di un quadro metodologico generale per l'integrazione, il warehousing e il mining di sorgenti eterogenee (D2I: From Data to Information), e lo sviluppo di metodi e strumenti specifici per i tre temi.

Nel primo anno, il progetto era caratterizzato dai seguenti obiettivi.

Oltre alla definizione dettagliata dei requisiti che il contesto generale del progetto pone sui vari temi di ricerca, un obiettivo generale era di specificare il ruolo del repository di meta-dati che fornisce la base comune per le metodologie e gli strumenti che verranno sviluppati nelle fasi successive. Gli obiettivi di ricerca specifici sui singoli temi viene descritto qui di seguito.

TEMA 1: INTEGRAZIONE DI DATI PROVENIENTI DA SORGENTI ETEROGENEE.

L'obiettivo generale nell'ambito di questo tema e' lo studio e analisi dei nuovi requisiti che emergono sulla integrazione di dati quando si considerano sorgenti fortemente eterogenee, cioè strutturate e semi-strutturate.

Questo studio include l'analisi dei requisiti per la scoperta e la rappresentazione di proprietà intra e inter-schema delle sorgenti, sia intensionali che estensionali. L'indagine sui metodi per definire e specificare parametri di qualità delle sorgenti e i metodi per la riconciliazione di dati provenienti da sorgenti eterogenee.

Lo studio dell'impatto che la presenza di diverse versioni dello schema di una sorgente, con particolare riferimento a sorgenti object-oriented, può avere sul processo di integrazione. L'analisi del ruolo dei meta-dati e delle ontologie in un contesto in cui si integrano sorgenti strutturate e semi-strutturate. L'analisi dei metodi esistenti per il problema del query rewriting e del query answering using views. La definizione della struttura del meta-data repository per descrivere le diverse tipologie di sorgenti e di relazioni intra ed inter-schema. Un obiettivo primario in questo tema e' la definizione di una metodologia per la costruzione di viste riconciliate di dati semi-strutturati provenienti da sorgenti eterogenee, basata su tecniche intelligenti di tipo semi-automatico per l'identificazione e riconciliazione di eterogeneità basate su affinita' e clustering, sulla estrazione semi-automatica di proprietà interschema, e su conoscenza di ontologie di dominio. La metodologia prevede esplicitamente tecniche e passi specifici per la rappresentazione ed il trattamento di sorgenti semistrutturate. La metodologia prevede anche metodi e tecniche per il trattamento di interrogazioni formulate sulla vista integrata. Un importante sotto-obiettivo e' la definizione degli algoritmi per la riscrittura di interrogazioni rispetto ad un insieme di viste (query rewriting e query answering using views).

Globalmente, si tende alla specifica funzionale di un "Query Manager" che supporti interrogazioni globali rispetto ad una vista virtuale integrata delle sorgenti. Compito primario del query manager è la decomposizione di una query globale in sub-query relative alle sorgenti e l'ottimizzazione della esecuzione delle sub-query.

TEMA 2: PROGETTAZIONE E INTERROGAZIONE DI DATA WAREHOUSE

Il primo obiettivo comprendeva l'esigenza di una sistematizzazione della vasta letteratura sulla progettazione logica e fisica di data warehouse, con lo scopo di identificare le principali limitazioni degli approcci esistenti alla materializzazione di viste, focalizzando l'attenzione sulla determinazione di una classe generale di interrogazioni da usare come punto di partenza per mettere a punto tecniche di materializzazione più efficaci.

Aspetti importanti di questa indagine riguardano la stima della cardinalità delle viste, e l'analisi dei tipi di indici più diffusi sugli strumenti per il data warehousing: accanto ai B-tree, join index, star index, bitmap index e projection index. Per ciascun tipo di indice lo scopo era di elaborare un modello di costo da utilizzare durante la fase di progettazione fisica. Per quanto riguarda l'interrogazione di data warehouse, dopo uno studio preliminare dello stato dell'arte sulle tecniche di interrogazione efficienti di basi di dati (query containment, query rewriting, ecc.), l'obiettivo era l'individuazione delle specificità del contesto data warehouse in cui dovranno essere risolti i problemi di efficienza delle interrogazioni. Si tratterà essenzialmente di individuare i metodi di ottimizzazione esistenti più adatti ad essere estesi nel nuovo contesto applicativo. Dopo la fase di studio gli obiettivi prefissi riguardavano lo studio del problema della materializzazione di viste sulla base di un carico di lavoro complesso che contempli la presenza contemporanea di più operatori di aggregazione all'interno delle interrogazioni, tenendo conto dell'utilizzo di misure derivate e di eventuali misure di supporto per realizzare la distributività degli operatori. Un ulteriore obiettivo riguardava il problema della progettazione fisica utilizzando opportuni modelli di costo. Per quanto riguarda l'interrogazione di data warehouse, l'obiettivo era lo sviluppo di tecniche innovative di interrogazione in ambiente data warehouse attraverso l'estensione di tecniche preesistenti concepite per basi di dati relazionali. L'idea di base è quella di sfruttare le proprietà strutturali delle interrogazioni e delle viste materializzate per ottenere un'esecuzione ottimizzata. A tal fine viene sfruttata la proprietà di aciclicità strutturale della query riscritta per guidare il "query rewriting", rendendo in tal modo efficiente la successiva verifica di "query containment".

TEMA 3: DATA MINING

Il primo obiettivo comprendeva lo studio dello stato dell'arte nei vari sottoargomenti, inclusi metodi e algoritmi di clustering, con particolare attenzione alla capacita` di trattare dati categorici e spazi metrici, studi comparativi sulle prestazioni dei vari algoritmi, sia dal punto di vista dell'efficienza che da quello della qualita` dei cluster prodotti, valutazione della possibilita` di modifica dei vari algoritmi per trattare il caso di elaborazione incrementale, analisi dei paradigmi per query di similarita`, inclusi quelli con approssimazione, formalizzazione degli indicatori in grado di quantificare il compromesso "qualita` vs costo".

Riguardo al meta-querying, gli scopi del progetto comprendenvano l'individuazione di un insieme di varianti che rivelassero un buon interesse applicativo, e lo studio delle sorgenti di intrattabilita` computazionale che caratterizzano tali varianti. Lo stesso tipo di analisi si prevedeva di condurlo per altre tecniche di data mining, quali le association rules. Inoltre, l'obiettivo riguardante la visualizzazione era lo studio teorico sul rapporto tra le varie modalita` di visualizzazione dei dati e le varie attivita` di scoperta di informazioni. Per quanto riguarda la produzione di risultati piu' tecnici, l'obiettivo erano cosi' sintetizzabili: sviluppo di metodi di clustering per problemi derivanti dall'aggiornamento incrementale dei dati del warehouse, definizione di un paradigma di ricerca approssimata in grado di permettere all'utente di controllare la qualita` del risultato, anche in presenza di ricerche complesse, individuazione di sottocasi trattabili delle varianti di metaquerying individuate precedentemente, progettazione degli algoritmi efficenti per la loro implementazione. In linea generale, l'obiettivo del progetto comprendeva la definziione di un'architettura di un sistema di data mining "user-centered", con la possibilita` di offrire sistemi diversi in un ambiente integrato ed orientato all'utente. In questo contesto, un ulteriore obiettivo riguardava lo studio teorico di alcuni dei problemi centrali legati alla visualizzazione nel data mining.

Attivita` comuni ai tre temi

Nella prima fase, sono stati definiti i metodi di rappresentazione e di gestione dei meta-dati necessari per produrre le specifiche per il repository, che fornisce la base comune per le metodologie e gli strumenti sviluppati nell'ambito del progetto. La specifica del repository per i meta-dati e` stata ottenuta tramite la fusione e l'integrazione delle specifiche prodotte singolarmente dalle diverse unita` coinvolte nei tre temi del progetto. Tale specifica e` riportata nel rapporto D0.R1.

Nella seconda fase e` stata definita la struttura del repository di meta-dati, ed e` stato specificato l'insieme dei servizi che il repository stesso deve offrire. La specifica dell'architettura funzionale del repository di meta-dati e` riportata nel rapporto D0.R2.

Tema 1 - Integrazione di dati provenienti da sorgenti eterogenee

Durante la prima fase del progetto le unita` coinvolte nel tema 1 hanno inizialmente svolto un'analisi approfondita dello stato dell'arte relativo all'integrazione di sorgenti eterogenee di dati. Particolare attenzione e` stata posta al confronto dei modelli per dati semistrutturati proposti in letteratura, allo scopo di caratterizzarne il diverso potere espressivo, ed allo studio dei metodi esistenti per il problema del query rewriting e del query answering using views. Questa attivita` di studio ed analisi e` documentata principalmente nei rapporti D1.R1 e D1.R5. Successivamente le attivita` si sono concentrate nella formulazione dei requisiti di integrazione in presenza di sorgenti di dati fortemente eterogenee (strutturate e semistrutturate): sono stati studiati i requisiti per nuovi metodi di rappresentazione dei dati, con particolare riguardo a sorgenti di dati semistrutturati (dati OEM, documenti XML), e sono state definite nuove tecniche per l'identificazione e la riconciliazione di eterogeneita` basate sulle proprieta` dei dati e per l'estrazione semiautomatica di proprieta` interschema. Diversamente da molti altri approcci all'integrazione proposti in letteratura, le tecniche introdotte identificano ed estraggono proprieta` inter- ed intra-schema, intensionali ed estensionali, che riguardano sia aspetti linguistici (ad es. sinonimie, omonimie, etc.) che aspetti strutturali (similarita` fra schemi o porzioni di schemi). Inoltre, l'estrazione di relazioni interschema viene effettuata attraverso meccanismi semiautomatici, sfruttando le capacita` di ragionamento offerte dalle logiche descrittive utilizzate per la rappresentazione del dominio di integrazione. Questi meccanismi hanno lo scopo di automatizzare quegli aspetti del processo di integrazione che in genere risultano realizzati manualmente nei sistemi tradizionali. I risultati ottenuti sono descritti nei rapporti tecnici D1.R1 e D1.R2, in cui vengono estese tecniche precedentemente sviluppate dalle unita` partecipanti al progetto per sorgenti di dati strutturati al caso di sorgenti di dati semistrutturati, e sono opportunamente generalizzate tecniche per l'estrazione di alcune tipologie di proprieta` interschema anch'esse realizzate in precedenti studi sull'argomento. Nel corso della prima fase del progetto, e` stato inoltre sviluppato un modello generalizzato, denominato CVM (Conceptual Versioning Model), per la gestione di versioni di schema in ambiente eterogeneo, nel caso in cui sia necessario interoperare dati di tipo strutturato (orientati agli oggetti) e semistrutturato. La descrizione completa del modello, insieme ad uno studio approfondito di alcune logiche descrittive che sono alla base del modello stesso, e` presentata nel rapporto D1.R4. Infine, e` stato affrontato il problema della traduzione dei dati da un modello di rappresentazione ad un altro, oggetto del rapporto D1.R3 e del rapporto D1.R9 prodotto nella seconda fase.

Nella seconda fase sono state sviluppate tecniche di clustering basate su affinita` e corrispondenze semantiche per l'identificazione di cluster di candidati all'integrazione, tenendo conto non solo di proprieta` inter-schema di tipo intensionale ma anche di proprieta` di tipo estensionale. Sono state studiate le modifiche da apportare alla metodologia generale di integrazione per gestire anche sorgenti internamente dotate di meccanismi di gestione di versioni di schema. In particolare, sono state individuate tecniche di estrazione automatica di proprieta` interschema, indotte dai cambiamenti di schema, che consentono di incapsulare le sorgenti versionate rendendo del tutto trasparente l'aspetto di schema versioning. Tali risultati sono descritti nel rapporto D1.R6. E` stata definita una metodologia per la costruzione semi-automatica di viste riconciliate di sorgenti eterogenee e semistrutturate basata su affinita` e clustering e sull'uso di ontologie. L'architettura sviluppata consente una rappresentazione integrata ed uniforme delle informazioni memorizzate nelle sorgenti informative coinvolte, dopo la rimozione di eventuali conflitti ed inconsistenze. La capacita` di gestire una grande varieta` di tipologie di sorgenti informative e` stata ottenuta attraverso la definizione di modelli concettuali e logici capaci di rappresentare e gestire sorgenti di dati di diverso formato ed attraverso una attivita` di integrazione intensionale ed estensionale sulle sorgenti informative, tesa alla creazione di un unico schema globale virtuale. La decrizione dell'architettura funzionale di ausilio alla costruzione di viste e` oggetto del rapporto D1.R7.
Nei rapporti D1.R8, D1.R10 e D1.R11 sono stati affrontati gli aspetti piu` propriamente legati alla integrazione dei dati ed al problema di rispondere ad interrogazioni poste sullo schema globale virtuale del sistema di integrazione utilizzando esclusivamente i dati memorizzati alle sorgenti. Nel primo rapporto sono state definite le specifiche funzionali di un "Query Manager" (QM) che gestisce, per ogni interrogazione posta da utente, la rappresentazione globale ottenuta mediante le fasi di integrazione al fine di materializzare presso l'utente le entita` che popolano la vista virtuale e che costituiscono la risposta cercata. In particolare il QM gestisce aspetti relativi alla individuazione delle sorgenti locali ritenute necessarie per rispondere alla query, alla riformulazione della query nei termini delle sorgenti individuate, ed alla ricomposizione delle risposte ottenute da ogni singola sorgente al fine di produrre la risposta globale. Tale ricomposizione e` realizzata tramite l'utilizzo di tecniche di "Object Fusion", basate in particolare sulla "omogeneita` semantica" di attributi di differenti sorgenti. Inoltre il QM gestisce meccanismi di ottimizzazione del processo di risposta basati sull'utilizzo di relazioni estensionali. Nel rapporto D1.R10 e` stato definito un linguaggio fuzzy per l'interrogazione di viste riconciliate per la generazione semi-automatica di query sulle sorgenti con cui popolare lo schema globale. Infine nel rapporto D1.R11 sono stati definiti metodologia e strumenti per la risposta ad interrogazioni rispetto ad un insieme di viste, estendendo, gli approcci attuali per tener conto della necessita` di riconciliare sorgenti di dati eterogenee. In particolare e` stato affrontato il problema nei due approcci comunemente adottati nei sistemi di integrazione dei dati: local-as-view (LAV), in cui le sorgenti di dati sono descritte nei termini di viste espresse sullo schema globale, e global-as-view (GAV), in cui, al contrario, ad ogni elemento dello schema globale e` associata una vista sulle sorgenti. Nel rapporto e` descritta una metodologia di riconciliazione in LAV, approccio in cui il problema di rispondere alle interrogazioni e` comunemente considerato di difficile soluzione ed e` risolto mediante l'utilizzo di opportune tecniche di ragionamento. Inoltre e` mostrato come il problema sia di fatto un problema di risposta ad interrogazioni in presenza di informazione incompleta anche nell'approccio GAV, e che i metodi usati comunemente in GAV per rispondere alle interrogazioni risultano in generale inadeguati. Anche per questo caso sono state sviluppate tecniche per rispondere alle interrogazioni, sotto opportune assunzioni, tenendo in considerazione l'incompletezza dei dati memorizzati alle sorgenti e la inconsistenza dei dati stessi rispetto a vincoli di integrita` espressi sullo schema globale.

Tema 2 - Progettazione e interrogazione di Data Warehouse

Nella prima fase del progetto le unita` coinvolte nel tema 2 hanno portato avanti uno studio approfondito dello stato dell'arte sulle architetture dei data warehouse proposte in letteratura (rapporto D2.R1), sulle tematiche relative alla progettazione logico-fisica dei dati derivati (rapporto D2.R2) e sulle tematiche di interrogazione di sistemi di grandi dimensioni (rapporto D2.R3). Relativamente agli aspetti di progettazione logico-fisica descritti nel rapporto D2.R2, e` stata presentata, per il livello logico, un'analisi critica delle principali limitazioni degli approcci esistenti alla materializzazione di viste. L'attenzione e` stata focalizzata su due fattori: l'insufficiente generalita` della categoria di interrogazioni su cui e` basata la materializzazione, e la scarsa precisione delle funzioni adottate per la stima della cardinalita` delle viste. Per il livello fisico, sono stati analizzati i tipi di indici piu` diffusi sugli strumenti per il data warehousing: accanto ai B-tree, sono stati considerati join index, star index, bitmap index e projection index. Per ciascun tipo di indice e` stato elaborato un modello di costo da utilizzare durante la fase di progettazione fisica. Sono poi stati studiati i piu` diffusi algoritmi per la scelta degli indici in basi di dati di tipo operazionale. Nel rapporto D2.R3 e` stato condotto uno studio preliminare delle tecniche di interrogazione efficienti di basi di dati (query containment, query rewriting, ecc.) e sono state individuate le specificita` del contesto data warehouse in cui studiare l'efficienza delle interrogazioni. Si e` trattato essenzialmente di individuare i metodi di ottimizzazione esistenti piu` adatti ad essere estesi nel nuovo contesto applicativo. In particolare sono stati presi in considerazione sia metodi quantitativi che metodi strutturali per l'ottimizzazione delle interrogazioni e sono state identificate classi di interrogazioni trattabili. Sono state prese in considerazione le interrogazioni necessarie per realizzare le operazioni di popolamento e aggiornamento di "data cube". E` bene notare che tali interrogazioni assumono un carattere estremamente differente dalle interrogazioni di tipo OLAP in quanto non sono eseguite su uno "star schema", ma prevedono l'utilizzo di join fra molte tabelle dello schema globale prodotto dalle attivita` di integrazione e talvolta l'utilizzo di operatori aggregati.

Nella seconda fase e` stata sviluppata una nuova tecnica per l'esecuzione efficiente di interrogazioni volte a popolare i "data cube", basata sull'approccio strutturale. Tale tecnica utilizza la nozione di decomposizione di "HyperTree". Essa consente di risolvere efficientemente la classe di interrogazioni aventi "HyperTree width" limitata e permette anche di utilizzare le informazioni quantitative relative alle relazioni, alla selettivita` degli attributi, etc.. Per quanto riguarda gli altri aspetti di progettazione logica, e` stato proposto un approccio originale alla frammentazione in cui il carico di lavoro e` caratterizzato dalla presenza di query complesse che non possono essere efficacemente descritte solo dal loro pattern di aggregazione. In particolare, sono state considerate interrogazioni espresse da espressioni Nested Generalized Projection/Selection/Join (NGPSJ), in cui e` possibile applicare sequenze di operatori di aggregazione alle misure e definire predicati di selezione, a diverse granularita`, su attributi e misure. Inoltre e` stata prevista la possibilita` di includere nelle viste misure derivate nonche` eventuali misure di supporto per calcolare correttamente gli aggregati in presenza di operatori non distributivi. Sotto queste ipotesi, e` stato proposto un algoritmo efficiente che determina un ristretto insieme di viste candidate alla materializzazione. L'algoritmo costruisce un query view graph i cui vertici rappresentano viste candidate e i cui archi denotano la possibilita` di calcolare una vista a partire da un'altra. Il query view graph puo` poi essere l'input di un algoritmo di ottimizzazione che selezioni, dall'insieme di viste candidate, il sottoinsieme che massimizza le prestazioni con riferimento al carico di lavoro e nel rispetto di un vincolo di spazio assegnato. Per aumentare l'efficacia degli algoritmi proposti, e` stato messo a punto un metodo per la stima delle dimensioni delle viste candidate alla materializzazione tenendo conto degli specifici vincoli di cardinalita` suggeriti dal dominio applicativo. Il problema e` stato affrontato calcolando dapprima bound soddisfacenti per le cardinalita`, poi utilizzandoli per determinare una buona stima probabilistica. In particolare, e` stata proposta una strategia di bounding che raggiunge un compromesso efficace tra bonta` dei bound calcolati e complessita` computazionale, ed e` stato delineato un approccio branch-and-bound per la sua implementazione. I risultati ottenuti nell'ambito della progettazione logico-fisica e del popolamento e dell'interrogazione di data warehouse sono riportati nel rapporto D2.R4.

Infine e` stato affrontato il problema della progettazione fisica utilizzando i modelli di costo messi a punto durante la prima fase. E` stato proposto un algoritmo euristico per la selezione di un insieme ottimale di indici da costruire nell'ambito di data warehouse con viste materializzate. Per raggiungere tale obiettivo e` stato messo a punto un algoritmo di scelta dei piani di esecuzione di un'interrogazione e un modello di costi per la valutazione delle diverse alternative. Gli indici suggeriti dall'algoritmo appartengono a due categorie: i tid-list index e i bitmap index. La progettazione fisica e` descritta nel rapporto D2.R5

Tema 3 - Data Mining

Nella prima fase, sono stati studiati sistemi ed approcci esistenti per il data mining, concentrandosi su tecniche di clustering, metaquerying, visualizzazione, e ricerche approssimate e di similarita`. Per il clustering sono stati effettuati accurati studi comparativi sulle prestazioni dei vari algoritmi, sia dal punto di vista dell'efficienza che da quello della qualita` dei cluster prodotti, anche in presenza di dati affetti da rumore. Per il metaquerying e` stato svolto uno studio approfondito sulle sorgenti di intrattabilita` computazionale di alcune varianti del problema. Sono stati identificati ulteriori casi trattabili che evidenziano un buon interesse applicativo e sono stati progettati alcuni algoritmi per il riconoscimento e la risoluzione di tali casi. Successivamente ci si e` concentrati sull'individuazione di un insieme di varianti del metaquerying che rivelano un buon interesse applicativo e sullo studio delle sorgenti di intrattabilita` computazionale che caratterizzano tali varianti. Lo stesso tipo di analisi e` stata condotta per altre tecniche di data mining, quali le association rules. E` stato effettuato uno studio teorico finalizzato a sistematizzare e formalizzare il rapporto esistente tra le varie modalita` di visualizzazione dei dati e le varie attivita` di scoperta di informazioni. I sistemi e gli approcci esistenti per la visualizzazione di informazioni sono stati confrontati sulla base di un insieme di casi reali di applicazione, allo scopo di scoprirne da una parte le mancanze da superare, e, dall'altra, le caratteristiche positive da mantenere. Tali attivita` di ricerca sono descritte nel rapporto tecnico D3.R1. Sono poi state individuate le caratteristiche di un meta-repository per la descrizione delle attivita` e dei risultati del data mining, in modo da favorire la fruizione di servizi di data mining da parte delle unita` partecipanti al progetto(rapporto D0.R1).

Nella seconda fase e` iniziata la trattazione teorica dei problemi evidenziati nella prima fase, con sviluppo di algoritmi, e individuazione di architetture di sistema. Sono stati studiati metodi di clustering per la soluzione dei problemi derivanti dall'aggiornamento incrementale dei dati del warehouse. In particolare, e` stato presentato un modello generale per la conversione di algoritmi di clustering alla versione dinamica e in grado di operare in memoria esterna. Infine, sono anche state individuate alcune modalita` di visualizzazione dei risultati del clustering e sono state definite le modalita` di comunicazione tra il sottosistema di calcolo, che esegue il data mining, e quello di visualizzazione. L'architettura del sistema integrato di data mining e visualizzazione cosi` ottenuto e` descritta nel rapporto tecnico D3.R2.
Per quanto riguarda le interrogazioni di similarita`, si sono analizzati i paradigmi esistenti per la risoluzione di query approssimate. In particolare, e` stato proposto uno schema di classificazione dei diversi metodi presenti in letteratura, in grado di caratterizzare ogni tecnica sulla base di quattro diverse coordinate: il tipo di dati a cui e` applicabile, il tipo di misure sugli errori prodotti, le garanzie offerte in termini di qualita` dei risultati, il grado di interazione con l'utente. Tale schema risulta estremamente utile nell'analisi delle tecniche approssimate per la risoluzione di query di similarita`, poiche` permette di individuare relazioni e similarita` esistenti tra le diverse tecniche che potrebbero non risultare evidenti ad una prima analisi. Inoltre, tale schema consente di rivelare i limiti intrinseci di ciascuna tecnica, ad esempio per quanto riguarda il campo di applicabilita`. Si e` quindi passati a studiare tecniche di ricerca approssimate in grado di permettere all'utente di controllare la qualita` del risultato. Tra queste si e` identificato l'approccio PAC (Probabilisticamente Approssimativamente Corretto) come il piu` promettente. A partire dalla definizione piu` generale, che permette di ottenere un risultato con un errore inferiore ad un parametro di accuratezza (espresso dall'utente) con probabilita` superiore ad un certo valore di confidenza (anch'esso espresso dall'utente), si sono definiti alcuni tipi generali applicabili alle interrogazioni di similarita`. L'approccio PAC, inizialmente introdotto per la risoluzione di query 1-nearest neighbor, e` stato esteso per la risoluzione di query di range e k-nearest neighbor. Sono quindi stati proposti algoritmi sequenziali per la risoluzione di tali interrogazioni ed un modello in grado di predire il costo necessario per effettuare la ricerca sequenziale. Infine, sono stati proposti degli algoritmi per la risoluzione di interrogazioni di range e k-nearest neighbor approssimate tramite indice. La correttezza di tali algoritmi e` stata dimostrata formalmente ed e` stata anche provata l'ottimalita` della politica di scelta del nodo cui accedere negli algoritmi per la risoluzione di query k-nearest neighbor. Infine relativamente la metaquerying sono stati progettati degli algoritmi efficienti per la risoluzione dei sottocasi trattabili delle varianti di metaquerying individuati nel corso della prima fase. Tali risultati sono riportati nel rapporto tecnico D3.R3.

Per quanto riguarda la disseminazione di risultati, il sito del progetto, all'indirizzo http://www.dis.uniroma1.it/~lembo/D2I/, e' costantemente aggiornato, ed offre accesso a tutti i deliverables prodotti. Si segnala che, tramite questo sito, sono stati presi contatti con alcune aziende del settore interessate ai temi del progetto, e con le quali si stanno intessendo rapporti di collaborazione. Inoltre, in relazione alle attivita` condotte all'interno del tema 1, segnaliamo che le tecniche proposte per l'individuazione e l'estrazione automatica di proprieta` interschema e la generazione automatica di viste riconciliate di dati, sono state oggetto di un'analisi comparativa, che ha coinvolto sia aspetti metodologici che aspetti legati alle prestazioni, da parte di Jayant Madhavan (Universita` di Washington), Philip A. Bernstein (Microsoft Research), and Erhard Rahm (Universita` di Leipzig). Tale analisi e` riportata in

Generic schema matching with Cupid - J. Madhavan, P. A. Bernstein, and Erhard Rahm In Proc. of the 27th International Conference on Very Large Databases (VLDB 2001), Roma, Italia, Settembre 2001.

Segnaliamo ancora che nel corso del primo anno di attivita` del progetto il coordinatore del programma di ricerca Maurizio Lenzerini ha presentato le seguenti relazioni invitate:

- "Data Integration Needs Reasoning" alla 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2001, Vienna, Austria, Settembre 2001;

- "Data Integration Is Harder Than You Thought" alla 6th International Conference on Cooperative Information Systems CoopIS 2001, Trento, Italia, Settembre 2001.

Maurizio Lenzerini e` stato anche organizzatore del 8th International Workshop on Knowledge Representation meets Databases (KRDB-2001, Roma, Italia, 15 Settembre 2001), in cui sono state presentati i primi risultati del progetto, e Guest Editor per una speciale edizione della rivista internazionale "Information Systems" su Data extraction, cleaning and reconciliation (Vol. 26, N.8, Dec. 2001).

Diego Calvanese e` stato co-organizzatore dell'International Workshop on Foundations of Models for Information Integration (FMII-2001), Viterbo, Italia, 16-18 Settembre 2001.

In relazione alle attivita` condotte nel tema 2 durante il primo anno di attivita`, segnaliamo i seguenti eventi di rilievo nazionale ed internazionale che hanno coinvolto alcuni partecipanti al progetto:

- Stefano Rizzi e Matteo Golfarelli hanno tenuto un tutorial dal titolo "Data warehouse design" alla 17th International Conference on Database Engineering (ICDE'01), Heidelberg, nell'Aprile 2001.

- Nell'Ottobre 2001 Stefano Rizzi ha presentato una relazione invitata dal titolo "Applying the Lattice Theory to Estimation Problems in Multidimensional Databases" alla Joint session of the 47th Séminaire Lotharingien de Combinatore and 8th Incontro Italiano di Combinatoria Algebrica (Bertinoro, Forli`).

Relativamente alle attivita` condotte nell'ambito del data mining durante il primo anno di vita del progetto, Tiziana Catarci ha tenuto diverse relazioni invitate in cui ha esposto i risultati del progetto per quanto riguarda visualizzazione e data mining. Inoltre e` stata uno degli organizzatori della 27th International Conference on Very Large Databases (VLDB-2001), Roma, Italia, 11-14 Settembre, 2001.

Infine, segnaliamo che nel 2002 Maurizio Lenzerini presentera` i risultati del progetto nell'ambito di relazioni invitate presso:

- 9th International Workshop on Knowledge Representation meets Databases, KRDB-2002, Tolosa, Francia, 21 Aprile 2002;

- 2002 International Workshop on Description Logics, DL-2002, Tolosa, Francia, 19-21 Aprile 2002;

- 17th Annual IEEE Symposium on Logic in Computer Science LICS 2002, Copenhagen, Danimarca, 22-25 Luglio 2002.

- 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems PODS 2002, Madison, Wisconsin, USA, 3-6 Luglio 2002.

nº	Responsabile	Università	Materiale inventariabile	Materiale di consumo	personale a contratto	Servizi esterni	Missioni	Altro	TOTALE
1.	BERGAMASCHI Sonia	Universita' degli Studi di MODENA e REGGIO EMILIA	28.984.498	1.768.499	24.340.000	1.620.000	19.879.786	5.350.000	81.942.783
2.	CASTANO Silvana	Universita' degli Studi di MILANO	22.115.988	288.000	0	0	19.357.382	0	41.761.370
3.	GRECO Sergio	Universita' degli Studi della CALABRIA	17.377.200	512.730	13.020.000	954.000	55.626.837	6.978.111	94.468.878
4.	LENZERINI Maurizio	Universita' degli Studi di ROMA "La Sapienza"	13.577.000	5.000.000	24.000.000	0	25.789.000	5.238.000	73.604.000
5.	RIZZI Stefano	Universita' degli Studi di BOLOGNA	22.770.610	2.112.800	15.190.002	1.145.921	47.259.320	0	88.478.653
			104.825.296	9.682.029	76.550.002	3.719.921	167.912.325	17.566.111	380.255.684