43
Operations can be divided into several types in terms of this simple model. Some opera-
tions just change the contents of particular cells. We can lump together the various type-
specific operations on the content cells, and consider them as subtypes of a generic change
value operation. An operation can also change the properties of the addressing function for a
data structure. For instance, a sort arrayoperation changes only the locations of the cells (or
their contents), essentially rearrangingthe contents of the composite. Other operations may
add new cells to the structure, while others may remove cells from the structure. Insertand
deleteoperations on lists are perhaps the canonical example.
One critical way in which data type and operational definitions interact is in the area of
data structure invariantsthat may need to be enforced for a data structure to be valid. Any
editing operations may somehow affect a data structure’s required invariants, and thus the
representation of permissible operations. A sorted list, for instance, would need no location
for an insertion operation, and indeed, if one was used, conflicts would be more likely, as
separate positional insertions would be very unlikely to satisfy the sorting invariant. It is
even possible for an operation to impose an invariant on a structure. The sort listexample
mentioned previously might create a new invariant that would automatically affect the re-
sults of any operations in a history that contains it. It would also have a potential conflict
with other sorting operations on the same structure.
2.3 Change-completeness and version-completeness
Once the particular operations required for a given data structure and update pattern
have been selected, the issue remains of how those changes are to interact and be organized
into histories. This section considers some of the high-level issues of change-change interac-
tion in histories, potential conflicts and different possibilities for resolution. The examples
of operations in the discussion are concretely anchored in the problem of representing se-
Operations can be divided into several types in terms of this simple model. Some opera-
tions just change the contents of particular cells. We can lump together the various type-
specific operations on the content cells, and consider them as subtypes of a generic change
value operation. An operation can also change the properties of the addressing function for a
data structure. For instance, a sort arrayoperation changes only the locations of the cells (or
their contents), essentially rearrangingthe contents of the composite. Other operations may
add new cells to the structure, while others may remove cells from the structure. Insertand
deleteoperations on lists are perhaps the canonical example.
One critical way in which data type and operational definitions interact is in the area of
data structure invariantsthat may need to be enforced for a data structure to be valid. Any
editing operations may somehow affect a data structure’s required invariants, and thus the
representation of permissible operations. A sorted list, for instance, would need no location
for an insertion operation, and indeed, if one was used, conflicts would be more likely, as
separate positional insertions would be very unlikely to satisfy the sorting invariant. It is
even possible for an operation to impose an invariant on a structure. The sort listexample
mentioned previously might create a new invariant that would automatically affect the re-
sults of any operations in a history that contains it. It would also have a potential conflict
with other sorting operations on the same structure.
2.3 Change-completeness and version-completeness
Once the particular operations required for a given data structure and update pattern
have been selected, the issue remains of how those changes are to interact and be organized
into histories. This section considers some of the high-level issues of change-change interac-
tion in histories, potential conflicts and different possibilities for resolution. The examples
of operations in the discussion are concretely anchored in the problem of representing se-
