Path: utzoo!attcan!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!crackers!jjmhome!smds!rh
From: rh@smds.UUCP (Richard Harter)
Newsgroups: comp.software-eng
Subject: Re: style guides and testing tools comments and requests
Summary: Sometimes simplest works very well
Message-ID: <280@smds.UUCP>
Date: 21 Dec 90 09:38:27 GMT
References: <1990Dec15.071555.14971@nixtdc.uucp>
Organization: SMDS Inc., Concord, MA
Lines: 38

In article <1990Dec15.071555.14971@nixtdc.uucp>, dt@nixtdc.uucp (David Tilbrook) writes:

> Request: I am currently doing a requirements analysis of a
>      versioning system.  One aspect of this research is the
>      problems inherent in using a write-once storage system.  For
>      obvious reasons, using the change recording mechanisms used
>      by either SCCS or RCS would not be satisfactory to anyone
>      other than a WORM salesperson (would consume disks at an
>      unaffordable rate).  So system should probably use some sort
>      of mechanism that did not rewrite existing information ...
>      however, the system must retrieve any version of the source
>      in equal time (like SCCS but unlike RCS).  Any comments?  Any
>      interest?

Surprisingly enough a sequential update system, which incorrect rumor
credits with terrible performance, will do what you want quite nicely.
The general scheme runs as follows:  Store the original file with
(implictly) numbered records in order.  Store the deltas as units.
The only trick is that each new number gets the next insertion number
as an ID.  Inserts are stated as inserts after previous record n,
deletes are stated as deletes of previous records using absolute
record numbers.  You can then rebuild any prior version using a pick
and choose strategy.

At first sight it would seem that this would be expensive.  However,
_if you arrange the processing correctly_, each record is only accessed
once -- the cost is equivalent to the cost for using the SCCS scheme.

The reason that sequential update reconstruction has a bad reputation
is that it is very expensive if you rebuild each intermediate version
as a complete file -- the cost being that a record is moved many times,
once for each intermediate version.  However the actual cost need only
be proportional to the total number of records.
-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.