We present an archiving technique for hierarchical data with key
structure. Our approach is based on the notion of timestamps
whereby an element appearing in multiple versions of the database is
stored only once along with a compact description of versions in
which it appears. The basic idea of timestamping was discovered by
Driscoll et al. in the context of persistent data structures
where one wishes to track the sequences of changes made to a data
structure. We extend this idea to develop an archiving tool for XML
data that is capable of providing meaningful change descriptions and
can also efficiently support a variety of basic functions concerning
the evolution of data such as retrieval of any specific version from
the archive and querying the temporal history of any element. This
is in contrast to diff-based approaches where such operations may
require undoing a large number of changes or significant reasoning
with the deltas. Surprisingly, our archiving technique does not
incur any significant space overhead when contrasted with other
approaches. Our experimental results support this and also show
that the compacted archive file interacts well with other
compression techniques. Finally, another useful property of our
approach is that the resulting archive is also in XML and hence can
directly leverage existing XML tools.
/ Fax: +81(Japan) 75-753-5978 / Office: Research Bldg. #7, room 404