Page History

...

This schedule is serializable, but not conflict serializable.

It is useful to capture all potential conflicts between the transactions in a schedule in a precedence graph, also called a serializability graph.

The precedence graph for a schedule S contains:

• A node for each committed transaction in S.
• An arc from Ti to Tj if an action of Ti precedes and conflicts with one of Tj's actions.

A schedule S is conflict serializable if and only if its precedence graph is acyclic. An equivalent serial schedule in this case is given by any topological sort over the precedence graph.

Conflict serializability is sucient but not necessary for serializability. A more general sucient condition is view serializability.

Until now we have talked about schedules having only committed transactions. We must also take into account consideration schedules containing aborted transactions. 

Intuitively, two schedules are equivalent if the executions that produced them leave the database in the same state. The formal definition of equivalence is:

Two schedules are computationally equivalent if and only if:

• Each read operation reads from the same write operation in both schedules , and
• Both schedules have the same final writes.

We say a read operation j reads from a write operation i if read operation j reads a value most recently written by write operation i. The final write of a schedule is the schedule's last write operation.

A schedule is view serializable if it is computationally equivalent to some serial schedule. Every conflict serializable schedule is view serializable, although the converse is not true.

It can be shown that any view serializable schedule that is not conflict serializable contains a blind write.

Enforcing or testing view serializability turns out to be much more expensive, and the concept therefore has little practical use.

Consider two transactions

T1 = w1[x] a1, T2 = r2[x] w2[x] c2

and a schedule

and S = w1[x] r2[x] w2[x] c2 a1

Such schedule is unrecoverable, because T2 is committed and can't be undone on T1 abort. Another example:

T1 = w1[x] c1, T2 = w2[x] a2

and S = w2[x] w1[x] a2 c1

Here w1[x] will be undone by a2, causing lost update on c1for T1.

For a schedule to be recoverable, it's necessary to read only committed data. Recoverable schedules also avoid cascading aborts.

...