|
|
Partecipante |
Dipartimento/Istituto |
Qualifica |
|
|
BARTOLINI
ILARIA |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Dottorando |
|
|
CIACCIA
PAOLO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Prof. ordinario |
|
|
GOLFARELLI
MATTEO |
CENTRO DI GESTIONE DELLA SPESA DI CESENA |
Ricercatore |
|
|
GRANDI
FABIO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Prof. associato |
|
|
LODI STEFANO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Ricercatore |
|
|
MAIO
DARIO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Prof. ordinario |
|
|
PATELLA
MARCO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Titolare di assegno di ricerca |
|
|
PENZO
WILMA |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Ricercatore |
|
|
RIZZI
STEFANO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Prof. associato |
|
|
SARTORI
CLAUDIO |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Prof. associato |
|
|
SCALAS
MARIA RITA |
ELETTRONICA, INFORMATICA E SISTEMISTICA |
Prof. associato |
Titolo specifico
del programma svolto dall'unità di ricerca
Aspetti progettuali, di integrazione e di interrogazione
per sistemi di data warehousing
Descrizione del
programma e dei compiti dell'Unità di Ricerca
Gli argomenti che verranno trattati dall'unità sono
classificabili secondo i tre temi definiti all'interno del progetto
nazionale:
Tema 1: Verranno studiati i problemi di integrazione di sorgenti eterogenee
in presenza di versioni di schema.
Tema 2: Verranno affrontate le principali problematiche legate alla
progettazione logica e fisica di data warehouse, assumendo come modello
logico target il modello relazionale.
Tema 3: Verranno affrontati argomenti legati al trattamento di interrogazioni
di similarità, nonché metodi incrementali di data clustering per il
data warehousing su dati metrici e categorici.
Fase 1 (durata
4 mesi
- dal 1/12/2000 al 31/3/2001)
TEMA 1. In questa fase la ricerca inizierà lo studio dell'impatto
della presenza di diverse versioni di schema sul processo di integrazione
(con particolare riferimento alle basi di dati object-oriented), presenza
che è fonte intrinseca di eterogeneità. In particolare,
verranno prese in considerazione sorgenti in cui i medesimi dati sono
rappresentati mediante versioni di schema diverse, create da successive
modifiche apportate allo schema stesso. La presenza di sorgenti "versionate"
influirà quindi sulla definizione dei metadati che descrivono
le diverse tipologie di sorgenti nel meta-data repository. Le sorgenti
da integrare verranno descritte mediante la definizione di un modello
generalizzato per il supporto di versioni di schema. Il tipo di eterogeneità
di interesse sarà invece modellato tramite la formalizzazione
delle relazioni inter-versione indotte dalle modifiche di schema applicate.
L'enfasi non sarà posta tanto sull'aspetto procedurale della
gestione delle versioni di dati e schemi, che costituisce l'approccio
"classico", ma piuttosto sulla semantica sottostante: l'uso
di una specifica dichiarativa per il processo di generazione e gestione
delle versioni costituirà il punto di partenza per la descrizione
delle sorgenti a livello integrato/riconciliato, in cui le versioni
potranno essere coinvolte in query e modifiche multischema.
TEMA 2. L'unità condurrà un’analisi approfondita
della letteratura sulla progettazione logica e fisica di data warehouse.
In particolare, per il livello logico si analizzeranno in modo critico
le funzioni di costo proposte finora e si identificheranno 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. Verranno
poi studiati gli algoritmi di partizionamento proposti nell’ambito
delle basi di dati operazionali e dei sistemi distribuiti. Per quanto
riguarda la stima della cardinalità delle viste, si valuterà
l’efficacia dei criteri di tipo statistico e si evidenzieranno
ulteriori possibili criteri da adottare. Per il livello fisico, l'unità
analizzerà i tipi di indici più diffusi sugli strumenti
per il data warehousing: accanto ai B-tree, verranno considerati join
index, star index, bitmap index e projection index. Per ciascun tipo
di indice verrà elaborato un modello di costo da utilizzare
durante la fase di progettazione fisica. Verranno infine analizzati
i più diffusi algoritmi per la scelta degli indici in basi
di dati di tipo operazionale.
TEMA 3. L'applicazione di un metodo di clustering a un data warehouse
richiede la capacità di elaborazione incrementale dei dati.
Poiché il metodo deve fornire una soluzione il più possibile
uniforme, per la presenza elaborazioni effettuate in tempi diversi
è necessario occuparsi sia delle prestazioni che della qualità
dei risultati. Si propone una valutazione dei metodi di accesso a
spazi metrici e della loro applicabilità agli algoritmi locality-based.
Inoltre, si propongono l’analisi e il confronto dei metodi di
clustering in data warehouse attualmente noti in letteratura, con
valutazione dei costi e della qualità delle clusterizzazioni
ottenibili. In questa prima fase si analizzeranno anche i paradigmi
esistenti per query di similarità, inclusi quelli che fanno
uso di tecniche di approssimazione. In particolare, si analizzeranno
criticamente i criteri esistenti per misurare la "qualità
del risultato".
Fase 2 (durata
8 mesi
- dal 1/4/2001 al 30/11/2001)
TEMA 1. Verrà sviluppato un approccio per la gestione di sorgenti
dotate di versioni di schema con lo scopo di definire una metodologia
di integrazione sulla base della quale saranno introdotte le specifiche
funzionali di un Query Manager (in collaborazione con l'unità
di MO). In particolare, la metodologia di integrazione sarà
basata anche sull'impiego delle relazioni inter-versione definite
in precedenza. Tramite l'uso di logiche descrittive, di cui si intende
sfruttare l'apparato di deduzione automatica, saranno riformulati
descrizione delle sorgenti, relazioni inter-versione e problemi di
integrazione. Verrà dimostrata la correttezza formale dell'approccio,
che costituisce il fondamento teorico dell'intero edificio metodologico.
Infine, nella definizione degli algoritmi di riscrittura di interrogazioni
utilizzati nel Query Manager si terrà conto della possibile
presenza di sorgenti "versionate". Una singola interrogazione
rispetto a sorgenti "versionate" potrà coinvolgere
una o più versioni. Si definiranno quindi algoritmi per la
riscrittura di interrogazioni multiversione basate su tecniche di
query rewriting e query answering using views.
TEMA 2. L'unità affronterà dapprima il problema della
progettazione logica di data warehouse. Verrà studiato il 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. Verrà
poi analizzata l’utilità della frammentazione orizzontale
e verticale delle viste materializzate, effettuata sulla base del
carico di lavoro e tenendo conto di vincoli di spazio. Per entrambi
i problemi dovranno essere definite funzioni di costo ad hoc, che
ne permettano una formulazione come problemi di ottimizzazione. Per
aumentare l’efficacia degli algoritmi proposti, verranno messi
a punto metodi per la stima delle dimensioni delle viste candidate
alla materializzazione tenendo conto degli specifici vincoli di cardinalità
suggeriti dal dominio applicativo. Successivamente, l'unità
affronterà il problema della progettazione fisica utilizzando
i modelli di costo messi a punto durante la prima fase. Il problema
della scelta ottimale degli indici verrà affrontato delineando
un insieme di criteri "di buon senso" da un lato, definendo
algoritmi di tipo euristico dall'altro.
TEMA 3. Gli algoritmi locality-based utilizzano solo informazioni
nell'intorno di un punto per stabilire l'appartenenza di esso ad un
cluster; la proprietà di località rende possibile, in
linea di principio, l’analisi incrementale, cioè la ricostruzione
della clusterizzazione aggiornata dall’ultima e da transazioni
d’aggiornamento. Algoritmi di clustering locality-based, in particolare
basati sul principio di condivisione dei primi vicini sono stati proposti
nella pattern recognition. Proponiamo di studiare la applicabilità
dei metodi di clustering basati sui primi vicini all’analisi
incrementale. Inoltre, verranno definiti indicatori adeguati a caratterizzare
la qualità del risultato di ricerche approssimate, estendendo
i classici concetti di "precisione" e "completezza"
al fine di meglio modellare il caso di query complesse; coerentemente
con tali indicatori verranno poi definiti paradigmi di ricerca approssimata
in grado di permettere all'utente di controllare la qualità
del risultato. Infine, si lavorerà alla definizione dell’architettura
del sistema integrato di data mining e visualizzazione e alla definizione
del meta-data repository per la descrizione dei risultati e delle
attività del data mining.
Fase 3 (durata
8 mesi -
dal 1/12/2001 al 31/7/2002)
TEMA 1. Nella terza fase verrà sviluppato un prototipo che realizza
le funzioni descritte nella fase 2. Tale prototipo si occuperà della
riscrittura di interrogazioni multiversione integrata nella fase di
riscrittura di interrogazioni supportata dal Query Manager.
TEMA 2. Le tecniche prodotte durante la seconda fase verranno implementate
in un prototipo. Il prototipo accetterà in ingresso uno schema concettuale
di data mart, un carico di lavoro espresso nei termini individuati
durante la prima fase, eventuali vincoli aggiuntivi propri del dominio
applicativo (di spazio, di cardinalità, classi di indici disponibili,
ecc.); effettuerà il progetto logico utilizzando gli algoritmi di
materializzazione e frammentazione proposti nella seconda fase, producendo
lo schema logico del data mart; effettuerà il progetto fisico utilizzando
gli algoritmi di scelta degli indici proposti nella seconda fase,
producendo infine lo schema fisico del data mart. Verranno generate
in automatico le istruzioni SQL per la creazione delle tabelle necessarie,
nonché per la creazione degli indici.
TEMA 3. Uno degli obiettivi della ricerca sarà sviluppare uno strumento
integrato di clustering di dati originati da Data Warehouse. In tale
ambiente, è certamente desiderabile l'applicazione di algoritmi incrementali,
per sfruttare le tecniche di consolidamento e materializzazione incrementali
tipiche degli strumenti di DW. Poiché le transazioni di aggiornamento
solo una frazione dei punti di un warehouse, un algoritmo locality-based
in grado di costruire la nuova clusterizzazione a partire dalla più
recente e da transazioni di aggiornamento può consentire l'ottenimento
di un rilevante speed-up rispetto alla costruzione dall'immagine già
aggiornata del warehouse. Si propone di produrre un prototipo che
comprenda un motore di data clustering, un generatore di dati sintetici
per la sperimentazione, un’interfaccia grafica utente in ambiente
Windows NT/95, uno strumento di valutazione delle prestazioni. Per
una più facile condivisione con le altre componenti del progetto,
le attività e i risultati del clustering saranno descritte nel meta-data
repository. Sarà anche sviluppato un prototipo in grado di supportare
e risolvere efficientemente query complesse permettendo all'utente
di decidere le risorse da impiegare e di controllare la qualità del
risultato.
Fase 4 (durata
4 mesi
- dal 1/8/2002 al 30/11/2002)
TEMA 1. Si procederà con l'integrazione del prototipo definito
nella fase precedente nell'ambito di un framework comune per la descrizione
delle singole sorgenti e del livello integrato/riconciliato. Seguirà
una fase di validazione e sperimentazione del framework così
ottenuto con applicazione ad un caso reale.
TEMA 2. Le tecniche di progettazione logica e fisica saranno sperimentate
utilizzando i più diffusi strumenti di data warehousing, sulla
base di benchmark di varia natura. Verranno validati sperimentalmente
i modelli di costo degli indici elaborati durante la prima fase. Infine,
verrà effettuata una valutazione comparativa dei benefici della
materializzazione, della frammentazione e dell’indicizzazione.
TEMA 3. Quest'ultima fase prevede la sperimentazione estensiva e congiunta
dei prototipi realizzati, considerando sia insiemi di dati reali che
sintetici, al fine di caratterizzarne compiutamente le prestazioni.
In particolare, si definiranno criteri di qualità per la clusterizzazione
ottenuta, per valutare il rapporto tra costi di esecuzione e prestazioni.
Prodotti dell'Unità
di Ricerca
La cifra dopo la D indica il tema di ricerca di
riferimento per il prodotto (se è 0 il risultato è comune
a tutti i temi). La lettera successiva indica il tipo del documento
(sigla R: rapporto tecnico, sigla P: prototipo software). La lista
tra parentesi indica le unità coinvolte nella produzione del
risultato (BO-Bologna, CS-Cosenza, MI-Milano, MO-Modena, RM-Roma).
In grassetto è evidenziata l'unità responsabile per
ciascun prodotto.
Al
termine della Fase 1
(scadenza il 31 marzo 2001)
D0.R1:
Specifiche per il meta-data repository (RM,BO,CS,MI,MO).
D1.R1: Metodi
e tecniche di estrazione, rappresentazione ed integrazione di sorgenti
strutturate e semistrutturate (CS,BO,MI,MO,RM).
D1.R4:
Introduzione di un approccio formale per la gestione di versioni di
schema in ambiente eterogeneo (BO).
D2.R1: Documento
sui risultati dell'analisi dello stato dell'arte sulle architetture
di data warehouse (CS,BO)
D2.R2:
Documento sull'analisi dello stato dell'arte sulle tematiche di progettazione
logico-fisica del livello dei dati derivati (BO)
D3.R1:
Analisi e confronto di metodi e algoritmi di data mining, con particolare
riferimento a clustering, metaquerying, tecniche di visualizzazione,
ricerche approssimate e di similarità (BO,CS,RM)
Al
termine della Fase 2
(scadenza il 30 novembre 2001)
D0.R2: Specifica della architettura funzionale del repository di meta-dati
(RM,BO,CS,MI,MO).
D1.R6:
Descrizione della metodologia di integrazione di sorgenti fortemente
eterogenee (MI,BO,MO).
D2.R4:
Tecniche di progettazione logica e di interrogazione efficiente di
data warehouse (BO,CS).
D2.R5:
Scelta ottimale di indici in sistemi di data warehouse (BO).
D3.R2: Architettura
del sistema integrato di data mining e visualizzazione (RM,BO,CS).
D3.R3:
Studio di metodi di mining per: clustering, ricerche approssimate,
metaquerying (BO,CS).
Al
termine della Fase 3
(scadenza il 31 luglio 2002)
D0.P1: Repository di Meta-dati (BO,CS,MI,MO,RM).
D1.P4: Prototipo di strumento per la manipolazione di versioni di
schema di schema in ambito eterogeneo (BO).
D2.P1: prototipo sviluppato per la progettazione logico-fisica (BO).
D3.P1: Algoritmi di clustering incrementale di dati (BO).
D3.P2: Risoluzione di query approssimate (BO).
Al
termine della Fase 4
(scadenza il 30 dicembre 2002)
D1.R12: Risultati della sperimentazione delle metodologie e dei prototipi
per l'integrazione (BO,CS,MI,MO,RM)
D2.R6: Risultati della sperimentazione condotta con in prototipi sviluppati
nella fase 3 per il data warehouse (BO,CS)
D3.R4: Validazione e studio di usabilita` dei prototipi di clustering,
metaquerying, ricerche approssimate e visualizzazione (BO,CS,RM)