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) 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
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 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 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. 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.
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)
Dostları ilə paylaş: |