Database Reference
In-Depth Information
T1
T2
T1
T2
BEGIN
READ (A)
A :
=
A
+
100
WRITE (A)
READ (B)
B :
BEGIN
READ (A)
A :
100
WRITE (A)
=
A
+
200
WRITE (B)
COMMIT
END
=
B
+
BEGIN
READ (A)
A :
50
WRITE (A)
=
A
-
BEGIN
READ (A)
A :
READ (B)
B :
=
B
+
200
WRITE (B)
COMMIT
END
50
WRITE (A)
READ (B)
B :
=
B
-
100
WRITE (B)
COMMIT
END
=
A
-
READ (B)
B :
=
B
-
100
WRITE (B)
COMMIT
END
SERIAL SCHEDULE
EQUIVALENT
SERIALIZABLE SCHEDULE
Figure 15-13
Equivalence of a serial and a serializable schedule.
it follows that, if two operations do not conflict, we can swap the order of the oper-
ations to produce another schedule that is equivalent to the original schedule.
Consider Schedule-1 as shown Figure 15-14.
Look for sets of two operations that do not conflict and swap the operations
within each set. After swapping we arrive at Schedule-2 as shown in Figure 15-15.
Closely examine Schedule-2. You can see that Schedule-2 is a serial schedule
obtained by swapping nonconflicting operations. Because Schedule-2 is obtained by
swapping nonconflicting operations in Schedule-1, Schedule-1 and Schedule-2 are
said to be conflict equivalent.
Conflict serializability
A schedule is conflict-serializable if it is conflict equivalent to a serial schedule.
Let us relax the equivalence conditions slightly and establish the concept of two
schedules being view equivalent. Two schedules, Schedule-1 and Schedule-2, are
view equivalent if the following conditions are satisfied:
•
For a particular data item, if T1 reads the initial value of the data item in Sched-
ule-1, then T1 must also read the initial value of the same data item in Sched-
ule-2.
•
For a particular data item, if T1 reads that data item in Schedule-1 and that
value was produced by T2, then T1 must also read the data item in Schedule-
2 that was produced by T2.
Search WWH ::
Custom Search