The structure of a relevant benchmark data set must be complex enough to capture all characteristics of XML data representation. XML and relational data models are radically different. In particular, XML provides an implicit ordering of its elements since it is designed as a subset of SGML to represent documents. XML also provides references, deep nesting, as well as hyperlinks. These features, which we elaborate upon in the next section, are similar to those found in object-oriented models. In addition to the traditional object-oriented complex object-modeling features, the benchmark database should also capture the document (i.e., the implicit order of elements) and navigation (references) features while providing an understandable semantics and structure. The scalability of a system can be measured by using data sets of varying sizes. Since XML data can be represented as a tree, the depth and width of the tree should be adjustable. This can be achieved as follows:
The depth of a tree can be controlled by varying the number of repetitions of recursive elements.
The width of the tree can be adjusted by varying the cardinality of some elements.
Since XML itself is platform and application independent, portability is not a major issue here. We observe that unlike XML elements, the ordering of attributes in XML is optional. Hence, an XML management system can return the results of a query without preserving the attribute order.
The performance of the implementations of query languages for XML depends greatly on their expressive power?that is, the functionalities they provide. Bonifati and Ceri address the functionalities of XML query languages by carrying out a comparative analysis of the major XML query languages (Bonifati and Ceri 2000). The W3C XML Query Language Working Group has also published a list of "must have" requirements for XML query languages (Chamberlin et al. 2001). Table 17.1 presents these requirements. Note that the requirement R21 represents the functionality based upon element ordering, an important feature of XML representation assumed by the document community that has dramatic impact on the expressive power of query languages (Fernandez et al. 2000).
The requirements enumerated by the W3C specify an XML query language that provides data-centric, document-centric, and navigational capabilities. XML can represent structured and unordered data, and an XML query language must be as expressive as a structured query language such as SQL is for relational databases. Such data-centric capabilities or relational queries include various types of join operations (R9), aggregation (R10), sorting (R11), and so on. Queries that use the implicit and explicit order of elements or use textual operators are classified as document queries. Such document-centric capabilities are required when order and document structure need to be preserved in some form (R17, R21). Queries that require traversal of XML document structure using references/links as supported by XLink/XPointer specification (DeRose, Maler, Daniel 2001; DeRose, Maler, Orchard 2001) are called navigational queries (R13, R20).
Some XMS may have limited query-processing capabilities and it is possible that many benchmark queries cannot be executed on such systems. For example, XPath (Clark and DeRose 1999) supports only the count function but not the avg (average) function. A benchmark query that tests the performance of both count and avg functions cannot be evaluated on systems that implement XPath. This problem can be resolved by having separate benchmark queries, each testing a different type of aggregation. Furthermore, depending on the application, users may want to test only a subset of the functionalities covered by some queries. For example, some applications may never need to update the database while others do not need to restructure the retrieved results. Hence, it is important to distribute the various functionalities into different queries so that users can always choose the queries according to the functionalities they need. Separating the functionalities also facilitates the analysis of the experiment results since it will be very clear which feature is being tested. Finally, the benchmark queries should allow the range of values of selected attributes to be varied in order to control the percentage of data retrieved by queries?that is, the selectivity of queries.