8. The following transactions execute under a optimistic concurrency control: •

Question

8. The following transactions execute under a optimistic concurrency control:

• T1: ReadSet:{B, E}, WriteSet: {C, E, F }
• T2: ReadSet: {F}, WriteSet: {A,B}
• T3: ReadSet: {A}, WriteSet:{C}

• T4: ReadSet: {A,C}, WriteSet: {B,D}

• T5: ReadSet: {F }, WriteSet: {C, D} Consider the following sequence of events:

1. T1 initiates Read phase
2. T2 initiates Read phase
3. T2 initiates Validation phase 4. T1 initiates Validation phase 5. T3 initiates Read phase
6. T2 completes Validation phase 7. T4 initiates Read phase
8. T5 initiates Read phase
9. T4 initiates Validation phase

10. T1 completes Validation phase 11. T5 Initiates Validation Phase 12. T3 Initiates Validation Phase 13. T4 completes Validation phase 14. T3 completes Validation phase 15. T5 completes Validation phase

Assume that for each transaction the Read phase ends exactly before the beginning of the validation phase of that transaction. For instance, ‘4 T1 initiates Validation phase’ implicitly means that T1 completes the Read phase before this event and after the previous event (event #3). And for each transaction the Write phase is completed immediately after the completion of the validation phase of that transaction (if the validations is successful). For instance, ‘10 T1 completes Valida- tion phase’ implicitly means that T1 completes the Write phase immediately after completing the Validation phase of T1 and before the beginning of the next event (event #11).

Which of these five transactions (T1, T2, T3, T4 and T5) validate successfully? For the transactions failed to validate explain the reason.

Explanation / Answer

Solution:

======================================================================

Transaction T2 is successfully validated.

The read set of transaction T2 is - {F} and none of the other transactions are in validation phase before this transaction, the transaction T2 is successfully validated.

Transaction T1 is not successfully validated, because the read set of T1 - { B,E} has B, which is present in the write set of T2 - {A,B}, whose validation phase has started before transaction T1. Hence there is a overlap and transaction T1 can't be successfully validated.

The read set of transaction T3 is - {A} and transactions T1,T2 , T4 and T5 are in validation phase before this transaction. The write set of transaction T2 - {A, B} has A which is common in read set of T3. Hence there is a overlap and transaction T3 can't be successfully validated.

The read set of transaction T4 is -{A, C} and transaction T1 is in validation phase before this transaction. The write set of transaction T1 -{C,E,F} has C in common in read set of T3. Hence there is an overlap and transaction T4 can't be successfully validated.

The read set of transaction T5 is - {F} and transactions T1 and T4 are in validation phase before this transaction. The write set of T1 is - {C,E,F} has F in common in read set of T5. Hence there is an overlap and transaction T5 can't b successfully validated.

============================================================================

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.