CSE 444 Homework 2

Objectives:

To understand query execution, recovery and concurrency control.

Reading Assignments:

Chapters: 17.2-17.4 and 18

Number of points:

100

Due date:

Sunday, July 25, 11:00 pm. No late assignments will be accepted, so we can hand out the solution immediately for you to study for the midterm.

How to turn in:

Please use the online dropbox for your submission. However, if you wish, you can hand in a paper copy in class on the Friday before the due date.

1. [20 points] After a system's crash, the undo-log using non-quiescent checkpointing contains the following data:

   <START T1>

   <T1, X1, 1>

   <START CKPT ????>

   <START T2>

   <T2, X2, 2>

   <T1, X1, 3>

   <START T3>

   <COMMIT T1>

   <END CKPT>

   <START CKPT ????>

   <T2, X2, 4>

   <T3, X3, 5>

   <START T4>

   <COMMIT T2>

   <T4, X4, 6>

   <COMMIT T3>

   <END CKPT>

   <START T5>

   <T5, X5, 7>

   <START CKPT ????>

   <T4, X4, 8>

   CRASH !!!

   
   
   1. What are the correct values of the three <START CKPT ????> records? You have to provide three correct values for the three “????”s.
   2. Assuming that the three <START CKPT ???> records are correctly stored in the log, according to your answer at a., show which elements are recovered by the undo recovery manager and compute their values after recovery.
   3. Indicate what fragment of the log the recovery manager needs to read.
      
   
   
2. [20 points] The SuperSQL database system stores its undo log file in a table, with the following schema:
   
             Log(N, T, E, V)
   
   where N is the entry number (0, 1, 2, 3, …), T is the transaction id, E is the element id, and V is the old value.  A log entry of the form <T, E, V> is simply represented by the tuple (N, T, E, V), where N is the entry number and E > 0 for an ordinary element id. The log entries <START T>, <COMMIT T>, and <ABORT T> are represented by a tuple (N, T, E, null), where E=-1 for START, E=-2 for COMMIT, and E=-3 for ABORT. For example, the log:
   
   

   <START T1>

   <T1, X1, 55>

   <START T2>

   <T2, X2, 99>

   <COMMIT T1>

   . . . .

   Is represented by the table:

   N	T	E	V
   0	T1	-1
   1	T1	X1	55
   2	T2	-1
   3	T2	X2	99
   4	T1	-2
   . . .

   Recall that each transaction starts and ends at most once; for example, a sequence <START T> … <COMMIT T> … <START T> … will not occur in the log. Moreover, any update by the transaction T will occur between its <START T> and <COMMIT T>, or between <START T> and <ABORT T> respectively. Finally, once a transaction has ended in COMMIT or ABORT and the corresponding log record is on disk, the transaction has completed and does not need to be undone.
   
   Write a SQL query that can be run during database recovery, after a system crash. The answer to your query should return a table with two attributes, E, and V, indicating which elements have to be updated with what values. You should include each element E at most once in your answer: otherwise it would be ambiguous how to update it.

3. [40 points] Solve the following problems from the textbook:
   1. Exercise 18.2.4 (a,b,d) and (i) and (ii) on page 897
   2. Exercise 18.2.5 on page 897
   3. Exercise 18.8.1 (a,b) on page 942
   4. Exercise 18.9.1 (a,b) on page 948
   
   
4. [20 points] Consider a database with objects X and Y and assume that there are two transactions T1 and T2. Transaction T1 reads objects X and Y and then writes X. Transaction T2 reads objects X and Y and then writes objects X and Y. Give three examples of schedules for the transactions T1, T2 to illustrate each of the points below:
   1. Your schedule should contain a write-read conflict.
   2. Your schedule should contain a write-write conflict.
   3. Your schedule should contain a read-write conflict.
   In each case your schedule may contain additional conflicts, but should contain at least one conflict of the type indicated. (In particular you may give a single schedule, which illustrates all three conflicts !). In each case, indicate the conflict of the type you are illustrating.