Testo italiano

Data-X: Gestione, Trasformazione e Scambio di Dati in Ambiente Web

Testo inglese

Data-X: Management, Transformation and Exchange of Data in a Web Environment

ATZENI	PAOLO
(cognome)	(nome)
Università degli Studi ROMA TRE	Facoltà di INGEGNERIA
(università)	(facoltà)
K05A	Dipartimento di INFORMATICA E AUTOMAZIONE
(settore scient.discipl.)	(Dipartimento/Istituto)

atzeni@dia.uniroma3.it
(E-mail)

GHELLI	GIORGIO
(cognome)	(nome)

Professore associato	29/10/1961	GHLGRG61R29B157M
(qualifica)	(data di nascita)	(codice di identificazione personale)

Università degli Studi di PISA	Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI
(università)	(facoltà)
K05B	Dipartimento di INFORMATICA
(settore scient.discipl.)	(Dipartimento/Istituto)

050/887258	050/887226	ghelli@di.unipi.it
(prefisso e telefono)	(numero fax)	(E-mail)

K05B

K05A

Testo italiano
BASI DI DATI ; WORLD WIDE WEB ; SISTEMI DI TIPI ; MODELLI DI DATI ; LINGUAGGI

Testo inglese
DATA BASES ; WORLD WIDE WEB ; TYPE SYSTEMS ; DATA MODELS ; LANGUAGES

Testo italiano

Giorgio Ghelli è professore Associato di Basi di Dati e Sistemi Informativi all' Università di Pisa, dal Novembre del 1992. È stato visiting professor all'Ecole Normal Supérieure di Parigi (1993), e Visiting Researcher al Microsoft Research Center di Cambridge (UK) (1998).
I suoi interessi di ricerca sono: progettazione e realizzazione di linguaggi per basi di dati, teoria dei tipi e sua applicazione al tema precedente, fondamenti di linguaggi ad oggetti, linguaggi per programmare ed interrogare il Web. Ha contribuito al disegno ed alla realizzazione dei linguaggi per basi di dati Galileo e Fibonacci.
Ha partecipato a progetti internazionali, come membro o come responsabile dell'unità locale, relativi a linguaggi e sistemi per basi di dati ed a fondamenti di linguaggi ad oggetti.
Ha partecipato a comitati di programma di conferenze e workshop internazionali e nazionali dedicati a linguaggi ad oggetti ed a basi di dati.
Ha pubblicato otto lavori su riviste internazionali e ventotto articoli in conferenze e workshop internazionali con referee, lavorando con Antonio Albano, Luca Cardelli, Giuseppe Castagna, Richard Connor, Pierre-Louis Curien, Giuseppe Longo, Benjamin Pierce ed altri.

Testo inglese

Giorgio Ghelli has been Associate Professor of Computer Science (Data Bases), at Pisa University, since November 1992. He was Visiting Professor at Ecole Normal Supérieure Paris (1993), and Visiting Researcher at Microsoft Research Center, Cambridge (UK) (1998).
His research interests are: design and implementation of database languages; type theory, and its application to the previous theme; foundations of object-oriented languages; languages to query and program the Web. He contributed to the design and implementation of the Galileo and Fibonacci object-oriented database languages.
He has been involved in international projects on database languages and systems and on foundations of object-oriented languages, either as a group member or as the site leader.
He has been part of the program committee of international conferences and workshops devoted to database and object-oriented languages and systems.
He published eight papers on refereed journals and twentyeight papers in international refereed conferences and workshops, coauthored with Antonio Albano, Luca Cardelli, Giuseppe Castagna, Richard Connor, Pierre-Louis Curien, Giuseppe Longo, Benjamin Pierce, and others.

1. ALBANO A., GHELLI G., ORSINI R., "Fibonacci: A Programming Language for Object Databases" , Rivista: The VLDB Journal , Volume: 4(3) , pp.: 403-444 , (1995) .
2. CASTAGNA G., GHELLI G., LONGO G., "A Calculus for Overloaded Functions with Subtyping" , Rivista: INFORMATION & COMPUTATION , Volume: 117(1) , pp.: 115-135 , ISSN 0890-5401 , (1995) .
3. CARDELLI L., GHELLI G., GORDON A., "Mobility Types for Mobile Ambients" , Rivista: PROCEEDINGS ICALP , (1999) TO APPEAR .
4. GHELLI G., PIERCE B., "Bounded Existentials and Minimal Typing" , Rivista: THEORETICAL COMPUTER SCIENCE , Volume: 193(1-2) , pp.: 75-96 , ISSN 0304-3975 , (1998) .
5. COLAZZO D., GHELLI G., "Subtyping Recursive Types in Kernel Fun" , Rivista: PROCEEDINGS IEEE LICS , (1999) TO APPEAR .

Nº	Cognome	Nome	Dipart./Istituto	Qualifica	Settore scient.	Mesi uomo
						1999	2000
1	GHELLI	GIORGIO	INFORMATICA	Prof. associato	K05B	4	4
2	ALBANO	ANTONIO	INFORMATICA	Prof. ordinario	K05B	4	4

1.10.2 Personale universitario di altre Università

Nº	Cognome	Nome	Università	Dipart./Istituto	Qualifica	Settore scient.	Mesi uomo
							1999	2000

1.10.3 Titolari di assegni di ricerca

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo

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

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo
1.	COLAZZO	DARIO	INFORMATICA	2002	8
2.	MANGHI	PAOLO	INFORMATICA	2000	10
3.	SARTIANI	CARLO	INFORMATICA	2002	10

1.10.5 Personale a contratto da destinare a questo specifico programma

Nº	Qualifica	Costo previsto	Mesi uomo
1.	Dottore	24	12

1.10.6 Personale extrauniversitario dipendente da altri Enti

Nº	Cognome	Nome	Dipart./Istituto	Qualifica	Mesi uomo

Testo italiano

Modellizazione ed interrogazione tipizzata di sorgenti dati in ambiente Web

Testo inglese

Type based models and languages for Web data

Testo italiano

L'enorme massa di dati pubblicati sul World Wide Web ha prodotto una serie di lavori di ricerca su tecniche per l'interrogazione e la ristrutturazione del contenuto dei dati semistrutturati in ambiente Web. In particolare, sono stati definiti diversi modelli dei dati e linguaggi di interrogazione. Seguendo (Florescu, Levy, Mendelzon 1998), questi linguaggi possono essere classificati come "linguaggi di prima generazione" -- per esempio, W3QL (Konopnicki, Shmueli 1995), WebSQL (Mendelzon, Mihaila, Milo 1996) -- basati su di un modello dei dati elementare con pagine e puntatori, e "linguaggi di seconda generazione", che permettono anche di modellare i dati all'interno delle pagine Web, e sono basati su modelli dei dati semistrutturati, come ad esempio i linguaggi di Lorel (Abiteboul, Quass, McHugh 1997), UnQL (Buneman, Davidson, Hillebrand 1996), Strudel (Fernandez, Florescu, Kang 1998). Queste proposte sono state recentemente estese all'interrogazione di documenti XML; la maggior parte dei contributi puo' essere trovata negli atti del Workshop QL'98 (Query languages 1998) promosso dal consorzio W3C; tra queste ricordiamo (Deutsch, Fernandez, Florescu 1998) e (Robie, Lapp, Schach 1998).

Tra i linguaggi di seconda generazione, possiamo distinguere due diversi approcci alla descrizione dei dati estratti dal Web. Il primo approccio è basato sull'uso di tipi unione per definire uno schema che possa gestire le irregolarità dei dati, mentre il secondo approccio, ad oggi il più diffuso, è basato sull'uso di dati auto-descrittivi, senza uno schema predefinito.
Un esempio del primo approccio è la soluzione proposta per gestire documenti SGML all'interno del sistema di gestione di basi di dati ad oggetti O2, estendendone il modello dei dati (Christophides, Abitebuol, Cluet 1994).
Un esempio del secondo approccio è rappresentato dal modello OEM (Object Exchange Model) sviluppato a Stanford e dall'analogo modello definito dal gruppo dell'University of Pennsylvania (Buneman, Davidson, Suciu 1995).
In OEM ogni oggetto può avere un numero arbitrario di attributi, con nomi diversi od uguali, i cui valori sono altri oggetti o valori atomici; un insieme S con n elementi è rappresentato, in questo modello, come un record con n campi, tutti etichettati S, ciascuno contenente un elemento dell'insieme. OEM è un modello ad oggetti "leggero" nel senso che (a) non richiede la definizione di classi e tipi, e permette la rappresentazione di strtture arbitrarie con nomi di attributi qualunque, (b) non supporta incapsulazione (c) non permette di rappresentare il comportamento degli oggetti.

L'approccio con tipi unione etichettata richiede poche modifiche ad un sistema per la gestione di basi di dati e mantiene i vantaggi dei linguaggi tradizionali per ci`ò che riguarda la possibilità di effettuare verifiche di tipo e di ottimizzare le interrogazioni (Christophides, Abitebuol, Cluet 1994). Tuttavia, l'uso di tipi unione etichettata, con il relativo costrutto "case", non è abbastanza flessibile per gestire la variabilità presente nei dati semistrutturati; per questa ragione, alcuni ricercatori stanno attualmente investigando la possibilità di passare ad un approccio più flessibile, basato su tipi unione non etichettata.

L'approccio basato su dati auto-descrittivi è più flessibile, ma soffre di alcuni importanti problemi: (a) i dati vengono memorizzati e gestiti in maniera inefficiente, a causa della mancanza di uno schema e della replicazione delle informazioni strutturali in ogni dato; (b) è difficile valutare le interrogazioni in maniera efficiente; (c) le interrogazioni sono più difficili da formulare e non è possibile verificarne la correttezza (Suciu 1998). In particolare, un problema che si presenta nella maggior parte dei linguaggi per l'interrogazione di dati semistrutturati è la mancanza di controlli di consistenza tra dati ed interrogazioni: quando un'interrogazione è formulata ipotizzando una struttura dei dati che non corrisponde a quella effettiva, non viene ritornato alcun errore, ma solo una risposta vuota, anche nel caso di errori banali come la scrittura errata del nome di un campo. Per superare questa limitazione alcuni gruppi stanno esplorando la definizione di linguaggi per dati semistrutturati disegnati attorno ad un sistema di tipi; ci riferiamo in particolare al gruppo basi di dati dell'University of Pennsylvania (Buneman, Pierce 1999) ed al progetto Hippo (Connor, Sibson, Manghi 1998).

L'altra questione chiave è la definizione del linguaggio di interrogazione per il modello dei dati considerato (Buneman, Davidson, Suciu 1995) (Buneman, Davidson, Hillebrand 1996) (Abiteboul, Quass, McHugh 1997) (Fernandez, Florescu, Levy 1997). La caratteristica comune ai linguaggi per l'interrogazione di dati semistrutturati è la possibilità di attraversare cammini di lunghezza arbitraria, specificati in genere nella forma di espressioni di cammino regolari, per permettere agli utenti di scrivere interrogazioni su dati la cui struttura non è perfettamente nota (e.g. "trova il numero di telefono di una persona, ma non so se questo è un attributo della persona o di un suo qualche sottocomponente"). Inoltre è possibile interrogare lo schema (e.g. "trova tutti i nomi degli attributi"), o scrivere interrogazioni che ignorano parte dello schema (e.g. "trova tutti i valori degli attributi, indipendentemente dai nomi degli attributi stessi") (Suciu 1998). I linguaggi di interrogazione sono usati sia per interrogare i dati che per trasformarli, ovvero per costruire nuovi grafi a partire dal grafo interrogato. Le soluzioni specifiche differiscono per ciò che riguarda le applicazioni a cui il linguaggio è mirato, il potere espressivo, la capacità di definire trasformazioni (Cluet 1997).

Infine, l'ottimizzazione delle interrogazioni, in questo contesto, è un aspetto che presenta ancora molti problemi aperti. Sono state studiate fino ad ora, in particolare, tecniche di valutazione per espressioni di cammino e per interrogazioni su dati senza schema (Christophides, Cluet and Moerkotte 1996) (Goldman, Widom 1997) (Fernandez, Suciu 1998).


Questa unità affronterà i problemi della formalizzazione di un modello dei dati per dati Web e della definizione del relativo linguaggio di interrogazione e programmazione sfruttando gli strumenti della teoria dei sistemi di tipo. Il nostro gruppo ha una lunga esperienza di disegno di linguaggi per basi di dati basato sulla teoria dei tipi, che ha prodotto in particolare il linguaggio Fibonacci (Albano, Ghelli, Orsini 1995). Il lavoro del gruppo è stato focalizzato in particolare sulla definizione di modelli dei dati e di operatori per linguaggi ad oggetti (Castagna, Ghelli, Longo 1995), concentrando l'attenzione sugli aspetti che caratterizzano i linguaggi per basi di dati (Albano, Bergamini, Ghelli 1993), (Ghelli, Palmerini 1999). Tuttavia, le attività più recenti del gruppo sono state dirette allo studio di sistemi di tipi adatti all'interrogazione ed alla programmazione del Web (Connor, Sibson, Manghi 1998) (Cardelli, Ghelli, Gordon 1999). Il gruppo ha anche accumulato una lunga esperienza nella realizzazione dei linguaggi definiti (Albano, Ghelli, Orsini 1988) (Ghelli 1992) (Albano, Diotallevi, Ghelli 1995).

Testo inglese

The huge amount of data published via the World Wide Web has led to a number of research efforts on techniques to query and restructure semistructured data sources on the Web. In particular, several data models and query languages have been defined. According to (Florescu, Levy, Mendelzon 1998), these languages can be classified as "first generation languages" -- for example W3QL (Konopnicki, Shmueli 1995), WebSQL (Mendelzon, Mihaila, Milo 1996) -- which only deal with a basic data model of pages and links, and "second generation languages", which also allow the data inside web pages to be modeled, by means of semistructured data models, such as the languages Lorel (Abiteboul, Quass, McHugh 1997), UnQL (Buneman, Davidson, Hillebrand 1996), Strudel (Fernandez, Florescu, Kang 1998). These proposals have been recently extended to the issue of querying XML documents; most of the proposals can be found in the proceedings of the W3C workshop QL'98 (Query languages 1998); among the others we mention (Deutsch, Fernandez, Florescu 1998) and (Robie, Lapp, Schach 1998).
Among second generation languages, two approaches have been considered to describe the structure of Web data. The first approach is based on the use of union types to define a schema to deal with data irregularities, while the second approach, the preferred one so far, is based on the use of self-describing data, modeled as a labeled graph, without a predefined schema.

An example of the first approach is the solution proposed to manage SGML documents in the O2 object-oriented database system with appropriate extensions of its data model (Christophides, Abitebuol, Cluet 1994).
An example of the second approach is the Stanford's Object Exchange Model (OEM), and a similar model has been also proposed at the University of Pennsylvania (Buneman, Davidson, Suciu 1995).
In OEM each object has an arbitrary number of attributes, with different or equal names, whose values are other objects or atomic data; a set S with n elements is represented as a record with n fields, all labeled S, each containing one element of the set. OEM is a "lightweight object model" in the sense that (a) it does not requires the definition of classes or types, and arbitrary structures with arbitrary attribute names can be modeled, (b) it does not support encapsulation, and (c) it does not support object behavior.

The approach with tagged union types requires few modifications to a DBMS and preserves the advantages of traditional database languages with respect to the possibility of type-checking and query optimization (Christophides, Abitebuol, Cluet 1994). However the use of tagged union types, and their related "case" operators, is not flexible enough to deal with semistructured data; for this reason, some researchers are currently investigating the possibility of switching to a more flexible approach based on untagged union types.

The approach with self-describing data has the advantage of flexibility, but suffers some important drawbacks: (a) data is inefficient to store, since the schema is replicated with each data item; (b) queries are hard to evaluate efficiently; (c) queries are hard to formulate and cannot be typecheked (Suciu 1998). Indeed, a general problem with most SSD query language is the lack of any consistency control between data and query: when the query is written assuming a structure which does not correspond to the actual structure of data, no error is indicated, but an empty result is returned, even in the case of trivial errors such that the mistyping of a field name. The use of type systems as a foundation for languages for SSD, is a new research direction, aiming to overcome this limitation, which is being followed in particular by the database group at University of Pennsylvania (Buneman, Pierce 1999) and by the Hippo project in Glasgow (Connor, Sibson, Manghi 1998).

The other basic issue is the definition of the query language for the considered data model (Buneman, Davidson, Suciu 1995) (Buneman, Davidson, Hillebrand 1996) (Abiteboul, Quass, McHugh 1997) (Fernandez, Florescu, Levy 1997). The common feature of query languages for SSD is the ability to traverse arbitrary long paths in the data, usually specified in the form of regular path expression, to allow users to write queries on data whose structure is not fully known (e.g. "find the phone of a person but we don't know if phone is an attribute of a person or an attribute of a subcomponent of an attribute of a person"). Moreover one can query the schema components (e.g. "find all attribute names"), or write queries which ignore part of the schema (e.g. "retrieve all attribute values, regardless of the attribute name") (Suciu 1998). Query languages are used to express both queries and transformations: queries return a subset of a collection of data, while transformations may construct new graph. The specific solutions differ with respect to their target application, expressive power, and restructuring capabilities (Cluet 1997).

Finally, query optimization for SSD is another issue which has received a limited attention, in particular the evaluation techniques for path expressions and for data without schema (Christophides, Cluet and Moerkotte 1996) (Goldman, Widom 1997) (Fernandez, Suciu 1998).


We will face the problems of the formalization of a data model for Web data and of the definition of its query language by exploiting the tools of the theory of type systems. Our group has a well estabilished tradition of database language design based on type theory, which culminated in the design of the Fibonacci language (Albano, Ghelli, Orsini 1995). We mainly worked on the definition of data models and operators for object-oriented languages (Castagna, Ghelli, Longo 1995), focusing the attention on the new aspects which arise in the context of database languages (Albano, Bergamini, Ghelli 1993), (Ghelli, Palmerini 1999). However, our latest research has been directed toward those aspects of type theory which are directly applicable to languages to query and to program the Web (Connor, Sibson, Manghi 1998) (Cardelli, Ghelli, Gordon 1999). The group has also a long experience in the realization of the designed languages (Albano, Ghelli, Orsini 1988) (Ghelli 1992) (Albano, Diotallevi, Ghelli 1995).

(Abiteboul 1997) S. Abiteboul. "Querying Semistructured Data", Proc. of International Conference on Database Theory (ICDT), 1997.

(Abiteboul, Quass, McHugh 1997) S. Abiteboul, D. Quass, J. McHugh, J. Widom, J. Wiener. "The Lorel Query Language for Semistructured Data", International Journal on Digital Libraries, 1(1), pp.48-88, April 1997.

(Albano, Ghelli, Orsini 1988) Albano A., G. Ghelli and R. Orsini, "The Implementation of Galileo's Persistent Values", in Data Types and Persistence, M. Atkinson, P. Bunemann and R. Morrison (eds.), Topics in Information Systems, Springer-Verlag, pp.253-263, 1988.

(Albano, Ghelli, Orsini 1991) Albano A., G. Ghelli and R. Orsini, "A Relationship Mechanism for a Strongly Typed Object-Oriented Database Programming Language", Proc of VLDB, Barcelona, pp.565-576, 1991.

(Albano, Bergamini, Ghelli 1993) A. Albano, R. Bergamini, G. Ghelli, R. Orsini. "An Object Data Model with Roles", Proc. of VLDB, Dublin, pp.39-51, 1993.

(Albano, Diotallevi, Ghelli 1995) A. Albano, M. Diotallevi, and G. Ghelli, "Extensible Objects for Database Evolution: Language Features and Implementation Issues", Proc. of Data Base Programming Languages (DBPL), Perugia, Italy, 1995.

(Albano, Ghelli, Orsini 1995) Albano A., G. Ghelli, R. Orsini. "Fibonacci: A Programming Language for Object Databases", The VLDB Journal, 4 (3), pp.403-444, 1995.

(Buneman 1997) P. Buneman. "Tutorial: Semistructured Data", Proc. of Symposium on Principles of Database Systems (PODS), pp.117-121, 1997.

(Buneman, Davidson, Hillebrand 1996) P. Buneman, S. Davidson, G. Hillebrand, D. Suciu. "A Query Language and Optimization Techniques for Unstructured Data", Proc. of SIGMOD, pp.506-516, 1996.

(Buneman, Davidson, Suciu 1995) P. Buneman, S. Davidson, D. Suciu. "Programming Constructs for Unstructured Data", Proc. of Data Base Programming Languages (DBPL), 1995.

(Buneman, Pierce 1999) P. Buneman, B. Pierce. "Types for Semistructured Data", internal report, 1999.

(Cardelli, Ghelli, Gordon 1999) L. Cardelli, G. Ghelli, A. D. Gordon. "Mobility Types for Mobile Ambients", Proc. of International Colloquium on Automata, Languages and Programming (ICALP)", Prague, Czech Republic, July 1999.

(Castagna, Ghelli, Longo 1995) G. Castagna, G. Ghelli, G. Longo. "A Calculus for Overloaded Functions with Subtyping", Information & Computation, 117(1), pp.115-135, 1995.

(Christophides, Abitebuol, Cluet 1994) V. Christophides, S. Abitebuol, S. Cluet, M. Scholl. "From Structured Documents to Novel Query Facilities", Proc. of SIGMOD, pp.313-324, 1994.

(Christophides, Cluet, Moerkotte 1996) V. Christophides, S. Cluet, G. Moerkotte. "Evaluating Queries with Generalized Path Expressions", Proc. of SIGMOD, Montreal, Quebec, Canada, pp.413-422, June 1996.

(Cluet 1997) S. Cluet. "Modeling and Querying Semistructured Data", Information Extraction (M. T. Pazienza ed.), LNAI 1299, Springer, pp. 192-213, 1997.

(Colazzo, Ghelli 1999) D. Colazzo, G. Ghelli. "Subtyping Recursive Types in Kernel Fun, Extended Abstract", Proc. of the 14th Annual IEEE Symposium on Logic in Computer Science (LICS), Trento, Italy, June 1999.

(Connor, Sibson, Manghi 1998) R.C.H. Connor, K. Sibson, P. Manghi. "On the Unification of Persistent Programming and the World Wide Web", Proc. Workshop on the Web and Data Bases (WebDB), Valencia, Spain, 1998.

(Deutsch, Fernandez, Florescu 1998) A.Deutsch, M.Fernandez, D.Florescu, A.Levy, D.Suciu. "XML-QL: a query language for XML". W3C Notes, 1998.

(Fernandez, Florescu, Levy 1997) M. Fernandez, D. Florescu, A. Levy, D. Suciu. "A Query Language for a Web Site Management System", SIGMOD Record 26(3), pp.4-11, September 1997.

(Fernandez, Florescu, Kang 1998) M.Fernandez, D.Florescu, J.Kang, A.Levy, D.Suciu. "Catching the Boat with Strudel: Experiences with a Web-Site Management System". Proc. of SIGMOD, 1998.

(Fernandez, Suciu 1998) M. Fernandez, D. Suciu. "Optimizing Regular Path Exressions Using Graph Schemas", Proc. of International Conference on Data Engineering (ICDE), pp.14-23, 1998.

(Florescu, Levy, Mendelzon 1998) D. Florescu, A. Levy, A. Mendelzon. "Database Techniques for the World-Wide Web: A Survey", SIGMOD RECORD, December 1998.

(Ghelli 1992) G. Ghelli, "Run-Time Support for Hierarchic Records in Persistent Languages", Proc. of the International Workshop on Persistent Object Systems (POS), San Miniato, Pisa, Workshops in Computing, Springer-Verlag, 107-123, Settembre 1992.

(Ghelli, Palmerini 1999) G. Ghelli, D. Palmerini. "Foundations for Extensible Objects with Roles, Extended Abstract", Proc. of Workshop on Foundations of Object-Oriented Languages (FOOL), San Antonio, Texas, January 1999.

(Goldman, Widom 1997) R. Goldman, J. Widom. "Data Guides: Enabling Query Formulation and Optimization in Semistructured Databases", Proc. of VLDB, pp.436-445, 1997.

(Konopnicki, Shmueli, 1995) D. Konopnicki, O. Shmueli. "W3QS: A query system for the World Wide Web", Proc. of VLDB, 1995.

(Mendelzon, Mihaila, Milo 1996) A.Mendelzon, G. Mihaila, T. Milo. "Querying the World Wide Web", Proc. of International Conference on Parallel and Distributed Information Systems (PDIS), 1996.

(Robie, Lapp, Schach 1998) J.Robie, J.Lapp, D.Schach. "XML Query Language (XQL)", Proc. of W3C QL Workshop, Boston, 1998.

(Query Languages 98) Proceedings of the W3C QL'98 Workshop http://www.w3.org/Tands/QL/QL98/, 1998.

(Suciu 1998) D. Suciu. "An Overview of Semistrucured Data", SIGACT News, 29(4), pp.28-38, December 1998.

Testo italiano

L'unità è coinvolta nel tema 2 del progetto (Modellizzazione e Interrogazione di Sorgenti di Dati in Ambiente Web).
L'obiettivo specifico dell'unità è la definizione di un sistema di tipi e di un linguaggio per interrogare e manipolare dati semistrutturati provenienti dal Web, che abbia le seguenti caratteristiche: (a) flessibilità del sistema dei tipi, per rendere possibile la descrizione delle caratteristiche comuni dei dati in una collezione semistrutturata; (b) potenza espressiva del linguaggio di interrogazione, che deve permettere di esprimere interrogazioni sulla struttura dei dati, e di interrogare dati con una struttura irregolare; (c) apertura del sistema dei tipi e del linguaggio, che devono permettere di descrivere ed interrogare dati reperiti da fonti esterne, ed in particolare dal Web; analogamente, i dati prodotti dal linguaggio dovranno essere pubblicabili per l'accesso esterno, in particolare in formato XML. Il sistema dei tipi sarà una formalizzazione del modello di riferimento adottato dal progetto Data-X.
La presenza di un sistema di tipi che permetta di effettuare controlli di consistenza è in contrasto con l'esigenza di flessibilità delle collezioni di dati semistrutturati. Conciliare questi due aspetti rappresenta uno degli aspetti cruciali della ricerca proposta.

Lo strumento teorico su cui verrà basata questa ricerca è la teoria dei tipi. L'esperienza precedente del gruppo ha dimostrato come questo strumento abbia una grande flessibilità che lo rende utilizzabile per la descrizione tanto di strutture rigide quanto di strutture a priori indeterminate. In particolare, in questo caso, l'uso di una variante dei tipi record, combinata con l'uso di tipi ricorsivi, appare adatta alla rappresentazione di dati OEM. Arricchendo tale nozione con tipi collezione e con tipi unione non etichettati sembra possibile catturare le nozioni base del modello Data-X, ottenendo un sistema che concilia espressività e flessibilità. La bontà della scelta è confermata dal fatto che altri gruppi stanno seguendo approcci simili (Glasgow University, University of Pennsylvania), con risultati fino ad ora interessanti.
Il linguaggio di interrogazione avrà una struttura OQL arricchita con gli operatori associati ai costruttori di tipo individuati. In particolare, per ciò che riguarda le unioni non etichettate, la loro interrogazione può avvenire con operatori simili agli operatori "case" usati per le più comuni unioni etichettate, utilizzando però come discriminante la struttura che circonda l'espressione esaminata.

Per ciò che riguarda l'accesso a dati Web, il problema sarà affrontato definendo tecniche di traduzione per importare strutture con un formato XML, o comunque descrivibile in OEM. L'attenzione sarà rivolta alla traduzione da un sistema di tipi XML a quello che rappresenta il modello di riferimento; l'analisi e l'estrazione di tale informazione saranno invece studiati all'interno di altri temi del progetto.

Per ciò che riguarda la pubblicazione, vi sono due problematiche correlate ma distinte: uso del linguaggio per definire siti Web; uso di browser Web per visualizzare dati costruiti nel linguaggio.
Nel primo caso, è importante definire un sistema di tipi abbastanza ricco da poter avere nel linguaggio costrutti corrispondenti a tutti i meccanismi di astrazione utilizzati nella progettazione del sito; nel secondo caso, al contrario, è necessario che tutti i costrutti del sistema dei tipi siano rappresentabili sul Web. In entrambi i casi, l'attenzione sarà focalizzata sugli aspetti strutturali del problema ma non sulla presentazione dei dati, che verrà studiata da altre unità. La separazione dei due aspetti risulterà facile grazie alle caratteristiche di XML.


L'attività sarà organizzata come segue.

Il primo semestre sarà dedicato allo studio di un sistema di tipi, con i relativi operatori, che corrisponda al modello dei dati prescelto, ed alla definizione di un meccanismo che permetta l'integrazione, in questo sistema dei tipi, di dati provenienti da sorgenti esterne.
In questa fase verranno prodotti due rapporti.
Il primo rapporto descriverà un sistema di tipi e operatori, basato su tipi record, collezione, unione non etichettata e tipi ricorsivi, che sia in grado di rappresentare il modello dei dati che costituisce la base di partenza del progetto. Il problema critico è qui rappresentato dalla definizione di una nozione di corrispondenza tra valori e tipi che consenta controlli di coerenza senza tuttavia essere troppo restrittiva.
Il secondo rapporto definirà un sistema di tipi in grado di descrivere i dati proveninenti da fonti esterne, basato fondamentalmente su tipi record con etichette ripetute, ed una nozione di corrispondenza tra questi tipi e quelli definiti nel precedente rapporto, da cui sia possibile derivare un'analoga corrispondenza sui dati.

Il secondo semestre sarà dedicato al disegno di un linguaggio ed al disegno di algoritmi per verificarne la correttezza dal punto di vista dei tipi, e verranno prodotti due rapporti.
Il primo rapporto definirà, a partire dagli operatori definiti in precedenza, un linguaggio di interrogazione e ristrutturazione ed un linguaggio per la costruzione di applicazioni su dati conformi al modello prescelto. Il problema critico è rappresentato in questo caso dalla definizione di operazioni le quali non facciano assunzioni troppo stringenti sulla struttura dei dati, senza tuttavia cadere nell'errore opposto di definire un linguaggio nel quale ogni interrogazione può essere applicata ad ogni collezione di dati senza che il sistema sia in grado di controllare alcuna nozione di correttezza dell'interrogazione.
Il secondo rapporto definirà algoritmi per la verifica della correttezza statica di tale linguaggio, affrontando quindi i problemi della verifica di sottotipo e della verifica di tipo.

Durante il terzo semestre inizierà l'attivita di realizzazione del linguaggio definito, in parallelo alla definizione formale della sua semantica operazionale; proseguirà inoltre lo studio sull'accesso a dati da fonti esterne; è prevista anche in questo caso la produzione di due rapporti.
Nel primo verrà definita la semantica operazionale del linguaggio proposto. L'aspetto qualificante del lavoro sarà rappresentato dalla dimostrazione della coerenza tra la semantica operazionale qui definita e la semantica statica del linguaggio.
Nel secondo è prevista la descrizione di ulteriori risultati relativamente all'accesso a dati provenienti da sorgenti esterne. Questo rapporto sarà focalizzato su aspetti algoritmici, legati in particolare al problema di importare i dati esterni nel dominio del linguaggio, e su aspetti teorici, costruendo in particolare sui risultati del rapporto precedente per definire in modo preciso la semantica dell'operazione di importazione di dati esterni.

Il quarto semestre sarà dedicato ad attività di implementazione e sperimentazione del prototipo ed alla fondazione di studi su aspetti di ottimizzazione; la fase produrrà un rapporto ed un prototipo.
Il prototipo realizzerà il linguaggio definito, per ciò che riguarda il controllo dei tipi, l'esecuzione di programmi ed interrogazioni, e la gestione di dati persistenti. È prevista anche la presenza di qualche meccanismo di accesso a dati esterni.
Il rapporto sarà dedicato alla definizione di un modello di esecuzione delle interrogazioni finalizzato alla loro ottimizzazione. Tra i problemi cruciali da affrontare in questo lavoro, citiamo in particolare il fatto che questo modello dovrà tenere conto della diversa efficienza dell'accesso a dati interni ed esterni al sistema, e del fatto che diverse sorgenti dati mettono a disposizione meccanismi di accesso ai propri dati estremamente diversi.

Testo inglese

The group works on theme 2 of the Data-X project (Modeling and Querying Data Sources in a Web Environment).
The specific research goal of the group is the design of a type system and a programming language to query and manipulate SSD coming from the Web, with the following requirements: (a) flexibility of the type system, to make it possible to describe the common features of the elements of a semistructured collection; (b) expressive power of the query language, which must allow both data elements and their structure to be analyzed, and data with an irregular structure to be queried; (c) openness of the type system and the language, meaning that the collections to be queried may come from external sources, and in particular from the Web, and that the data produced by the language can be published on the Web, in particular in XML format. The type system will be a formalization of the reference model adopted as a base for the whole Data-X project.
The presence of a type system that allows some consistency checking is in contrast with the flexibility needs of SSD. The conciliation of these two aspects is one of the most difficult problem to be solved.

The research will be based on the theoretical framework of type theory. The past experience of the research group in database language design has shown that type theory has the necessary flexibility to deal with both regular and irregular structures. In particular, it seems that a combination of a variation of record types with recursive types can be used to describe OEM-like data. A promising research direction is the study of type systems which include also collection and untagged union types, which should be able to formalize the Data-X reference model, and would define a type system which is both flexible and expressive. The relevance of this approach has been recognized also by others groups (Glasgow University, University of Pennsylvania...), which have achieved interesting preliminary results.
The query language will be OQL-like, extended with the operators provided by the proposed type constructors. Union types require a careful design of their operators to overcome the limitations of the "case" operator, provided by the traditional tagged unions, for example by exploiting operators based on pattern-matching on the expected value structure.

The openness of the type system and of the language with respect to data which comes from external sources is another basic requirement.
Mapping techniques will be explored to import data with an XML structure, or, more generally, with an OEM-like structure. The focus will be on the mapping from an OEM-like type system to the reference type systems; the aspects of data analysis and extraction will be studied by other groups.

The possibility of publishing data on the Web raises two different related issues: the use of the language to build a Web site, and the use of a Web browser on data created by the language.
The first issue requires a rich type system with constructors finalized to site building. On the other hand, the second issue requires that every piece of data which is described in our type system is representable on the Web. In both cases the attention will be on the structural issues and not on data presentation, which will be studied by other groups. The separation of these aspects will be natural using XML.


The research activity will be organized as follows.

The first semester will be focused on the study of a type system, with its operators, which corresponds to the chosen data model, and on the definition of a mechanism which allows the integration of data coming from external sources.
During this phase, two reports will be produced.
The first will define a type system, with the corresponding operators, based on record, collection, union, and recursive types, able to represent the data model which is the basis of this research. The crucial problem is the definition of a correspondence relationship between values and types which allows consistency checking without being too restrictive.
The second report will define a type system, based on record types with repeatable labels, which is able to define SSD which comes from external sources. A notion of correspondence between these types and the ones defined in the previous report will be defined, such that a mapping from external data to data described in the internal type system will derive from this correspondence.

The second semester will be focused on the design of the language, and on the definition of the corresponding type checking algorithms, and we will produce two reports.
The first report will define a language to query and restructure SSD, and to write complete applications, based on the operators defined in the previous phase. The crucial problem is the definition of a query language which does not depend on rigid assumptions about the structure of the data, avoiding, at the same time, to end up with a language where every query can be applied to every piece of data without any control of the coherence between the two.
The second report will define subtype checking and type checking algorithms for the proposed language.

During the third semester, the implementation of the defined language will start, in parallel with the formal definition of its operational semantics, and with a study of the problem of external data access; two reports will be produced.
The first report will define the operational semantics of the proposed language. The basic result here will be the proof of the coherence between this semantics and the type checking rules of the language.
The second report will be focused on the access to external data. The attention will be on algorithmic aspects related to the importation of external data into the language environment, and on theoretical aspects, exploiting the formal definition of the language semantics to define the precise semantics of the data import operation.

The fourth semester will be focused on implementation and experimentation with the prototype, and on laying the basis of a research on optimization; a report and a prototype will be produced.
The prototype will implement the proposed language, including type-checking, query and application execution. The prototype will also provide some external data access mechanism. The prototype will be used to experiment with the language usability and to gain some understanding about query execution.
The report will focus on the definition of a query execution model, which will be the basis for studies on query optimization. The model shall deal, in particular, with the fact that different data sources have vastly different speed, offer different access mechanisms and different kinds of access paths.

Nº	Anno di acquisizione	Descrizione
		Testo italiano	Testo inglese
1.	1995	Sun 10	Sun 10
2.	1997	PC Pentium	PC Pentium
3.	1997	PC Pentium	PC Pentium
4.
5.

Attrezzatura I
Descrizione

valore presunto (milioni)   percentuale di utilizzo per il programma

Attrezzatura II
Descrizione

valore presunto (milioni)   percentuale di utilizzo per il programma

QUADRO RD

4.1.1 Altro

QUADRO RA

4.2.1 Altro

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 ____________________________________________	01/04/1999 16:08:00