CSE 444 Homework 4

Objectives:
To understand query execution, recovery and concurrency control.
Reading Assignments:
Chapters: 15 & 18
Number of points:
100
Due date:
12:20pm, Wednesday March 1st, 2006 (in class)

Questions:

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

                                         

          a.      What are the correct values of the three <START CKPT ????>  records ?  You have to provide three correct values for the three “????”s.

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

                      c.        Indicate what fragment of the log the recovery manager needs to read.
    2.  
  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; here E > 0. 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, i.e. 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.

    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 931
    2. Exercise 18.2.5 on page 931
    3. Exercise 18.8.1 (a,b) on page 978
    4. Exercise 18.9.1 (a,b) on page 984

  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. Now answer the following questions
    1. Given an example schedule with actions of transactions T1 and T2 on objects X and Y that results in a write-read conflict
    2. Given an example schedule with actions of transactions T1 and T2 on objects X and Y that results in a write-write conflict
    3. Given an example schedule with actions of transactions T1 and T2 on objects X and Y that results in a read-write conflict