Assignment 1: Transaction management and concurrency control

DEADLINE: 3 pm, Friday 11th November 2011

For the first practical assignment you are asked to complete the following exercises. Be as complete as possible, and add a justification for your answers. Yes or no answers are not acceptable.

Exercise 1 (30 marks)

Determine if the schedules below are conflict serialisable by drawing the precedence graph. If so, identify an equivalent serial schedule, otherwise explain why not. When drawing the precedence graph show all the edges, even if redundant.

S1: r1(X); w1(X); r1(Y); r2(X); w3(Y); r2(Z); r4(Y); r4(W); w4(W); r2(W);

S2: r1(X); r2(Y); w1(Y); w2(Z); r3(Z); w3(X);

S3: r1(X); r2(X); r1(Y); r2(Y); r3(X); r4(Y); w1(X); w2(Y);

Exercise 2 (20 marks)

For each of the following schedules indicate if it is recoverable and/or conflict serialisable.

Sa :  w1(X); w2(Y); w3(Z); c1; r3(X); c2; r3(Y); c3;

Sb :  w1(X); w2(Y); w3(Z); r3(X); c2; r3(Y); c3; c1;

Sc :  r1(X); w2(X); w2(Y); c2; r1(Y); c1;

Sd :  w1(X); w1(Y); r2(X); w2(Y); a2; w1(Z); c1; r3(Y); w3(Z); c3;

Exercise 3 (10 marks)

Suppose to have a DBMS using basic timestamp based concurrency control, and two transactions, T1, and T2 with timestamp 1 and 3 respectively.

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.

Try to execute the following schedule in the order shown.

r1(X); w1(X); r2(X); r2(Y); w1(Y); w2(X);

What is the outcome of the transactions?

Exercise 4 (20 marks)

Examine the schedule given below. There are three transactions, T1, T2, and T3. Initially, the value of X = 1 and Y = 2. The assignments happen within the local memory space of the transactions and the effects of these assignments are not reflected in the database until the write_item operation. Assume that the operations happen instantaneously, so there is no delay on the execution of an operation in the schedule.

a. Show the undo/redo log file entries that would be generated by this execution. For each log entry, indicate what line in the schedule given above generates it. Use for the log the following notation, similar to the one used in the lecture.

b. Assume that the undo/redo algorithm with checkpoints is used. The database crashes immediately after statement 7. Assume that the log records up to now are on disk.

    1. What transactions would have to be rolled back?

    2. What transactions would need to be redone.

c. Whilst we maintain the assumption that the undo/redo algorithm with checkpoints is being used, let us now assume that the database crashes just after statement 17. Assume that all the log records until this point are on disk.

    1.What transactions would have to be rolled back?

    2.What transactions would have to be redone?

Exercise 5 (20 marks)

Consider the following two transactions T1 and T2.

T1 = w1(Z); r1(X); w1(X); r1(Y); w1(Y);

T2 = r2(Y); w2(Y); r2(X); w2(X);

Assume that the scheduler in the DBMS performs only exclusive locking and no shared locks. For each of the following two instances of transactions T1 and T2  annotated with lock and unlock operations, determine whether the transactions:

    a.obey the two phase locking protocol;

    b.result in a conflict serialisable schedule;

    c.result in a strict schedule;

    d.may result in deadlock.

Case 1

T1 = Lock (Y); Lock(Z); w1(Z); Lock(X); r1(X); w1(X); r1(Y); w1(Y); Commit; Unlock(X); Unlock(Z); Unlock(Y)
T2 = Lock(Y); r2(Y); w2(Y); Lock(X); r2(X); w2(X); Commit; Unlock(X); Unlock(Y)

Case 2

T1 = Lock (Z); Lock(X); r1(X); w1(Z); w1(X); Lock(Y); r1(Y); w1(Y); Unlock(X); Unlock(Z); Unlock(Y); Commit;
T2 = Lock(Y); r2(Y); w2(Y); Lock(X); r2(X); w2(X); Commit; Unlock(X); Unlock(Y)

Assignment submission

Assignments are handed in electronically through the departmental coursework submission system.  For technical problems with the submission site please email either Dr. Tamma or Mr Shield.

When submitting, check that you have adhered to the following list:

1. 1. The solution to the exercises is contained in one PDF file. Text files or MS Word files will not be marked.
   

2. 2. The naming convention for submitting the assignment is to name the file as: YourSurname-Assignment1.pdf
   

3. 3.  Your solution must not bear undue resemblance to anybody else's! Electronic checks for similarity will be performed on all submissions and instances of plagiarism will be severely dealt with. The rules on plagiarism and collusion are explicit: do not copy anything from anyone else’s, do not let anyone else copy from your assignment and do not hand in 'jointly developed' solutions.