Serial schedule: no interleaving of transactions

Serial schedule: no interleaving of transactions

• Serial schedule: no interleaving of transactions

• S1, S2 are conflict equivalent schedules if S1 transforms into S2 by swaps on non-conflicting actions.

• A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

P(S1) acyclic  S1 conflict serializable

• P(S1) acyclic  S1 conflict serializable

Example: Tj Ti

• Example: Tj Ti

• Wj(A)

• ri(A)

• Commit Ti

• Abort Tj

Example: Tj Ti

• Example: Tj Ti

• Wj(A)

• ri(A)

• Commit Ti

• Abort Tj

Example: Tj Ti

• Example: Tj Ti

• Wj(A)

• ri(A)

• Commit Ti

• Abort Tj

Example: Tj Ti

• Example: Tj Ti

• Wj(A)

• ri(A)

• wi(B)

• Abort Tj

• [Commit Ti]

Example: Tj Ti

• Example: Tj Ti

• wj(A)

• ri(A)

• wi(B)

• Abort Tj

• [Commit Ti]

Example: Tj Ti

• Example: Tj Ti

• Wj(A)

• ri(A)

• wi(B)

• Abort Tj

• [Commit Ti]

• Key Observation:

• Schedule is conflict serializable,

• Yet not “recoverable”.

Need to make “final’ decision for each transaction:

• Need to make “final’ decision for each transaction:

• commit decision - system guarantees transaction will or has completed, no matter what (final effect will stick)
• abort decision - system guarantees transaction will or has been rolled back
• (has no effect)

Ci - transaction Ti commits

• Ci - transaction Ti commits

• Ai - transaction Ti aborts

Ti reads from Tj in S (denoted as Tj STi) if

• Ti reads from Tj in S (denoted as Tj STi) if

• (1) wj(A)

• (2) aj

• (3) If wj(A)

• ak

Intuition : A schedule S is recoverable, if transactions only commit after all transactions they read from have already been committed first.

• Intuition : A schedule S is recoverable, if transactions only commit after all transactions they read from have already been committed first.

• Formal :

• Schedule S is recoverable if

• whenever Tj S Ti and j  i and Ci  S

• then Cj

Note: in transactions, reads and writes precede commit or abort

• Note: in transactions, reads and writes precede commit or abort

•  If Ci  Ti, then ri(A) < Ci

• wi(A) < Ci

•  If Ai  Ti, then ri(A) < Ai

• wi(A) < Ai

• Another rule:

• at most one Ci or Ai per transaction

Tj Ti

• Tj Ti

• Wj(A)

• Cj

• uj(A)

• ri(A)

S is recoverable if each transaction commits only after all transactions from which it read have committed.

• S is recoverable if each transaction commits only after all transactions from which it read have committed.

• S avoids cascading rollback if each transaction may read only those values written by committed transactions.

• S is strict if each transaction may read and write only items previously written by committed transactions.

S is recoverable if each transaction commits only after all transactions from which it read have committed.

• S is recoverable if each transaction commits only after all transactions from which it read have committed.

• Allows dirty read

• S avoids cascading rollback if each transaction may read only those values written by committed transactions.

• Disallows dirty read

• S is strict if each transaction may read and write only items previously written by committed transactions.

Types of schedules:

• Types of schedules:

Recoverable:

• Recoverable:

• w1(A) w1(B) w2(A) r2(B) c1 c2

• Avoids Cascading Rollback:

• w1(A) w1(B) w2(A) c1 r2(B) c2

• Strict:

• w1(A) w1(B) c1 w2(A) r2(B) c2

Recoverable and serializable:

• Recoverable and serializable:

• w1(A) w1(B) w2(A) r2(B) c1 c2

• Recoverable and not serializable:

• w2(A) w1(B) w1(A) r2(B) c1 c2

• Not recoverable yet serializable:

• w1(A) w1(B) w2(A) r2(B) c2 c1

• Every STRICT schedule is serializable.

• Every STRICT schedule is ACR (and thus recoverable).

Recoverable and serializable:

• Recoverable and serializable:

• w1(A) w1(B) w2(A) r2(B) c1 c2

• Recoverable and not serializable:

• w2(A) w1(B) w1(A) r2(B) c1 c2

• Not recoverable yet serializable:

• w1(A) w1(B) w2(A) r2(B) c2 c1

Recoverable and serializable:

• Recoverable and serializable:

• w1(A) w1(B) w2(A) r2(B) c1 c2

• Recoverable and not serializable:

• w2(A) w1(B) w1(A) r2(B) c1 c2

• Not recoverable yet serializable:

• w1(A) w1(B) w2(A) r2(B) c2 c1

• Every STRICT schedule is serializable.

• Every STRICT schedule is ACR (and thus recoverable).

Recoverable and serializable:

• Recoverable and serializable:

• w1(A) w1(B) w2(A) r2(B) c1 c2

• Recoverable and not serializable:

• w2(A) w1(B) w1(A) r2(B) c1 c2

• Not recoverable yet serializable:

• w1(A) w1(B) w2(A) r2(B) c2 c1

• Not recoverable and not serializable:

• w2(A) w1(B) w1(A) r2(B) c2 c1

0. Start T1.

• 0. Start T1.
• 1. L1(A)
• 2. R1(A)
• 3. W1(A)
• 4. O1(A)
• 5. Start T2.
• 6. L2(C)
• 7. L1(B)
• 8. U1(A)
• 9. L2(A)
• 10. W1(B)
• 11. Commit T1
• 12. R2(A)
• 13. W2(C)
• 14. U1(B)
• 15. Commit T2
• 16. U2(A)
• 17. U2(C)