Using semantic knowledge of transactions to increase concurrency

Abstract

When the only information available about transactions is syntactic information, serializability is the main correctness criterion for concurrency control. Serializability requires that the execution of each transaction must appear to every other transaction as a single atomic step (i.e., the execution of the transaction cannot be interrupted by other transactions). Many researchers, however, have realized that this requirement is unnecessarily strong for many applications and can significantly increase transaction response time. To overcome this problem, a new approach for controlling concurrency that exploits the semantic information available about transactions to allow controlled nonserializable interleavings has recently been proposed. This approach is useful when the cost of producing only serializable interleavings is unacceptably high. The main drawback of the approach is the extra overhead incurred by utilizing the semantic information. We examine this new approach in this paper and discuss its strengths and weaknesses. We introduce a new formalization for the concurrency control problem when semantic information is available about the transactions. This semantic information takes the form of transaction types, transaction steps, and transaction break-points. We define a new class of “safe” schedules called relatively consistent (RC) schedules. This class contains serializable as well as nonserializable schedules. We prove that the execution of an RC schedule cannot violate consistency and propose a new concurrency control mechanism that produces only RC schedules. Our mechanism assumes fewer restrictions on the interleavings among transactions than previously introduced semantic-based mechanisms.