Back to search

University of Waterloo

Encoding XQuery using <em>System F</em>

Abstract

dc:description.abstract

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 is proposed as an XQuery fragment to express XML queries. <br /><br /> In this thesis, XQ is intensively investigated. It is encoded by <em>System F</em>, a second-order lambda calculus with a considerable expressive power and a strong normalization property. Since XML data is defined as inductive data types, XML tree and XML forest, in <em>System F</em>, all basic XML operators in XQ have been successfully encoded. Also, the semantics of XQ are represented in <em>System F</em> where XQ's semantics environment is encoded by an <em>Environment</em> data type with the corresponding operators. The successful encoding of XQ by <em>System F</em> ensures the termination of XQ query evaluation. <br /><br /> Moreover, an extension of XQ by a new tree operator Xtree and a vertical Vfor clause is proposed in this thesis to express some <em>undefinable</em> 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 <em>System F</em> encodable property that ensures the termination of query evaluation.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Xia, Yun

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright: 2005, Xia, Yun. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1203

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Xia, Yun. Encoding XQuery using <em>System F</em>. University of Waterloo, 2005. http://hdl.handle.net/10012/1203