CS145 - Spring 2003
Introduction to Databases
Challenge Problems #4   --   Due 11:59pm, Tuesday May 20
Email to cs145-submit@cs.stanford.edu

Challenge Problems

  1. This problem explores the differences between row-level and statement-level triggers. For the entire problem you may assume that triggers are not permitted to introduce temporary variables or tables, and they cannot call stored procedures. Otherwise, use the SQL99 trigger language as presented in class and the textbook. We suggest that your example triggers operate over a single table Student(ID,major,GPA), where ID is a key. If you prefer to use a different table or wish to introduce additional tables you are welcome to do so as long as you state the schemas clearly.

    (a) Write a row-level trigger such that no statement-level trigger can be guaranteed to always achieve the same final state of the database. In addition to specifying the trigger in SQL, describe in English what your trigger does, and explain why an equivalent statement-level trigger cannot be written. (Recall that the equivalent trigger is not allowed to use temporary variables, temporary tables, or stored procedures.)

    (b) Write a statement-level trigger such that no row-level trigger can be guaranteed to always achieve the same final state of the database. In addition to specifying the trigger in SQL, describe in English what your trigger does, and explain why an equivalent row-level trigger cannot be written. (Recall that the equivalent trigger is not allowed to use temporary variables, temporary tables, or stored procedures.)


  2. In lecture on Monday May 12 we proposed a simple implementation protocol for the various transaction isolation levels. Specifically, filling in the lecture notes:
    Assume each transaction obtains locks as it needs them and releases them 
    all when it commits or rolls back.
    
    READ lock on tuple t:   Records that a transaction reads t
    WRITE lock on tuple t:  Records that a transaction updates/deletes tuple t
    INSERT lock on table T: Records that a transaction inserts into T
    
    
      Serializable transactions:
        To perform any operation on a table: no other INSERT lock
        To read a tuple: no other WRITE lock, set READ lock
        To update or delete a tuple: no other READ or WRITE lock, set WRITE lock
        To insert a tuple: set INSERT lock
    
    
      "Read uncommitted" transactions:
        No global checking for INSERT locks
        To read a tuple: no checking or setting
        To update or delete a tuple: no other READ or WRITE lock, set WRITE lock
        To insert a tuple: set INSERT lock
    
    
      "Read committed" transactions:
        No global checking for INSERT locks
        To read a tuple: no other WRITE lock
        To update or delete a tuple: no other READ or WRITE lock, set WRITE lock
        To insert a tuple: set INSERT lock
    
    
      "Repeatable read" transactions:
        No global checking for INSERT locks
        To read a tuple: no other WRITE lock, set READ lock
        To update or delete a tuple: no other READ or WRITE lock, set WRITE lock
        To insert a tuple: set INSERT lock
    

    Unfortunately this implementation protocol is not quite correct. Find as many bugs in the protocol as you can. (Hint: we know of at least two.) To illustrate each protocol bug you should specify:

    (a) two or more transactions and their isolation levels

    (b) an execution sequence for the operations in the transactions that respects the protocols for the isolation levels

    Each of your examples should be such that the resulting behavior violates at least one of the transaction's isolation levels. The style of transaction specification and behavior description can be similar to the informal style followed in lecture.


  3. Consider the following simple view over tables R(A,B) and S(C,D):
    create view V as
      (select A, D
       from   R, S
       where  R.B = S.C)
    
    

    For each of the following types of modifications to V, state conditions (such as keys for base relations or other constraints) under which a view update of that type can always be translated unambiguously to base relation modifications.

    (a) Update the A value in a single tuple of V

    (b) Update the D value in a single tuple of V

    (c) Insert a single new tuple into V

    (d) Delete a single tuple in V