CHAPTER 17: solutions to homework 5.
Please let me know if you have
different thoughts about solutions and you can discuss them with me.
17.14 Change transaction T 2 in
Figure 17.2b to read:
read_item(X);
X:= X+M;
if X > 90 then exit
else write_item(X);
Answer:
The above condition does not change
the final outcome unless the initial value of X > 88.
The outcome, however, does obey the
implied consistency rule that X < 90, since the
value of X is not updated if it
becomes greater than 90.
17.15 Repeat Exercise 19.14 adding a
check in T 1 so that Y does not exceed 90.
Answer:
Let us take a look at 17.3(a) first
T1 T2
read_item(X);
X := X-N;
read_item(X); // T2
X := X+M; //T2
write_item(X);
read_item(Y);
if X > 90 then exit //T2
else write_item(X); //T2
Y :=
Y+N;
if
Y> 90 then exit
else write_item(Y);
The above condition does not change
the final outcome unless the initial value of X > 88 or
Y > 88. The outcome obeys the
implied consistency rule that X < 90 and Y < 90.
Let us take a look at 17.3(b) first
T1 T2
read_item(X);
X := X-N;
write_item(X);
read_item(X); // T2
X := X+M; //T2
if X > 90 then exit //T2
else write_item(X); //T2
read_item(Y);
Y :=
Y+N;
if Y> 90 then exit
else write_item(Y);
rollback T1
The above condition does not change
the final outcome unless the initial value of X > 88 or
Y > 88. The outcome obeys the
implied consistency rule that X < 90 and Y < 90.
17.16
Answer:
T 1
read_item(X);
X := X - N
write_item(X);
read_item(Y);
Y := Y
+ N;
write_item(Y);
commit T 1
T 2
read_item(X);
X := X + M;
write_item(X);
commit T 2
The transactions can be written as
follows using the shorthand notation:
T 1 : r
1 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ;
T 2 : r 2 (X); w 2 (X); C 2 ;
In general, given m transactions
with number of operations n1, n2, ..., nm, the number
of possible schedules is: (n1 + n2 +
... + nm)! / (n1! * n2! * ... * nm!), where ! is the
factorial function. You can double
check the formula by picking a math book.
In this case, m =2 and n1 = 5 and n2
= 3, so the number of possible
schedules is:
(5+3)! / (5! * 3!) = 8*7*6*5*4*3*2*1/
5*4*3*2*1*3*2*1 = 56.
Below are the 56 possible schedules,
and the type of each schedule:
S 1 : r 1 (X); w 1 (X); r 1 (Y); w 1
(Y); C 1 ; r 2 (X); w 2 (X); C 2 ; strict (and hence
cascadeless)
S 2 : r 1 (X); w 1 (X); r 1 (Y); w 1
(Y); r 2 (X); C 1 ; w 2 (X); C 2 ; recoverable
S 3 : r 1 (X); w 1 (X); r 1 (Y); w 1
(Y); r 2 (X); w 2 (X); C 1 ; C 2 ; recoverable
S 4 : r 1 (X); w 1 (X); r 1 (Y); w 1
(Y); r 2 (X); w 2 (X); C 2 ; C 1 ; non-recoverable
S 5 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 1 (Y); C 1 ; w 2 (X); C 2 ; recoverable
S 6 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 1 (Y); w 2 (X); C 1 ; C 2 ; recoverable
S 7 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 1 (Y); w 2 (X); C 2 ; C 1 ; non-recoverable
S 8 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 2 (X); w 1 (Y); C 1 ; C 2 ; recoverable
S 9 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 2 (X); w 1 (Y); C 2 ; C 1 ; non-recoverable
S 10 : r 1 (X); w 1 (X); r 1 (Y); r
2 (X); w 2 (X); C 2 ; w 1 (Y); C 1 ; non-recoverable
S 11 : r 1 (X); w 1 (X); r 2 (X); r 1
(Y); w 1 (Y); C 1 ; w 2 (X); C 2 ; recoverable
S 12 : r 1 (X); w 1 (X); r 2 (X); r
1 (Y); w 1 (Y); w 2 (X); C 1 ; C 2 ; recoverable
S 13 : r 1 (X); w 1 (X); r 2 (X); r
1 (Y); w 1 (Y); w 2 (X); C 2 ; C 1 ; non-recoverable
S 14 : r 1 (X); w 1 (X); r 2 (X); r
1 (Y); w 2 (X); w 1 (Y); C 1 ; C 2 ; recoverable
S 15 : r 1 (X); w 1 (X); r 2 (X); r
1 (Y); w 2 (X); w 1 (Y); C 2 ; C 1 ; non-recoverable
S 16 : r 1 (X); w 1 (X); r 2 (X); r
1 (Y); w 2 (X); C 2 ; w 1 (Y); C 1 ; non-recoverable
S 17 : r 1 (X); w 1 (X); r 2 (X); w
2 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 ; recoverable
S 18 : r 1 (X); w 1 (X); r 2 (X); w
2 (X); r 1 (Y); w 1 (Y); C 2 ; C 1 ; non-recoverable
S 19 : r 1 (X); w 1 (X); r 2 (X); w
2 (X); r 1 (Y); C 2 ; w 1 (Y); C 1 ; non-recoverable
S 20 : r 1 (X); w 1 (X); r 2 (X); w
2 (X); C 2 ; r 1 (Y); w 1 (Y); C 1 ; non-recoverable
S 21 : r 1 (X); r 2 (X); w 1 (X); r
1 (Y); w 1 (Y); C 1 ; w 2 (X); C 2 ; strict (and hence
cascadeless)
S
22 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); w 2 (X); C 1 ; C 2 ;
cascadeless
S
23 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); w 2 (X); C 2 ; C 1 ;
cascadeless
S
24 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 2 (X); w 1 (Y); C 1 ; C 2 ;
cascadeless
S
25 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 2 (X); w 1 (Y); C 2 ; C 1 ;
cascadeless
S
26 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 2 (X); C 2 ; w 1 (Y); C 1 ;
cascadeless
S
27 : r 1 (X); r 2 (X); w 1 (X); w 2 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 ;
cascadeless
S
28 : r 1 (X); r 2 (X); w 1 (X); w 2 (X); r 1 (Y); w 1 (Y); C 2 ; C 1 ;
cascadeless
S
29 : r 1 (X); r 2 (X); w 1 (X); w 2 (X); r 1 (Y); C 2 ; w 1 (Y); C 1 ;
cascadeless
S
30 : r 1 (X); r 2 (X); w 1 (X); w 2 (X); C 2 ; r 1 (Y); w 1 (Y); C 1 ;
cascadeless
S
31 : r 1 (X); r 2 (X); w 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 ;
cascadeless
S
32 : r 1 (X); r 2 (X); w 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 2 ; C 1 ;
cascadeless
S
33 : r 1 (X); r 2 (X); w 2 (X); w 1 (X); r 1 (Y); C 2 ; w 1 (Y); C 1 ;
cascadeless
S
34 : r 1 (X); r 2 (X); w 2 (X); w 1 (X); C 2 ; r 1 (Y); w 1 (Y); C 1 ;
cascadeless
S 35 : r 1 (X); r 2 (X); w 2 (X); C
2 ; w 1 (X); r 1 (Y); w 1 (Y); C 1 ; strict (and hence
cascadeless)
S 36 : r 2 (X); r 1 (X); w 1 (X); r
1 (Y); w 1 (Y); C 1 ; w 2 (X); C 2 ; strict (and hence
cascadeless)
S
37 : r 2 (X); r 1 (X); w 1 (X); r 1 (Y); w 1 (Y); w 2 (X); C 1 ; C 2 ;
cascadeless
S
38 : r 2 (X); r 1 (X); w 1 (X); r 1 (Y); w 1 (Y); w 2 (X); C 2 ; C 1 ;
cascadeless
S
39 : r 2 (X); r 1 (X); w 1 (X); r 1 (Y); w 2 (X); w 1 (Y); C 1 ; C 2 ;
cascadeless
S
40 : r 2 (X); r 1 (X); w 1 (X); r 1 (Y); w 2 (X); w 1 (Y); C 2 ; C 1 ;
cascadeless
S
41 : r 2 (X); r 1 (X); w 1 (X); r 1 (Y); w 2 (X); C 2 ; w 1 (Y); C 1 ;
cascadeless
S
42 : r 2 (X); r 1 (X); w 1 (X); w 2 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 ;
cascadeless
S
43 : r 2 (X); r 1 (X); w 1 (X); w 2 (X); r 1 (Y); w 1 (Y); C 2 ; C 1 ;
cascadeless
S
44 : r 2 (X); r 1 (X); w 1 (X); w 2 (X); r 1 (Y); C 2 ; w 1 (Y); C 1 ;
cascadeless
S
45 : r 2 (X); r 1 (X); w 1 (X); w 2 (X); C 2 ; r 1 (Y); w 1 (Y); C 1 ;
cascadeless
S
46 : r 2 (X); r 1 (X); w 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 ;
cascadeless
S
47 : r 2 (X); r 1 (X); w 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 2 ; C 1 ;
cascadeless
S
48 : r 2 (X); r 1 (X); w 2 (X); w 1 (X); r 1 (Y); C 2 ; w 1 (Y); C 1 ;
cascadeless
S
49 : r 2 (X); r 1 (X); w 2 (X); w 1 (X); C 2 ; r 1 (Y); w 1 (Y); C 1 ;
cascadeless
S
50 : r 2 (X); r 1 (X); w 2 (X); C 2 ; w 1 (X); r 1 (Y); w 1 (Y); C 1 ;
cascadeless
S 51 : r 2 (X); w 2 (X); r 1 (X); w
1 (X); r 1 (Y); w 1 (Y); C 1 ; C 2 ; non-recoverable
S 52 : r 2 (X); w 2 (X); r 1 (X); w
1 (X); r 1 (Y); w 1 (Y); C 2 ; C 1 ; recoverable
S 53 : r 2 (X); w 2 (X); r 1 (X); w
1 (X); r 1 (Y); C 2 ; w 1 (Y); C 1 ; recoverable
S 54 : r 2 (X); w 2 (X); r 1 (X); w
1 (X); C 2 ; r 1 (Y); w 1 (Y); C 1 ; recoverable
S 55 : r 2 (X); w 2 (X); r 1 (X); C
2 ; w 1 (X); r 1 (Y); w 1 (Y); C 1 ; recoverable
S 56 : r 2 (X); w 2 (X); C 2 ; r 1
(X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; strict (and hence
cascadeless)
Again, the definitions of the three
concepts are very subtle; here I pick two examples to show why.
In both S
21 and S 50, neither T1 nor T2 reads an item that was written by
the other transaction.
The
definition of strict is:
a transaction does not read nor write an item (say X) until
the transaction that last wrote the item X has committed. In S21:
S 21 : r 1 (X); r 2 (X); w 1 (X); r 1 (Y); w 1 (Y); C 1 ; w 2 (X); C 2 ;
^
^
Actually, we need to go through every read and write operations.
For
example, T2 writes X after the transaction that last wrote X (T1) has
committed, so
it is strict
However, in S50:
S 50 : r 2 (X); r 1 (X); w 2 (X); C 2 ; w 1 (X); r 1 (Y); w 1 (Y); C 1
^
^
T2 writes X and then T1 writes X before T2 has committed, so it is not strict.
the definition of cascadeless is: A transaction does not
read an item X until the transaction that last wrote X has committed.
Since neither T1 nor T2 read an item that was previously written by the other,
S50 does not violate and is cascadeless.
The definition of recoverable
schedule is: A schedule is recoverable if no transaction T in S commits until
all transactions T’ that have written an item that T reads have committed.
17.17 List all possible schedules
for transactions T 1 and T 2 from figure 17.2, and
determine which are conflict
serializable (correct) and which are not.
Answer:
T 1
read_item(X);
X := X - N
write_item(X);
read_item(Y);
Y := Y
+ N;
write_item(Y);
T 2
read_item(X);
X := X + M;
write_item(X);
The transactions can be written as
follows using shorthand notation:
T 1 : r
1 (X); w 1 (X); r 1 (Y); w 1 (Y);
T 2 : r
2 (X); w 2 (X);
In this case, m =2 and n1 = 4 and n2
= 2, so the number of possible schedules is:
(4+2)! / (4! * 2!) = 6*5*4*3*2*1/
4*3*2*1*2*1 = 15.
Below are the 15 possible schedules,
and the type of each schedule:
S 1 : r 1 (X); w 1 (X); r 1 (Y); w 1
(Y); r 2 (X); w 2 (X); serial (and hence also serializable)
S 2 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 1 (Y); w 2 (X); (conflict) serializable
S 3 : r 1 (X); w 1 (X); r 1 (Y); r 2
(X); w 2 (X); w 1 (Y); (conflict) serializable
S 4 : r 1 (X); w 1 (X); r 2 (X); r 1
(Y); w 1 (Y); w 2 (X); (conflict) serializable
S 5 : r 1 (X); w 1 (X); r 2 (X); r 1
(Y); w 2 (X); w 1 (Y); (conflict) serializable
S 6 : r 1 (X); w 1 (X); r 2 (X); w 2
(X); r 1 (Y); w 1 (Y); (conflict) serializable
S 7 : r 1 (X); r 2 (X); w 1 (X); r 1
(Y); w 1 (Y); w 2 (X); not (conflict) serializable
S 8 : r 1 (X); r 2 (X); w 1 (X); r 1
(Y); w 2 (X); w 1 (Y); not (conflict) serializable
S 9 : r 1 (X); r 2 (X); w 1 (X); w 2
(X); r 1 (Y); w 1 (Y); not (conflict) serializable
S 10 : r 1 (X); r 2 (X); w 2 (X); w
1 (X); r 1 (Y); w 1 (Y); not (conflict) serializable
S 11 : r 2 (X); r 1 (X); w 1 (X); r
1 (Y); w 1 (Y); w 2 (X); not (conflict) serializable
S 12 : r 2 (X); r 1 (X); w 1 (X); r
1 (Y); w 2 (X); w 1 (Y); not (conflict) serializable
S 13 : r 2 (X); r 1 (X); w 1 (X); w
2 (X); r 1 (Y); w 1 (Y); not (conflict) serializable
S 14 : r 2 (X); r 1 (X); w 2 (X); w
1 (X); r 1 (Y); w 1 (Y); not (conflict) serializable
S 15 : r 2 (X); w 2 (X); r 1 (X); w
1 (X); r 1 (Y); w 1 (Y); serial (and hence also serializable)