View Serializability

 

View Serializability

Recall our discussion in Section ?? of how our true goal in the design of a

scheduler is to allow only schedules that are serializable. We also saw how dif-

ferences in what operations transactions apply to the data can a

ect whether

or not a given schedule is serializable. We also learned in Section ?? that sched-

ulers normally enforce \con

ict serializability," which guarantees serializability

regardless of what the transactions do with their data.

However, there are weaker conditions than con

ict-serializability that also

guarantee serializability. In this section we shall consider one such condition,

called \view-serializability." Intuitively, view-serializability considers all the

connections between transactions T and U such that T writes a database element whose value U reads. The key difference between view- and conict-

serializability appears when a transaction T writes a value A that no other

transaction reads (because some other transaction later writes its own value for

A). In that case, the wT (A) action can be placed in certain other positions

of the schedule (where A is likewise never read) that would not be permitted

under the de

nition of con

ict-serializability. In this section, we shall de

ne

view-serializability precisely and give a test for it.

19.2.1 View Equivalence

Suppose we have two schedules S1 and S2 of the same set of transactions.

Imagine that there is a hypothetical transaction T0 that wrote initial values for

each database element read by any transaction in the schedules, and another

hypothetical transaction Tf that reads every element written by one or more

transactions after each schedule ends. Then for every read action ri(A) in one

of the schedules, we can

nd the write action wj (A) that most closely preceded

the read in question.1 We say Tj is the source of the read action ri(A). Note

that transaction Tj could be the hypothetical initial transaction T0, and Ti

could be Tf .

If for every read action in one of the schedules, its source is the same in

the other schedule, we say that S1 and S2 are view-equivalent. Surely, view-

equivalent schedules are truly equivalent; they each do the same when executed

on any one database state. If a schedule S is view-equivalent to a serial schedule, we say S is view-serializable.

Example 19.1 : Consider the schedule S de

ned by:

T1: r1(A) w1(B)

T2: r2(B) w2(A) w2(B)

T3: r3(A) w3(B)

1While we have not previously prevented a transaction from writing an element twice,

there is generally no need for it to do so, and in this study it is useful to assume that a

transaction only writes a given element once.

2

Notice that we have separated the actions of each transaction vertically, to

indicate better which transaction does what; you should read the schedule from

left-to-right, as usual.

In S, both T1 and T2 write values of B that are lost; only the value of

B written by T3 survives to the end of the schedule and is \read" by the

hypothetical transaction Tf . S is not con

ict-serializable. To see why,

rst note

that T2 writes A before T1 reads A, so T2 must precede T1 in a hypothetical

con

ict-equivalent serial schedule. The fact that the action w1(B) precedes w2(B) also forces T1 to precede T2 in any con

ict-equivalent serial schedule.

Yet neither w1(B) nor w2(B) has any long-term a

ect on the database. It is

these sorts of irrelevant writes that view-serializability is able to ignore, when

determining the true constraints on an equivalent serial schedule.

More precisely, let us consider the sources of all the reads in S:

1. The source of r2(B) is T0, since there is no prior write of B in S.

2. The source of r1(A) is T2, since T2 most recently wrote A before the read.

3. Likewise, the source of r3(A) is T2.

4. The source of the hypothetical read of A by Tf is T2.

5. The source of the hypothetical read of B by Tf is T3, the last writer of B.

Of course, T0 appears before all real transactions in any schedule, and Tf ap-

pears after all transactions. If we order the real transactions (T2; T1; T3), then

the sources of all reads are the same as in schedule S. That is, T2 reads B, and

surely T0 is the previous \writer." T1 reads A, but T2 already wrote A, so the

source of r1(A) is T2, as in S. T3 also reads A, but since the prior T2 wrote A,

that is the source of r3(A), as in S. Finally, the hypothetical Tf reads A and

B, but the last writers of A and B in the schedule (T2; T1; T3) are T2 and T3 re-

spectively, also as in S. We conclude that S is a view-serializable schedule, and

the schedule represented by the order (T2; T1; T3) is a view-equivalent schedule.

2

19.2.2 Polygraphs and the Test for View-Serializability

There is a generalization of the precedence graph, which we used to test con

ict

serializability in Section ??, that re

ects all the precedence constraints required

by the de

nition of view serializability. We de

ne the polygraph for a schedule

to consist of the following:

1. A node for each transaction and additional nodes for the hypothetical

transactions T0 and Tf .

2. For each action ri(X) with source Tj , place an arc from Tj to Ti.

19.2. VIEW SERIALIZABILITY 3

3. Suppose Tj is the source of a read ri(X), and Tk is another writer of X.

It is not allowed for Tk to intervene between Tj and Ti, so it must appear

either before Tj or after Ti. We represent this condition by an arc pair

(shown dashed) from Tk to Tj and from Ti to Tk. Intuitively, one or the

other of an arc pair is \real," but we don't care which, and when we try

to make the polygraph acyclic, we can pick whichever of the pair helps to

make it acyclic. However, there are important special cases where the arc

pair becomes a single arc:

(a) If Tj is T0, then it is not possible for Tk to appear before Tj , so we

use an arc Ti ! Tk in place of the arc pair.

(b) If Ti is Tf , then Tk cannot follow Ti , so we use an arc Tk ! Tj in

place of the arc pair.

Tf TTTT 0123

A

A

B

A B

Figure 19.1: Beginning of polygraph for Example 19.2

Example 19.2 : Consider the schedule S from Example 19.1. We show in

Fig. 19.1 the beginning of the polygraph for S, where only the nodes and the

arcs from rule (2) have been placed. We have also indicated the database

element causing each arc. That is, A is passed from T2 to T1, T3, and Tf , while

B is passed from T0 to T2 and from T3 to Tf . Now, we must consider what transactions might interfere with each of these

ve connections by writing the same element between them. These potential

interferences are ruled out by the arc pairs from rule (3), although as we shall

see, in this example each of the arc pairs involves a special case and becomes a

single arc.

Consider the arc T2 ! T1 based on element A. The only writers of A are T0

and T2, and neither of them can get in the middle of this arc, since T0 cannot move its position, and T2 is already an end of the arc. Thus, no additional arcs

are needed. A similar argument tells us no additional arcs are needed to keep

writers of A outside the arcs T2 ! T3 and T2 ! Tf . Now consider the arcs based on B. Note that T0, T1, T2, and T3 all write

B. Consider the arc T0 ! T2

rst. T1 and T3 are other writers of B; T0 and T2

also write B, but as we saw, the arc ends cannot cause interference, so we need

not consider them. As we cannot place T1 between T0 and T2, in principle we

need the arc pair (T1 ! T0; T2 ! T1). However, nothing can precede T0, so

the option T1 ! T0 is not possible. We may in this special case just add the

4

arc T2 ! T1 to the polygraph. But this arc is already there because of A, so in

e

ect, we make no change to the polygraph to keep T1 outside the arc T0 ! T2. We also cannot place T3 between T0 and T2. Similar reasoning tells us to

add the arc T2 ! T3, rather than an arc pair. However, this arc too is already

in the polygraph because of A, so we make no change.

Next, consider the arc T3 ! Tf . Since T0, T1, and T2 are other writers of

B, we must keep them each outside the arc. T0 cannot be moved between T3

and Tf , but T1 or T2 could. Since neither could be moved after Tf , we must

constrain T1 and T2 to appear before T3. There is already an arc T2 ! T3, but we must add to the polygraph the arc T1 ! T3. This change is the only arc we must add to the polygraph, whose

nal set of arcs is shown in Fig. 19.2. 2

Tf TTTT 0123

Figure 19.2: Complete polygraph for Example 19.2

Example 19.3 : In Example 19.2, all the arc pairs turned out to be single arcs

as a special case. Figure 19.3 is an example of a schedule of four transactions

where there is a true arc pair in the polygraph.

T1 T2 T3 T4

r2(A);

r1(A); w1(C);

r3(C); w1(B);

r4(B); w3(A);

r4(C); w2(D); r2(B); w4(A); w4(B);

Figure 19.3: Example of transactions whose polygraph requires an arc pair

Figure 19.4 shows the polygraph, with only the arcs that come from the

source-to-reader connections. As in Fig. 19.1 we label each arc by the element(s)

that require it. We must then consider the possible ways that arc pairs could

be added. As we saw in Example 19.2, there are several simpli

cations we can make. When avoiding interference with the arc Tj ! Ti, the only transactions