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.
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 Grust • Manuel Mayr • Jan 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 Grust • Manuel Mayr • Jan 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.
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
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 Grust • Manuel Mayr • Jan 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 Grust • Jan 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 Grust • Jan 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 Grust • Jan 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
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
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
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
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.