DeweyIDs—The Key to Fine-Grained Management of XML Documents

Abstract. Because XML documents tend to be very large and are more and more collaboratively processed, their fine-grained storage and management is a must for which, in turn, a flexible tree representation is mandatory. Performance re-quirements dictate efficient query and update processing in multi-user environ-ments. For this reason, three aspects are of particular importance: index sup-port to directly access each internal document node if needed, navigation along the parent, child, and sibling axes, selective and direct locking of minimal doc-ument granules. The secret to effectively accelerate all of them are DeweyIDs. They identify the tree nodes, avoid relabeling of them even under heavy node in-sertions and deletions, and allow, at the same time, the derivation of all ancestor node IDs without accessing the document. In this paper, we explore the concept of DeweyIDs, refine the ORDPATH addressing scheme, illustrate its implemen-tation, and give an exhaustive performance evaluation of its practical use.