Database transaction schedule

Often it is a list of operations (actions) ordered by time, performed by a set of transactions that are executed together in the system.

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.

Grid notation: Operations (a.k.a., actions): Alternatively, a schedule can be represented with a directed acyclic graph (or DAG) in which there is an arc (i.e., directed edge) between each ordered pair of operations.

The schedule D above can be represented as list in the following way: D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3 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.

To maintain atomicity, a transaction must undo all its actions if it is aborted.

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 (e.g., when dealing with money within banks).

[1][2][3] If any specific order between some transactions is requested by an application, then it is enforced independently of the underlying serializability mechanisms.

The schedules S1 and S2 are said to be conflict-equivalent if and only if both of the following two conditions are satisfied: 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 (whether adjacent or not) while maintaining the order of actions for each transaction.

Equivalently, a schedule is conflict-serializable if and only if its precedence graph is acyclic when only committed transactions are considered.

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.

The schedule F is recoverable because T1 commits before T2, that makes the value read by T2 correct.

Schedule J is unrecoverable because T2 committed before T1 despite previously reading the value written by T1.

Cascading aborts avoidance is sufficient but not necessary for a schedule to be recoverable.