Lab 6: Transactions and schedules; marshalling

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. This means that 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

Marshalling questions for PS 3

In PS 3: Part II, you will implement portions of a simple relational DBMS.

The assignment includes a set of code-reading and design questions that will help you to become familiar with the provided code, and to map out a preliminary design for the code you will write.

Let’s work together on questions 8-10 from the section of the code-reading questions on marshalling.

Later, you should do questions 11 and 12 on your own, along with the rest of the code-reading and design questions.

As you work on the assignment, you should also consult the API pages for both the DBMS code framework and for Berkeley DB Java Edition.

Last updated on October 24, 2024.