SPEAKER: Victor Vianu
UC San Diego (CSE)
Databases and the Web are organically connected at many levels. Web sites are increasingly powered by databases. Collections of linked Web pages distributed across the Internet are themselves targets for databases. But this is just the beginning. The emergence of XML as the lingua franca of the Web holds tremendous potential for using database techniques to manage Web information.
Many Web applications are based upon data exchange and integration. For example, in a typical scenario, a user community would agree on a common type (content and structure, described by a DTD) for an integrated view of the information residing in various data sources. The view is constructed by querying, transforming, and integrating information from the sources. Documents in the view may be in turn queried by users or consumed by application programs. To avoid runtime typechecking (or crashes!) it is desirable to statically verify that the view always produces XML documents of the expected type. This talk discusses techniques for the static analysis of XML queries. In particular, we exhibit and take advantage of a powerful (and elegant) connection between DTDs and tree automata, and between XML queries and tree transducers. This connection enables us to develop a very general framework for typechecking a wide range of XML query languages.
This talk is based partly on joint work with Yannis Papakonstantinou (UCSD), and partly with Tova Milo (Tel Aviv U.) and Dan Suciu (U. Washington).