Database transaction schedule


In the fields of databases and transaction processing, a schedule of a system is an abstract model to describe the order of executions in a set of transactions running in the system. Often it is a list of operations ordered by time, performed by a set of transactions that are executed together in the system. If the order in time between certain operations is not determined by the system, then a partial order is used. Examples of such operations are requesting a read operation, reading, writing, aborting, committing, requesting a lock, locking, etc. Often, only a subset of the transaction operation types are included in a schedule.
Schedules are fundamental concepts in database concurrency control theory. In practice, most general purpose database systems employ conflict-serializable and strict recoverable schedules.

Notation

Grid notation:
Operations :
  • R: The corresponding transaction "reads" object X. This is done so that it can modify the data during a "write" operation rather than merely overwrite it. When the schedule is represented as a list rather than a grid, the action is represented as where is a number corresponding to a specific transaction.
  • W: The corresponding transaction "writes" to object X. When the schedule is represented as a list rather than a grid, the action is represented as where is a number corresponding to a specific transaction.
  • Com.: This represents a "commit" operation in which the corresponding transaction has successfully completed its preceding actions, and has made all its changes permanent in the database.
Alternatively, a schedule can be represented with a directed acyclic graph in which there is an arc between each ordered pair of operations.

Example

The following is an example of a schedule:
T1T2T3
R
W
Com.
R
W
Com.
R
W
Com.

In this example, the columns represent the different transactions in the schedule D. Schedule D consists of three transactions T1, T2, T3. First T1 Reads and Writes to object X, and then Commits. Then T2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and Commits.
The schedule D above can be represented as list in the following way:
D = R1 W1 Com1 R2 W2 Com2 R3 W3 Com3

Duration and order of actions

Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as atomic, occurring at a point in time, without duration. Real executed operations always have some duration.
Operations of transactions in a schedule can interleave, but time orders between operations in each transaction must remain unchanged. The schedule is in partial order when the operations of transactions in a schedule interleave. The schedule is in total order when the operations of transactions in a schedule do not interleave.

Types of schedule

A complete schedule is one that contains either an abort ''' or commit action for each of its transactions. A transaction's last action is either to commit or abort. To maintain atomicity, a transaction must undo all its actions if it is aborted.

Serial

A schedule is serial if the executed transactions are non-interleaved.
Schedule D is an example of a serial schedule:
T1T2T3
R
W
Com.
R
W
Com.
R
W
Com.

Serializable

A schedule is serializable if it is equivalent to a serial schedule.
In schedule E, the order in which the actions of the transactions are executed is not the same as in D, but in the end, E gives the same result as D.
T1T2T3
R
R
R
W
W
W
Com.Com.Com.

Serializability is used to keep the data in the data item in a consistent state. It is the major criterion for the correctness of concurrent transactions' schedule, and thus supported in all general purpose database systems. Schedules that are not serializable are likely to generate erroneous outcomes; which can be extremely harmful.
If any specific order between some transactions is requested by an application, then it is enforced independently of the underlying serializability mechanisms. These mechanisms are typically indifferent to any specific order, and generate some unpredictable partial order that is typically compatible with multiple serial orders of these transactions.

Conflicting actions

Two actions are said to be in conflict if and only if all of the 3 following conditions are satisfied:
  1. The actions belong to different transactions.
  2. At least one of the actions is a write operation.
  3. The actions access the same object.
Equivalently, two actions are considered conflicting if and only if they are noncommutative. Equivalently, two actions are considered conflicting if and only if they are a read-write, write-read, or write-write conflict.
The following set of actions is conflicting:
  • R1, W2, W3
While the following sets of actions are not conflicting:
  • R1, R2, R3
  • R1, W2, R3
Reducing conflicts, such as through commutativity, enhances performance because conflicts are the fundamental cause of delays and aborts.
The conflict is materialized if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a lock on the operation's object, held by another transaction, or when writing to a transaction's temporary private workspace and materializing, copying to the database itself, upon commit; as long as a requested/issued conflicting operation is not executed upon the database itself, the conflict is non-materialized; non-materialized conflicts are not represented by an edge in the precedence graph.

Conflict equivalence

The schedules S1 and S2 are said to be conflict-equivalent if and only if both of the following two conditions are satisfied:
  1. Both schedules S1 and S2 involve the same set of transactions such that each transaction has the same actions in the same order.
  2. Both schedules have the same set of conflicting pairs. This is equivalent to requiring that all conflicting operations are in the same order in both schedules.
Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting operations while maintaining the order of actions for each transaction.
Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting adjacent operations with different transactions.

Conflict-serializable

A schedule is said to be conflict-serializable when the schedule is conflict-equivalent to one or more serial schedules.
Equivalently, a schedule is conflict-serializable if and only if its precedence graph is acyclic when only committed transactions are considered. Note that if the graph is defined to also include uncommitted transactions, then cycles involving uncommitted transactions may occur without conflict serializability violation.
The schedule K is conflict-equivalent to the serial schedule , but not .
Conflict serializability can be enforced by restarting any transaction within the cycle in the precedence graph, or by implementing two-phase locking, timestamp ordering, or serializable snapshot isolation.

View equivalence

Two schedules S1 and S2 are said to be view-equivalent when the following conditions are satisfied:
  1. If the transaction in S1 reads an initial value for object X, so does the same transaction in S2.
  2. If the transaction reads a value written by the transaction in S1, it must do so in S2.
  3. If the transaction in S1 does the final write for object X, so does the same transaction in S2.
Additionally, two view-equivalent schedules must involve the same set of transactions such that each transaction has the same actions in the same order.
In the example below, the schedules S1 and S2 are view-equivalent, but neither S1 nor S2 are view-equivalent to the schedule S3.
The conditions for S3 to be view-equivalent to S1 and S2 were not satisfied at the corresponding superscripts for the following reasons:
  1. Failed the first condition of view equivalence because T1 read the initial value for B in S1 and S2, but T2 read the initial value for B in S3.
  2. Failed the second condition of view equivalence because T2 read the value written by T1 for B in S1 and S2, but T1 read the value written by T2 for B in S3.
  3. Failed the third condition of view equivalence because T2 did the final write for B in S1 and S2, but T1 did the final write for B in S3.
To quickly analyze whether two schedules are view-equivalent, write both schedules as a list with each action's subscript representing which view-equivalence condition they match. The schedules are view equivalent if and only if all the actions have the same subscript in both schedules:
  • S1: R1initial read, W1, R1initial read, W1, Com1, R2written by T1, W2final write, R2written by T1, W2final write, Com2
  • S2: R1initial read, W1, R2written by T1, W2final write, R1initial read, W1, Com1, R2written by T1, W2final write, Com2
  • S3: R1initial read, W1, R2written by T1, W2final write, R2initial read, W2, R1written by T2, W1final write, Com1, Com2