retagged by
17,326 views
29 votes
29 votes

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?

  1. I only
  2. II only
  3. Both I and II
  4. Neither I nor II
retagged by

5 Answers

Best answer
48 votes
48 votes
  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

edited by
11 votes
11 votes

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

11 votes
11 votes

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.

edited by
9 votes
9 votes

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)

Answer:

Related questions

18 votes
18 votes
3 answers
1
39 votes
39 votes
5 answers
3
Arjun asked Feb 7, 2019
27,180 views
A relational database contains two tables Student and Performance as shown below:$$\overset{\text{Table: student}}{\begin{array}{|l|l|} \hline \text{Roll_no} & \text{Stud...
32 votes
32 votes
2 answers
4
Arjun asked Feb 7, 2019
14,150 views
Consider the following relations $P(X,Y,Z), Q(X,Y,T)$ and $R(Y,V)$.$$\overset{\textbf{Table: P}}{\begin{array}{|l|l|l|} \hline \textbf{X} & \textbf{Y} & \textbf{Z} \\\hli...