Optimal versioning of objects

The purpose of versioning is to reconstruct any past state of an object class. The authors show that access to any past version is possible in almost constant time, while the space used is only linear to the number of changes occurring in the class evolution. As a result, versioning with fast reconstruction can be supported in an object-oriented environment without using excessive space requirements. It is also proved that the solution is optimal among all approaches that use the same space limitations. A crucial characteristic of the results is that they can be easily implemented on a storage facility that uses a magnetic disk and an optical disk