MINISTERO DELL

1. Area Scientifico Disciplinare principale	09: Ingegneria industriale e dell'informazione
2. Coordinatore Scientifico del programma di ricerca	LENZERINI Maurizio
- Università	Universita' degli Studi di ROMA "La Sapienza"
- Facoltà	Facolta' di INGEGNERIA
- Dipartimento/Istituto	Dip. INFORMATICA E SISTEMISTICA
3. Titolo del programma di ricerca	D2I: Integrazione, warehousing e mining di sorgenti eterogenee di dati
4. Settore principale del Programma di Ricerca:	K05A
5. Costo originale del Programma:	881.000.000 Lire (454.999 Euro)
6. Quota Cofinanziamento MIUR:	564.000.000 Lire (291.282 Euro)
7. Quota Cofinanziamento Ateneo:	254.000.000 Lire (131.180 Euro)
8. Finanziamento totale:	818.000.000 Lire (422.462 Euro)
9. Durata:	24 mesi

Gli sviluppi dell'informatica e delle telecomunicazioni hanno reso disponibile l'accesso ad un numero sempre piu' vasto di banche dati strutturate e semistrutturate, create in tempi diversi, su sistemi diversi e con criteri organizzativi diversi. Senza l'applicazione di opportuni metodi, gli utenti hanno a disposizione grandi quantita' di dati, ma trovano inevitabili difficolta' nel sintetizzare l'informazione utile ai propri scopi. Risulta quindi importante ricercare nuove metodologie per l'integrazione di sorgenti eterogenee di dati, per il progetto di basi di dati destinate all'analisi in linea di dati di sintesi (data warehouse), e per la scoperta di nuovi collegamenti e proprieta' non facilmente intuibili all'interno di una sorgente o di sorgenti diversi (data mining). L'obiettivo 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:
Tema 1: integrazione di dati provenienti da sorgenti eterogenee,
Tema 2: progettazione e interrogazione di data warehouse,
Tema 3: data mining.
La problematica trattata riveste grande importanza applicativa e industriale, specialmente in relazione alla opportunita' di estrarre informazione di rilevanza direzionale e strategica dai dati del livello operativo delle imprese. I temi del progetto sono infatti centrali per la componente di data management nei sistemi di Enterprise Knowledge Management e di Enterprise Resource Planning. Le unita' partecipanti sono 5, e le idee alla base della proposta sono state maturate in occasione della partecipazione a progetti europei ed italiani, in particolare Esprit DWQ e INTERDATA, finanziati rispettivamente dall'UE e dal MURST nel 1997. Il coordinamento e' centrato sulla collaborazione di un coordinatore per ciascuno dei temi, assicurando cosi' un monitoraggio ed una interazione continua tra le unita'. L'obiettivo e' sperimentare e valutare i metodi e gli strumenti proposti attraverso collaborazioni con partner industriali.

Oltre all'obiettivo generale di un quadro metodologico complessivo, che produrra' anche la definizione e la realizzazione di uno strumento per la gestione dei meta-dati rilevanti rispetto alle attivita' di integrazione, warehousing e mining, gli obiettivi specifici dei tre temi vengono illustrati di seguito.

TEMA 1: L'obiettivo è lo sviluppo di metodi e strumenti per l'integrazione di dati provenienti da sorgenti fortemente e strutturalmente eterogenee, ossia da sorgenti di tipo strutturato (ad es., basi di dati), o semistrutturato (ad es., documenti HTML e XML). I metodi di rappresentazione dei dati presenti nelle sorgenti devono tenere conto di sorgenti semistrutturate, e di possibile coesistenza di versioni diverse dei dati. Si deve poi tenere conto che la scoperta di proprietà inter-schema è cruciale per caratterizzare le relazioni semantiche tra dati in diverse sorgenti, ed è complicata dal fatto che le informazioni semantiche sulle sorgenti stesse sono spesso implicite. Infine, il processo che conduce alla risposta ad interrogazioni poste in termini di viste globali pone problemi sia per la suddivisione della query in sottoquery, sia per la ricostruzione della risposta. I principali risultati che si intendono perseguire riguardano la definizione di una metodologia di integrazione di sorgenti fortemente eterogenee, la definizione di tecniche semiautomatiche di clustering di sorgenti basate su proprieta' di affinita' e corrispondenze semantiche, la progettazione di algoritmi per la riscrittura di interrogazioni su viste globali in termini di interrogazioni sulle sorgenti, la definizione di metodi per la gestione di versioni diverse delle sorgenti, la caratterizzazione di opportuni parametri per descrivere la qualità dei dati, e di tecniche per la riconciliazione di dati provienti da sorgenti diverse, la progettazione e la realizzazione di un ambiente che supporti l'attivita' d'integrazione, basato sulla gestione di meta-dati.

TEMA 2: Nella letteratura sono state proposte diverse architetture per data warehouse e varie metodologie di progettazione a queste associate. Le architetture possono essere classificate in architetture ad uno, due o tre livelli. In un'architettura dell'ultimo tipo, i tre livelli memorizzano i dati operazionali, riconciliati e derivati. Il livello dei dati riconciliati viene gestito tramite tecniche di integrazione, oggetto del tema 1. Nel contesto data warehouse, si pongono nuove e complesse problematiche relative sia alla progettazione che all'interrogazione dei dati. Obiettivo del tema è lo sviluppo di tecniche per la progettazione e l'interrogazione efficiente di data warehouse, con particolare riferimento al livello dei dati derivati, sia dal punto di vista logico che fisico. Ci si propone di definire tecniche efficaci per la materializzazione di viste in presenza di un carico di lavoro complesso, e per l'individuazione di un insieme ottimale di indici per l'accesso veloce ai dati. Il problema della interrogazione efficiente di data warehouse sarà affrontato principalmente come problema di riscrittura di interrogazioni su viste materializzate. I risultati che si intendono perseguire in questo contesto riguardano la definizione di tecniche di ottimizzazione, basate sulla struttura delle interrogazioni, che estendono metodi già esistenti in maniera da tenere conto delle specificità dell'ambiente data warehouse.

TEMA 3: L'obiettivo e` l'estrazione di informazioni da grandi quantita` di dati, nota con il termine "data mining". La ricerca operera` in numerose direzioni con lo scopo di trattare gli aspetti piu` rilevanti e a tutt'oggi meno esplorati. Verranno trattati vari tipi di dati, da quelli strutturati, tipici dei sistemi di basi di dati, a quelli multimediali (quali DB di immagini). La conoscenza estratta sara` di diversi tipi, dall'informazione sui raggruppamenti di oggetti (clustering), al meta-querying, che cerca pattern complessi all'interno dei dati con tecniche di tipo logico. Particolare cura sara` dedicata agli aspetti di visualizzazione dell'informazione estratta e di adattabilita` a vari tipi di utenti, nella convinzione che la forma di presentazione e l'interazione con l'utente siano esse stesse fattori critici per l'efficacia del processo di estrazione e la fruibilita` dell'informazione. Per quanto riguarda i metodi di estrazione, verranno considerate le problematiche che sorgono quando la sorgente di dati e` un data warehouse. In questo caso, sorge spesso la necessita` di effettuare elaborazioni incrementali, poiche' i dati vengono consolidati periodicamente, ed e' importante evitare la ripetizione di attivita` molto onerose dal punto di vista computazionale, come ad esempio il clustering. I principali risultati che si intende produrre riguardano: algoritmi di clustering incrementale, paradigmi per query di similarita`, inclusi quelli con approssimazione, formalizzazione degli indicatori in grado di quantificare il compromesso "qualita` vs costo", strategie di ausilio per permettere all'utente di formulare facilmente un piano per la scoperta di informazioni nascoste, primitive per la creazione semiautomatica di visualizzazioni, caratterizzazione computazionale di varianti di meta-querying di interesse applicativo, algoritmi efficienti per il meta-querying. Il livello dei meta-dati, cui fanno riferimento i temi 1 e 2, costituira' il punto di riferimento sia per i dati di input alle attivita' di mining, sia per la rappresentazione delle proprieta' estratte dal mining.

La ricerca eseguita, insieme ai risultati conseguiti, verra' descritta facendo riferimenti alle tre fasi previste per il progetto, ed iniziando con le attivita` comuni ai tre temi. Riguardo a tali attivita', 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. 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. Nella terza fase si e' proceduto alla specifica dettagliata delle varie funzionalita'. Questa attivita', sotto la guida dell'unita' del responsabile del progetto, e' stata condotta congiuntamente da tutte le unita'.

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 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 e 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. Nella terza fase e' stato realizzato un insieme di prototipi che realizzano le funzioni enucleate dai risultati scientifici prodotti nella fase precedente. Le metodologie, le tecniche ed i prototipi sviluppati sono stati poi sperimentati secondo quanto stabilito dagli obiettivi iniziali.

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. Nella terza fase e' stato realizzato un insieme di prototipi che realizzano le funzioni enucleate dai risultati scientifici prodotti nella fase precedente. Le metodologie, le tecniche ed i prototipi sviluppati sono stati poi sperimentati secondo quanto stabilito dagli obiettivi iniziali.

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. 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. 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 isualizzazione. 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 equenziali 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. Nella terza fase e' stato realizzato un insieme di prototipi che realizzano le funzioni enucleate dai risultati scientifici prodotti nella fase precedente. Le metodologie, le tecniche ed i prototipi sviluppati sono stati poi sperimentati secondo quanto stabilito dagli obiettivi iniziali.

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 e prodotti. 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). 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). 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. Tiziana Catarci ha tenuto diverse relazioni invitate in cui ha esposto i risultati del progetto per quanto riguarda visualizzazione e data mining. Maurizio Lenzerini ha presentato i risultati del progetto presso: 9th International Workshop on Knowledge Representation meets Databases, KRDB-2002, Tolosa, Francia, 2002 - Relazione Invitata; 2002 International Workshop on Description Logics, DL-2002, Tolosa,Relazione Invitata; 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2002, Madison, - Tutorial Invitato. Sonia Bergamaschi ha tenuto un intervento al Knowledge Technologies Workshop organizzato da INFSO/D5 nella giornata dedicata ai progetti su Semantic Web, Lussemburgo, 16 Maggio 2002. Ha inoltre tenuto le seguenti relazioni invitate: Peer to Peer Paradigm for a Semantic Search Engine, AICA 2002 XL Congresso Annuale, Conversano (Bari), 2002; "SEWASIE: a Semantic SearchEngine", Workshop on Ontologies for Multi-Agent Systems, EKAW 2002, Siguenza, Spagna, 2002. Nel novembre 2002 Stefano Rizzi è stato invitato presso il FER dell'Università di Zagabria a tenere una lecture dal titolo Main issues in data warehouse design. Silvana Castano è stata invitata in qualità di relatore su tematiche di integrazione semantica di dati al panel su Scientific Data Integration presso la VIII Conference on Extending Database Technology (EDBT 2002). Tiziana Catarci è Conference Chair della Fourth International Conference on Web Information Systems Engineering (WISE 2003). Stefano Rizzi è Program chair del Sixth ACM International Workshop on Data Warehousing and OLAP (DOLAP'03). Tiziana Catarci ha ricevuto nel 2003 un Eclipse IBM Award per le sue attivita' di ricerca legate a visualizzazioni avanzate di grandi quantita' di dati. Maurizio Lenzerini nel corso del 2003 terrà interventi invitati su: Logic-based Information Integration (Fourth Panellenic Logic Symposium), Data Integration (Eleventh Italian Symposium on Advanced Database Systems, SEDB 2003), Intelligent Information Integration (IJCAI 2003).

I risultati complessivi del progetto saranno presentati in occasione di un workshop organizzato a Milano nel marzo 2003 come giornata del GdL su Basi di Dati dell'AICA. Infine, e' in corso di preparazione un volume della Springer Verlag dedicato alla illustrazione dei risultati del progetto.

nº	Università	Facoltà	Responsabile	Quota Ateneo	Cofinanziamento assegnato	Finanziamento totale	Pagato	Residuo da saldare (già fatturato)	Impegnato	Spese globali sostenute
1.	Universita' degli Studi di MODENA e REGGIO EMILIA	Facolta' di INGEGNERIA	BERGAMASCHI Sonia	19.108,9 (36.999.768 Lire)	43.898,83 (84.999.477 Lire)	63.007,73 (121.999.245 Lire)	63.005 (121.993.959 Lire)	0 (0 Lire)	0 (0 Lire)	63.007,73 (121.999.245 Lire)
2.	Universita' degli Studi di MILANO	Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI	CASTANO Silvana	21.174,72 (40.999.729 Lire)	44.415,29 (85.999.477 Lire)	65.590,01 (126.999.206 Lire)	57.856 (112.024.165 Lire)	0 (0 Lire)	7.740 (14.986.640 Lire)	65.590,01 (126.999.206 Lire)
3.	Universita' degli Studi della CALABRIA	Facolta' di INGEGNERIA	GRECO Sergio	32.536,77 (62.999.593 Lire)	67.655,85 (130.999.206 Lire)	100.192,62 (193.998.800 Lire)	84.427 (163.472.486 Lire)	15.780 (30.554.157 Lire)	0 (0 Lire)	100.192,62 (193.998.800 Lire)
4.	Universita' degli Studi di ROMA "La Sapienza"	Facolta' di INGEGNERIA	LENZERINI Maurizio	27.888,67 (53.999.671 Lire)	64.557,11 (124.999.245 Lire)	92.445,78 (178.998.916 Lire)	92.453 (179.012.895 Lire)	0 (0 Lire)	0 (0 Lire)	92.445,78 (178.998.916 Lire)
5.	Universita' degli Studi di BOLOGNA	Facolta' di SCIENZE MATEMATICHE FISICHE e NATURALI	RIZZI Stefano	30.470,95 (58.999.632 Lire)	70.754,59 (136.999.167 Lire)	101.225,54 (195.998.800 Lire)	101.233 (196.013.244 Lire)	0 (0 Lire)	0 (0 Lire)	101.225,54 (195.998.800 Lire)
				131.176 (253.990.629 Lire)	291.279 (563.991.403 Lire)	422.459 (817.989.777 Lire)	398.974 (772.516.749 Lire)	15.780 (30.554.157 Lire)	7.740 (14.986.640 Lire)	422.459 (817.989.777 Lire)

	(mesi uomo)
	I anno	II anno	TOTALE
da personale universitario	92	95	187
altro personale	84	83	167
personale a contratto	26	42	68

	(numero)
partecipazioni a convegni:
in Italia	39
all'estero	60
articoli pertinenti pubblicati:
su riviste italiane con referee	1
su riviste straniere con referee	40
su altre riviste italiane	1
su altre riviste straniere	0
comunicazioni a convegni/congressi internazionali	111
comunicazioni a convegni/congressi nazionali	20
rapporti interni	29
brevetti depositati	0

nº	Responsabile (Cognome e nome)	Università	Materiale inventariabile	Grandi Attrezzature	Materiale di consumo	Spese per calcolo ed elaborazione dati	personale a contratto	Servizi esterni	Missioni	Altro	TOTALE
1.	BERGAMASCHI Sonia	Universita' degli Studi di MODENA e REGGIO EMILIA	14.934 (28.916.083 Lire)	0 (0 Lire)	1.968 (3.810.556 Lire)	1.910 (3.698.253 Lire)	17.440 (33.768.346 Lire)	3.152 (6.103.086 Lire)	20.565 (39.819.153 Lire)	3.036 (5.878.480 Lire)	63.005 (121.993.959 Lire)
2.	CASTANO Silvana	Universita' degli Studi di MILANO	19.410 (37.582.775 Lire)	0 (0 Lire)	943 (1.825.892 Lire)	0 (0 Lire)	14.068 (27.239.283 Lire)	0 (0 Lire)	23.435 (45.376.215 Lire)	0 (0 Lire)	57.856 (112.024.165 Lire)
3.	GRECO Sergio	Universita' degli Studi della CALABRIA	23.381 (45.271.657 Lire)	0 (0 Lire)	3.877 (7.506.874 Lire)	3.840 (7.435.232 Lire)	15.510 (30.031.367 Lire)	9.732 (18.843.666 Lire)	39.264 (76.025.249 Lire)	4.603 (8.912.597 Lire)	100.207 (194.026.643 Lire)
4.	LENZERINI Maurizio	Universita' degli Studi di ROMA "La Sapienza"	21.227 (41.100.957 Lire)	0 (0 Lire)	7.480 (14.483.213 Lire)	2.612 (5.057.507 Lire)	14.460 (27.998.296 Lire)	10.100 (19.556.210 Lire)	30.811 (59.658.057 Lire)	5.763 (11.158.657 Lire)	92.453 (179.012.895 Lire)
5.	RIZZI Stefano	Universita' degli Studi di BOLOGNA	29.648 (57.406.188 Lire)	0 (0 Lire)	2.060 (3.988.692 Lire)	0 (0 Lire)	29.331 (56.792.394 Lire)	1.547 (2.995.392 Lire)	38.647 (74.830.577 Lire)	0 (0 Lire)	101.233 (196.013.244 Lire)
			108.600 (210.277.659 Lire)	0 (0 Lire)	16.328 (31.615.227 Lire)	8.362 (16.190.993 Lire)	90.809 (175.829.687 Lire)	24.531 (47.498.354 Lire)	152.722 (295.709.251 Lire)	13.402 (25.949.735 Lire)	414.754 (803.070.906 Lire)