Correctness Criteria Beyond Serializability
Abstract
A transaction is a logical unit of work that includes one or more database access operations such as insertion, deletion, modification, and retrieval [8]. A schedule (or history) S of n transactions T1,...,Tn is an ordering of the transactions that satisfies the following two conditions: (i) the operations of Ti (i = 1,...,n) in S must occur in the same order in which they appear in Ti, and (ii) operations from Tj (j 6¼ i) may be interleaved with Ti’s operations in S. A schedule S is serial if for every two transactions Ti and Tj that appear in S, either all operations of Ti appear before all operations of Tj, or vice versa. Otherwise, the schedule is called nonserial or concurrent. Non-serial schedules of transactions may lead to concurrency problems such as lost update, dirty read, and unrepeatable read. For instance, the lost update problem occurs whenever two transactions, while attempting to modify a data item, both read the item’s old value before either of them writes the item’s new value [2]. The simplest way for controlling concurrency is to allow only serial schedules. However, with no concurrency, database systems may make poor use of their resources and hence, be inefficient, resulting in smaller transaction execution rate for example. To broaden the class of allowable transaction schedules, serializability has been proposed as the major correctness criterion for concurrency control [7,11]. Serializability ensures that a concurrent schedule of transactions is equivalent to some serial schedule of the same transactions [12]. While serializability has been successfully used in traditional database applications, e.g., airline reservations and banking, it has been proven to be restrictive and hardly applicable in advanced applications such as Computer- Aided Design (CAD), Computer-Aided Manufacturing (CAM), office automation, and multidatabases. These applications introduced new requirements that either prevent the use of serializability (e.g., violation of local autonomy in multidatabases) or make the use of serializability inefficient (e.g., long-running transactions in CAD/CAM applications). These limitations have motivated the introduction of more flexible correctness criteria that go beyond the traditional serializability.
Keywords
Concurrency control, Preserving database consistency
Date of this Version
2009
Comments
Encyclopedia of Database Systems 2009, Part 3, 501-506