Translating XQuery to Relational Algebra

Abstract

XQuery is a flexible language for querying XML data across a variety of storage methods. This thesis is a part of iAD, an ongoing research effort in next generation information access solutions. iAD is hosted by Fast Search & Transfer, a company developing their next search engine platform MARS. This project seeks to investigate the utilisation of XQuery as a query language for MARS. The result of this project is a novel method of translation, dubbed “Tainting Dependencies” (TD), which seeks to avoid unecessary denormalisation of intermediate results, and is designed specifically for translation to MARS’ relational algebra. This method supports a large subset of XQuery features. Furthermore, we have developed a prototype implementation which supports basic constructs such as FLWOR and sequence construction. TD is then compared head-on to a similar method dubbed “Loop Lifting”, and the results of this comparison is evaluated through discussion. The outcome of this project is a novel and well-documented method for translation of XQuery to MQL – a method which is designed to perform equally or better than existing implementations.