111
6.1.1 Versions and version numbers
Since a change is applicable in any version that is a descendent of the version in which it
was added, ancestor queries are important in quickly determining whether a particular
change is present in a particular version. In VTML, this problem is solved by using a version
numbering scheme. While versions could be arbitrarily identified, structured naming schemes
are in wide use because they enable a program to determine the relationship between two
versions given only their version numbers. In particular, it is useful to be able to tell if a
version is a child of another version, and to calculate the version number of the common
ancestor of two versions given their version numbers. VTML versions are represented using
“L-shaped” version numbers. This numbering system has been (independently) described in
(Keller and Ullman 1995), which examines them in terms of their ordering properties, for
integrating version management into traditional database systems. Before describing L-
shaped version numbering, we will briefly review the two most obvious alternatives, and
their characteristics.
The first alternative can be called outline numbering. In this system, as in all the follow-
ing ones we shall examine, the root version is always number 1. The first child of a node, x,
will have number x.1. Then-th brother ofx.1will have numberx.n. This means that each
successor version increases the length of the version number. While this system is simple to
implement, and while ancestor testing and common ancestor determination are trivial, this
scheme is never used. This is because version trees tend to have many long chains, and out-
line numbers grow linearly in the length of a chain.
The second alternative can be called reverse outline numbering. In this system, the first
child of a node xwill have numberx+1. The first sibling ofx+1will have number(x+1).1.
Under these rules, further siblings will be numbered x+1.1.1, and so on. In this system, suc-
cessors are numbered sequentially, solving the problem of long identifiers, but any large
number of alternatives recreates the problem.
6.1.1 Versions and version numbers
Since a change is applicable in any version that is a descendent of the version in which it
was added, ancestor queries are important in quickly determining whether a particular
change is present in a particular version. In VTML, this problem is solved by using a version
numbering scheme. While versions could be arbitrarily identified, structured naming schemes
are in wide use because they enable a program to determine the relationship between two
versions given only their version numbers. In particular, it is useful to be able to tell if a
version is a child of another version, and to calculate the version number of the common
ancestor of two versions given their version numbers. VTML versions are represented using
“L-shaped” version numbers. This numbering system has been (independently) described in
(Keller and Ullman 1995), which examines them in terms of their ordering properties, for
integrating version management into traditional database systems. Before describing L-
shaped version numbering, we will briefly review the two most obvious alternatives, and
their characteristics.
The first alternative can be called outline numbering. In this system, as in all the follow-
ing ones we shall examine, the root version is always number 1. The first child of a node, x,
will have number x.1. Then-th brother ofx.1will have numberx.n. This means that each
successor version increases the length of the version number. While this system is simple to
implement, and while ancestor testing and common ancestor determination are trivial, this
scheme is never used. This is because version trees tend to have many long chains, and out-
line numbers grow linearly in the length of a chain.
The second alternative can be called reverse outline numbering. In this system, the first
child of a node xwill have numberx+1. The first sibling ofx+1will have number(x+1).1.
Under these rules, further siblings will be numbered x+1.1.1, and so on. In this system, suc-
cessors are numbered sequentially, solving the problem of long identifiers, but any large
number of alternatives recreates the problem.
