MINISTERO DELL'UNIVERSITÀ E DELLA RICERCA SCIENTIFICA E TE CNOLOGICA
DIPARTIMENTO AFFARI ECONOMICI
PROGRAMMI DI RICERCA SCIENTIFICA DI RILEVANTE INTERESSE NAZIO NALE
RICHIESTA DI COFINANZIAMENTO

(DM n. 10 del 13 gennaio 2000)
PROGETTO DI UNA UNITÀ DI RICERCA - MODELLO B
Anno 2000 - prot. MM09268483_002


Parte: I
1.1 Programma di Ricerca di tipo: interuniversitario

Area Scientifico Disciplinare: Ingegneria Industriale e dell'informazione (80%)
Area Scientifico Disciplinare: Scienze Matematiche (20%)

1.2 Durata del Programma di Ricerca: 24 mesi

1.3 Titolo del Programma di Ricerca

Testo italiano

D2I: Integrazione, warehousing e mining di sorgenti eterogenee di dati

Testo inglese

D2I: Integration, Warehousing, and Mining of Heterogeneous Data Sources

1.4 Coordinatore Scientifico del Programma di Ricerca

LENZERINI MAURIZIO  
(cognome) (nome)  
Università degli Studi di ROMA "La Sapienza" Facoltà di INGEGNERIA
(università) (facoltà)
K05A Dipartimento di INFORMATICA E SISTEMISTICA
(settore scient.discipl.) (Dipartimento/Istituto)


lenzerini@dis.uniroma1.it
(E-mail)


1.5 Responsabile Scientifico dell'Unità di Ricerca

RIZZI STEFANO  
(cognome) (nome)  


Professore associato 22/12/1963 RZZSFN63T22A944R
(qualifica) (data di nascita) (codice di identificazione personale)

Università degli Studi di BOLOGNA Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI
(università) (facoltà)
K05A Dipartimento di ELETTRONICA, INFORMATICA E SISTEMISTICA
(settore scient.discipl.) (Dipartimento/Istituto)


051/2093542 051/2093540 srizzi@deis.unibo.it
(prefisso e telefono) (numero fax) (E-mail)


1.6 Settori scientifico-disciplinari interessati dal Programma di Ricerca

K05A K05B


1.7 Parole chiave

Testo italiano
BASI DI DATI ; SISTEMI INFORMATIVI ; INTEGRAZIONE ; DATA WAREHOUSING ; DATA MINING ; PROGETTAZIONE LOGICA E FISICA ; INTERROGAZIONI DI SIMILARITÀ ; CLUSTERING ; GESTIONE DI VERSIONI DI SCHEMA

Testo inglese
DATABASES ; INFORMATION SYSTEMS ; INTEGRATION ; DATA WAREHOUSING ; DATA MINING ; LOGICAL AND PHYSICAL DESIGN ; SIMILARITY QUERIES ; CLUSTERING ; SCHEMA VERSIONING


1.8 Curriculum scientifico del Responsabile Scientifico dell'Unità di Ricerca

Testo italiano

Stefano Rizzi ha conseguito il titolo di Dottore di Ricerca nel 1996, ed è professore associato dal 1998. Ha partecipato a numerosi progetti di ricerca finanziati da CNR e MURST; è stato parte dell'unità di Bologna per il progetto MURST ex-40% INTERDATA. Nel 97/98 ha partecipato a una convenzione tra Olivetti Sanità e il DEIS per la messa a punto di tecniche di progettazione di data warehouse in ambiente ospedaliero.
L'attività scientifica nel settore delle basi di dati ha principalmente avuto per tema la progettazione di sistemi per il data warehousing e l'ottimizzazione del costo di formulazione di interrogazioni in database relazionali. In particolare, nell'ambito del primo argomento, è stato definito un modello concettuale per il data warehouse ed è stata messa a punto una tecnica per la progettazione concettuale dagli schemi concettuali o logici del database operazionale; sono altresì stati affrontati aspetti specifici della fase di progettazione logica. L'obiettivo è l'individuazione di una metodologia di progetto completa ed integrata.

Testo inglese

Stefano Rizzi received his PhD in 1996, and is associate professor since 1998. He participated in several research projects supported by CNR and MURST; he has been a member of the local unit of Bologna for the MURST ex-40% INTERDATA Project. In 97/98 he has been involved in a contract between Olivetti Sanità and DEIS aimed at investigating the impact of data warehouse techniques in hospital environments.
The research activity in the database area was mainly focused on the design of data warehouse systems and on optimizing the formulation costs for relational databases. In particular, within the first topic, a conceptual model for data warehouses has been defined, together with a technique for conceptual design starting from the schemes of the operational system; also specific issues related to logical design have been investigated. The research target is to devise a complete and consistent framework for design.

1.9 Pubblicazioni scientifiche più significative del Responsabile Scientifico dell'Unità di Ricerca
  1. GOLFARELLI M., RIZZI S., "Designing the data warehouse: key steps and crucial issues" , Rivista: Journal of Computer Science and Information Management , Volume: 2 , (1999) n.3, in corso di pubblicazione .
  2. BENZI F., MAIO D., RIZZI S., "Visionary: a viewpoint-based visual language for querying relational databases" , Rivista: Journal of Visual Languages and Computing , Volume: 10 , ISSN: 1045-926X , (1999) n.2, in corso di pubblicazione .
  3. GOLFARELLI M., MAIO D., RIZZI S., "The Dimensional Fact Model: a Conceptual Model for Data Warehouses" , Rivista: International Journal of Cooperative Information Systems , Volume: 7 , pp.: 215-247 , ISSN: 0218-8430 , (1998) n.2&3 .
  4. GOLFARELLI M., RIZZI S., "A Methodological Framework for Data Warehouse Design" , Rivista: Proceedings ACM First International Workshop on Data Warehousing and OLAP , pp.: 3-9 , (1998) .
  5. MAIO D., MALTONI D., RIZZI S., "Dynamic Clustering Of Maps In Autonomous Agents" , Rivista: IEEE Transactions on Pattern Analysis and Machine Intelligence , Volume: 18 , pp.: 1080-1091 , ISSN: 0162-8828 , (1996) n.11 .

1.10 Risorse umane impegnabili nel Programma dell'Unità di Ricerca

1.10.1 Personale universitario dell'Università sede dell'Unità di Ricerca

Cognome Nome Dipart./Istituto Qualifica Settore
scient.
Mesi
uomo
2000 2001
 
1  RIZZI  STEFANO  ELETTRONICA, INFORMATICA E SISTEMISTICA  Prof. associato  K05A  4  4
2  CIACCIA  PAOLO  ELETTRONICA, INFORMATICA E SISTEMISTICA  Prof. associato  K05A  3  3
3  GRANDI  FABIO  ELETTRONICA, INFORMATICA E SISTEMISTICA  Prof. associato  K05A  4  4
4  LODI  STEFANO  ELETTRONICA, INFORMATICA E SISTEMISTICA  Ricercatore  K05A  3  3
5  MAIO  DARIO  ELETTRONICA, INFORMATICA E SISTEMISTICA  Prof. ordinario  K05A  2  2
6  PENZO  WILMA  ELETTRONICA, INFORMATICA E SISTEMISTICA  Ricercatore  K05A  1  1
7  SARTORI  CLAUDIO  ELETTRONICA, INFORMATICA E SISTEMISTICA  Prof. associato  K05A  3  3
8  SCALAS  MARIA RITA  ELETTRONICA, INFORMATICA E SISTEMISTICA  Prof. associato  K05A  2  2
 

1.10.2 Personale universitario di altre Università

Cognome Nome Università Dipart./Istituto Qualifica Settore
scient.
Mesi
uomo
2000 2001
 
 

1.10.3 Titolari di assegni di ricerca

Cognome Nome Dipart./Istituto Anno del titolo Mesi
uomo
2000 2001
 
1  GOLFARELLI  MATTEO  CENTRO DI GESTIONE DELLA SPESA DI CESENA  1999  4  4
2  PATELLA  MARCO  Dip. ELETTRONICA, INFORMATICA E SISTEMISTICA  1999  3  3
 

1.10.4 Titolari di borse per Dottorati di Ricerca e ex L. 398/89 art.4 (post-dottorato e specializzazione)

Cognome Nome Dipart./Istituto Anno del titolo Mesi uomo
1. BARTOLINI  ILARIA  ELETTRONICA, INFORMATICA E SISTEMISTICA  2002 
2. MANDREOLI  FEDERICA  ELETTRONICA, INFORMATICA E SISTEMISTICA  2001 

1.10.5 Personale a contratto da destinare a questo specifico programma

Qualifica Costo previsto Mesi uomo
1. laureato  12 
2. laureato  12 
3. laureato  12 
4. laureato  12 

1.10.6 Personale extrauniversitario dipendente da altri Enti

Cognome Nome Dipart./Istituto Qualifica Mesi uomo


Parte: II
2.1 Titolo specifico del programma svolto dall'Unità di Ricerca

Testo italiano

Aspetti progettuali, di integrazione e di interrogazione per sistemi di data warehousing

Testo inglese

Issues in design, integration and querying for data warehousing systems

2.2 Base di partenza scientifica nazionale o internazionale

Testo italiano

L'attività del progetto è inquadrabile secondo tre temi che, pur conservando singolarmente una propria valenza di ricerca, contribuiscono attraverso un processo di integrazione al raggiungimento dell'obiettivo globale:
Tema 1: Integrazione di dati provenienti da sorgenti eterogenee.
Tema 2: Progettazione e interrogazione di data warehouse.
Tema 3: Data mining.
L'unità di Bologna ha maturato molteplici esperienze nell'ambito dei tre temi, come appresso specificato.
TEMA 1. Il gruppo di Bologna coinvolto nel Tema 1 si occupa da diversi anni di gestione di versioni dello schema [Roddick 95] in basi di dati relazionali e a oggetti. In particolare, per quanto riguarda le basi di dati relazionali, ha cercato in [De Castro 97] di sistematizzare la materia della gestione di versioni temporali dello schema con riguardo alle dimensioni temporali coinvolte (tempo di transazione e di validità), alle soluzioni implementative adottate e all'interazione fra i due livelli (intensionale ed estensionale) di "versionamento" dei dati. In [Grandi 99, Grandi 00] ha proposto un modello per l'introduzione di versioni temporali di schema anche nell'ambito di basi di dati a oggetti, nelle quali sono più tradizionalmente considerate versioni di tipo progettuale. Infine, in [Roddick 99] ha proposto l'utilizzo anche di versioni spaziali (e spazio-temporali) in un approccio generalizzato allo schema versioning. Negli ambiti considerati, sono in realtà numerosi i problemi d'integrazione in cui è probabile imbattersi e che la nostra unità si prefigge di affrontare nel corso di questa ricerca. Tali problemi riguardano principalmente l'integrazione di schemi e relative componenti estensionali richiesta per l'esecuzione di query, e cambiamenti di schema, che coinvolgono più versioni di schema. Problemi analoghi sono già stati in parte studiati in letteratura [Clamen 94, Lautemann 97] ma le soluzioni proposte sono parziali e di limitata applicabilità in questo ambito. Ad ogni modo, tecniche di integrazione di risorse eterogenee [Calvanese 98] potrebbero rappresentare una buona base di partenza per la soluzione di problemi specifici della gestione di versioni di schema. Versioni di schema (di tipo temporale o progettuale) sono sinora state sempre considerate nell'ambito di un unico sistema per la gestione di basi di dati, ove quindi l'unica fonte di eterogeneità è proprio rappresentata dalla coesistenza di schemi diversi riferiti ai medesimi dati. L'introduzione di versioni di schema di tipo spaziale, se corrispondenti alla dislocazione geografica delle sorgenti dei dati, rende esplicita l'esigenza di soluzioni ai problemi di integrazione dovuti all'interoperabilità di tali dati.
TEMA 2. I temi di ricerca legati al data warehouse sono oggetto di forte interesse da parte della comunità scientifica. Sebbene molti aspetti specifici legati alla modellazione concettuale [Franconi 99, Sapia 98], alla modellazione logica [Agrawal95, Gyssens 97], alla materializzazione delle viste [Gupta 99, Yang 97], all’ottimizzazione di interrogazioni [Cohen 99, Nutt 98] e alla selezione degli indici [Gupta 97, Johnson 97] siano stati trattati, a tutt’oggi non c’è accordo su una metodologia di progettazione completa. Progettare un data warehouse richiede l'utilizzo di tecniche completamente differenti da quelle utilizzate nei convenzionali sistemi informativi. In [Golfarelli 99], il gruppo di Bologna coinvolto nel Tema 2 ha delineato una metodologia per la progettazione di data warehouse, basata sul modello concettuale Dimensional Fact Model, descritto in dettaglio in [Golfarelli 98]. La metodologia proposta è caratterizzata da sei fasi: 1) Analisi del sistema informativo, 2) Raccolta delle specifiche, 3) Progettazione concettuale, 4) Formalizzazione del carico di lavoro e validazione dello schema concettuale, 5) Progettazione logica, 6) Progettazione fisica. Le prime quattro fasi sono già state oggetto di studio; in particolare, in [Golfarelli 98] è stata proposta una tecnica semi-automatica per la progettazione concettuale a partire dagli schemi E/R o logici che descrivono il sistema operazionale. Il risultato è uno schema dimensionale consistente in un insieme di schemi di fatto, ognuno dei quali descrive un evento che accade dinamicamente nell'azienda. I componenti principali degli schemi di fatto sono misure, dimensioni e gerarchie. Il carico di lavoro può essere definito formalmente in termini di volume dei dati e di interrogazioni attese; assieme allo schema dimensionale, esso costituisce l'ingresso per le successive fasi di progettazione logica e fisica il cui risultato finale deve rappresentare lo schema finale del data warehouse.
TEMA 3. In ambito data mining recenti lavori hanno messo in evidenza l'importanza di strutture, quali R-tree [Guttman 84] e M-tree [Ciaccia 97], atte a supportare "query di similarità", al fine di pervenire ad una corretta classificazione/clustering di (nuovi) oggetti [Ester 98]. Poiché tali query possono arrivare ad avere un costo (molto) elevato, e spesso, per la natura stessa del problema, un risultato "esatto" non è interessante e/o richiesto, è emersa l'importanza di query "approssimate" che, sacrificando parzialmente la qualità del risultato, riescano tuttavia a garantire prestazioni accettabili [Shivakumar 98, Ciaccia 00], generalizzando il concetto di "ranking parziale" elaborato nel contesto dell'Information Retrieval testuale [Wong 93]. In ambito multimediale e/o di strutture complesse (e.g. DB multimediali, Web e Data Warehouse), esistono molti lavori che si occupano di query di similarità ([Faloutsos 96] fornisce una panoramica introduttiva per l'ambito multimediale), ma molti problemi restano aperti, tra cui il trattamento di query di similarità complesse [Fagin 96,Ciaccia 98]. In tali contesti, inoltre, le problematiche di data mining sono state sinora poco studiate, in particolare come caratterizzare sinteticamente il contenuto di DB multimediali [Chang 98] per permettere all'utente un'esplorazione efficiente ed efficace della base di dati.
Sempre nell’ambito del Tema 3, recentemente sono stati ideati metodi generali di data clustering, stabili, insensibili agli outlier, con minima configurazione e complessità subquadratica, e anche in grado di minimizzare il costo di input/output quando la dimensione dei dati eccede la dimensione della memoria interna [Zhang 96]. Tuttavia, l’applicazione ai data warehouse ha finora ricevuto scarsa attenzione. In un warehouse, ai vincoli esposti devono aggiungersi l’aggiornamento dei risultati in modo incrementale dalle classi precedentemente ricavate e dalle transazioni di modifica del warehouse, entro l’intervallo di inattività. I metodi di clustering attuali possono essere classificati in [Sheikholeslami 98][Hinneburg 98]: partitivi (1); gerarchici (2); locality-based (3); grid-based (4). L’applicazione ai data warehouse non è praticabile per le classi 1 [Kaufman 90] e 2 [Guha 98], per ragioni d’efficienza o per la difficoltà di trattare le cancellazioni. La classe 4 comprende metodi utilizzabili solo per database spaziali. Nella classe 3 esiste un metodo utilizzabile in spazi metrici, generalizzabile all’aggiornamento batch in ambito warehouse [Ester 98]. Tali metodi sono però sensibili ai parametri. Resta dunque aperto il problema della progettazione di un metodo soddisfacente in ambito database, incrementale, applicabile a dati metrici/categorici, frequenti in ambito warehouse. Il gruppo proponente ha acquisito esperienza nell'ambito di algoritmi di clustering basati sui primi vicini [Lodi 99], i quali sono locality-based e dunque adatti all’analisi incrementale.

Testo inglese

The research carried out can be framed within three themes which, though maintaining their scientific interest, participate in achieving the global goal:
Theme 1: Integration of data coming from heterogeneous sources.
Theme 2: Data warehouse design and querying.
Theme 3: Data mining.
The Bologna unit is actively involved within these themes, as described in the following.
THEME 1. In the last years, the Bologna group involved in Theme 1 has been working on schema versioning [Roddick 95] for relational and object-oriented databases. In particular, as far as relational databases are concerned, [De Castro 97] tries to systematize temporal schema versioning by considering the temporal dimensions involved (transaction time but also valid time), the implementation solutions and the interaction between the two level (intensional and extensional) of data versioning. [Grandi 99, Grandi 00] proposes a model for the introduction of temporal schema versions in the object-oriented context, where design versions are usually considered. Finally, [Roddick 99] proposes a general approach to the schema versioning problem also considering the use of spatial (and spatio-temporal) versions. In the schema versioning framework, there are actually several integration problems (not always explicitly acknowledged) which our Unit intend to investigate in this research. These problems mainly concern the integration of schemas and their corresponding extensional component required for the execution of queries and schema changes involving more than one schema versions. Similar problems have been marginally studied in the literature [Clamen 94, Lautemann 97], where partial solutions with limited applicability have been proposed in this context. Anyway, the integration techniques proposed for heterogeneous sources [Calvanese 98] can be considered as a good starting point for the solution of specific schema versioning problems. Schema versions (temporal or design versions) were considered in the context of a single database system so far. In this case, the only source of heterogeneity is actually represented by the coexistence of different schemas related to the same data. The introduction of spatial schema versions, when they correspond to the geographic dislocation of the data sources, explicitly requires integration solutions for the interoperability of these data (multischema query processing).
THEME 2. The database community is strongly interested in the research themes concerning data warehouses. Though specific issues related to conceptual modeling [Franconi 99, Sapia 98], logical modeling [Agrawal95, Gyssens 97], view materialization [Gupta 99, Yang 97], query optimization [Cohen 99, Nutt 98] and index selection [Gupta 97, Johnson 97] have been investigated, still there is no substantial agreement on a complete design methodology. Designing a data warehouse requires techniques completely different from those adopted for operational information systems. In [Golfarelli 99], the Bologna group involved in Theme 2 outlined a general methodological framework for data warehouse design, based on the conceptual model we developed, called Dimensional Fact Model and described in detail in [Golfarelli 98]. The methodology proposed features six phases: 1) Analysis of the information system, 2) Requirement specification, 3) Conceptual design, 4) Workload refinement and validation of the conceptual scheme, 5) Logical design, 6) Physical design. The first four phases have already been investigated; in particular, in [Golfarelli 98] we proposed a semi-automated technique to carry out conceptual modeling starting from either the E/R or the logical relational schemes describing the operational information system. The output of conceptual design is a dimensional scheme consisting of a set of fact schemes, each describing an event occurring dynamically in the enterprise world. The main components of fact schemes are measures, dimensions and hierarchies. Finally, a workload can be characterized in terms of data volumes and expected queries, to be used as the input of the logical and physical design phases whose output is the final scheme for the data warehouse.
THEME 3. In the data mining field, some recent works have highlighted the relevance of access structures, such as the R-tree [Guttman 84] and the M-tree [Ciaccia 97], able to support "similarity queries", which are required in order to allow a correct classification/clustering of (new) objects [Ester 98]. Since such queries can lead to (very) high execution costs, and often, because of the very nature of the problem, an "exact" result is not necessary, "approximate" similarity queries have been considered, with the aim to improve the performance by somewhat sacrificing the quality of the result [Shivakumar 98, Ciaccia 00]. This scenario generalizes the one considered by the "partial ranking" approach developed in the Information Retrieval field [Wong 93]. In the multimedia context and/or when data are "complex" (e.g. Web and Data Warehouses), several works have dealt with similarity queries ([Faloutsos 96] is a good starting point for the multimedia case), but many problems have not been solved yet, including the management of complex similarity queries [Fagin 96,Ciaccia 98]. Furthermore, in such contexts data mining problems are nowadays poorly understood. In particular, it is not clear how to characterize the content of a multimedia DB [Chang 98] in order to allow users to efficiently and effectively explore the DB.
Still within the framework of Theme 3, during the past years general purpose data clustering methods have been designed, which are stable, insensitive to outliers, with minimal configuration requirements and subquadratic complexity, and satisfying the following database-oriented constraints [Zhang 96]: the data size may significantly exceed the internal memory size and the I/O cost must be minimized. However, the application of such methods to warehouses has received little attention. In a warehouse, we must add the ability to incrementally update the clustering results from previously computed classes and the warehouse update transactions within its offline period, and support for categorical and metric data, which are commonly used in all decision making processes supported by the warehouse. Current clustering methods can be classified into [Sheikholeslami 98] [Hinneburg 98]: partitioning (1); hierarchical (2); locality-based (3); grid-based (4). Methods in classes 1 [Kaufman 90] and 2 [Guha 98] are not feasible in warehouses, due to efficiency reasons or the difficulties of supporting deletions. Class 4 only includes methods for spatial databases. Class 3 includes a method which can be efficiently used in metric spaces, and admits a generalization to batch updating in a warehouse [Ester 98]. However, both methods are very sensitive to input parameters. Thus, how to design a satisfactory database clustering method supporting incrementality, metric and categorical data, which can be frequently found in warehouses, remains an open problem. This research group has recently gained experience with near neighbor clustering algorithms [Lodi 99], which are locality-based and hence suitable for incremental analysis.

2.2.a Riferimenti bibliografici

[Agrawal 95] R. Agrawal, A. Gupta, S. Sarawagi. "Modeling multidimensional databases", IBM Research Report, 1995.
[Calvanese 98] D. Calvanese, G. De Giacomo, M. Lenzerini, D. Nardi, R. Rosati. "Description Logic Framework for Information Integration", Proc. KR' 98, pp. 2-13, 1998.
[Chang 98] W. Chang, G. Sheikholeslami, J. Wang, A. Zhang. "Data resource selection in distributed visual information systems", IEEE Transactions on Knowledge and Data Engineering, Vol. 10, n. 6 1998, (926-946).
[Ciaccia 97] P. Ciaccia, M. Patella, P. Zezula. "M-tree: An efficient access method for similarity search in metric spaces", Proc. VLDB'97, Athens, Greece, 1997.
[Ciaccia 98] P. Ciaccia, M. Patella, P. Zezula. "Processing Complex Similarity Queries with Distance-based Access Methods", Proc. EDBT'98, Valencia, Spain, 1998.
[Ciaccia 00] P. Ciaccia, M. Patella. "PAC Nearest Neighbor Queries: Approximate and Controlled Search in High-Dimensional and Metric Spaces", Proc. ICDE 2000, San Diego, CA, 2000.
[Clamen 94] S.M. Clamen. "Schema Evolution and Integration", Distributed and Parallel Databases: An International Journal, Vol. 2, n.1, pp. 101-126, 1994.
[Cohen 99] S. Cohen, W. Nutt, A. Serebrenik. "Algorithms for rewriting aggregate queries using views", Proc. Int. Workshop on Design and Management of Data Warehouses, Heidelberg, Germany, 1999.
[De Castro 97] C. De Castro, F. Grandi, M.R. Scalas. "Schema Versioning for Multitemporal Relational Databases", Information System, Vol. 22, n.5, pp. 249-290, 1997.
[Ester 98] M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, X. Xu. "Incremental Clustering for Mining in a Data Warehousing Environment", Proc. VLDB'98, New York, USA, 1998.
[Fagin 96] R. Fagin. "Combining Fuzzy Information from Multiple Systems", Proc. ACM PODS'96, Montreal, Canada, 1996.
[Faloutsos 96] C. Faloutsos. "Searching multimedia databases by content", Kluwer Academic Publ., 1996.
[Franconi 99] E. Franconi, U. Sattler. "A data warehouse conceptual model for multidimensional aggregation", Proc. DMDW 99, Heidelberg, Germany, 1999.
[Golfarelli 98] M. Golfarelli, D. Maio, S. Rizzi. "The Dimensional Fact Model: a Conceptual Model for Data Warehouses", International Journal of Cooperative Information Systems, Vol. 7, n. 2&3, 1998 (215-247).
[Golfarelli 99] M. Golfarelli, S. Rizzi. "Designing the data warehouse: key steps and crucial issues", Journal of Computer Science and Information Management, Vol. 2, n. 3, 1999.
[Grandi 99] F. Grandi, F. Mandreoli: "ODMG Language Extensions for Generalized Schema Versioning Support", Proc. ECDM Workshop (ER'99), Paris, France, pp. 36-47, 1999.
[Grandi 00] F. Grandi, F. Mandreoli, M.R. Scalas: "A Generalized Modeling Framework for Schema Versioning Support", Australian Computer Science Communications, Vol. 22, No. 2, pp. 33-40, 2000.
[Guha 98] S. Guha, R. Rastogi, K. Shim. "Cure: An efficient clustering algorithm for large databases", Proc. ACM SIGMOD conf. on Management of Data, pages 73—84, Seattle, WA, 1998.
[Gupta 97] H. Gupta, V. Harinarayan, A. Rajaraman. "Index selection for OLAP", Proc. Int. Conf. Data Engineering, Binghamton, UK, 1997.
[Gupta 99] H. Gupta, I.S. Mumick. "Selection of views to materialize under a maintenance cost constraint", Proc. Int. Conf. on Database Theory, Jerusalem, Israel, 1999.
[Guttman 84] A. Guttman. "R-trees: A dynamic index structure for spatial searching", Proc. ACM SIGMOD'84, Boston, USA, 1984.
[Gyssens 97] M. Gyssens, L. Lakshmanan. "A foundation for multi-dimensional databases", Proc. 23rd VLDB, Athens, Greece, 1997 (106-115).
[Hinneburg 98] A. Hinneburg, D. Keim. "An Efficient Approach to Clustering in Large Multimedia Databases with Noise", Proc. Fourth Int. Conf. Knowledge Discovery in Databases, pages 58-65, New York, USA, 1998.
[Johnson 97] T. Johnson, D. Shasha. "Hierarchically split cube forests for decision support: description and tuned design", Bullettin of Technical Committee on Data Engineering, Vol. 20, n. 1, 1997.
[Kaufman 90] L. Kaufman, P. J. Rousseeuw. "Finding Groups in Data - An Introduction to Cluster Analysis", Wiley Series in Probability and Mathematical Statistics, 1990.
[Lautemann 97] S.-E. Lautemann. "A Propagation Mechanism for Populated Schema Versions", Proc. IEEE Int. Conf. On Data Eng., ICDE'97, Birmingham, 1997.
[Lodi 99] S. Lodi, L. Reami, C. Sartori. "Efficient Shared Near Neighbours Clustering of Large Metric Data Sets", in: Principles of Data Mining and Knowledge Discovery, Third European Conference, PKDD '99, Prague, Proceedings. Lecture Notes in Computer Science, Vol. 1704, Springer, 1999.
[Nutt 98] W. Nutt, Y. Sagiv, S. Shurin. "Deciding equivalences among aggregate queries", Proc. 17th Symposium on Principles of Database Systems, 1998.
[Roddick 95] J.F. Roddick. "A Survey of Schema Versioning Issues for Database Systems", Inf. Softw. Technology, Vol. 37, n.7, pp. 383-393, 1995.
[Roddick 99] J. F. Roddick, F. Grandi, F. Mandreoli, M.R. Scalas. "Towards a Formal Model for Spatio-Temporal Schema Selection", Proc. STDML Workshop (DEXA'99), Firenze, Italia, pp. 434-440, 1999.
[Sapia 98] C. Sapia, M. Blaschka, G. Höfling, B. Dinter. "Extending the E/R Model for the Multidimensional Paradigm", in: Y. Kambayashi et. al. (Eds.): Advances in Database Technologies, Springer LNCS Vol. 1552, 1998.
[Sheikholeslami 98] G. Sheikholeslami, S. Chatterjee, A. Zhang. "WaveCluster. A Multi_Resolution Clustering Approach for Very Large Spatial Databases", Proc. 24th VLDB conf., pages 428-439, New York City, August 1998.
[Shivakumar 98] N. Shivakumar, H. Garcia-Molina, C. Chekuri. "Filtering with Approximate Predicates", Proc. VLDB'98, New York, USA, 1998.
[Wong 93] W. Wong, D. Lee. "Implementations of partial document ranking using inverted files", Information Processing and Management, Vol. 29, n. 5, 1993, (647-669).
[Yang 97] J. Yang, K. Karlaplem, Q. Li. "Algorithms for Materialized View Design in Data Warehousing Environments", Proc. 23rd International Conference on Very Large Databases, Athens, Greece, pp. 136-145, 1997.
[Zhang 96] T. Zhang, R. Ramakrishnan, M. Livny. "BIRCH: An Efficient Data Clustering Method for Very Large Databases", Proc. 1996 ACM SIGMOD Int. Conf. on Management of Data, pages 103-114, Montreal, Canada, 1996.

2.3 Descrizione del programma e dei compiti dell'Unità di Ricerca

Testo italiano

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.
Dal punto di vista temporale, la ricerca si articola in quattro fasi, descritte di seguito e accompagnate dalla descrizione dei prodotti relativi.
PRIMA FASE (4 MESI):
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".
PRODOTTI PREVISTI
D0.R1: Specifiche per il meta-data repository (in collaborazione con CS,MI,MO,RM)
D1.R1: Metodi e tecniche di estrazione, rappresentazione ed integrazione di sorgenti strutturate e semistrutturate (in collaborazione con CS,MI,MO,RM)
D1.R4: Introduzione di un approccio formale per la gestione di versioni di schema in ambiente eterogeneo
D2.R1: Documento sui risultati dell'analisi dello stato dell'arte sulle architetture di data warehouse (in collaborazione con CS)
D2.R2: Documento sull'analisi dello stato dell'arte sulle tematiche di progettazione logico-fisica del livello dei dati derivati
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à (in collaborazione con CS,RM)
SECONDA FASE (8 MESI):
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.
PRODOTTI PREVISTI
D0.R2: Specifica della architettura funzionale del repository di meta-dati (in collaborazione con CS,MI,MO,RM)
D1.R6: Descrizione della metodologia di integrazione di sorgenti fortemente eterogenee (in collaborazione con MO,MI)
D2.R4: Tecniche di progettazione logica e di interrogazione efficiente di data warehouse (in collaborazione con CS)
D2.R5: Scelta ottimale di indici in sistemi di data warehouse
D3.R2: Architettura del sistema integrato di data mining e visualizzazione (in collaborazione con RM, CS)
D3.R3: Studio di metodi di mining per: clustering, ricerche approssimate, metaquerying (in collaborazione con CS)
TERZA FASE (8 MESI):
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.
PRODOTTI PREVISTI
D0.P1: Repository di Meta-dati (in collaborazione con CS,MI,MO,RM)
D1.P4: Prototipo di strumento per la manipolazione di versioni di schema di schema in ambito eterogeneo
D2.P1: prototipo sviluppato per la progettazione logico-fisica
D3.P1: Algoritmi di clustering incrementale di dati
D3.P2: Risoluzione di query approssimate
QUARTA FASE (4 MESI):
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 PREVISTI
D1.R12: Risultati della sperimentazione delle metodologie e dei prototipi per l'integrazione (in collaborazione con CS,MI,MO,RM)
D2.R6: Risultati della sperimentazione condotta con in prototipi sviluppati nella fase 3 per il data warehouse (in collaborazione con CS)
D3.R4: Validazione e studio di usabilita` dei prototipi di clustering, metaquerying, ricerche approssimate e visualizzazione
(in collaborazione con CS,RM)

Testo inglese

The topics investigated by the unit can be classified within the three integrated research themes defined in the national project:
Theme 1: The issues related to integrating heterogeneous sources when different schema versions are present will be studied.
Theme 2: The main issues related to logical and physical design of data warehouses will be addressed, assuming the relational model as the target logical model.
Theme 3: The unit will face topics related to similarity queries, as well as incremental techniques for data clustering in data warehouse environments on metric and categorical data.
From a temporal point of view, the research will be divided into four phases, described in the following together with the expected deliverables.
FIRST PHASE (4 MONTHS):
THEME 1. We will study of the impact of the coexistence of different schema versions on the integration process (with particular reference to object-oriented databases), where such coexistence is an intrinsic source of heterogeneity. In particular, we will consider data sources in which the same data are represented by means of several schema versions, as created by successive modifications applied to the schema itself. In the meta-repository, the metadata describing the different source types is affected by the presence of versioned data sources. We will describe the sources to be integrated through the definition of a generalized model for schema versioning support. The heterogeneity of interest here will be modeled by means of the formalization of the inter-version relationships induced by the schema changes. In this context, the focus is not on the procedural aspects of the schema and data versioning (which represents the "classical" approach) but rather on the underlying semantics: the adoption of a declarative specification for the version generation and management will be the staring point for the source description at the integrated/reconciled level, where different versions could be involved in multischema queries and modifications.
THEME 2. The unit will carry out an analysis of the existing literature on logical and physical design of data warehouses. In particular, on the logical level the cost functions devised so far will be analyzed and the main drawbacks of the approaches to view materialization will be identified, focussing on determining a general category of queries for supporting more effective materialization techniques. The partitioning algorithms devised for operational and distributed databases will be studied. As to estimating the cardinality of views, the effectiveness of statistical criteria will be evaluated and other possible criteria will be examined. On the physical level, the unit will analyze the most common indices supported by the data warehousing tools: besides B-trees, join indices, star indices, bitmap indices and projection indices will be considered. For each type, a cost model will be devised to be used during physical design. Finally, the most common algorithms for choosing indices in operational databases will be studied.
THEME 3. The goal of applying data clustering methods to a data warehouse requires incremental processing of data. Since a clustering method should constitute a uniform solution, due to processing in different times, we feel it is important to deal with both the performance and the quality of the results. We propose an evaluation of access methods for metric spaces and their applicability to locality-based clustering. We also propose an analysis and comparison of the clustering methods and algorithms for data warehouses in the literature, and an evaluation of their computational costs and the quality of clustering. Finally, the existing paradigms for similarity queries will be reviewed, including those based on some form of "approximation". In particular, existing criteria used to measure the "quality of the results" will be critically reviewed.
EXPECTED DELIVERABLES:
D0.R1: Specification for the Meta-data repository (in collaboration with CS,MI,MO,RM)
D1.R1: Methods and Techniques for the automatic extraction, representation and integration of structured and semi-structured data sources (in collaboration with CS,MI,MO,RM)
D1.R4: Introduction of a formal approach for the management of schema versioning in heterogeneous environment
D2.R1: State of the art of Data Warehouse Architectures (in collaboration with CS)
D2.R2: State of the art of logical and physical design of derived data
D3.R1: Analysis and comparison of data mining methods and algorithms, with reference to clustering, metaquerying, visualization techniques, approximate and similarity search. Analysis of research prospects in these areas (in collaboration with CS,RM)
SECOND PHASE (8 MONTHS):
THEME 1. We will develop an approach for the management of data sources with schema versions. Our aim is to define an integration methodology, on which the functional specifications of a Query Manager will be based (in collaboration with the MO Unit). In particular, the integration methodology will also employ the previously defined inter-version relationships. The description of the data sources, the inter-version relationships and the integration problems will be reformulated via description logics, whose automatic deduction capabilities we are interested in. We will show the formal correctness of the approach. Finally, we will take into account the presence of versioned sources in the definition of the query rewriting algorithms which are needed in the Query Manager. A single query on versioned sources could involve one or more schema versions. Thus, we will define multi-version query answering algorithms based on query rewriting and query answering with views techniques.
THEME 2. At first the unit will face the problem of logical design of data warehouses. The problem of view materialization will be studied, considering a complex workload which includes multiple aggregation operators within queries, and taking into account the presence of derived measures and of additional measures to support non-distributive aggregation operators. The unit will analyze the utility of horizontal and vertical fragmentation of views, based on the workload and taking space constraints into account. Specific cost functions will be defined, aimed at formulating both problems as optimization problems. In order to increase the effectiveness of the proposed algorithms, the unit will study methods to estimate the size of the views candidate to materialization, considering the cardinality constraints suggested by the application domain. Afterwards, the problem of physical design will be faced by relying on the cost models devised during the first phase. The problem of choosing the optimal set of indices will be addressed by outlining some rules of thumb on the one hand, by devising heuristic algorithms on the other.
THEME 3. Locality-based cluster analysis algorithms use information only from the neighborhood of a point in order to determine the cluster it belongs to. The locality property makes it feasible in principle to perform incremental analysis, namely reconstructing an updated clustering from the last clustering and update transactions. Locality-based algorithms based on the shared or mutual near neighbor principle have been proposed in pattern recognition. We propose to investigate the applicability of near neighbor data clustering methods to incremental cluster analysis. Besides, suitable indicators able to characterize the quality of the result will be defined, thus extending the classical concepts of "precision" and "recall" in order to better cover the case of complex queries. Consequently, new paradigms for approximate similarity search will be defined, able to give the user the possibility to explicitly control the quality of the result. Finally, we will work on the definition of the meta-data repository for the descriptions of activities and results of the data mining.
EXPECTED DELIVERABLES:
D0.R2: Functional architecture of the meta-data repository (in collaboration with CS,MI,MO,RM)
D1.R6: Description of the methodology for integration of strongly heterogeneous sources (in collaboration with MO,MI)
D2.R4: Techniques for data warehouse design and efficient querying (in collaboration with CS)
D2.R5: Estimation of the size of the views candidate to materialization, considering the cardinality constraints
D3.R2 Architecture of an integrated data mining and visualization tool (in collaboration with CS,RM)
D3.R3 Development of data mining methods: Incremental clustering, Approximate search with quality index, Tractable cases of metaquerying (in collaboration with CS)
THIRD PHASE (8 MONTHS):
THEME 1. A prototype will be developed to support the functionalities outlined in the phase 2. Such a prototype will manage the rewriting of multi-version queries in an integrated fashion with respect to the rewriting functionalities supported by the Query Manager.
THEME 2. The techniques produced during the second phase will be implemented into a prototype. Input to the prototype will be a data mart conceptual scheme, a workload expressed according to the results of the first phase, additional constraints from the application domain (on space, cardinality, indices available, etc.); logical design will be carried out by means of the materialization and fragmentation algorithms proposed in the second phase, producing in output the data mart logical scheme; physical design will be carried out by means of the algorithms for choosing indices proposed in the second phase, producing in output the data mart physical scheme. The SQL statements for creating tables and indices will be automatically generated.
THEME 3. One of the goals of the research will be to develop an integrated tool to perform cluster analysis of data originated from a Data Warehouse. In such context, it is certainly desirable to apply incremental algorithms, in order to take advantage of the materialization techniques made available by Data Warehousing tools. Since update transactions usually involve only a fraction of the points in a warehouse, a locality-based algorithm capable of building the new clustering from the latest one and the update transactions may achieve a considerable speed-up when compared to building the clustering from the already updated warehouse. Such a speed-up should be evaluated with respect to the obtainable clustering quality. We propose to build a prototype, which will include a clustering engine, a synthetic dataset generator for testing purposes, a Windows NT/95 graphical user interface, and a profiling tool. In order to ease the sharing with the other components of the project, the activities and results of the clustering will be described in the meta-data repository. Besides, a prototype system able to support and efficiently process complex queries will be developed; this prototype will enable the user to control both the amount of resources to be spent for solving the queries and the quality of the results obtained.
EXPECTED DELIVERABLES:
D0.P1: Meta-data repository (in collaboration with CS,MI,MO,RM)
D1.P4: Prototype of a tool to support the managing of different versions of schemata for the data coming from heterogeneous sources
D2.P1: A prototype for the logical-physical design of data warehouses
D3.P1 Incremental clustering algorithms
D3.P2 Approximate queries resolution
FOURTH PHASE (4 MONTHS):
THEME 1. We will proceed with the integration of the prototype resulting from the previous phase in the context of a common framework. The framework is aimed at giving an overall description of the single sources and of the integrated/reconciled level. A validation and evaluation of the so built framework will eventually be made with reference to a real-world application.
THEME 2. The techniques for logical and physical design will be tested on the most common tools for data warehousing, based on standard benchmarks. The cost models for indices will be experimentally validated. Finally, a comparative analysis of the benefits of view materialization, fragmentation and indexing will be carried out.
THEME 3. This last phase will be devoted to the thorough and joint experimentation of the prototypes, by taking into account both real and synthetic datasets, in order to obtain accurate experimental results. In particular, quality criteria for the clustering will be defined, in order to evaluate the ratio between execution costs and performance.
EXPECTED DELIVERABLES:
D1.R12: Experimentation and evaluation of the prototypes (in collaboration with CS,MI,MO,RM)
D2.R6: Report describing the experimental results obtained on data warehuose design and querying (in collaboration with CS)
D3.R4 Evaluation and usability study of the prototypes for clustering, meta-querying, approximate search and visualization (in collaboration with CS,RM)

2.4 Descrizione delle attrezzature già disponibili ed utilizzabili per la ricerca proposta

Anno di acquisizione Descrizione
Testo italiano Testo inglese
1.  1999Server NT  NT Servers 
2.  1997Workstation SGI  SGI Workstation 
3.  1999Workstation LINUX  LINUX Workstations 
4.     
5.     


2.5 Descrizione della richiesta di Grandi attrezzature (GA)

Attrezzatura I
Descrizione

valore presunto (milioni)   percentuale di utilizzo per il programma

Attrezzatura II
Descrizione

valore presunto (milioni)   percentuale di utilizzo per il programma


Parte: III
3.1 Costo complessivo del Programma dell'Unità di Ricerca

Voce di spesa Spesa Descrizione
Euro Testo italiano   Testo inglese  
Materiale inventariabile 40  20.658  workstation, dispositivi, personal computer  workstations, devices, personal computers 
Grandi Attrezzature        
Materiale di consumo e funzionamento 45  23.241  software, cancelleria, ecc.  software, paper, etc. 
Spese per calcolo ed elaborazione dati        
Personale a contratto 48  24.790  progettazione e sviluppo  design and development 
Servizi esterni 22  11.362  assistenza sistemistica, assistenza sui prodotti software, inserimento dati  assistance on hardware and software, data input 
Missioni 60  30.987  partecipazione a riunioni e convegni  meetings and conferences 
Altro        


  Euro
Costo complessivo del Programma dell'Unità di Ricerca 215  111.038 
 
Costo minimo per garantire la possibilità di verifica dei risultati 172  88.831 
 
Fondi disponibili (RD) 35  18.076 
 
Fondi acquisibili (RA) 30  15.494 
 
Cofinanziamento richiesto al MURST 150  77.469 
 


Parte: IV
4.1 Risorse finanziarie già disponibili all'atto della domanda e utilizzabili a sostegno del Programma

QUADRO RD

Provenienza Anno Importo disponibile nome Resp. Naz. Note
Euro
Università          
Dipartimento          
MURST (ex 40%)          
CNR          
Unione Europea          
Altro 1999   35  18.076     
TOTAL   35  18.076     

4.1.1 Altro

Convenzione SIAER (1999), responsabile Maio: 10 ML
Finanziamento MURST 60% (1999), resp. Sartori: 10 ML
Convenzione TEMA (1998), resp. Sartori: 5
Finanziamento MURST 60% (1998), resp. Grandi: 10 ML

4.2 Risorse finanziarie acquisibili in data successiva a quella della domanda e utilizzabili a sostegno del programma nell'ambito della durata prevista

QUADRO RA

Provenienza Anno della domanda o stipula del contratto Stato di approvazione Quota disponibile per il programma Note
Euro
Università 2000   disponibile in caso di accettazione della domanda  30  15.494   
Dipartimento          
CNR          
Unione Europea          
Altro          
TOTAL     30  15.494   

4.2.1 Altro


4.3 Certifico la dichiarata disponibilità e l'utilizzabilità dei fondi di cui ai punti 4.1 e 4.2:      SI     

Firma ____________________________________________




(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")




Firma ____________________________________________ 27/03/2000 10:51:15