Pathfinder

A Purely Relational XQuery Processor

We believe that relational databases are the most researched and best engineered query processing infrastructures available today. They are able to efficiently query tons of data. By using a relational database as runtime environment for an XQuery processor we can port 30+ years of research to the XQuery domain and build a processor that is able to scale well with increasing input sizes. Pathfinder is a re-targetable query compiler that turns XQuery expressions into table algebra queries. While Pathfinder is tightly coupled with MonetDB we also provide a SQL code generator that allows any database to become a faithful XQuery processor.

Pathfinder Overview

The Approach

Pathfinder assumes a database to store shredded XML documents—documents that are transformed into a relational encoding. An incoming XQuery query is compiled by Pathfinder into a relational query plan. The database evaluates the generated query plan based on the shredded XML documents and returns a table. A serializer consumes this table and transforms it into an XQuery result sequence. (In MonetDB/XQuery automatic shredding and serialization as well as the tight integration of Pathfinder lead to a runtime where the relational approach is not visible for the user anymore.).

MonetDB/XQuery

Pathfinder has been released in the form of MonetDB/XQuery and is available at the MonetDB project. Note, though, that MonetDB/XQuery is no longer maintained and is only available in MonetDB releases up to March, 2011.

Publications

Let SQL Drive the XQuery Workhorse.

Torsten GrustManuel MayrJan Rittinger

Proceedings of the 13th Int’l Conference on Extending Database Technology (EDBT 2010), Lausanne, Switzerland, March 2010.

XQuery Processors.

Torsten Grust • H.V. Jagadish • Fatma Özcan • Cong Yu

Encyclopedia of Database Systems, Editors-in-chief: M. Tamer Öszu; Ling Liu, © Springer Verlag, (print and online), September 2009.

Recursion in XQuery: Put Your Distributivity Safety Belt On.

Loredana Afanasiev • Torsten Grust • Maarten Marx • Jan Rittinger • Jens Teubner

Proceedings of the 12th Int’l Conference on Extending Database Technology (EDBT 2009), St. Petersburg, Russia, March 2009.

XQuery Join Graph Isolation.

Torsten GrustManuel MayrJan Rittinger

Proceedings of the 25th Int’l Conference on Data Engineering (ICDE 2009), Shanghai, China, March/April 2009.

Pathfinder: XQuery Off the Relational Shelf.

Torsten Grust • Jens Teubner • Jan Rittinger

Bulletin of the IEEE Technical Committee on Data Engineering. Special Issue on XQuery Processing: Practice and Experience. Vol. 31, No. 4, December 2008.

Dependable Cardinality Forecasts for XQuery.

Jens Teubner • Torsten Grust • Sebastian Maneth • Sherif Sakr

Proceedings of the 34th Int’l Conference on Very Large Databases (VLDB 2008)/Journal of Data Management Research (JDMR), vol. 1, Auckland, New Zealand, August 2008.

Jump Through Hoops to Grok the Loops — Pathfinder's Purely Relational Account of XQuery-style Iteration Semantics.

Torsten GrustJan Rittinger

Proceedings of the ACM SIGMOD/PODS 5th Int’l Workshop on XQuery Implementation, Experience and Perspectives (XIME-P 2008), Vancouver, Canada, June 2008.

An Inflationary Fixed Point Operator in XQuery.

Loredana Afanasiev • Torsten Grust • Maarten Marx • Jan Rittinger • Jens Teubner

Proceedings of the 24th IEEE Int’l Conference on Data Engineering (ICDE 2008), Cancún, México, April 2008.

Pathfinder meets DB2.

Manuel Mayr

Ph.D. Workshop of the 11th Int’l Conference on Extending Database Technology (EDBT 2008), Nantes, France, March 2008.

A SQL:1999 Code Generator for the Pathfinder XQuery Compiler.

Torsten GrustManuel MayrJan Rittinger • Sherif Sakr • Jens Teubner

Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD 2007), Beijing, China, June 2007.

Data-Intensive XQuery Debugging with Instant Replay.

Torsten GrustJan Rittinger • Jens Teubner

Proceedings of the ACM SIGMOD/PODS 4th Int’l Workshop on XQuery Implementation, Experience and Perspectives (XIME-P 2007), Beijing, China, June 2007.

Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect.

Torsten GrustJan Rittinger • Jens Teubner

Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD 2007), Beijing, China, June 2007.

XQuery Implementation Paradigms.

Peter Boncz • Torsten Grust • Jérôme Siméon • Maurice van Keulen (Eds.)

In Dagstuhl Seminar Proceedings, Nº 06472, Dagstuhl Castle, May 2007.

eXrQuy: Order Indifference in XQuery.

Torsten GrustJan Rittinger • Jens Teubner

Proceedings of the 23rd Int’l Conference on Data Engineering (ICDE 2007), Istanbul, Turkey, April 2007.

Pathfinder: A Relational Query Optimizer Explores XQuery Terrain.

Jan Rittinger • Jens Teubner • Torsten Grust

GI-Fachtagung für Datenbanksysteme in Business, Technologie und Web (BTW 2007), Aachen, Germany, March 2007.

Pathfinder: XQuery Compilation Techniques for Relational Database Targets.

Jens Teubner

PhD Thesis, Technische Universität München, October 2006.

MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine.

Peter Boncz • Torsten Grust • Maurice van Keulen • Stefan Manegold • Jan Rittinger • Jens Teubner

Proceedings of the ACM SIGMOD Conference on Management of Data (SIGMOD 2006), Chicago, IL, USA, June 2006.

MonetDB/XQuery—Consistent & Efficient Updates on the Pre/Post Plane.

Peter Boncz • Jan Flokstra • Torsten Grust • Maurice van Keulen • Stefan Manegold • Sjoerd Mullender • Jan Rittinger • Jens Teubner

Proceedings of the 10th Int’l Conference on Extending Database Technology (EDBT 2006), Munich, Germany, Springer LNCS 3896, pages 1190-1193, March 2006. © Springer Verlag

Pathfinder: XQuery—The Relational Way.

Peter Boncz • Torsten Grust • Maurice van Keulen • Stefan Manegold • Jan Rittinger • Jens Teubner

Proceedings of the 31th Int’l Conference on Very Large Databases (VLDB 2005), Trondheim, Norway, August/September 2005.

Purely Relational FLWORs.

Torsten Grust

Proceedings of the ACM SIGMOD/PODS 2nd Int’l Workshop on XQuery Implementation, Experience and Perspectives (XIME-P 2005), Baltimore, MD, USA, June 2005.

Updating the Pre/Post Plane in MonetDB/XQuery.

Peter Boncz • Stefan Manegold • Jan Rittinger

Proceedings of the ACM SIGMOD/PODS 2nd Int’l Workshop on XQuery Implementation, Experience and Perspectives (XIME-P 2005), Baltimore, MD, USA, June 2005.

Loop-Lifted Staircase Join: From XPath to XQuery

Peter Boncz • Torsten Grust • Maurice van Keulen • Stefan Manegold • Jan Rittinger • Jens Teubner

Technical Report INS-E0510. CWI, Amsterdam, March 2005.

Pathfinder/MonetDB: A High Performance Relational Runtime for XQuery.

Jan Rittinger

Studierenden-Programm of the 11. GI-Fachtagung für Datenbanksysteme in Business, Technologie und Web (BTW 2005), Karlsruhe, Germany, March 2005.

Pathfinder: Relational XQuery Over Multi-Gigabyte XML Inputs In Interactive Time

Peter Boncz • Torsten Grust • Stefan Manegold • Jan Rittinger • Jens Teubner

Technical Report INS-E0503. CWI, Amsterdam, March 2005.

XQuery on SQL Hosts.

Torsten Grust • Sherif Sakr • Jens Teubner

Proceedings of the 30th Int’l Conference on Very Large Databases (VLDB 2004), Toronto, Canada, August/September 2004.

Supporting Positional Predicates in Efficient XPath Axis Evaluation for DOM Data Structures

Torsten Grust • Jan Hidders • Philippe Michiels • Roel Vercammen • Maurice van Keulen

Technical Report (TR 2004-05), University of Antwerp, Belgium, July 2004.

Relational Algebra: Mother Tongue—XQuery: Fluent.

Torsten Grust • Jens Teubner

Twente Data Management Workshop on XML Databases and Information Retrieval (TDM 2004), Invited Paper, Enschede, The Netherlands, June 2004.

Accelerating XPath Evaluation in Any RDBMS.

Torsten Grust • Maurice van Keulen • Jens Teubner

ACM Transactions on Database Systems (TODS), 29(1), March 2004.

Staircase Join: Teach A Relational DBMS to Watch its (Axis) Steps.

Torsten Grust • Maurice van Keulen • Jens Teubner

Proceedings of the 29th Int’l Conference on Very Large Databases (VLDB 2003), Berlin, Germany, September 2003.

Tree Awareness for Relational DBMS Kernels: Staircase Join.

Torsten Grust • Maurice van Keulen • H. Blanken • T. Grabs • H.-J. Schek • R. Schenkel • G. Weikum (Eds.)

Intelligent Search on XML Data, Springer Verlag, ISBN 3-540-40768-5, September 2003.

Bridging the Gap Between Relational and Native XML Storage with Staircase Join.

Torsten Grust • Maurice van Keulen • Jens Teubner

Proceedings of the 15th GI Workshop on Foundations of Database Systems, Tangermünde, Germany, June 2003.

Accelerating XPath Location Steps.

Torsten Grust

Proceedings of the 21st ACM SIGMOD Int’l Conference on Management of Data (SIGMOD 2002), pages 109-120, ACM Press, Madison, Wisconsin, USA, June 2002.