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.
Additional Metadata
Keywords XML, Value index
THEME Information (theme 2)
Publisher CWI
Series Information Systems [INS]
Project XIRAF
Citation
Sidirourgos, E, & Boncz, P.A. (2008). Generic and updatable XML value indices covering equality and range lookups. Information Systems [INS]. CWI.