• This was a closed-book test, duration 65 minutes.
• This quiz focused on Chapters 15, 23 and the first parts of 25.

Question 1.

Assume a system supports update locks. An update lock is requested at the time a read is done if the transaction will write the same variable later in the transaction. The conflict table for the locks is shown below.

1A. Show that with only read-write locking, the following schedule will deadlock. Assume that all locks are held until the end of the transaction.

       r1(x) r1(z) r2(x) w1(x) w1(z) w2(x)

1A. ANSWER. With all locks held until the end and with conflicts between read and write locks, the w1(x) will have to wait (because of r2(x) read lock) and then the w2(X) write lock request will not be granted because T1, in a wait state, holds a read lock on x.

 T1:   r1(x)   r1(z)            req. w1(x) wait .........       w1(z)(never executes)
       
 T2:                   r2(x)                   req. w2(x) wait .......   DEADLOCK

1B. Now explain how the situation is changed if the update locks are requested instead of read locks. Again, assume that all locks are held until the end of the transaction.

1B. ANSWER. Note that the question said that update locks are requested INSTEAD OF read locks. Since each data item will be written by the same transaction at a later time, update locks are requested. That is what they're for. So T1 requests and obtains update locks on x and z. This prevents the update lock associated with the request for r2(x) from being granted, since update locks conflict. T1 can proceed to the end without deadlocking. Only at that time, when all T1's locks are released, can T2 begin, with its update lock on x granted. Update locks are designed to prevent just these common deadlock situations. They are sometimes called "reads with intent to write". Below, a "Ux" is a request for an update lock for x.

T1:  Ux r1(x)  Uz r1(z)          w1(x)    w1(z) (end transaction)
       
T2:                    Ux   wait ......                           r2(x)  w2(x) 

Question 2.

The problem below is identical to the one in the locks/waits handout, except that rows 3, 4 and 7 in the table have been left blank. Your job is to fill in the missing entries. Create the three missing rows IN YOUR BLUE EXAM BOOKLET and fill them in there. Do NOT hand in this question sheet.

Notes on the table below:

• Time refers to the time points in the figure above
• Lock-x is the lock set L(x) of all read or write locks held on x by transaction 1 and 2, and similarly for Lock-y.
• Wait-x is the wait set W(x) of all locks requested on x by transaction 1 and 2, and similarly for Wait-y.
• T1 shows the status of T1 as running (R) or waiting (W) or not running (N) and similarly for T2.
• Locks-1 is the lock list of all locks held or waited for by T1, and similarly for Locks-2.
• What happens describes the requests, grants, suspension, release and running of the transactions.
• "wwx" means "waiting for a write lock on x".

2. ANSWER. The full table, from the earlier handout is shown below, with rows 3, 4 and 7 filled in.

Some points to note in the table above: some people omitted the "wwx" items in rows 3 and 4. But the fact that they were visible in rows 5 and 6 should have made you stop and think about where they first appeared. Occasionally people would have a row in which a read lock was held by 1 at the same time a write lock was held by 2. That's not allowed by the standard conflict rules, so again, you needed to be on the lookout for such inconsistencies and delayed the granting of a conflicting lock.

    T1:   w(x)                  commit-or-abort
    T2:          r(x)  w(y)

3A. Explain why the schedule is or is not serializable if T1 commits.

3A. ANSWER. Questions of serializability can be answered independently of concerns about locking. This is such a case. We just inspect the schedule as presented and see if it serializable. The only conflicting operations are w(x) for T1 and r(x) for T2. For this pair, T1 precedes T2 so the schedule is serializable.

I did not explicitly state where the commit/abort point was for T2, so for that I lost 3 points and 3 points were added to each person's score.

3B. Explain why the schedule is or is not serializable if T1 aborts. (Hint: Assume that an abort is equivalent to one or more writes.)

3B. ANSWER. In wording this question I've tried to sidestep the entire topic of recoverability by asking you to think of the abort as an event that causes writes to occur. In this case, a write w(x) by T1 would be required at the abort point in order to restore x to its original value. See the example of a Dirty Read Fig. 23.6(a) on pg. 825. So the schedule including the abort could be viewed as equivalent to:

    T1:   w(x)                  w(x) (the rewrite when  the abort occurs)
    T2:          r(x)  w(y)

3C. How is the schedule altered if both long read and write locks are used? What effect will an abort of T1 have under these conditions?

3C. ANSWER. In this case the initial read of T2 is not granted, because of the write lock held by T1. T2 is suspended until the lock is released at T1's commit or abort time and T2 then starts and completes. Obviously neither a commit or abort by T1 will have any effect on T2 which doesn't execute any operations until T1 is entirely finished. Final equivalent serial order is T1, T2.

    T1:   w(x)                      commit or abort
    T2:         req. r(x) wait..                        r(x)    w(y)

3D.Extra Credit. Explain the concept of "recoverability" and how it applies to 3B. .

3D. ANSWER. (up to 5 points) Recoverability is concerned with whether or not an abort by a transaction can lead to effects that violate isolation, such as a dirty read. Without proper locking, the schedule in this question is not recoverable. Only strong locking, strict two-phase in this example, will assure recoverability. See Fig. 23.7, pg. 826.

Question 4.

The following notation is used to describe the entries in the log shown below. In addition, "CRASH" denotes the point at which a crash occurs.

Bn = Begin record for transaction n

Un = Update record for transaction n (has "before" value)

Cn = Commit record for transaction n

An = Abort record for transaction n

CK = Checkpoint record

The question you are to answer: How is each entry in the log dealt with as the log is scanned backwards to bring the database back to a consistent state after the crash? (The log presumably extends very far to the left, not shown.)

4. ANSWER. This question is identical to the one on Quiz 2. Only the numbers on the transactions have been changed. The answer below discusses what is done with each item in the log as it is met while scanning backwards. Some people gave a general discussion rather than an item-by-item answer that corresponds to the way that log is handled during recovery. Some people worried about isolation matters, but that was already handled by the concurrency control before any updates were logged.

• U1 -- This is the first mention of T1 in scanning backwards so the system knows that it neither committed or aborted. The system crashed before the transaction was completed. Therefore this update is undone by using the before value in the U1 record. T1 is marked as requiring rollback so any other undoes found for T1 will also be processed.



• C3 -- T3 committed here, so it is marked so that all mentions of T3 earlier in the log will be ignored. Nothing more needs to be done with them. The committed data is in the database whenever such a commit record is found in the log.



• A2 -- T2 aborted here, so it is treated in the same way that a commit would be and any earlier mentions of T2 in the log should be and will be ignored.



• U3 -- Since T3 committed, this is ignored.



• U2 -- Since T2 aborted, this is ignored.



• B3 -- Ignored.



• U1 -- Since T1 is being rolled back, this undo record is used to rollback this change.



• CK T2 T1 -- The checkpoint tells us that T2 and T1 were active here. T2 can be ignored since it properly aborted. But it is known at this point that T1 never completed, so the log will continue to be searched backwards for any other T1 changes until the begin record for T1 is found. Any records found for any transactions other than T1 that are found while further scanning backwards will thus be ignored.



• C4 -- T4, therefore ignore it.



• U1 -- Undo this update.



• U4 -- Ignore.



• B1 -- Begin record found for the only transaction still in question, so the scan of the log is complete at this point.

Question 5.

In the following schedule, how is the request to read x by T3 treated by a simple consideration of read/write conflicts and how would this be changed by using a fair policy? Describe the appropriate wait and lock sets and how they're examined and changed to implement a fair policy (one that avoids "starvation"). We're assuming strict two-phase locking with all locks held until the end of a transaction, once granted. ("req." means that the corresponding lock is requested at this point.)

   T1:  r(x)                   w(z)           commit
   T2:             req. w(x) ....
   T3:       r(y)                  req. r(x) ....

5. ANSWER. Read locks for T1 and T3 are placed in the L(x) and L(y) and the two Lock Lists. When T2 requests w(x), the wait requests is placed in L(x) and T2 is suspended. (Ignore w(z).. a distinct data item). Then when T3 requests r(x), L(x) is examined and it is found that a transaction at an earlier time, T2, is waiting for a write lock on x. In a simple strategy, paying attention only to lock conflicts, T3 could legally be allowed to proceed -- its read request does not conflict with T1's read lock for the same variable. But in a fair strategy, such requests are not granted because they could lead to "starvation" of transactions such as T2 that are waiting for a stronger lock. So in a fair strategy, T3 is made to wait. Then after T1's commit, T2 will be granted the w(x) lock. When it finishes, presumably the next transaction to be freed to run will be T3. These transactions serialize in commit order, as they should, T1, T2, T3.

Some people got the "fair" policy turned around and worried about starving reads. The problem is that writes can be starved, since concurrent read locks are easy to get.