Prefix-Based Node Numbering for Temporal XML

摘要

Prefix-based numbering (also called Dewey numbering, Dewey level order, or dynamic level numbering) is a popular method for numbering nodes in an XML data model instance. The nodes are numbered so that spatial relationships (e.g., is a node a descendant of another) can be determined just from the numbers. In a temporal XML data collection the spatial relationships change over time as nodes are edited, deleted, and inserted. In this paper we adapt prefix-based numbering to support the concise representation of items (elements that share the same identity over time) and versions (changes to an item over time). We call our new numbering system time-tunneling dynamic level numbering (TTDLN). We show how to create, store, and update TTDLNs, and how they can be used to efficiently evaluate sequenced and non-sequenced temporal queries.