Solutions for Exercise no. 12

14.2 See the text in the book
Answer:
A: Lock and unlock instructions
 

T31	lock-S (A) read (A) lock-X (B) read (B) if A=0 then B = B+1 write (B) unlock (A) unlock (B)

 

T32	lock-S (B) read (B) lock-X (A) read (A) if B=0 then A = A+1 write (A) unlock (B) unlock (A)

B: Execution of these transactions can result in deadlock. For example, consider the following partial schedule.
 

T31	T32
lock-S (A)     read (A) lock-X (B)	lock-S (B) read (B)      lock-X (A)

The transactions are now deadlocked.

14.6 See the text in the book
Answer:
It is relatively simple to implement, imposes low rollback overhead because of cascadeless schedules, and usually allows an acceptable level of concurrency.

14.20 See the text in the book
Answer:
A schedule which is allowed in the two-phase locking protocol but not in the timestamp protocol is:
 

step	T0	T1	Precedence remarks
1 2 3 4 5 6 7 8 9	lock-S (A) read (A)     lock-S (B) read (B) unlock (A) unlock (B)	lock-X (B) write (B) unlock (B)	T1 ® T0

This schedule is not allowed in the timestamp protocol because at step 7, the W-timestamp of B is 1.

A schedule which is allowed in the timestamp protocol but not in the two-phase locking protocol is:
 

step	T0	T1	T2
1 2 3 4 5	write (A)   write (B)	write (A)   write (B)	write (A)

This schedule cannot have lock instructions added to make it legal under two-phase locking protocol because T1 must unlock (A) between steps 2 and 3, and must lock (B) between steps 4 and 5.
 

14.21 See the text in the book
Answer:

• Two-phase locking: Use for simple applications where a single granularity is acceptable. If there are large read-only transactions, multiversion protocols would do better. Also, if deadlocks must be avoided at all costs, the tree protocol would be preferable.
• Two-phase locking with multiple granularity locking: Use for an application mix where some applications access individual records and others access whole relations or substantial parts thereof. The drawback of two-phase locking mentioned above also apply to this one.
• Timestamp ordering: Use if the application demands a concurrent execution that is equivalent to a particular serial ordering say, the order of arrival), rather than any serial ordering. But conflicts are handled by rollback of transactions, rather than waiting, and schedules are not recoverable. To make them recoverable, additional overhead and increased response time have to be tolerated. Not suitable if there are long read-only transactions, since they will starve. Deadlocks are absent.

Validation: If the probability that two concurrently execution transactions conflict is low, this protocol can be used advantageously to get better concurrency and good response time with low overheads. Not suitable under high contention, when a lot of wasted work will be done.

14.26 See the text in the book
Answer:
The phantom phenomenon arises when, due to an insertion or deletion , two transaction logically conflict despite not locking any data items in common. The insertion case is described in the book. Deletion can also lead to this phenomenon. Suppose Ti deletes a tuple from a relation while Tj scans the relation. If Ti deletes the tuple and then Tj reads the relation, Ti should be serialized before Tj. Yet there is no tuple that both Ti and Tj conflict on.

An interpretation of 2PL as just locking the accessed tuples in a relation is incorrect. There is also an index or a relation data that has information about the tuples in the relation. This information is read by any transaction that scans the relation, and modified by transactions that update, or insert into or delete from the relation. Hence locking must also be performed on the index or relation data, and this will avoid the phantom phenomenon.