-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathdb2_practice10.txt
110 lines (102 loc) · 5.35 KB
/
db2_practice10.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
Exercise 1.
We have the following 3 transactions. Give the possible values of data element X after
the execution of the transactions, if the schedule is serial and the initial value of X = 100.
T1: READ(X,t); t:=t+100; WRITE(X,t);
T2: READ(X,t); t:=t*2; WRITE(X,t);
T3: READ(X,t); t:=t+10; WRITE(X,t);
--------------------------------------------------------------------------------
Exercise 18.1.2:
If two transactions consist of 4 and 6 actions, respectively,
how many interleavings of these transactions are there?
--------------------------------------------------------------------------------
Exercise 18.2.1:
Below are two transactions, described in terms of their effect on two database elements A and B,
which we may assume are integers.
T1: READ(A,t); t:= t+2; WRITE(A,t); READ(B,t); t:= t*3; WRITE(B,t);
T2: READ(B,s); s:= s*2; WRITE(B,s); READ(A,s); s:= s+3; WRITE(A.s);
We assume that, whatever consistency constraints there are on the database,
these transactions preserve them in isolation. Note that A = B is not the
consistency constraint.
a) It turns out that both serial orders have the same effect on the database;
that is, (T1 ,T2) and (T2,T1) are equivalent. Demonstrate this fact by showing the effect
of the two transactions on an arbitrary initial database state.
b) Give examples of a serializable schedule and a nonserializable schedule of
the 12 actions above.
c) How many serial schedules of the 12 actions are there?
--------------------------------------------------------------------------------
Exercise 18.2.2:
The two transactions of Exercise 18.2.1 can be written in our notation that shows
read- and write-actions only, as:
T1: R1(A); W1(A); R1(B); W1(B);
T2: R2(B); W2(B); R2(A); W2(A);
a) Among the possible schedules of the eight actions above, how many are
conflict-equivalent to the serial order (T1, T2)?
b) How many schedules of the eight actions are conflict-equivalent to the serial order (T2, T1)?
--------------------------------------------------------------------------------
Exercise 18.2.3:
Suppose the transactions of Exercise 18.2.2 are changed to be:
T1: r1(A); w1(A); r1(B); w1(B);
T2: r2(A); w2(A); r2(B); w2(B);
That is, the transactions retain their semantics from Exercise 18.2.1, but T2 has been changed
so A is processed before B.
Give:
a) The number of conflict-serializable schedules.
--------------------------------------------------------------------------------
Exercise 2.
Give the number of conflict-serializable schedules for the following pairs of transactions:
(Give some justification in several words too.)
a) T1: R1(A); W1(A); R1(B); W1(B); T2: R2(C); W2(C); W2(D);
b) T1: W1(A); R1(B); W1(B); T2: R2(B); W2(B); R2(A);
c) T1: R1(A); W1(A); R1(B); T2: R2(B); W2(B); W2(A);
--------------------------------------------------------------------------------
Exercise 18.2.4:
For each of the following schedules:
a) R1(A); R2(A); R3(B); W1(A); R2(C); R2(B); W2(B); W1(C);
b) R1(A); R2(A); W1(B); W2(B); R1(B); R2(B); W2(C); W1(D);
c) R1(A); R2(A); R1(B); R2(B); R3(A); R4(B); W1(A); W2(B);
Answer the following questions:
- What is the precedence graph for the schedule?
- Is the schedule conflict-serializable? If so, what are all the conflict-equivalent
serial schedules?
--------------------------------------------------------------------------------
Exercise 18.3.2:
Here are the transactions of Exercise 18.3.1, with all unlocks moved to the end so
they are two-phase-locked.
T1: l1(A); R1(A); W1(A); l1(B); R1(B); W1(B); u1(A); u1(B);
T2: l2(B); R2(B); W2(B); l2(A); R2(A); W2(A); u2(B); u2(A);
How many legal schedules of all the read and write actions of these transactions are there?
--------------------------------------------------------------------------------
Exercise 3.
Give for the following schedules:
- Are they legal?
- Which transactions are consistent/two-phase-locked
a) l1(A); W1(A); l1(B); u1(A); l2(A); W2(A); u2(A); R1(B); l2(C); W2(C); u2(C); u1(B)
b) l1(A); W1(A); u1(A); l2(A); W2(A); l1(B); u2(A); R1(B); l2(C); W2(C); u2(C); u1(B)
c) l1(A); W1(A); l2(A); W2(A); l1(B); u1(a); u2(A); R1(B); l2(C); W2(C); u2(C); u1(B)
--------------------------------------------------------------------------------
Exercise 18.3.4:
For the transaction described below, suppose that we insert one lock and one unlock
action for each database element that is accessed.
r1(A); w1(B);
Tell how many orders of the lock, unlock, read, and write actions are:
a) Consistent
b) Consistent, but not two-phase locked
c) Consistent and two-phase locked
d) Two-phase locked
e) Neither consistent nor two-phase locked
--------------------------------------------------------------------------------
Exercise 18.4.7:
Here is a schedule with one action missing:
R1(A); R2(B); ???; W1(C); W2(A);
Figure out what actions of certain types could replace the ??? and make the schedule not be
serializable. (Here we mean conflict-serializable.)
Tell all possible nonserializable replacements for each of the following types of action:
(a) Read
(b) Write
--------------------------------------------------------------------------------
Exercise 4.
Insert lock (l) and unlock (u) actions into the following sequence, if possible, in such a way
that the transaction be consistent, two-phase locked and the schedule be legal.
If it is not possible, explain why.
a) R2(A), W3(B), W1(A), W2(B), W1(C), R3(C)
b) R2(A), W3(B), W1(A), W2(B), R3(C), W1(C)