COM1317 Assignment 2 -- Hardcopy due in class April 29th
Locking for transaction isolation

Prof. Futrelle, College of Computer Science, Northeastern University

This assignment is based on Chapter 6 of your textbook, but specifically on the revised version of the chapter that I will hand out on Monday, April 22nd. It is an important assignment, because substantial amounts of the midterm exam will be based on isolation, and locking in particular. [announced/posted 4/22/02.]

1. For each of the following schedules, explain briefly why they are or are not serializable by studying the exchange of commuting operations. Hint: You can consider exchanges ("moves past") many operations at once, instead of just interchanging adjacent pairs.
  1. r1[x] r2[y] r1[z] r3[z] r2[x] r1[y]
  2. r1[x] w2[y] r1[z] r3[z] w2[x] r1[y]
  3. r1[x] w2[y] r1[z] r3[z] w1[x] r2[y]
  4. r1[x] r2[y] r1[z] r3[z] w1[x] w2[y]
  5. r1[x] r2[y] w2[x] w3[x] w3[y] r1[y]
  6. w1[x] r2[y] r1[z] r3[z] r1[x] w2[y]
  7. r1[z] w2[x] r2[z] r2[y] w1[x] w3[z] w1[y] r3[x]

2. Draw the serialization graphs for the seven examples in Problem 1. Explain the significance of cyclic versus acyclic serialization graphs and label each as one or the other. Should your answers agree with your answers to Problem 1? Do they?

3. Use the vertical flow representation (one line for each transaction, time going down) to draw the time course for the following schedules. Then explain whether or not they will deadlock or run to completion if locking is used and also draw the vertical representation for the transactions after locks are applied.

  1. r1[x] r2[x] w1[x]
  2. r1[x] w2[x] w1[x]
  3. r1[x] r2[x] w1[x] w2[x]
4. Consider a system that makes the following guarantee: While a transaction T is active (i.e., after it executes Start and before it finishes executing Commit or Abort), any data item written by T is not read or written by any other transaction.
  1. Are executions of this system recoverable?
  2. Do they avoid cascading aborts?
  3. Are they strict?
  4. Are they serializable?
5. EXTRA CREDIT Toss four coins repeatedly, e.g., penny, nickel, dime and quarter, to produce a sequence of 4-bit random numbers. Let the first bit be read or write, the next be the variable x or y, the next two bits being used to identify transaction 1 or 2 or 3 (skip ones that come up 4). Create two sequences of eight operations each and analyze them in all the ways included in questions 1, 2 and 3.
Return to COM1317 home page.