The final will be Thursday, May 3.
The exam will not be open book.
Instead, I will give you the notes pages indicated on the course
website (~8 pages if printed normal-sized), and you will also be
allowed to bring up to two pages (single-sided) of your own notes.
Ch 18: 18.18abcdefgh
Ch 19: 19.13a, 19.14
Ch 21: 21.16, identify recoverable and cascadeless only, 21.17, 21.22
1. (a) Insert these into an empty B-tree of order 5 (max 4 values / 5 pointers per block):
1 2
3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20
(b) Now insert these values into an empty B-tree in the following order:
1 20 3 18
5 16 7 14 9 12 11 10 13
8 15 6 17 4 19 2
2(a). Suppose we have 2 records per block, and we want to build an ISAM
index that has 5 entries per index block. Give the index, assuming the
file is sorted by the key field and the values for the key field are
the integers from 1 to 40.
3. Suppose we are doing the join of two files A and B; the join
condition is A.a = B.b. File A has 10,000 records and B has 20,000
records. Each file has 10 records/block. A is sorted by field a;
looking up a value requires ~10 = log2(1000) block lookups using binary search. B has a hash index; finding a record takes on average 7 block accesses. B is not sorted by attribute b.
(a) Give an estimate of the cost of the join, if we use the approach
for each a in A
lookup a in B using the hash index
(b) Give an estimate of the cost of the join if we use the approach
for each b in B
look up b in A using binary search
4. (a) Here are transaction schedules for T1 and T2. Is this
recoverable? If so, why? If not, how could it be fixed? Recoverability
should be the case whether the commit/abort is a commit (if success) or
abort (if failure).
T1 |
T2 |
read(x) write(x) |
|
read(x) write(x) |
|
read(y) write(y) commit/abort |
|
read(z) write(z) commit/abort |
(b). Here are schedules for T1, T2, T3. Who reads from whom? Who precedes whom in the precedence graph?
T1 |
T2 |
T3 |
read(x) write(x) |
||
read(x) |
||
read(x) write(x) |
||
write(x) |
(c). Create a schedule of two transactions T1 and T2 that contains a
conflict. If you use the tabular style, above, be careful to show (eg
with clear horizontal lines) when control switches between T1 and T2.