119
aging a shared artifact by accepting and integrating user requests and updates from other
instances. In either case, these persistent change sets change incrementally rather than be-
ing constructed arbitrarily. While arbitrary version construction is common in sme software
engineering applications (Lie, Conradi et al. 1989; Munch 1993), it is unlikely in most
authoring applications. When fully dynamic version construction is being used, the optimiza-
tion of representing explicit version sets is inapplicable. The operation set above reflects the
use of explicitly represented versions. The Palimpsest addressing mechanism is a significant
in both sorts of implementation, since it provides a well-ordered set of keys with which aux-
iliary structures can be built to speed access and update functions.
The capabilities in items 1and 2are relatively simple, and provide the ability to look up
information about a change given its change ID. Lookup of basic information about a change
given its ID can be handled by standard index structures in logarithmic time without diffi-
culty, or even faster if hashing methods are used. The rest of the listed capabilities deal with
finding the contents of an arbitrary change set, and represent the difficult part of an imple-
mentation.
One highly significant issue is tracking the areas of effect for operations. There are five
sorts of region with significance to the Palimpsest change model, most of which require some
special indexing support:
1. Insertion points represent the destinations of insert operations: places where con-
stant data is inserted.
2. Variable insertion points are similar to regular insertion points since they cause the
addition of new data, however that data is not necessarily constant. For a copy op-
eration, the inserted data also appears elsewhere. For a move operation, the source
data is deleted and its selection is more complex, due to interactions between over-
lapping move sources. However, the difference in behavior at the insertion point is
determined entirely by the behavior at the operation’s source. For instance, both
aging a shared artifact by accepting and integrating user requests and updates from other
instances. In either case, these persistent change sets change incrementally rather than be-
ing constructed arbitrarily. While arbitrary version construction is common in sme software
engineering applications (Lie, Conradi et al. 1989; Munch 1993), it is unlikely in most
authoring applications. When fully dynamic version construction is being used, the optimiza-
tion of representing explicit version sets is inapplicable. The operation set above reflects the
use of explicitly represented versions. The Palimpsest addressing mechanism is a significant
in both sorts of implementation, since it provides a well-ordered set of keys with which aux-
iliary structures can be built to speed access and update functions.
The capabilities in items 1and 2are relatively simple, and provide the ability to look up
information about a change given its change ID. Lookup of basic information about a change
given its ID can be handled by standard index structures in logarithmic time without diffi-
culty, or even faster if hashing methods are used. The rest of the listed capabilities deal with
finding the contents of an arbitrary change set, and represent the difficult part of an imple-
mentation.
One highly significant issue is tracking the areas of effect for operations. There are five
sorts of region with significance to the Palimpsest change model, most of which require some
special indexing support:
1. Insertion points represent the destinations of insert operations: places where con-
stant data is inserted.
2. Variable insertion points are similar to regular insertion points since they cause the
addition of new data, however that data is not necessarily constant. For a copy op-
eration, the inserted data also appears elsewhere. For a move operation, the source
data is deleted and its selection is more complex, due to interactions between over-
lapping move sources. However, the difference in behavior at the insertion point is
determined entirely by the behavior at the operation’s source. For instance, both
