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.

This work may be seen as a further proof of the versatility of the relational database model. Here, we add XQuery to the catalog of languages which RDBMSs are able to “speak” fluently.

Given suitable relational encodings of sequences and ordered, unranked trees—the two data structures that form the backbone of the XML and XQuery data models—we describe a compiler that translates XQuery expressions into a simple and quite standard relational algebra which we expect to be efficiently implementable on top of any relational query engine. The compilation procedure is fully compositional and emits algebraic code that strictly adheres to the XQuery language semantics: document and sequence order as well as node identity are obeyed. We exercise special care in translating arbitrarily nested XQuery FLWOR iteration constructs into equi-joins, an operation which RDBMSs can perform particularly fast. The resulting purely relational XQuery processor shows promising performance figures in experiments.