Querying and Updating Advanced Database Systems:
Languages and Computational Aspects
Victor Vianu (PI)
Department of Computer Science and Engineering
University of California, San Diego
Contact Information
Victor Vianu
CSE 0114
U.C. San Diego
La Jolla, CA 92093-0114
Phone: (619) 534-6227
Fax : (619) 534-7029
Email: vianu@cs.ucsd.edu, http://www-cse.ucsd.edu/~vianu
Project Award Information
Award Number: IIS-9802288
Duration: 09/01/1998 to 8/31/2001
Title: Querying and Updating Advanced Database Systems:
Languages and Computational Aspects
Project Summary
The area of databases has evolved rapidly in recent years
in response to new requirements of advanced applications.
Databases must now handle a wide variety of data types,
ranging from relational to textual, sequential, spatial, audio, etc.
Data is increasingly heterogeneous
and globally distributed among a variety of sources.
And, applications increasingly require functionalities such as activeness.
These developments pose new challenges to
the design and implementation of query and update languages,
and raise fundamentally novel issues
that require developing specific, principled approaches.
The aim of the present project is to develop such approaches
to querying and updating advanced database systems, focusing primarily
on the logical level: languages and computational aspects.
The results of the project are expected to
yield better understanding of basic problems facing current database systems,
and will provide tools to facilitate the principled
design and implementation of query and update languages.
They will contribute to technological advances in several fast-developing
areas: representing and querying information on the Web,
applications requiring activeness capabilities (such as electronic commerce),
and applications handling heterogeneous data (such as spatial databases).
Status Report
(Last update: February, 2000.)
The focus of the first year of the project has been
on semistructured XML data. The
database group at UCSD,
including Victor Vianu (PI of the present project),
Yannis Papakonstantinou,
several graduate students and one post-doctoral researcher,
initiated the development of a prototype mediator system
and query language for XML data, called XMAS. A central
component of the mediator system will be a DTD inference mechanism
whose purpuse is to infer a DTD for an integrated view of XML sources,
from the DTDs of the sources and the definition of the view.
Preliminary formal results have been obtained on
methods and algorithms for DTD inference in views defined by XMAS queries.
A closely related line of research concerns typechecking XML transformation
programs with respect to pre-specified output DTDs.
The results obtained so far show decidability of the problem
for a very wide class of XML transformers, modeled
by an abstract device called k-pebble transducer.
This subsumes the core of current XML languages, such as XML-QL and XSL.
This line of research will also be pursued in the near future.
Another topic to be investigated
is workflow specification and verification and the connection with XML views,
with applications to electronic commerce.
Finally, another line of research
has focused on heterogeneous data,
including spatial data and
topological queries, with applications to geographic information systems.
The first year of the project has proven to be quite fruitful
in terms of research advances and prototype development. The research
on semistructured data and XML has good momentum and can be expected to yield
substantial new results over the next year.
Recent publications acknowledging NSF support
N. Alon, T. Milo, F. Neven, D. Suciu and V. Vianu:
XML with Data Values: Typechecking Revisited
(pdf),
Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, 2001.
S. Abiteboul, L. Segoufin and V. Vianu:
Representing and Querying XML with Incomplete Information
(pdf),
Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, 2001.
V. Vianu: A Web Odyssey: from Codd to XML
(pdf),
Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, 2001
N. Alon, T. Milo, F. Neven, D. Suciu and V. Vianu:
Typechecking XML Views of Relational Databases
(Preliminary version, ps), Proc. IEEE Conf. on Logic in
Computer Science, 2001.