Cardinality-Aware and Purely Relational Implementation of an XQuery Processor

With the rapid growth in the use of XML documents as a universal format for storage and interchange of the data on the Web, several efforts have been made in order to develop efficient techniques for storing and querying XML data. Since XQuery is becoming the standard XML query language, significant effort has been made in developing efficient implementations of XQuery query processor. This thesis describes a purely relational implementation of an XQuery processor which exploits the well-known maturity and performance acceleration techniques of the relational database technology to translate XQuery expressions into their equivalent SQL evaluation scripts. The generated SQL evaluation scripts are based on the XPath accelerator relational mapping scheme of the XML documents and can be executed on any conventional relational database management systems with no need for any changes in its kernel or any other special requirements. The translation process starts by compiling the input XQuery expression into an intermediate algebraic plan which is then translated into its equivalent SQL evaluation script by means of a predefined SQL translation template for each algebraic operator. In order to produce efficient and concise SQL queries, different XQuery to SQL translation approaches are proposed and different relational optimization techniques have been exploited. In addition, this thesis presents a novel framework for estimating the cardinality of XQuery expressions as well as its sub-expressions. Although cardinality size estimation is very important on its own, it is also very crucial for an effective query optimization process. This thesis presents an integrated framework for exploiting the available estimated cardinality information to provide the RDBMS query optimizers with hints for selecting the best alternative execution plan for the SQL evaluation scripts of the input XQuery expression. The experiments of this thesis demonstrate the efficiency and scalability of our purely relational approach in comparison to the native XML/XQuery functionality supported by conventional RDBMSs.