Native XML Data Storage and Retrieval

Proper specification and use of indexes can increase query speeds by orders of magnitude. However, indexes consume space on disk and in the cache—a classic space versus speed trade-off. Under certain situations, the presence of indexes slows operations. When frequently updating indexed data, time spent re-indexing can offset the benefit of indexed access.

The data models for querying XML imply that virtually all indexes deal with elements, attributes and their respective text content, as well as possible data types represented by their value strings. However, there is no standard or convention regarding how to specify indexes or even what is indexed and how. Different XML databases have made different choices regarding indexes in these areas:

Structural indexes are used for tracking structure and path information, such as “track existence of all element nodes with the path /a/b/c” or “track all paths to the node c.” Such indexes are useful for navigational portions of queries. Some indexes reduce the result set to a smaller set of possible results, rather than give a single definitive result. For example, the index above that tracks all paths /a/b/c can be positive about its answer to the query /a/b/c. The index that tracks all paths to c cannot be definite, because it also contains entries for paths such as /e/f/c.

Value indexes are used to track all values for specific elements or attributes. A value index on the element “color” would have an index entry for every separate instance of color and would be useful for a query such as //color[.='green']. In addition, value indexes may be typed so that comparisons can be performed correctly. The typed data model of XPath 2.0 and XQuery 1.0 brings a long list of potential data types from the XML Schema recommendation, such as xs:date, xs:time and various numeric formats. Support for typed indexes allows applications to use them directly rather than modify their content to map, for example, xs:datetime to integer, so that range-based comparisons can be used.

Full-text indexing is a large topic unto itself. There is a working draft for full-text extensions to XQuery, but it is not yet in general use. Some native XML database products implement what they call full-text indexing, which minimally is a word index over a document. Because there is no standard, a full-text index requires a proprietaryy query language or extension as an interface.

Most native XML databases store documents in a collection. The scope of a given index could be collection-wide or it could be restricted to a single document. A native XML database system can choose the index scope it implements. Queries against a collection can return documents or sets of nodes within documents. In order to support efficient restriction of a query to a manageable set of documents, the system must support indexes at the collection scope. This does not mean that it is not also possible to have indexes at the document scope, which contain entries that apply only to a given document.

Related to scope is the target or the object referenced by an index entry. It can be a document or an object within a document. An index is capable of pointing down to the addressable unit in the system, but such granularity is not always necessary and can be expensive. Because navigational operations within a document stored with fine granularity are not as expensive as those used for intact document storage, due to parsing, it can be sufficient to return the document element for further navigation. Although this is possible, it is the case that most database systems with fine-grained document storage reference directly to nodes in indexes rather than to the containing documents.

Another dimension of index type is how indexes are specified. Voluntary indexes are specified explicitly by an interface to the system. These indexes allow for some experimentation to find the minimal useful set of indexes. Some systems have automatic indexes, where a well-defined set of indexes always is created, except for those that are disabled explicitly, by way of configuration or interface. The system also may have required indexes, which cannot be disabled because they are necessary for proper functioning of the system.