Pathfinder—A Relational Query Optimizer Explores XQuery Terrain
Torsten Grust, Jan Rittinger, and Jens Teubner
GI-Fachtagung für Datenbanksysteme in Business, Technologie und Web (BTW 2007)
paper (PDF), presentation slides (PDF), demo poster (PDF)
Relational encodings of the static aspects of the XQuery data model, i.e., tabular representations for XML documents and ordered sequences of items, are widely used today. Since 2002, the Pathfinder and MonetDB/XQuery companion projects pursue the primary goal to also embrace the complete dynamic semantics of XQuery (expression evaluation and runtime aspects) with the help of relational database systems.
In earlier work, we have shown that relational algebra makes for a suitable target language in an XQuery compiler. This purely relational approach to XQuery inherits the scalability advantages of the underlying relational database back-end and makes proven optimization techniques immediately applicable to the construction of XQuery processors. MonetDB/XQuery, an open-source system that implements this approach, is found among the fastest and most scalable XQuery processors available today].
This is a demonstration of the relational optimizer of Pathfinder, the query compiler behind MonetDB/XQuery. To account for the significant size and unusual shape of the relational query plans derived from input XQuery expressions, Pathfinder implements various optimization techniques in a peephole-style fashion and provides support for graph-shaped plans from the ground up.