In the absence of failures, all transaction must always terminated. However, a transaction may not always complete its execution successfully. In that case, we have an unchanged database and the transaction is called aborted. A transaction can be in one of the following states during the execution:

Figure 1: State diagram of the transaction

A transaction starts in the active state. When it finishs its final statement, it enter partially committed state. At this point, even the transaction has already completed all is statements, it may have still be aborted since the actual output may still be temporarily residing in main memory not yet be copied to the disk. A transaction is committed only if it has performed updates transforms the database into a consistent sate, which must be persist even if there is a system failure . A transaction is said to have terminated if either committed or aborted.

A transaction enter failed state after the system cannot process the transaction normal execution because of hardware or logical errors. Such transactions must be rolled back and enter aborted state. At this point, the system can do either restart the transaction or kill the transaction.

In order to recover the database from failures that affect transactions, the database system maintain a log file in which records all the operations that access the values of data items. A log record can be one of the following entries

This log file will be used to do recover of database system. We will discuss more about recovery later.

A transaction is at the commit point if all of its operations are successfully complete and the effects of all operations have been recorded in the log and performed in the database.

Beyond the commit point, the transction write record [commit, T] to the log. If a failure occure, all transactions with no commit record will have to be rolled back.

Two operations have a potential conflict if they belongs to two different transactions, they perform operations on the same data item and at least one of the operations is a write operation. In such cases, the order of operations affects the result. Conversely, if two operations in a schedule don't conflict, we can swap their order without affecting the overall result.

Definition: Two schedules are said to be conflict equivalent if the order of any two conflicting operations is the same in both schedules.

Definition: A schedule S is conflict serializable if it is conflict equivalent to some serial schedule S’.

In practice, if we can transform a schedule by swapping the orders of two consecutive non-conflicting operations such that the result is a serial schedule then we say that the schedule is conflict serializible

Example: Consider the schedule 3 in figure 4 with only read, write operations

We have two consecutive operations write(A) of T1­ and read(A) of T2 are conflict but write(A) of T2 is not conflict with read(B) of T1.

Schedule 3 is a conflict serializable. We can do ther following swappings step by step in schedule 3 to produce a serial schedule.

Immediate schedule after the first swapping:

Test for Conflict Serializability

Let S be a schedule. We construct a directed graph, called precedence graph, from S.

A precedence graph G = (V,E) for a schedule S consists of

• a vertex in V for each transaction from T1 .. Tn
• an edge in E for each pair Tj and Tk, such that there is a pair of conflicting operations between Tj & Tk and the Tj operation occurs before the Tk operation ( the edge if directed from Tj to Tk)

If an edge Tj  Tk exists in the precedence graph then Tj must appear before Tk in any serial schedule . This implies that if the precedence graph has cycles, then S can't be serialized.

Thus, the serializability test is reduced to cycle-detection.

Figure 3: Precedence graph. a) Schedule 1. b) Schedule 2. c) Schedule 4

The above figure shows that, schedule 4 (in figure 5) is not conflict serializable since the graph contains a cycle.

View equivalence is another less restrictive definition of equivalence in compare with conflict equivalence.

Definition: Two schedule S and S’ are said to be view equivalent if the following conditions are met:

The conditions in above definition ensure that each transaction reads the same values in both schedules and therefore performs the same computation and ensure that both schedules result in the same final state.

Definition: Schedule S is view serializable if it is view equivalent to a serial schedule.

Schedule in the figure below is view equivalent to serial schedule <T3, T4, T6> since T3 read

the initial value of X , T6 performs the final write in both schedule

Every conflict-serializable schedule is view serializable but there are view serializable schedules that are not conflict serializable. The above schedule 7 is not conflict serializable since every pair of consecutive operations conflicts and no swapping possible.

As for conflict serializability, there is an algorithm to test whether a schedule S is view serializable or not. However, the algorithm is proved to be NP-hard meaning that finding an efficient polynomial time algorithm for this problem is highly unlikely. Thus, we will not discuss this algorithm in this course.

Definition: A schedule S is recoverable if for each pair of transactions Ti , Tj such that Tj reads a data items previously written by Ti , the commit operation of T­i appear before the commit operation of Tj.

Schedule 9 in the figure 12.10 is non-recoverable schedule. Suppose T8 fails before it commits. Because T9 has read the value of A which is written by T8, we must abort T9. However, T9 has already committed and thus cannot be aborted. We have a situation where it is impossible to recover correctly from the failure of T8.

To recover correctly from the failure of a transaction Ti we may haveto roll back several

transactions. This results a phenomenon called cascading rollback in which a single

transactions failure leads to a series of transaction rollbacks. For example, consider the

schedule 10 in figure 12.11. T11 reads a value A which is previously written by T10. Then

T11 writes a value of A that is read by T12. Suppose that, at this point T10 fails. It must be

rollbacked, we also need to rollback T11 and T12 since T11 depends on T10 and T12

depends on T11.

We need restrict the schedules to those where cascading rollback cannot occur.

Definition: A schedule S is cascadeless if for each pair of of transactions Ti , Tj such that Tj reads a data items previously written by Ti , the commit operation of T­i appear before the read operation of Tj.