Formal aspects of optimistic concurrency control in a multiple version database system

摘要

Formal aspects of optimistic concurrency control in a multiple version database system are discussed. It is distinguished between element-optimistic and set-optimistic methods. In an element-optimistic method the unit of scheduling for the concurrency control is one action/transaction, while in a set-optimistic method a set of transactions is scheduled. The underlying decision problems of serializability are defined and shown to be NP-complete in a model, which is typical for most modern transaction oriented database management systems. Therefore it is most probable, that both optimistic concurrency control types cannot be implemented efficiently in the general case.