9

9.3.3

d) r1(A), r2(A), w1(B),w2(B), r1(B), r2(B), w2(C), w1(D)

l1(A), r1(A), u1(A), l2(A), r2(A), u2(A), l1(B), w1(B), l2(B) Denied, r1(B), u1(B),

l2(B), w2(B), r2(B), u2(B),l2(C), w2(C), u2(C), l1(D) w1(D), u1(D)

e) r1(A), r2(A), r1(B), r2(B), r3(A),r4(B),w1(A),w2(B)

l1(A), r1(A), l2(A) Denied, l1(B), r1(B), u1(B), l3(A) Denied, l4(B) r4(B) u4(B), w1(A), u1(A), l2(A), r2(A), u2(A), l2(B), r2(B), l3(A), r3(A), u3(A), w2(B), u2(B)

9.4.1

Note: Almost everyone tried to interpret the schedules as static events—i.e. you tried to assign the locks regardless of the scheduler’s runtime behavior. This is not possible, as a schedule, by definition, is a run-time occurrence (statically, you have a bunch of transactions)

b) r1(A), r2(B),r3(C),w1(B),w2(C),w3(A)

s1(A), r1(A), s2(B), r2(B), s3(C), r3(C), x1(B) Denied, x2(C) Denied, x3(A) Denied

e) r1(A), r2(B), r3(C), r1(B), r2(C), r3(A), w1(A), w2(B), w3(C)

x1(A), r1(A), x2(B), r2(B), x3(C), r3(C), s1(B) Denied, s2(C) Denied, s3(A) Denied

9.4.6

	X	Y	Angle	Magnitude
X	No	Yes	No	No
Y	yes	No	No	No
Angle	No	No	No	yes
Magnitude	No	No	yes	No

	X	Y	Angle	Magnitude
X	yes	Yes	No	No
Y	yes	yes	No	No
Angle	No	No	yes	yes
Magnitude	No	No	yes	yes

10.1.2

d) r2(A), r3(A), r1(A), w1(B), r3(B), w2(C), r3(C)

T1 has to be rolled back.

T3 has to be rolled back as it read an incorrect value. No other transactions are affected.

10.3.1

r1(A), r2(B), w1(C), w2(D), r3(C), w1(B), w4(D), w2(A)

Graph

s1(A)

r1(A)

x1(C)

w1(C)

x1(B) Denied

s2(B)

r2(B)

x2(D)

w2(D)

x2(A) Denied

s3(C) Denied

x4(D) Denied

T3àT1

T1àT2

T4àT2

T2àT1

Abort T1. Locks on A and C are reliesed.

Graph

s1(A)

r1(A)

x1(C)

w1(C)

x1(B) Denied

ABORT

Restart T1

s2(B)

r2(B)

x2(D)

w2(D)

x2(A) Denied

x2(A), w2(A), u2(A),u2(D),u2(B)

s3(C) Denied

s3(C)

r3(C)

u3(C)

x4(D) Denied

x4(D), w4(D), u4(D)

T3àT1

T1àT2

T4àT2

T2àT1

8.2.7

<S,A,60>

<T,A,10>

<U,B,20>

<T,C,30>

<U,D,40>

<START CKPT(U,V,T)>

<V,F,70>

<T,E,50>

<V,B,80>

ii) Crash can occur before the <END CKPT> since with undo logging <end ckpt> will come after the <commit v>. We need to scan back to the starting point of the earliest of U,V and T, which is <START T> if crash occurs prior to <COMMIT T> or back to <START V> if crash occurs after <COMMIT T>

(we only undo transactions for which we haven’t seen a commit, depending on where the crash occurred)

<S,A,60>

<T,A,10>

<U,B,20>

<T,C,30>

<U,D,40>

<V,F,70>

<T,E,50>

<START CHKPT(V,T)>

<V,B,80>

ii). Again, the <END CKPT> belongs after the commit, so a crash would occur before the <END CKPT>. We need to scan back to at most <START T>

8.4.5

<S,A,60,61>

<T,A,61,62>

<U,B,20,21>

<T,C,30,31>

<U,D,40,41>

<START CKPT(U,V,T)>

<V,F,70,71>

<T,E,50,51>

<V,B,21,22>

<END CKPT>

(i) <END CKPT> can be written any time after the <START CKPT>

(ii)Active transactions are U,V,T. Hence the start checkpoint record has
the form <START CKPOINT(U,V,T)>. Assume crash happens after <END CKPOINT>
has been written. The possible subcases are:
[A] Crash happened before <COMMIT U>: need to undo effect of U,V, and T.
Hence, we need to go back to the earliest record involving U,V, or T. This
will be <START T>.
[B} Crash happens after <COMMIT U> but before <COMMIT T>: need to undo
effect of V and T and redo actions (after CKPOINT) of U. Thus, we need to go
back to <START T>.
[C} Crash happens after <COMMIT T> but before <COMMIT V>: need to undo
effect of only V and redo actions (after CKPOINT) of T and U. Therefore,
need to go back to <START V>.
[D} Crash happens after <COMMIT V>: No undo needed. We need to only redo
steps. Hence, we need to go back to <START CKPOINT(U,V,T)>

If crash happens before <END CKPOINT>, then we will need to go back all the
way to the start of the previous checkpoint or the beginning of the log
whichever is later. In this case, that will be <START S>.

i) <END CKPT> can be written any time after the <START CKPT>

ii) Active transactions are T and V. Hence the checkpoint record
written is <START CKPOINT(V,T)>. Using the same line of reasoning as above,
when the crash happens after <END CKPOINT>, the possible scenarios are [B},
[C] and [D] (although start checkpoint looks like <START CKPOINT (V,T)>. If
crash happens before <END CKPOINT>, then we need to go back to <START S> as
in the previous case.

[Comment: Note that in undo/redo logging, flushing dirty pages to disk can
follow independently as long as Rule UR1 in Page 452 is followed. Read also
Example 8.13 carefully to understand the above solution]

3.4.4

Assumptions:

A test takes 40 bytes: 10 bytes for the name, 8 bytes for the date, and a result field of 22 bytes , stored with probability p. A test contains an average of n results.

p% of the time, a record will hold results of size 22n, (1-p)%, the size will be 0.

We only need one pointer per record.

4+22np

4.1.5

The data file is sequential, sorted on the index attribute (assume primary index).

To acess data: retrieve the first block that holds a record with the correct key and scan sequentially

I/O to retrieve data:

(for a, b and c)

In 1/3 of the cases, we will do just 1 I/O. We will need a second I/O in 1/3 of the cases, with a probability of 1/3. A third I/O in 1/3 of the cases, with probability of 2/3.

à Data: 1+(1/3)*(1/3)+(1/3)*(2/3)=1.33 I/Os

Retrieval of index blocks:

Perform a binary search on the index. Finding the correct value takes log B, where B is the number of blocks in the index file.

Assume x distinct values in the index file.

a) Records: x/3+2*x/3+3*x/3=2x.

For 2x records, we need 2x key/pointer pairs (as per problem specification)

Since a block holds 10 keys, we have 2*x/10 index blocks, i.e. log (x/5) I/O’s to retrieve the index.

b) Similar to a), but now we have 1 pointer per block, rather than per record. Each block has 3 records so we have 2x/3 data blocks and keys. Each index block holds 10 keys, so we have 2x/30 index blocks.

I/O cost is log (x/15)

Note: You might need an additional I/O for data retrieval as with sparse index you might need to fetch an extra block

c) I/O is same as b).

4.2.2

The file is not sequential any more. We assume that there are many distinct values that are well distributed over the file, i.e. no block holds 2 records with the same key.

Data I/O: 1/3+2*1/3+3*1/3=2 I/Os

Index: the index is a sequential file. Therefore, to get three values we need to fetch at most 2 blocks. 1/3 of the cases, 1 I/O, 1/3 of the cases, a second I/O with a probability of 1/10, in 1/3 of the cases, a third I/O with a probability of 2/10:

1+(1/3)*(1/10)+(1/3)*(2/10)=1.1 I/Os

Total: 3.1 I/Os