Evaluating nested queries on XML data

In the past few years, much attention has been paid to the study of semistructured data, i.e., data with irregular, possibly unstable, and rapidly changing structure, and, in particular, to the study of their best-known incarnation: XML. The growing interest toward XML leaded to the definition of many querying and manipulating tools, such as the standard query language XQuery (Boag et al., 2002). Unlike SQL, XQuery poses no restriction on query nesting (an XQuery query can be nested wherever a well-formed XML document is expected), and lacks explicit clauses for performing group-by operations. As a result, nested queries play an important role in the context of XQuery. This paper shows the techniques used in the Xtasy system for processing and evaluating nested queries on XML data. These techniques applies to the physical level only, and they are based on the massive use of node sharing, with the aim of decreasing as much as possible the use of secondary storage. The proposed solutions are general enough to be applied, with a few modifications, to more structured contexts.