# 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.

# 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:
if(A > 0) then A := -B;
write(A);

T2:
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.

# 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:

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.