BOUNDING THE EFFECTS OF COMPENSATION UNDER RELAXED MULTILEVEL SERIALIZABILITY

The multi-level transaction concept provides a powerful tool for struc turing activities in multidatabase systems. However, even multi-level serializability is sometimes too restrictive as a correctness criterio n, either because of very high concurrency requirements, or because of the practical difficulties of implementing a scheduler in actual prod uction environments. The extended multi-level transaction model presen ted in this paper supports higher concurrency in cases where higher le vel operations commute in one direction, but not in the other - i.e., when it is valid to interchange them when they occur in one order in a history, but not when they occur in the other order. We introduce a r elaxed correctness criterion based on allowing a bounded number of out of order conflicts at each level in the multi-level framework, where the bound can be different for different levels. Finally we discuss th e properties of compensation in this framework, developing a theory of compensation which depends only on the semantics of the operations an d not on the particular state of the database. We illustrate the use o f these concepts in the context of a particular class of practical app lications.