Database Systems: Schedules and Serial Schedules

Schedules

• A schedule is a history of computations showing all the events of interest.
• A schedule or history of T1...Tn has operations of T1…Tn.

Event of Interest

• Events of interest: Read, Write, Commit, Abort in Ti
• Abbreviations: ri, wi, ci, ai

Serial Schedule

• A serial schedule is a schedule that does not interleave the actions of different transactions.
• Transactions are wholly before or after others.
• Serial schedules are correct (assuming each transaction is correct).

Concurrent Schedule

• A concurrent schedule is good if it is equivalent to a serial schedule.
• A bad concurrent schedule may lead to an inconsistent state.

Equivalent Schedules

• Equivalent schedules: 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.

Serializable Schedule

• A serializable schedule is a schedule whose effect on any consistent database instance is guaranteed to be identical to that of some complete serial schedule over the set of committed transactions.
• Only consider read and write operations in serializability analysis.

View Equivalence

• Two schedules are view equivalent if for each data item, the item is read and updated by the same sequence of transactions in both schedules.
• A schedule S is view serializable if it is view equivalent to a serial schedule.

Conflict Serializability

• Conflict Serializable => View Serializable
• Every conflict serializable schedule is view serializable but vice versa is not true.
• If a schedule S is view serializable but not conflict serializable S contains a blind write.

Recoverability

• A schedule S is recoverable if for each pair of transactions T1 and T2 in S such that T1 reads a data item previously written by T2, the commit operation of T2 appears before the commit operation of T1.

Concurrency Problems

• This problem occurs when two transactions that access the same database items have their operations interleaved in a way that makes the value of database items incorrect.
• This problem occurs when one transaction updates a database item and then the transaction fails for some reason.

Data Item Access

• Idea: Data items should be accessed in a mutually exclusive way.

Instruction Equivalence

• Instructions l1 and l2 are equivalent if they have the same effect.
• l1 = op(X), l2 = op(Y), X not equal to Y. => Yes
• l1 = read(Q), l2 = read(Q). => Yes
• l1 = read(Q), l2 = write(Q). => No
• l1 = write(Q), l2 = read(Q). => No
• l1 = write(Q), l2 = write(Q). => No

Conflict

• l1 and l2 are conflict if:
  • l1 and l2 are in different transactions.
  • l1 and l2 are on the same data item.
  • At least one of them is a write operation.

Conflict Equivalence

• If a schedule S can be transferred into a schedule S’ by a series of nonconflicting instructions, then S and S’ are conflict equivalent schedules.
• A schedule S is a conflict serializable if it is conflict equivalent to a serial schedule.

Considerations for Schedules

• For each data item Q if transaction T1 reads the initial value of Q in schedule S, then transaction T1 must also do the same in S’.
• For each data item, the same transaction reads the item both in S and S’.
• For each data item Q if transaction T1 executes read in schedule S and if that value was produced by write(Q) executed by transaction T2, then the similar case must be in S’.
• For each data item, the sequence of updates made by the transactions are same both in S and S’.
• For each data item Q if (any) transaction performs the final write operation in schedule S, then it must do the same in S’.