Lab 6: Transactions and schedules; locking

Transactions and schedules

1. Consider this schedule of two transactions:

   T1	T2
   r(X)
   	r(X)
   w(Y)
   	w(Y)
   commit
   	commit

   Is this schedule:

   • conflict serializable?

     Yes, when it comes to conflicting actions, the schedule above is equivalent to the serial schedule T1;T2.

     To see this, note that there is only one pair of conflicting actions: T1’s write of A, and T2’s write of A. Because w1(A) comes before w2(A), T1 must come before T2 in any equivalent serial schedule. And since this is the only conflict-based constraint, the original schedule is equivalent to T1;T2.

     An alternative way of showing this is to note that T2’s read of X doesn’t conflict with T1’s write of Y because the two operations involve different data items. Therefore, we can swap those two operations to produce the serial schedule T1;T2. (Note that the commits do not matter when it comes to determining conflict serializability).

   • serializable?

     Yes. If a schedule is conflict serializable, it is also serializable.

     If we didn’t already know that the schedule is conflict serializable, we could also show that it is serializable by showing that its effects are equivalent to those of the serial schedule T1;T2:

     T1	T2
     r(X)
     w(Y)
     commit
     	r(X)
     	w(Y)
     	commit

     In both the original schedule and the schedule T1;T2:

     • Y is the only data item that is changed, and T2 writes it after T1 does.
     • T2 reads the original value of X, and it does not read the value of Y that X wrote.

     Thus, the schedule above is serializable.

   • recoverable?

     Yes, because there are no dirty reads—i.e., there are no situations in which one transaction reads a value that has been written by another transaction that has yet to commit. Therefore, there’s no need to worry about the order in which the transactions commit, since during recovery we can roll back an uncommitted transaction regardless of whether the other transaction has committed.

   • cascadeless?

     Yes, because there are no dirty reads.

     A cascading rollback occurs when:

     • One transaction (call it T) writes a data item A.

     • Another transaction (call it U) reads the value that T wrote before T commits; that is a dirty read.

     • T is rolled back, and thus the old value of A is restored.

     • U must also be rolled back, because it read a value of A that no longer exists.

     Since there are no dirty reads in this schedule, there will never be a reason for a cascading rollback, and thus the schedule is cascadeless.

2. Consider this schedule of two transactions:

   T1	T2
   r(Y)
   	r(Y)
   	w(X)
   r(X)
   w(Y)
   	w(Y)
   	commit
   commit

   Is this schedule:

   • conflict serializable?

     No. Examining the constraints imposed by conflicting actions, we see that:

     • r1(Y)...w2(Y) (the fact that T1 reads Y before T2 writes Y) means that T1 must come before T2 in the equivalent serial schedule.

     • r2(Y)...w1(Y) means that T2 must come before T1.

     These constraints contradict each other, so the original schedule is not conflict serializable.

   • serializable?

     No. Although in theory it’s possible for a schedule that isn’t conflict serializable to still be serializable, that isn’t the case for this schedule.

     We can show this by showing the schedule is not equivalent to either of the two possible serial schedules, T1;T2 or T2;T1.

     It’s not equivalent to T1;T2 because:

     • In the schedule above, T2 reads the initial value of Y, and it performs the final writes of both X and Y.

     • In T1;T2, T2 still performs the final writes of X and Y, but it would read the value of Y written by T1 and thus it might write different values for those data items.

     It’s not equivalent to T2;T1 because:

     • In the schedule above, T2, writes the final value of Y.

     • In T2;T1, T1 would write the final value of Y.

     Thus, it is not serializable.

   • recoverable?

     Yes. Although T1 performs a dirty read in this schedule (reading the value of X that T2 writes before T2 has committed), T1 commits after T2, which satisfies the requirement for a recoverable schedule. If T2’s write is undone by a crash or abort, T1 can also be rolled back, since it won’t have committed yet. While such a cascading rollback is undesirable, it prevents us from a possible inconsistent state.

   • cascadeless?

     No, because T1 performs a dirty read, and thus we can end up with a cascading rollback as described above.

3. Would any of the answers for schedule 2 change if we swapped the order of the two commits?

   The schedule would no longer be recoverable.

   Now that T1 commits before T2 does, if the system were to crash after T1 committed but before T2 committed—or if T2 were to be rolled back after T1 committed—the system could be put into an inconsistent state.

   This is because:

   • T1 performed a dirty read of the value of X that T2 wrote (and may have based its write of Y on that value).

   • A rollback of T2 will undo T2’s write of X.

   • Because T1 read that value, it should be rolled back, too, but if T2’s rollback happens after T1 commits, it’s too late to roll back T1.

Precedence graphs

Precedence graphs can help us to determine if a schedule is conflict serializable.

Consider this schedule of four transactions:

Draw a precedence graph for this schedule.

If the schedule is conflict serializable, state one possible equivalent serial schedule. If the schedule is not conflict serializable, explain briefly why the schedule is not equivalent to the serial schedule T1; T2; T3; T4. Your explanation should include a discussion of why particular actions from the original schedule are not consistent with that serial schedule.

T1→T3→T4→T1
T1→T2→T3→T4→T1

Locking basics

Assume that a DBMS is using regular two-phase locking with three types of locks: shared, update and exclusive.

Consider the following partial schedule of three transactions:

Given the locks that the transactions would need to acquire, which of the following operations could happen next in the schedule? Explain each answer briefly.

1. r1(F)

   Could not occur next.

   T1 would need to lock item F, but it has already released its lock for item A. Under two-phase locking, a transaction cannot acquire any new locks after releasing a lock.

2. w2(A)

   Could occur next.

   T1 has released its lock for A and no one else has any locks for item A, so T2 would be able to acquire the exclusive lock for A and write it.

3. r2(E)

   Could occur next.

   T2 would need a shared lock for E. Since the only current lock on E is a shared lock, T2 can acquire a shared lock and read E.

4. w3(D)

   Could occur next.

   In order to write D, T3 would need to upgrade its update lock for D to an exclusive lock for D. And since there are no other locks on D, this upgrade can occur and T3 can write D.

5. w2(C)

   Could not occur next.

   T2 would need an exclusive lock for C. However, T2 already has a shared lock for C, and when a DBMS uses update locks, shared locks cannot be upgraded to exclusive locks. Instead, if T2 wanted to read and then write C, it should have acquired an update lock in order to read the item, and then it could upgrade that update lock to an exclusive lock in order to write the item.

6. r2(D) (followed sometime later by w2(D))

   r2(D) could not occur next.

   Because T2 wants to read and later write D, it would need to acquire an update lock for the read of D. However, it can’t do that because T3 already has an update lock for D. Once a transaction acquires an update lock for an item, other transactions cannot a new lock for that item until the update lock is released. T2 would need to wait for T3 to release its update lock for D.

7. r3(C) (followed sometime later by w3(C))

   r3(C) could occur next.

   Because T3 wants to read and later write C, it would need to acquire an update lock for the read of C. Since the only current lock on C is a shared lock, T3 can acquire an update lock for C and read it.

   Note: T3 won’t be able to write C until T2 releases its shared lock for C, since upgrading an update lock to an exclusive lock can’t happen until there are no locks being held for that item.

Last updated on October 23, 2025.