MINISTERO
DELL'ISTRUZIONE
DELL'UNIVERSITÀ
E DELLA RICERCA |
![](http://cofin.cineca.it/murst-dae/icone/fin95/STEMMA2.GIF) |
Programmi di ricerca cofinanziati - Modello D
Rendiconto del programma di ricerca - ANNO 2000
prot. MM09268483
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 |
10. Obiettivo della ricerca eseguita
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.
11. Descrizione della Ricerca eseguita e dei
risultati ottenuti
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.
12. Problemi riscontrati nel corso della ricerca
Nella relazione prodotta alla
fine del primo anno si segnalava la difficoltà da parte dell'unità di
Bologna a portare a compimento gli obiettivi stabiliti per le fasi 3 e 4 del
progetto, in particolare relativamente alla realizzazione di prototipi. Il
responsabile dell'unita' di Bologna sottolineava le difficoltà dovute alla
defezione di alcuni membri del gruppo di ricerca. Per fronteggiare le
situazione, l'unita' di Bologna ha messo in campo un rilevante sforzo
aggiuntivo, ed ha prodotto, senza oneri ulteriori per il consorzio, il
prototipo previsto, "D1-P4: Prototipo di strumento per la manipolazione
di versioni di schema in ambito eterogeneo".
Negli obiettivi generali del progetto, era prevista una sperimentazione
condotta in collaborazione con la Telecom Italia. L'accordo con tale azienda
prevedeva che i metodi e gli strumenti proposti fossero sperimentati e
validati attraverso una collaborazione con la Divisione di Data
Administration, Data Warehouse, Data Mining (Direttore: Ing. Stefano
Trisolini) della Telecom Italia. La sperimentazione doveva riguardare in
particolare la raccolta e l'analisi dei dati relativi al traffico telefonico e
al customer care. Nel corso del secondo anno del progetto, a fronte di una
riorganizzazione della Telecom Italia, la Divisione di Data Administration,
Data Warehouse, Data Mining e' stata sciolta, ed il Direttore, Ing. Stefano
Trisolini ha lasciato l'azienda. I successivi tentativi per individuare un
Dipartimento Telecom con cui riprendere i contatti non hanno avuto successo.
Per fronteggiare questa situazione, sono stati presi contatti, all'inizio del
secondo anno, con altre aziende potenzialmente interessate alla
sperimentazione. Tra queste, la CM Sistemi, Roma, ha offerto forme di
collaborazione concreta, che sono sfociate in due accordi scientifici,
rispettivamente con l'Universita' di Roma "La Sapienza", e con
l'Universita' della Calabria, con l'obiettivo di realizzare un sistema di
integrazione ed un sistema di progettazione di data warehouse in linea con le
tecniche sviluppate nell'ambito del progetto. Le collaborazioni, che sono
attualmente in corso, hanno quindi per oggetto il tema 1 ed il tema 2, e
prevedono anche la sperimentazione, in parte gia' condotta, delle metodologie
proposte nel progetto in ambiti applicativi di interesse per l'azienda.
Nell'ambito del Tema 3 del progetto, sono stati presi contatti ed effettuati
riunioni con la società Inspiring Software s.r.l. di Milano, che opera nel
settore dell'Information Technology per le aziende manufatturiere. La
collaborazione con tale societa' e' scaturita in contratto di ricerca con
l'Unità di Roma, avente per oggetto l'applicazione di tecniche di data mining
visuale sviluppate nell'ambito del progetto. Tali tecniche sono di interesse
per la Inspiring Software s.r.l. allo scopo di dotare i sistemi di controllo
di processi manufatturieri di capacita' di data warehousing e data mining. Le
tecniche e le metodologie oggetto della collaborazione sono state
successivamente sperimentate dalla Inspiring Software s.r.l. in una
applicazione relativa a processi manufatturieri nell'industria alimentare.
Un ultimo problema riscontrato ha riguardato la realizzazione del prototipo
del repository di meta-dati. Poiche' nella definizione di tale repository ci
si e' basati sul linguaggio XML, che sta diventando uno standard nello scambio
dati, al momento della realizzazione e' stata condotta un'analisi degli
strumenti disponibili per la gestione di dati XML. Tale analisi ha rilevato
carenze sostanziali di questi strumenti (ad esempio nella espressione e nella
esecuzione di query), che avrebbero pregiudicato la significativita' della
realizzazione. Si e' quindi deciso di non procedere alla realizzazione stessa,
e di affidare il coordinamento degli altri prototipi alle specifiche del
repository stesso, che di fatto stabiliscono il formato dei meta-dati oggetto
di scambio tra i vari prototipi, e che sono state concordate da tutte le
unita'.
13. Elenco unità di ricerca che hanno
partecipato al programma di ricerca
nº |
Università |
Facoltà |
Responsabile |
Quota Ateneo |
Cofinanziamento
assegnato |
Finanziamento totale |
Pagato |
Residuo da saldare
(già fatturato) |
Impegnato |
Spese globali
sostenute |
Nota |
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) |
|
14. Risorse umane complessivamente ed
effettivamente impegnate
|
(mesi uomo) |
I anno |
II anno |
TOTALE |
da personale universitario |
92 |
95 |
187 |
altro personale |
84 |
83 |
167 |
personale a contratto |
26 |
42 |
68 |
15. Modalità di svolgimento (dati complessivi)
|
(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 |
16. Tabella delle spese sostenute
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) |
(per la copia da depositare presso l’Ateneo e
per l’assenso alla diffusione via Internet delle informazioni riguardanti i
programmi finanziati legge del 31.12.96 n° 675 sulla "Tutela dei dati
personali")
Data
30/01/2003 10:40 |
|
Firma
....................................................... |