With the significant increase of web-based applications, the eXtensible Markup Language (XML), as a de facto standard for data interchange on the web, has attracted considerable attention in theory and practice. XML deals with irregular and heterogeneous semi-structured data that, give rise to trees, i.e. the predominant data structure in complex data models. This leads to new challenges for database research such as new data structures and models, and new database query languages in this area. 1.1 XML Data Challenges In essence, the major challenge of XML lies in its data structure, which is greatly different from the traditional data structure treated as relations. A comparison with respect to the differences between XML data and relational data has been discussed in . Generally speaking, XML data has the following unique characteristics: • XML data have irregular and heterogeneous structures leading to optional values which are absent in relational data; • Metadata that describes the structure of the data is distributed throughout the data in the form of markup, instead of being stored separately as in relational data; • XML data is nested in a hierarchy, and complex nested structures might need to be decomposed and reconstructed on the fly to facilitate data manipulations; • XML data are encoded with an intrinsic order that is an important property of data themselves. This means that the order property must be taken into consideration for modelling.