Chapter 6: Algorithms for P-sequences
This chapter discusses algorithms for change-oriented management of sequences. We will
consider the issue from a data structure perspective, examining ways to retain a database of
changes, and produce the results of applying subsets of those changes. This chapter proceeds
incrementally to a full solution: first presenting algorithms sufficient for managing change
sets including only insert and delete operations, and then extending them to handle move
and copy operations. The first stage will begin with an examination of the algorithms for
VTML editors, and then continue with an examination of how to implement the more com-
plex model provided by Palimpsest. VTML is a change-oriented data format to help support
collaboration over the World Wide Web, which provides an interesting contrast to Palimpsest.
6.1 The VTML model
This section gives a brief description of VTML 2.0, (the Versioned Text Markup Language)
a system supporting change-oriented concurrency control for web applications. The initial
description of VTML (VTML 1.0) was presented in (Vitali and Durand 1995). VTML is a file
format for the interchange of multiple revisions of documents, and is intended as a building
block for protocols for collaboration over the web. A VTML document can represent a set of
updates to be applied to another VTML document, or it can be a self-contained representa-
tion of multiple versions of a document. VTML is still has versions which use a pure branch-
ing scheme. It also supports additional change-oriented features, which store information
about the individual insertion and deletion operations that make up a version. Versions can
explicitly add in, or remove particular changes that were created in other versions.
This chapter discusses algorithms for change-oriented management of sequences. We will
consider the issue from a data structure perspective, examining ways to retain a database of
changes, and produce the results of applying subsets of those changes. This chapter proceeds
incrementally to a full solution: first presenting algorithms sufficient for managing change
sets including only insert and delete operations, and then extending them to handle move
and copy operations. The first stage will begin with an examination of the algorithms for
VTML editors, and then continue with an examination of how to implement the more com-
plex model provided by Palimpsest. VTML is a change-oriented data format to help support
collaboration over the World Wide Web, which provides an interesting contrast to Palimpsest.
6.1 The VTML model
This section gives a brief description of VTML 2.0, (the Versioned Text Markup Language)
a system supporting change-oriented concurrency control for web applications. The initial
description of VTML (VTML 1.0) was presented in (Vitali and Durand 1995). VTML is a file
format for the interchange of multiple revisions of documents, and is intended as a building
block for protocols for collaboration over the web. A VTML document can represent a set of
updates to be applied to another VTML document, or it can be a self-contained representa-
tion of multiple versions of a document. VTML is still has versions which use a pure branch-
ing scheme. It also supports additional change-oriented features, which store information
about the individual insertion and deletion operations that make up a version. Versions can
explicitly add in, or remove particular changes that were created in other versions.
