Latches + Transactions View as a PDF

Question 1

Given the following concurrent transaction schedule, draw the corresponding precedence graph and give a serial order of execution based on a topological sort order.

Q1

Question 2

Consider the following schedule, S:

T1 T2 T3
R(X)
R(Y)
W(X)
R(Y)
W(Y)
W(X)
R(Y)
  1. Is this schedule conflict-serializable? Why or why not?
  2. Is this schedule view-serializable? Why or why not?
  3. Determine the precedence graph for this schedule.

For each of the following, modify S to create a complete schedule that satisfies the stated condition. If a modification is not possible, briefly explain why. If it is possible, use the smallest possible number of actions (read, write, commit, or abort). You are free to add commits and aborts to the schedule if that makes it clearer.

  1. Resulting schedule is recoverable.
  2. Resulting schedule avoids cascading aborts but is not recoverable.
  3. Resulting schedule is conflict-serializable.

Question 3

Consider the following transactions:

T1:
read(B);
read(A);
if(A > 0) then A := -B;
write(A);

T2:
read(A);
read(B);
if(B > 0) then B := -A;
write(B);

Assume that the database is consistent if A = 1 or B = 1, with A = B = 1 as initial values.

  1. Show that every serial execution involving these two transactions preserves the consistency of the database.
  2. Show a concurrent execution of T1 and T2 that produces a non-serializable schedule.
  3. Is there a concurrent execution of T1 and T2 that produces a serializable schedule? If such execution exists, show an example, otherwise prove why it doesn't exist. (Hint: can we swap?)
  4. Add locking instructions to the above transactions so that they are compatible with 2-Phase Locking.
  5. Can your new transaction code result in a deadlock? Explain your answer.

Question 4

Given the following BTree (max degree 3), explain the steps that a database system that uses lock crabbing would go through to do the following operations:

  1. Read "28"
  2. Write "23"

Assume that all operations are done using a single pointer curr. You should include locking, unlocking, and moving in your steps. An example of a response would be: Lock {8}. Unlock {8}. Lock {13, 22} and so on. Assume that the system will never abort.

Q4

  1. Now, suppose we want to write "6" to the B-tree. Explain the lock steps in this situation. How many locks in total will we have to acquire using crabbing?
  2. Write "6" using optimistic locking. How many locks did we acquire?
  3. In our "optimistic" scheme, we don’t have locks on ancestor nodes. Suppose we go to read "6", but we concurrently delete "4" from the tree. How can we handle this? When should we use crabbing and optimistic locking?

Feedback

As this is a new course, we appreciate any feedback you have for us! If you enjoyed this assignment, hated this assignment, or have other thoughts to share, please do so here!