Comp 353 final-exam study guide

The final will be Tuesday, May 3. 

The exam will be open book, though you will not be allowed to use notes. If you will need to use an e-book version of the text, you must contact me beforehand.

Selected solutions are here.

Topics

• SQL
• Normalization (ch 15): 2NF, 3NF, BCNF
  
• Hash indexes (17.8)
  
• Indexing, ISAM and B-Tree indexes (ch 18: 18.1, 18.2, 18.3.1)
• Familiarity with per-record and per-block cost estimates
  
• SQL algorithms and query optimization (19.3, 19.7)
• Transactions and Locking: ch 21 (esp 21.1, 21.4, 21.5), ch 22.1
  

Sample problems

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 = log₂(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).

(b). Here are schedules for T1, T2, T3. Who reads from whom? Who precedes whom in the precedence graph?

(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.