CPS 432/562 Homework #4

Coverage: [DBCB] §18.1-18.4, pp. 918-949
Assigned: March 1
Due: March 8, 4:30p, in class
  1. (5*4=20 points) Consider the following two transactions:

    • Transaction 1: TransferBalance
        READ(A,x);
        x = x-50;
        WRITE(A,x);
        READ(B,y);
        y = y+50;
        WRITE(B,y);

    • Transaction 2: ReportSum
        READ(A,x);
        READ(B,y);
        print x+y;

    For the following items, take into account all operations, even those like x=x-50 and print x+y. Count the number of:

    1. interleavings of the above two schedules (all combinations)
    2. serial schedules
    3. serializable schedules (provide and explain a good consistency constraint)
    4. conflict-serializable schedules

  2. (10+10=20 points) Consider the following two transactions:

    T1: r1(A) r1(B) inc1(A) inc1(B)
    T2: r2(A) r2(B) inc2(A) inc2(B)

    where inc1(A) refers to an increment of A by transaction 1 and so on. Notice that the quantity of the increment is unknown. For example, inc1(A) could mean `increment by 1,' `increment by 10,' `increment by B,' or something else. In other words, you cannot assume anything.

    1. How many interleavings of these transactions are conflict-serializable?
    2. If the order of the increments in T2 are reversed, how many interleavings are conflict-serializable?

  3. (5+5=10 points) Exercise 18.4.5 on p. 950 from [DBCB]: The action of multiplication by a constant factor can be modeled by an action of its own. Suppose MC(X,c) represents an atomic execution of the steps READ(X,t) t:=t*c WRITE(X,t). We can also introduce a lock mode that allows only multiplication by a constant factor.

    1. Show the compatibility matrix for read, write, and multiplication-by-a-constant locks.
    2. Show the compatibility matrix for read, write, incrementation, and multiplication-by-a-constant locks.

  4. (10 points) Required only for CPS 562 students
    Exercise 18.3.4 (part b) on p. 940 from [DBCB]: Consider the following transaction:

    r2(A) w2(A) w2(B)

    Suppose that we insert one lock and one unlock action for each database element this is accessed. Indicate how many orders of the lock, unlock, read, write actions are:

    1. consistent and two-phase locked
    2. consistent, but not two-phase locked
    3. inconsistent, but two-phase locked
    4. neither consistent nor two-phase locked

Return Home