XQuery streaming by Forest Transducers

Shizuya Hakuta, Sebastian Maneth, Keisuke Nakano, Hideya Iwasaki

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Citations (Scopus)


Streaming of XML transformations is a challenging task and only a few existing systems support streaming. Research approaches generally define custom fragments of XQuery and XPath that are amenable to streaming, and then design custom algorithms for each fragment. These languages have several shortcomings. Here we take a more principled approach to the problem of streaming XQuery-based transformations. We start with an elegant transducer model for which many static analysis problems are well-understood: the Macro Forest Transducer (MFT). We show that a large fragment of XQuery can be translated into MFTs - indeed, a fragment of XQuery, that can express important features that are missing from other XQuery stream engines, such as GCX: our fragment of XQuery supports XPath predicates and let-statements. We then use an existing streaming engine for MFTs and apply a well-founded set of optimizations from functional programming such as strictness analysis and deforestation. Our prototype achieves time and memory efficiency comparable to the fastest known engine for XQuery streaming, GCX. This is surprising because our engine relies on the OCaml built in garbage collector and does not use any specialized buffer management, while GCX's efficiency is due to clever and explicit buffer management.

Original languageEnglish
Title of host publication2014 IEEE 30th International Conference on Data Engineering, ICDE 2014
PublisherIEEE Computer Society
Number of pages12
ISBN (Print)9781479925544
Publication statusPublished - 2014
Event30th IEEE International Conference on Data Engineering, ICDE 2014 - Chicago, IL, United States
Duration: 2014 Mar 312014 Apr 4

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference30th IEEE International Conference on Data Engineering, ICDE 2014
Country/TerritoryUnited States
CityChicago, IL


Dive into the research topics of 'XQuery streaming by Forest Transducers'. Together they form a unique fingerprint.

Cite this