1 2 3 4 5 6
w2(D)u2(D)u2(B)u2(C)
18.4.4
Schedule is r1(A)r1(B)w1(B)r1(C)w1(C)r1(D)w1(D)r1(E)w1(E)
18.4.5a)
Requested
S
X
M
S
Yes
No
No
X
No
No
No
M
No
No
Yes
18.4.5b)
Requested
S
X
I
M
S
Yes
No
No
No
X
No
No
No
No
I
No
No
Yes
No
M
No
No
No
Yes
18.4.6a)
The only actions that commute are (i)-(ii) and (iii)-(iv). That is, it doesn’t matter whether
we first set the x-axis and then the y-axis, or vice-versa. Likewise, it doesn’t matter
Held
18.4.6b)
Requested
Y
A
M
X
Yes
No
No
18.4.6c)
Requested
Y
A
M
X
Yes
No
No
Y
Yes
No
No
A
No
Yes
Yes
M
No
Yes
Yes
18.4.7a)
The only constraint on a serial order so far is that T1 must precede T2, because T1 reads A
before T2 writes A. The only way we could get a cycle in the precedence graph is if ???
18.4.7b)
18.4.7c)
r1(C) or r2(A) will cause update locks.
Both of these actions do not lead to a cycle. So, no schedule is non-serializable.
18.4.7d)
18.5.1a)
Based on the compatibility matrix of shared and exclusive locks, the only possible sets of
Y
Yes
No
No
No
A
No
No
No
Yes
M
No
No
Yes
No
18.5.1b)
Based on the compatibility matrix of shared, exclusive and increment locks, we see that
the only possible sets of locks on a single element are either
18.5.1c)
Based on the compatibility matrix drawn up in 18.4.6b, the only possible sets of locks on
a single element are either:
18.5.2a)
r1(A)r2(A)r3(B)w1(A)r2(C)r2(B)w2(B)w1(C)
The lock scheduler described in this section inserts shared-exclusive-update locks. Thus
the sequence of lock requests and actions for the above schedule is:
u1(A)r1(A)sl2(A)r2(A)sl3(B)r3B)xl1(A)w1(A)sl2(C)r2(C)ul2(B)r2(B)xl2(B)w2(B)xl1(C)w1(C
)
18.5.2b)
r1(A)w1(B)r2(B)w2(C)r3(C)w3(A)
The sequence of lock requests in the schedule (assuming no delays) would be:
Sl1(A)r1(A)xl1(B)w1(B)sl2(B)r2(B)xl2(C)w2(C)sl3(C)r3(C)xl3(A)w3(A)
18.5.2c)
w3(A)r1(A)w1(B)r2(B)w2(C)r3(C)
18.5.2d)
r1(A)r2(A)w1(B)w2(B)r1(B)r2(B)w2(C)w1(D)
Here we show the sequence of lock requests (assuming no delays):
sl1(A)r1(A)sl2(A)r2(A)xl1(B)w1(B)xl2(B)w2(B)r1(B)sl2(B)r2(B)xl2(C)w2(C)ul2(A)ul2(B)ul2
18.5.2e)
r1(A)r2(A)r1(B)r2(B)r3(A)r4(B)w1(A)w2(B)
Here we show the sequence of lock requests (assuming no delays):
ul1(A)r1(A)sl2(A)r2(A)sl1(B)r1(B)ul2(B)r2(B)sl3(A)r3(A)sl4(B)r4(B)xl1(A)w1(A)ul1(A)ul1(
B)
18.6.1a)
Refer to the following hierarchy for all four sub-parts:
C
B1
B2
O1
O2
O3
O4
O5
i) T1 puts IS lock on C and B1, and S lock on O1
18.6.1b)
i) T1 puts IS lock on C, B2 and S lock on O5.
18.6.1c)
i) T1 puts IS lock on C, B1 and S lock on O1
18.6.2d)
i) T1 puts IS lock on C, B1 and S lock on O1
18.6.2
By replacing w4(D3) by w4(Movie), the schedule becomes:
R3(D1)r3(D2)w4(Movie)w4(X)w3(L)w3(X)
The hierarchy of elements:
The sequence of actions of warning protocol scheduler are:
i) T3 puts IS lock on Movie and S lock on D1.
18.6.3
With increment locks, the steps of the warning protocol scheduler stay the same, except
the compatibility matrix is updated to include II (intention increment) and I (increment)
locks as following:
IS
IX
II
S
X
I
IS
Y
Y
Y
Y
N
N
IX
Y
Y
Y
N
N
N
II
Y
Y
Y
N
N
Y
S
Y
N
N
Y
N
N
X
N
N
N
N
N
N
I
N
N
Y
N
N
Y
18.7.1a)
As soon as we reach the left child of the root, we see that node is not full. Thus, the insert
of 10 cannot cause that node to split, and there will be no reason to rewrite the root. We
18.7.1b)
Movie
D1
D2
X
Lookup of 20 leads to right child of root node. Since right child is full, we might need to
18.7.1c)
For delete of 5, lookup of 5 leads to left child of root node. We then get directed to first
18.7.1d)
Lookup of 23 leads us to the right child of root node. We can release the exclusive lock
18.7.2a)
Note: we shall assume only a single type of lock, so that even though the operations are
all reads (and therefore, any interleaving could in principle be considered serializable), it
is not possible for two transactions to access the same element until one has relinquished
18.7.2b)
T1 can lock A anytime. Next T1 can get a lock on B if T3 didn’t lock B yet. If T1 gets a
lock on B first it will get a lock on E first also. Now T1 can release a lock on B and T3
1) T1 -> T3:
2) T3 -> T1:
r1(A)–> r1(B)->r1(E)
r3(B)->r3(E)->r3(F)
18.7.2c)
1) T1 – T2 – T3 : … The sequence of Ts get locks on a common element.
2)T1 – T3 – T2 :
r1(A)->r1(B)->r1(E)
3) T2 – T1 – T3 :
4) T2 – T3 – T1 :
r1(A)-> r1(B)->r1(E)
5) T3 – T1 – T2 :
r1(A)-> r1(B)->r1(E)
6) T3 – T2 – T1:
r1(A)->r1(B)->r1(E)
r2(A)->r2(C)->r2(B)
18.7.3
R (T1–T3–T5–T7)
|
l1(R); r1(R);
l8(C); r8(C);
l1(A); r1(A);
T4 and T8 are not dependent on any other transaction after T3 and before T7 respectively.
4 possible serial order based on T4’s position (before T6, after T7, or between those) * 6
possible serial order based on T8’s position (before T1, after T5, or between those) = 24
serial orders are consistent with the statement.
18.7.4
Let’s consider the following serializable transaction.
S: w1(C); r1(B); r2(B); w2(D)
Suppose we have the following tree.
A
|
+——–+
B C
|
D
Based on Rule(2) of the tree protocol, each transaction needs to get a lock on a parent
18.8.1a)
T1
T2
A
B
RT = 0
WT=0
RT=0
WT=0
st1
Assume TS(T1)=1
st2
Assume TS(T2)=2
RT=1
RT=2
WT=2
TS(t1)<RT(B)
18.8.1b)
T1
T2
A
B
RT=0
WT=0
RT=0
WT=0
st1
Assume TS(T1)=1
RT=1
st2
RT=2
already written B.
So w1(B) ignored.
18.8.1c)
T1
T2
T3
A
B
C
RT=0
WT=0
RT=0
WT=0
RT=0
WT=0
st1. Assume
TS(T1) = 1
st2.Assume
TS(T2)=2
18.8.1d)
T1
T2
T3
A
B
C
RT=0
WT=0
RT=0
WT=0
RT=0
WT=0
st1.Assume
TS(T1)=1
st3. Assume
TS(T3)=2
TS(T2)=3
r1(A)
RT=1
r2(B)
RT=3
w1(C)
WT=1
RT(B) since
RT(B)>TS(T3)
r3(C)
RT=2
unchanged
W3(A)
WT=2
18.8.2a)
The three writes create three versions of A. When T2 tries to rad A, it is given the value
that it itself wrote, since that is the version with the greatest timestamp that does not
st3. Assume
TS(T3)=3
r1(A)
RT=1
r2(B)
RT=2
w1(C)
WT=1
r3(B)
RT=3
r3(C)
RT=3
w3(A)
WT=3
18.8.2b)
T1
T2
T3
T4
A1
A3
w1(A)
Create
w3(A)
r4(A)
r2(A)
st1.
Assume
st2.
Assume
st3.
Assume
st4.
Assume
18.8.2c)
T1
T2
T3
T4
A1
A4
st1. Assume
TS(T1)=1
st2. Assume
TS(T2)=2
st3. Assume
TS(T3)=3
st4. Assume
TS(T4)=4
w1(A)
w4(A)
r3(A)
On w2(A), following occurs:
RT=3
Without multi-version timestamp scheduler, T3 would have aborted on r3(A) since A
18.8.3
When a younger transaction T2 requests an item X held by an older transaction T1, T2 waits until
the commit bit, C(X), becomes true. T1 never waits for T2. Wait-die strategy is for T2, where the
18.9.1a)
As T1 is the first to validate, there is nothing to check; T1 validates successfully.
T3 validates next. The only other validated transaction is T1, and T1 has not yet finished.
18.9.1b)
The sequence of validation steps are explained below:
– v1
o No transaction has validated yet. So, T1 validates.
18.9.1c)
– v1
o No transaction validated yet. So T1 validates.
18.9.1.d)
– v1
o No transaction validated yet. So T1 validates.
18.9.1e)
– v1
o No transaction validated yet. T1 validates.
18.9.1f)
– v1
o No transaction validated yet. T1 validates.