Concurrency control

The aim of today’s tutorial is to complete our introduction to concurrency control techniques in preparation for Assignment 1.

Make sure you have completed the exercises in the previous tutorials before attempting the ones below.

Exercise 1

Consider the following table Books(name, price) and assume that the following values exist in the database:

(′Connolly′, 40); (′Elmasri′, 50); (′Garcia-Molina′, 60).

Consider the following two transactions:

T1: BEGIN TRANSACTION

S1: UPDATE Books SET price=22 WHERE name=’Connolly’ S2: INSERT INTO Books VALUES (’Date’, 0)
S3: UPDATE Books SET price=38 WHERE name=‘Connolly’
COMMIT;

T2: BEGIN TRANSACTION
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
S4: SELECT AVG(price) AS average-price FROM Books
COMMIT;

The two transactions above hit the DBMS roughly at the same time. What are the possible value(s) for the average price?

Exercise 2

Consider the following two transactions:

T1: read_item(X);
       read_item(Y);
       if X = 0 then Y := Y+1;
       write_item(Y);

T2: read_item(Y);
       read_item(X);
       if Y = 0 then X := X + 1;
       write_item(X);

Add the appropriate lock, and the unlock instructions to transactions T1 and T2 so that they satisfy the two-phase locking protocol. Determine if the execution of these transactions can result in a deadlock.

Additional exercise

To be completed during the lab session, or in your own time.

Consider the following schedule S that includes transactions T1, T2 and T3:

S = r2(Z); r2(Y); w2(Y); r3(Y); r3(Z); r1(X); w1(X); w3(Y); w3(Z); r2(X); r1(Y); w1(Y); w2(X);

Assume a clock with linear time points 0, 1, …, and that each operation takes only 1 time unit.
Assume also that the original read and write timestamps of all items are 0 and that each transaction timestamp corresponds to the time of its first operation in each schedule.

The basic timestamp ordering algorithm states:

1.  Transaction T issues a write_item(X) operation:

    (a) If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an younger transaction has already read the data item so abort and roll-back T and reject the operation.

    (b) If the condition in part (a) does not exist, then execute write_item(X) of T and set write_TS(X) to TS(T).

2.  Transaction T issues a read_item(X) operation:

    (a) If write_TS(X) > TS(T), then an younger transaction has already written to the data item so abort and roll-back T and reject the operation.

    (b) If write_TS(X) ≤ TS(T), then execute read_item(X) of T and set read_TS(X) to the larger of TS(T) and the current read_TS(X).

Apply the basic timestamp ordering algorithm to the schedule S and determine whether the algorithm will allow the execution of the schedule.