Database Research Group

WSI – Database Systems Research Group

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

Torsten Grust, Jan Rittinger

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

Online version

What remains if you remove XML trees and node construction, XPath location path traversal, atomization, and all other XML-inflicted concepts from XQuery? — We describe how the design of the database-supported XQuery processor Pathfinder has been centered around the compilation of the language’s core side effect-free iteration construct, for, a concept that XQuery shares with many (data-intensive) languages, e.g., SQL, LINQ, Links, Ruby, and Haskell’s or Python’s list comprehensions. The compiler implements loop lifting, a compilation technique that lets a relational database back-end fully realize—and benefit from—the independence of the individual iterations of a for loop. We explore useful extensions and special cases of loop lifting and will see how XQuery 1.1’s proposed windowed iteration construct forseq may be grokked this way—this also uncovers, however, forseq’s lurking cost.