Efficient Management of Multiversion Documents by Object Referencing

Abstract

Traditional approaches to versioning documents are edit-based, and represent successive versions using edit scripts. This paper proposes a reference-based versioning scheme that preserves the rich logical structure of the evolving document via object references. This approach produces better support for queries, and reconciles the storage-level and transport-level representations of multiversioned XML documents. In particular, we present efficient algorithms for supporting projection and selection queries, and for querying the document evolution history. Then, we show that our representation is also efficient at the transport level, where XML documents are exchanged between remote parties. In fact, with the reference-based scheme, an XML document's history can also be viewed and processed as yet another XML document. Finally, we demonstrate the effectiveness of the new scheme at the storage level, for which we define a usefulness-based page management policy, adapted from transactiontime databases, to ensure efficient temporal clustering between versions. The experimental evaluation of the new scheme against previous representations used in temporal databases and persistent-object managers shows the performance advantages of the new approach.