Schedules

• List of actions from a set of transactions

• Well-formed when the actions of a particular transaction T are in the same order they appear in T

• Complete schedule - contains an abort or commit action for every transaction that occurs in the schedule

• Serial schedule - the actions of different transactions aren't interleaved

Scheduling Transactions

• Serial schedule - schedule that doesn't interleave the actions of different transactions

• Serializable schedule - schedule that is equivalent to some serial execution of the transactions

Equivalent Schedules

• Schedules involving the same set of operations on the same data objects

• Schedules that leave database with state after executing them in any order

• And, for any database state, the effect (on the set of objects in the database) of executing the first schedule is identical to the effect of executing the second schedule

Conflict Serializable Schedules

2 schedules are conflict equivalent if:

• Involve the same actions of the same transactions

• Every pair of conflicting actions are ordered the same way
  Schedule S is conflict serializable if S is conflict equivalent to SOME serial schedule

How to Check?

Precedence graph (serializability graph)

• One node per transaction

• Edge from Ti to Tj if Ti has a conflicting action with Tj and Ti precedes Tj

Recoverable Schedule

A transaction T isn’t allowed to commit until all other transactions that wrote values that T read have committed

Cascading Aborts

Recoverable schedule that illustrates a cascaded abort

• T3 aborts, forcing T2 to abort, which then forces T1 to abort