COMP207 Assignment 1 – Transaction Management
Issue Date:Thursday, 31 October 2019
Submission Deadline:Thursday, 7 November 2019, 17:00
About This Assignment
This is the first of two assignments for COMP207. It is worth 10% of the total marks for this module. It consists of six questions, which you can find at the end of this document.
Submit your solutions to these questions in PDF format by the given submission deadline. Your solutions must be submitted on Vital (see the detailed submission instructions below).
Accuracy and relevance are more important in your answers, so don’t write large volumes in your submission, but do ensure that what you write covers what is asked for and keeps to the problem statement.
Submission Details
Please submit one PDF file with your solutions. Name your file as follows:
If your student ID is 12345678, then your file should be named: 12345678-Assignment-1.pdf.
Please submit only this file (no archives).
To act as your ‘signature’ for the assignment, at the top of your PDF document put your
Student ID number.
Your solutions must be submitted on Vital (see Vital for submission instructions).
The submission deadline for this assignment is Thursday, 7 November 2019, 17:00. Earlier submission is possible, but any submission after the deadline attracts the standard lateness penalties. Plagiarism and collusion guidelines will apply throughout the assignment submission. For details on late submissions, how to claim extenuating circumstances, etc., please see the undergraduate student handbook, which can be found at http://intranet.csc.liv.ac.uk/student/ug-handbook.pdf , or in Section 6 of the Code of Practice on Assessment.1
Assessment information at a glance
Assignment Number1 (of 2)
Assignment CirculatedThursday, 31 October 2019
Submission ModeElectronically on Vital
Purpose of AssessmentAssessment of knowledge of multi-user databases and the
need for relevant control to ensure database integrity
Submission necessary inN/A
order to satisfy module requirements?
1 https://www.liverpool.ac.uk/media/livacuk/tqsd/code-of-practice-on- assessment/code_of_practice_on_assessment.pdf
Question 1 (16 marks)
Consider the following two transactions (we omit the final ‘commit’ operation):
Transaction T1
read item(X );
X := X + 2;
write item(X ); read item(Y ); Y := Y * 3;
write item(Y );
commit;
Transaction T2
read item(Y );
Y := Y * 2;
write item(Y );
readitem(X );
X := X + 3;
write item(X ); commit;
Assume that transactions T1 and T2 use shared buffers (i.e., once a transaction writes X back to the buffer, the new value of X can be read by the other transaction, and similarly for Y ).
(a)Give serial schedules S1 for T1 ◊ T2 and S2for T2◊ T1.(1 mark per schedule)
(b)For each of the two schedules you gave in (a) S1 and S2, give the values of X and Y
after executing the schedule on a database with items X = 1 and Y = 2?
(2 marks per schedule)
(c)Give a serialisable schedule S3 for T1 and T2 that is not serial. Explain why your schedule S3 is serialisable.(5 marks)
(d)Give a schedule S4 for T1 and T2 that is not serialisable. Explain why S4 is not serialisable.(5 marks)
Question 2 (35 marks)
Consider the following schedules:
•S1 : r1(X ); r2(X ); r3(Y ); w1(X ); r2(Z); r2(Y ); w2(Y ); w1(Z)
•S2 : r1(X ); r1(Y ); w1(Y ); r3(Y ); r2(Y ); r2(Z); w3(U ); w2(Z); r4(Z); r4(U ); w4(U )
•S3 : w3(X ); r1(X ); w1(Y ); r2(Y ); w2(Z); r3(Z)
•S4 : r1(X ); r4(X ); r3(Y ); w4(Y ); r1(Y ); r2(Y ); r3(X ); r4(Y ); w1(X ); w2(Y )
•S5 : r1(X ); w1(Y ); r2(Y ); w2(Z); r3(Z); w3(X )
For each of these schedules, answer the following questions:
(a)What are the conflicts in the schedule?(2 marks per schedule)
(b)What is the precedence graph of the schedule?(2 marks per schedule)
(c)Is the schedule conflict-serialisable? Why? If the schedule is conflict-serialisable, give a conflict-equivalent serial schedule.(3 marks per schedule)
(a)
Question 3 (15 marks)
For each of the following schedules, determine if the schedule is:
i)Recoverable
ii)Cascadeless
iii)Strict
(a) S1 : r1(X ); r2(X ); w2(X ); w1(X); a2; c1(3 marks)
(b) S2 : r1(X ); r2(X ); w2(X ); w1(X); c2; c1(3 marks)
(c) S3 : r1(X ); w1(X ); r2(X ); w1(X); c2; c1(3 marks)
(d) S4 : r1(X ); w1(X ); r2(X ); w1(X); a2; c1(3 marks)
(e) S5 : r1(X ); r2(X ); w2(X ); c2; w1(X); c1; r3(X); c3(3 marks)
Question 4 (18 marks)
For each of the following sequences of operations, simulate its execution until it finishes or cannot proceed. If the execution cannot proceed, explain why.
For each step, indicate which of the two transactions T1 and T2 holds which type of lock on X
and Y.
Note. Each schedule spans two lines of text.
(a) S1 : sl1(X ); r1(X ); ul1(Y ); r1(Y ); sl2(Y ); r2(Y ); sl2(X ); r2(X ); u2(X ); u2(Y );
xl1(Y ); w1(Y ); u1(Y ); u1(X )(6 marks)
(b) S2 : sl1(X ); r1(X ); sl2(Y ); r2(Y ); ul1(Y ); r1(Y ); sl2(X ); r2(X ); u2(X ); u2(Y );
xl1(Y ); w1(Y ); u1(Y ); u1(X )(6 marks)
(c) S3 : sl2(Y ); r2(Y ); sl1(X ); r1(X ); ul1(Y ); r1(Y ); xl1(Y ); w1(Y ); u1(Y ); u1(X );
sl2(X ); r2(X ); u2(X ); u2(Y )(6 marks)
Question 5 (10 marks)
For each of the following schedules, determine if the schedule is allowed by 2PL or not and explain your reasons for each schedule.
Note. Each schedule spans two lines of text.
(a) S1: l1(X ); r1(X ); w1(X ); l1(Y ); u1(X ); l2(X ); r2(X ); r1(X ); w1(Y ); u1(Y ); l2(Y ); r2(Y );
w2(X ); w2(Y ); u2(X ); u2(Y )(2 marks)
(b) S2: l1(X ); l1(Y ); r1(X ); w1(X ); u1(X ); l2(X ); r2(X ); r1(Y ); w1(Y ); u1(Y ); l2(Y ); r2(Y );
w2(X ); u2(X ); w2(Y ); u2(Y )(2 marks)
(c) S3: l1(X ); r1(X ); w1(X ); u1(X ); l2(X ); r2(X ); l1(Y ); r1(Y ); w1(Y ); u1(Y ); l2(Y ); r2(Y );
w2(X ); w2(Y ); u2(X ); u2(Y )(2 marks)
(d) S4: l1(X ); r1(X ); w1(X ); u1(X ); l1(Y ); r1(Y ); w1(Y ); u1(Y ); l2(X ); r2(X ); w2(X ); u2(X );
l2(Y ); r2(Y ); w2(Y ); u2(Y )(2 marks)
(e) S5: l1(X ); r1(X ); w1(X ); l1(Y ); u1(X ); r1(Y ); w1(Y ); u1(Y ); l2(X ); r2(X ); w2(X ); l2(Y );
u2(X ); r2(Y ); w2(Y ); u2(Y )(2 marks)
Question 6 (6 marks)
Examine the schedule given below. There are three transactions, T1, T2 and T3. Again, assume that the transactions use shared buffers.
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 commit operation.
Assume that the undo/redo algorithm with simple checkpoints is used and that the log records up to now are on disk.
Determine what recovery is needed for each of the transactions T1, T2 and T3 if the system crashes with immediate effect at time t = 13 (at the end of line 13 but before the start of line 14).
(2 marks per transaction)
Time (t)
Transaction T1
Transaction T2
Transaction T3
0
Start_transaction
1
read_item (Y )
2
Y := Y + 1
3
Start_transaction
4
read_item (X )
5
X := X + 1
6
write_item (Y )
7
commit
8
Start_transaction
9
read_item (Y )
10
read_item (X )
11
Y := Y + X
12
write_item (Y )
13
commit
14
read_item (Y )
15
Y := Y + X
16
write_item (X )
17
checkpoint
18
commit
Reviews
There are no reviews yet.