Consider this schedule of two transactions:
T1 | T2 |
---|---|
r(X) | |
r(X) | |
w(Y) | |
w(Y) | |
commit | |
commit |
Is this schedule:
conflict serializable?
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?
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:
Thus, the schedule above is serializable.
recoverable?
cascadeless?
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.
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?
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?
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?
cascadeless?
Would any of the answers for schedule 2 change if we swapped the order of the two commits?
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.
Consider this schedule of four transactions:
T1 | T2 | T3 | T4 | |
---|---|---|---|---|
1 | r(X) | |||
2 | r(X) | |||
3 | w(Y) | |||
4 | r(Y) | |||
5 | r(Y) | |||
6 | w(X) | |||
7 | r(W) | |||
8 | w(Y) | |||
9 | r(W) | |||
10 | r(Z) | |||
11 | w(W) | |||
12 | r(Z) | |||
13 | w(Z) |
Draw a precedence graph to determine if this schedule is conflict serializable.
We add an edge from transaction A to transaction B in the graph if transaction A would have to come before transaction B in an equivalent serial schedule.
Here are all of the conflicting actions from different transactions and their corresponding constraints:
conflicting actions | ordering constraint |
---|---|
r1(X)...w2(X) | T1 → T2 |
w1(Y)...r3(Y) | T1 → T3 |
w1(Y)...r2(Y) | T1 → T2 |
w1(Y)...w3(Y) | T1 → T3 |
r2(Y)...w3(Y) | T2 → T3 |
r3(W)...w4(W) | T3 → T4 |
r4(Z)...w1(Z) | T4 → T1 |
r1(X)...w2(X) | T1 → T2 |
And here’s the precedence graph:
As you can see, there are two cycles in the graph:
T1→T3→T4→T1 T1→T2→T3→T4→T1
This means that the schedule is not conflict serializable.
Consider the following schedule of two transactions:
T1 | T2 |
---|---|
r(X) | |
r(Y) | |
w(X) | |
r(X) | |
w(Y) | |
commit | |
r(Y) | |
w(X) | |
commit |
Which of the reads is a dirty read?
T1’s read of X is a dirty read because the value of X was written by T2, which has not yet committed.
Note that T1’s read of Y is not dirty, because it occurs after the writer (T2) commits.
Would two-phase locking prevent the dirty read from occurring? If so, explain why. If not, modify the schedule so that it uses two-phase locking but still includes a dirty read.
No, regular two-phase locking would not necessarily prevent the dirty read. Here’s a schedule that demonstrates this fact:
T1 | T2 |
---|---|
xl(X); r(X) | |
xl(Y); r(Y) | |
w(X); u(X) | |
xl(X); r(X) | |
w(Y); u(Y) | |
commit | |
sl(Y); r(Y) | |
w(X) | |
u(X); u(Y) | |
commit |
Note that both T1 and T2 employ two-phase locking: once they begin releasing locks, they don’t acquire any additional locks. However, because T2 releases its exclusive lock on X before it commits, T1 is able to read X after T2 has written it and before T2 has committed, which constitutes a dirty read.
How can we use locking to prevent dirty reads? Explain how your proposed approach would prevent the dirty read in the schedule from problem 1.
We can use strict locking, which requires that transactions hold all exclusive locks until they complete. Under strict locking, T2 would hold its exclusive lock on X until it committed. Thus, T1 would not be able to acquire the lock needed to read X until after T2 commits. Thus, it would not be able to perform the dirty read.
Does the approach that you specified in your answer to problem 3 replace two-phase locking (2PL), or do we still need 2PL as well? Explain your answer.
No, strict locking does not replace 2PL; it augments it. We still need 2PL, because strict locking only governs the exclusive locks, and we still need to require that transactions do not acquire any shared locks after they have begun releasing them. For example, here is an example of a problematic schedule that uses strict locking but does not use 2PL:
T1 | T2 |
---|---|
xl(X); r(X) | |
sl(Y); r(Y) | |
w(X) | |
sl(Y); r(Y) | |
u(Y) | |
xl(Y); w(Y) | |
u(X); u(Y); commit | |
xl(X); r(X) | |
w(X) | |
u(X); commit |
Note that both T1 and T2 employ strict locking: they hold their exclusive locks until they commit. However, T1 does not employ 2PL: it acquires a lock for X after having released a lock for Y.
The resulting schedule is not serializable. To see this, note that T2 writes both X and Y. T1 reads the value of X written by T2, but it reads the prior value of Y. Thus, this transaction is equivalent to neither of the two possible serial orderings.
Last updated on March 22, 2024.