A blind write occurs when a transaction writes a database item it has not read. For example, in the Student Registration System a transaction might compute a student’s GPA by reading her course grades, computing the average, and then (blindly) writing the result in the appropriate database item without first reading that item. Some applications have the property that no transactions perform blind writes. Show that for such applications

a. Viewequivalence is equivalent to conflict equivalence.
b. The timestamp-ordered concurrency control described in Section 20.9.1 never uses
the Thomas Write Rule.
c. In the timestamp-ordered concurrency control described in the text, for each item,
x, that a transaction, T, w rites, w hen T commits, rt(x) = wt(x) = TS(T).

a. Assume we are given a schedule, S, without blind writes that is view equivalent to another schedule S . We first prove by induction that the order of the writes of each item, x, in S is the same as in S
. (This statement is not true in general for view
equivalent schedules that have blind writes as shown by the example in Figure 20.4.)
Consider the sequence of transactions in S that wrote x, Tw(x)1, Tw(x)2,..., Tw(x)n ,
ordered by their occurrence in S
.

To start the induction, we show that the first write of x in S was made by
Tw(x)1 (the first transaction that wrote x in S

). No later transaction in S
, Tw(x)i ,
could have made the first write of x because, since there are no blind writes, Tw(x)i
would have had to read some version of x and since S is viewequivalent to S
, that
version would have had to be the one written by Tw(x)i?1, but Tw(x)(i?1) has not
yet written x (no transaction has).
Nowassume the statement is true for the the first j ? 1 transactions in the
above list. We showthat the next write of x in S was made by Tw(x)j (the next
transaction that wrote x in S

). It cannot have been made by any earlier transaction
in the list because of the induction hypothesis. It cannot have been made by any
later transaction using the same reasoning as in the previous paragraph.

Thus the order of the writes of each item in S is the same as the order of the
writes of that item in S

, and hence the writes are in the same conflict order in both

schedules. Also, because S is viewequivalent to S

, the reads in S read the same

values as the reads in S

, and hence the reads are in the same conflict order with

the writes in both schedules. Thus S is conflict equivalent to S

b. As described in the text, the Thomas Write Rule is used when a transaction, T,
requests to write an item x and rt(x) < TS(T) < wt(x). But since every transaction
that writes x must have previously read it, the last transaction T
that wrote x and set its write timestamp to wt(x) = TS(T) must have previously read x, and hence x’s read timestamp must be at least TS(T) (if T has committed,
another transaction with a later timestamp might also have read it). Thus for such
applications, it is always true that rt(x) ? wt(x) and hence the condition for the
Thomas Write Rule is never satisfied.

c. When a transaction, T, requests to write an item, x, since T has already read
x, the read timestamp, rt(x) must satisfy rt(x) ? TS(T). If rt(x) > TS(T), then
(as described in the text) T is too old to write x and so will be aborted by the
concurrency control. Hence if T is allowed to write x, it must be true that at
that instant rt(x) = wt(x) = TS(T). If later, but before T commits, some younger
transaction requests to read x, that transaction will be made to wait until T commits
(and hence cannot write either). Therefore when T commits, it will still be true
that rt(x) = wt(x) = TS(T)