Processing XML Data in the Presence of Side-Effects

Jérôme Siméon (IBM T.J. Watson)


Abstract:

Usage of XML is spreading to all three tiers of Web applications. It can
be stored natively in the database, used as the common format in the 
middleware, and manipulated directly by the browser. This has recently 
led to the development of languages that blend database querying, general 
programming features, and user interaction, along with native XML 
support. Examples of such languages include Links (Univ.Edinburgh), HOP 
(INRIA), Linq (MicrosofT), and XQuery Scripting (W3C). A challenge common 
to all those approaches is in supporting database optimizations in a the 
context of a much more expressive language, notably one that includes some
form of side-effect.

In this talk, I will present an approach to extend a typical XML query
compiler and optimizer to handle side-effects. We consider an extension
to the W3C XML query language with operations that modify the data during
query evaluation. We study the impact of that extension on logical
optimization, join detection, and pipelining. The main result of this
work is to show that, with proper care, a number of typical nested-relational
optimizations remain applicable in the presence of side effects. Our
approach relies on static analysis for key conditions (purity, commutativity,
and idempotency) that must be checked in order for algebraic rewritings to
hold. The approach has been tested successfully in the Galax XQuery compiler.

Bio:

Jérôme Siméon is a Research Staff Member at the IBM T.J. Watson Research
Center. Jérôme graduated from Ecole Polytechnique in France in 1994, and
obtained his Ph.D. in Computer Science from Université D'Orsay in 1999.
His research interests are in XML infrastructure and applications, databases
and programming languages, distributed programming, semantics, optimization,
and formal methods. His recent contributions include work on XML query and 
schema languages, XML query optimization, and XML updates. He is an editor
of "XQuery 1.0", "XPath 2.0", and the "XQuery 1.0 and XPath 2.0 Formal
Semantics" and a lead developer for Galax, a reference XQuery implementation.