Pathfinder

Regrettably this section is outdated. We will try to fill in interesting bits and pieces in the near future.

Relational XQuery Processing Stack

There is an apparent gap between the table-oriented processing model of relational databases and the XQuery data model, with the item sequence as its basic data type and its operations on XML trees.

The Pathfinder research project thus develops techniques to bridge this gap as depicted in our processing stack on the right:

• The XPath accelerator tree encoding shreds XML documents into a relational equivalent that allows for efficient XML tree processing.
• Our new join operator, the staircase join encapsulates detailed knowledge about this encoding and turns RDBMSs into high-performance XPath engines.
• The loop-lifting compilation procedure translates incoming XQuery expressions into relational query plans. These plans allow for high-volume XML processing and benefit from our tree encoding and the staircase join implementation.

We implemented these techniques in the course of our MonetDB/XQuery implementation. They should be implementable, however, on any relational DBMS, as we demonstrated with the staircase join implementation on PostgreSQL.¹

Pathfinder Research Team

Since the Pathfinder project started at the University of Konstanz in 2001, our research team now spans three research institutions in two countries.

Publications

Pathfinder XML technology has been described in a number of research articles. We have collected them on our publications list.

¹ Sabine Mayer, Torsten Grust, Maurice van Keulen, Jens Teubner. An Injection with Tree Awareness: Adding Staircase Join to PostgreSQL. Proceedings of the 30th Int'l Conference on Very Large Databases (VLDB 2004), Toronto, Canada, August/September 2004. (Demo)