44
quences and their editing, although the issues apply to other types of aggregate data struc-
tures as well.
There are two fundamental properties that might be satisfied by a change-oriented repre-
sentation of state changes. One possibility is a set of operations that is version-complete. We
will define the term version-complete to refer to a set of operation types that suffices to rep-
resent all the possible differences between significant states (versions) of a data object.
When the goal is to represent onlyparticular states of data objects, without concern for
combining or modifying change histories, a version-complete set of changes is all that is
needed to meet the functional requirement.
With a version-complete set of operation types, any version graph can be represented by
sets of changes in a history structure. Such representations are often used as a storage opti-
mization technique to reduce the overhead and data duplications of saving many distinct
but similar states. Such representations are chosen so that the storage to hold all needed
versions of an object will be as small as practical. The precise operation types and their rep-
resentation are critical to satisfying a system’s time and space efficiency goals, both in terms
of the space required to hold typical histories, and the time required to find the representing
any particular history. However, the actual operations used are not important in themselves,
and there are in fact many possible operation sets, with fairly simple semantics.
Version-completeness is not a very difficult property to ensure. More difficult is to find a
set of basic operations that is change-complete.Such a set of operations is sufficient not only
to represent differences among arbitrary versions, but is also chosen to be “natural” for the
application area in question. While this may involve very specialized operations of use only
in a particular application, there are in fact many useful generalized operations, depending
on an application’s requirements. One key issue in determining the naturalness of an opera-
tion set for an application’s needs is whether the operations directly correspond to a user’s
actions in using the application, or to a user’s model of what is being accomplished by those
quences and their editing, although the issues apply to other types of aggregate data struc-
tures as well.
There are two fundamental properties that might be satisfied by a change-oriented repre-
sentation of state changes. One possibility is a set of operations that is version-complete. We
will define the term version-complete to refer to a set of operation types that suffices to rep-
resent all the possible differences between significant states (versions) of a data object.
When the goal is to represent onlyparticular states of data objects, without concern for
combining or modifying change histories, a version-complete set of changes is all that is
needed to meet the functional requirement.
With a version-complete set of operation types, any version graph can be represented by
sets of changes in a history structure. Such representations are often used as a storage opti-
mization technique to reduce the overhead and data duplications of saving many distinct
but similar states. Such representations are chosen so that the storage to hold all needed
versions of an object will be as small as practical. The precise operation types and their rep-
resentation are critical to satisfying a system’s time and space efficiency goals, both in terms
of the space required to hold typical histories, and the time required to find the representing
any particular history. However, the actual operations used are not important in themselves,
and there are in fact many possible operation sets, with fairly simple semantics.
Version-completeness is not a very difficult property to ensure. More difficult is to find a
set of basic operations that is change-complete.Such a set of operations is sufficient not only
to represent differences among arbitrary versions, but is also chosen to be “natural” for the
application area in question. While this may involve very specialized operations of use only
in a particular application, there are in fact many useful generalized operations, depending
on an application’s requirements. One key issue in determining the naturalness of an opera-
tion set for an application’s needs is whether the operations directly correspond to a user’s
actions in using the application, or to a user’s model of what is being accomplished by those
