Conflict Serializable Schedule

Conflict Serializable Schedule

Given non-serial schedules can be transformed into a serial schedule by changing its non-conflicting operations, then it is known as a conflict serializable schedule.

Conflicting Operations

Two instructions are said to be conflicting if they satisfy the following three conditions:

• They belong to different transactions.
• They access the same data item.
• In any case, one of the operations is a write operation.

Conflict Equivalent Schedule

Two schedules S and S^’ are said to be conflict equivalent, if, by a series of swap of non-conflicting instructions, S gets transformed into S^‘.

Conclusion:A concurrent schedule S is said to be conflict serializable if it is conflict equivalent to some serial schedule S^‘.

Examples of a Conflict Serializable Schedule

Schedule 1

Read and Write Instruction for T1 and T2

The read (Q) and write (Q) instructions of T₁ can be swapped with read (P) and write (P) instructions of T₂, resulting in an equivalent schedule 2 (shown below), which is a serial.

Schedule 2

Conflict Serializable Schedule

Thus, the non-serial schedule 1, is a conflict serializable schedule, since it is conflict equivalent to a serial schedule 2.

Examples of a Non-Conflict Serializable Schedule

Schedule 3

Non-Conflict Serializable Schedule

No swapping of non-conflicting instructions will result in a serial schedule. Thus, schedule 3 is not a conflict serializable schedule.

Testing the Conflict Serializability

The precedence graph is also called a serialization graph, and the conflict graph is utilized to test conflict serializability of a schedule within the circumstances that design the putting of concurrency control in the databases.

It is also called a directed graph G=(V,E), which includes a pair of a collection of nodes V= {V₁,V₂,V₃….V_n } and a collection of directed edges E= {E₁,E₂,E₃….E_m }where the collection of nodes V is testing to recover identical information attribute among the transactions of a schedule, and the selection of edges E has measured connections between a collection of two nodes.

Nodes: In the graph, for every transaction, T_p the graph consists of an individual node. Therefore, the schedule of a precedence diagram, and the total amount of transactions, would be equal to the total amount of nodes.

Edges: An edge is measured connections between a set of two different transactions T_q and T_r, and it’s displayed in the format T_q →T_r, where T_q is the starting of the edge, and T_r is the ending.

Algorithm for testing Conflict Serializability of a schedule

• Make a node T for every transaction participating in schedule S in the precedence graph.
• For every condition in schedule S create an edge T_p → T_q in the precedence graph if a Transaction T_q implements a read-item (Z) after T_p implements a write-item (Z). This is a read write conflict.
• For every condition in schedule S create an edge T_p → T_q in the precedence graph if a Transaction T_q implements a write-item (Z) after T_i implements a read-item (Z). This is a write read conflict.
• For each condition in schedule S make an edge T_p → T_q in the precedence diagram. If a Transaction, T_q implements a write-item (Z) after T_p implements a write-item (Z). This is a write write conflict.
• Whether that there is no cycle in the precedence structure, additionally, the schedule S is serializable.

Example

Solution

Let us create a precedence graph.

In the above precedence diagram, by subsequent correspondingly to the method, transaction T_p executes reads A before transaction T_q executes writes A. Therefore the first arrow directed from Transaction T_p towards Transaction T_q and Transaction T_q reads B before Transaction T_p writes B, therefore the second arrow directed from Transaction T_q towards transaction T_p.

Because from the above precedence graph, it is clear that the graph is cyclic. Thus, schedule S is a not-conflicted serializable.

Solution

Let us create a precedence graph.

In the above precedence graph, by subsequent correspondingly to the method, Transaction T_p executes reads A before transaction T_q executes writes A. Therefore the first arrow directed from Transaction T_p towards Transaction T_q and Transaction T_q reads B before Transaction T_r writes B, therefore the second arrow directed from Transaction T_q towards Transaction T_r and then the Transaction T_p reads C before Transaction T_r writes C, accordingly the third arrow directed from Transaction T_p towards T_r.

Because from the above precedence graph, it is clear that the graph is acyclic. Thus, schedule S is a conflicted serializable.

View Serializable Schedule

The concurrent schedule is viewing serializable, whether it is a view equivalent to the serial schedule.

Each conflict serializable schedule is also a view serializable, except the opposite is not true.

View Equivalent

Two schedules S1 and S2 are view equivalent if both fulfilled the subsequent conditions:

1. 1. Initial Read

      The initial read of both the schedules may be a similar transaction. Assume two schedules S1 and S2. Whether the schedule S1, given a transaction T1 is read the data element P, therefore, in S2, transaction T1 can also read P.

There are two schedules, which are view equivalent. T1 completes an initial reading instruction in S1, and in S2, it is also achieved by T1.

1. 1. Updated Read

      During a schedule S1, given the transaction, T_i is reading the data element P that is updated by transaction T_j. Therefore, in schedule S2 additionally, T_i can read data element P, which is updated by T_j.

The above two schedules are not viewed equally, therefore, in S1, transaction T3 is reading P updated by transaction T2, and in S2, the transaction T3 is reading P updated by T1.

1. Final Write

   The final write should be similar to both the schedules. Whether a schedule S1, given a transaction, T1 updates data element P; finally therefore in schedule S2, final write transaction T1 can also complete instructions.

   

   There are two schedules that are view equal since final write instructions in S1 are ended by T3, and in S2, the final write instructions are correspondingly ended by T3.

View Serializable

This schedule is view serializable, whether that schedule is view equivalent to the serial schedule.

Example

Schedule S1 (Non-Serial Schedule)

Schedule S2 (Serial Schedule)

Let us check the three conditions of view serializability.

1. Initial Read

   Whether the S1 schedule, the T1 transaction initial reads the data element P. During schedule S2, further transaction T1 initial reads the data element P.

   Now, test for Q. During a schedule S1, the T1 transaction initial reads the data element Q. Whether a schedule S2 also the initial read instructions on data element Q is implemented by T1.

   We tested for both the data elements P and Q, and the initial read condition is fulfilled in both schedule S1 and S2.

2. Updated Read

   Whether a Schedule S1, transaction T2 reads the value of P, which is explicit by transaction T1. In Schedule S2, the similar transaction T2 reads the data element P following T1 updates it.

   Now test for Q. In Schedule S1, transaction T2 reads the value of Q, which is explicit by T1. In the schedule S2, the similar transaction T2 reads the value of data element Q subsequent T1 writes it.

   An update read condition is further fulfilled for the two schedules S1 and S2.

3. Final Write

   Whether the transaction T2 ends a schedule S1, the final write instructions on data element P. In the schedule, S2 further transaction T2 implements the final write instruction on P.

   Now, test for data element Q. Given a schedule S1, the final write instruction on Q is ended by the T2 transaction. In schedule S2, a final write instruction on Q is ended by the T2.

   We tested for the two data elements P and Q, and the final write condition is also fulfilled for twain the schedule S1 and S2.

Note: Therefore, all the three conditions are satisfied in this instance, which represent schedule S1, and S2 are view equivalent. Further, we understand that schedule S2 is the serial schedule of S1, and therefore, we can tell that S1 schedule is the view serializable schedule.

Enroll Yourself in Live Training: DBMS Training