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

    1. 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.
    2. 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.
    3. V. Vianu: A Web Odyssey: from Codd to XML (pdf), Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, 2001
    4. 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.
    5. Y. Papakonstantinou and V. Vianu: DTD Inference for Views of XML Data. PODS 2000: 35-46.
    6. D. Suciu, T. Milo, and V. Vianu: Typechecking for XML Transformers. PODS 2000: 11-22.
    7. Christos H. Papadimitriou, Dan Suciu, Victor Vianu: Topological Queries in Spatial Databases. JCSS 58(1): 29-53 (1999).
    8. Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. JCSS 58(3): 428-452 (1999).
    9. B. Ludaescher, Y. Papakonstantinou, P. Velikhov and V. Vianu: View Definition and DTD Inference for XML. Int'l. Workshop on Semistructured Data, Jerusalem, January 1999.
    10. Serge Abiteboul, Victor Vianu, Bradley S. Fordham, Yelena Yesha: Relational Transducers for Electronic Commerce. PODS 1998: 179-187.
    11. L. Segoufin and V. Vianu: Querying spatial databases via topological invariants, PODS 1998: 89-98.
    12. Other publications related to the project.