Generic and updatable XML value indices covering equality and range lookups

We describe a collection of indices for XML text, element, and attribute node values that (i) consume little storage, (ii) have low maintenance overhead, (iii) permit fast equi-lookup on string values, and (iv) support range-lookup on any XML typed value (e.g., double, dateTime). The equi- lookup string value index depends on an elaborate hash function and on an associative combination function to facilitate updates on both mixed-content and element nodes. We also present techniques for creating range-lookup indices supporting any ordered XML typed value. These indices rely on a finite state machine that accepts the type specific language, and on a state combination table for combining state to speed-up updates. We evaluate the stability of the hash function, the storage overhead, and the indices creation and maintenance time in the context of the open-source XML database system MonetDB/XQuery.