Encoding XQuery using System F
Yun Fei Xia · 2005
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. public. I understand that my thesis may be made electronically available to the ii Since the World Wide Web Consortium (W3C) has recommended XQuery as the standard XML query language, the interest in using existing relational technology to query the XML data has dramatically increased. The most significant challenge of the relational approach is how to fully support XQuery semantics in XQuery-to-SQL translation. To eliminate the implicit semantics of XQuery, an XQuery fragment must be defined with simple syntax and explicit semantics. XQ [6] is proposed as an XQuery fragment to express XML queries. In this thesis, XQ is intensively investigated. It is encoded by System F, a second-order lambda calculus with a proven expressive power and a strong normalization property. Since XML data is defined as inductive data types, XML tree and XML forest, in System F, all basic XML operators in XQ have been successfully encoded. Also, the semantics of XQ are represented in System F where XQ’s semantics environment is encoded by an Environment data type with the corresponding operators. The successful encoding of XQ by System F ensures the termination of XQ query evaluation. Moreover, an extension of XQ by a new tree operator Xtree and a vertical Vfor clause is proposed in this thesis to express the undefinable XQ queries. It is demonstrated that this extension still allows XQ to retain its XQ-to-SQL translation property that ensures the polynomial evaluation time complexity, and its System F encodable property that ensures the termination of query evaluation. iii Acknowledgments I would like to acknowledge the support of several people who have made this thesis possible. First and foremost, I am very grateful to Dr. David Toman, my supervisor, for his great guidance and support during my grad-uate studies. His patience, valuable suggestions and comments have directly facilitated the completion of this thesis.