75
3.5 Merging
Using serializability to guarantee simple histories can be expensive to enforce in terms of
system resources, but more importantly, it is expensive in its impact on the ability of users
to maintain an effective workflow without being blocked. Therefore, a variety of “merge”
tools have been developed (Goldstein and Bobrow 1984; Tichy 1985; Neuwirth, Chandhok et
al. 1992; Munson and Dewan 1994; Zeller and Snelting 1995). These tools have the basic task
of reconciling a pair of editing histories to create a single resultant history. Sometimes the
operations in a history are the result of a differencing process that calculates the changes
between one state and another.
Most merge tools have adopted a simple model of the basic operations on a sequence. The
operations of insertion and deletion suffice to express all possible transformations from one
sequence to another sequence, and also correspond to the editing histories constructed by
most difference-finding tools. Only a very few systems can detect operations that move text,
even though most editing systems provide such operations, and most users rely heavily on
such operations. Recent work on the difference problem has come up with good approxima-
tion algorithms that find differences that use move and copy operations, for example, see
(Chawathe, Rajaraman et al. 1996).
Palimpsest makes two alternative choices to this tradition of system design. First, it has a
“contextual history” which does not directly reflect the temporal order of operations, but
captures a particular type of contextual dependency. The dependencies in the new model
can be thought of as a variation of causal orderings (Lamport 1978). While all inter-change
dependencies cannot be eliminated, it turns out that the totally ordered timeline of most
standard approaches can be considerably relaxed to a partial order. The “change-oriented”
version control technique in software engineering (Kruskal 1984; Lie, Conradi et al. 1989;
3.5 Merging
Using serializability to guarantee simple histories can be expensive to enforce in terms of
system resources, but more importantly, it is expensive in its impact on the ability of users
to maintain an effective workflow without being blocked. Therefore, a variety of “merge”
tools have been developed (Goldstein and Bobrow 1984; Tichy 1985; Neuwirth, Chandhok et
al. 1992; Munson and Dewan 1994; Zeller and Snelting 1995). These tools have the basic task
of reconciling a pair of editing histories to create a single resultant history. Sometimes the
operations in a history are the result of a differencing process that calculates the changes
between one state and another.
Most merge tools have adopted a simple model of the basic operations on a sequence. The
operations of insertion and deletion suffice to express all possible transformations from one
sequence to another sequence, and also correspond to the editing histories constructed by
most difference-finding tools. Only a very few systems can detect operations that move text,
even though most editing systems provide such operations, and most users rely heavily on
such operations. Recent work on the difference problem has come up with good approxima-
tion algorithms that find differences that use move and copy operations, for example, see
(Chawathe, Rajaraman et al. 1996).
Palimpsest makes two alternative choices to this tradition of system design. First, it has a
“contextual history” which does not directly reflect the temporal order of operations, but
captures a particular type of contextual dependency. The dependencies in the new model
can be thought of as a variation of causal orderings (Lamport 1978). While all inter-change
dependencies cannot be eliminated, it turns out that the totally ordered timeline of most
standard approaches can be considerably relaxed to a partial order. The “change-oriented”
version control technique in software engineering (Kruskal 1984; Lie, Conradi et al. 1989;
