GATE CSE 2019 | Question: 11

Question

Consider the following two statements about database transaction schedules:

1. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
2. Timestamp-ordering concurrency control protocol with Thomas’ Write Rule can generate view serializable schedules that are not conflict serializable

Which of the above statements is/are TRUE?

• A. I only
• B. II only
• C. Both I and II
• D. Neither I nor II

Answer 1

1. Strict $\text{2PL}$ allows only schedules whose precedence graph is acyclic i.e. schedule is Conflict Serial. In strict $\text{2PL}$, transactions do not release exclusive locks until the transaction has committed or aborted i.e. schedule is recoverable.
2. Time stamp ordering schedule with Thomas write rule generate View serial schedule with BLIND WRITE. Because of BLIND WRITE it won't be Conflict Serial.

So, Option C - both are true

Comments

@Rutuja Desai 

Timestamp ordering protocol guarantee conflict serializable schedules but say there exists  schedules which are not conflict serializable due to blind writes for example ,

$T1$	$T2$
$R(A)$
	$W(A)$
$W(A)$
$Committ$
	$Commit$

Now this schedule is not conflict serializable and it also not allowed by basic time stamp protocol. But this schedule is view serializable .

Now Thomas write rule says that if we ignore blind write conflict in time stamp based protocol then we will cover some view serializable schedules as well.

---

@Arjun @Kabir5454 @Lakshman Patel RJIT Sir edit necessary.

Point 1: It should be : "In STRICT $2PL$, transactions do not release exclusive locks until the transaction has committed or aborted i.e. schedule is recoverable."

Point 2 can be re-written as: “Timestamp-ordering concurrency control protocol with Thomas’ Write Rule ignores outdated writes. Thomas Write Rue is a bit flexible, and allows more no. of schedules than Timestamp-ordering concurrency control protocol. Hence it can generate View serial schedules for those non-conflict serializable schedules with the testing of BLIND WRITE. Because of BLIND WRITE some of the non-conflict serializable schedules may be view-equivalent.”

---

@Digvijay Pandey Sir I think this statement  “Because of BLIND WRITE it won't be Conflict Serial.”  should be “Because of BLIND WRITE sometimes it won’t be conflict serial but it may be view serial.”

Answer 2

A strict 2PL protocol has both a growing phase and a shrinking phase. In the growing phase, it acquires locks; in the shrinking phase, it only releases shared locks. The exclusive locks are released after the transaction commits.

=> There can be no dirty reads by other transactions. 

=> No cascading rollbacks or aborts.

=> recoverable.

---

---

The basic timestamp ordering protocol enforces conflict serialisability.

Thomas write rule enforces view serialisability. It does so by ignoring the blind writes. The blind writes are meaningless operations that prevent a serial to be conflict serialisable; but by ignoring them, we can make them view serialisable.

 

Hence, both are true.

Option C

Comments

“but by ignoring them” do you mean rollback the blind write or what ?

Answer 3

Answer: (C)

 

In strict 2PL, a transaction T does not release any of its exclusive (write) locks until after it commits or aborts.

Hence, no other transaction can read or write an item that is written by T unless T has committed, leading to a strict schedule for recoverability.

-> (Ref: Fundamentals of Database Systems by Elmasri and Navathe, 7e Pg. No. 789)

By ignoring the OUTDATED write, Thomas write rule allows schedules that are not conflict serializable but are nevertheless correct.

Those non-conflict-serializable schedules allowed satisfy the definition of view serializable schedules.

-> (Ref: Database System Concepts by Silberschatch, Korth and Sudarshan, 6e Pg No. 686)

 

PROOF  OF STATEMENT 2 :

Eg:

T1                    T2                         T3

r(a)      

                       w(a) 

                                                    r(a)

w(a)

                                                     w(a)

This Schedule Is View Serializable but not Conflict Serializable . CHECK IT.

It Is View Serializable To T1T2T3, with T2 having a Blind Write.

 

NOW SOLVING BY THOMAS WRITE RULE:

-> By TimeStamp Ordering , Correct Order Is : T1T2T3.

-> But CONFLICT w2(a)r1(a) is not in Timestamp order.

-> But Thomas write rule can ignore it as this is Outdated Write. So w1(a) can be completely IGNORED from The Transaction .

-> Other Remaining Conflicts (with w1(a) discarded) are r1(a)w3(a), w2(a)r3(a),w2(a)w3(a) which are in Correct Timestamp Order.

-> Thus after ignoring 1 OUTDATED WRITE , THOMAS WRITE RULE ACCEPTED A SCHEDULE WHICH IS VIEW SERIALIZABLE AND NOT CONFLICT SERIALIZABLE.

Comments

Read Time Stamp(A) changed to 3 whenever T$_3$.R(A)

So W(A) should be rejected even in Thomos write rule.

---

Best suited example and the line ` Thus after ignoring 1 OUTDATED WRITE , THOMAS WRITE RULE ACCEPTED A SCHEDULE WHICH IS VIEW SERIALIZABLE AND NOT CONFLICT SERIALIZABLE.`  clears the meaning of the statement.

 @Kabir5454 ‘s example is not convincing, as the 3 conditions (initial read, final write, updated read must be same to any serial schedule) must be met. But his example is not view equivalent to any serial schedule. 

Answer 4

In strict 2PL, a transaction T does not release any of its exclusive (write) locks until after it commits or aborts.
Hence, no other transaction can read or write an item that is written by T unless T has committed, leading to a strict schedule for recoverability.
(Ref: Fundamentals of Database Systems by Elmasri and Navathe, 7e Pg. No. 789)

By ignoring the write, Thomas write rule allows schedules that are not conflict serializable but are nevertheless correct.
Those non-conflict-serializable schedules allowed satisfy the definition of view serializable schedules.
(Ref: Database System Concepts by Silberschatch, Korth and Sudarshan, 6e Pg No. 686)