Relative serializability (extended abstract): an approach for relaxing the atomicity of transactions

Reviewer: William Campbell McGee

The relative atomicity model of transaction processing is a technique for exploiting knowledge of application semantics to increase the number of correct schedules that are possible with a given set of transactions, and thus to increase the concurrency of these transactions. In contrast to conventional or absolute atomicity, in which each transaction is an atomic unit, relative atomicity allows the user to partition transactions into multiple atomic units, and to provide a different partitioning of a given transaction for each of the other transactions. A schedule is correct if it conforms to the relative atomicity specification, or if it is conflict-equivalent to some schedule that does. This paper describes an efficient procedure for testing the correctness of schedules resulting from the application of the relative atomicity technique. A schedule that conforms to a set of relative atomicity specifications is called relatively atomic, and a schedule that is equivalent to some relatively atomic schedule is called relatively serializable. The paper defines a special kind of relatively serializable schedule, the relatively serial schedule, in which an interleaved operation and the operations of the atomic unit in which it is interleaved are mutually independent. From the standpoint of the main result of the paper, there does not appear to be any use for this special case. The authors use it to establish a new definition of “correct” schedule, namely a correct schedule is relatively atomic or relatively serial, but this use of correct is arbitrary: relatively atomic, relatively serial, and relatively serializable schedules are all correct. The relatively serial schedule appears to have been a stepping-stone for the authors in extending the related work of Farrag and O¨zsu [1] to reach their main result. It may also be useful in speeding up correctness enforcement procedures. The paper makes an important contribution to concurrency theory. It is not easy to follow, however, mainly because of the diversion created by the special case of relatively serial schedules. It would have been clearer to present relatively serializable schedules first, and then describe the special case. Examples of transaction systems, schedules, and graphs are given, but they are not well coordinated and they are not motivated by application semantics. No examples of incorrect schedules are given. The paper does not get into correctness procedures, but mentions that work on this subject is in progress.