serializability in dbms

V Serializability - Conflict Serializability, View Serializabiltiy with Examlples

1. UNIT III Serializability

2. Serializability When multiple transactions are being executed by the operating system in a multiprogramming environment, there are possibilities that instructions of one transactions are interleaved with some other transaction.

3. Schedule   : A chronological execution sequence of a transaction is called a schedule. A schedule can have many transactions in it, each comprising of a number of instructions/tasks . Serial schedule: A schedule S is serial if, for every transaction T participating in the schedule, all the operations of T are executed consecutively in the schedule. Otherwise, the schedule is called non serial schedule. Serializable schedule: Serializable schedules are always considered to be correct when concurrent transactions are executing.

4. Difference between serial schedule and a serializable schedule The main difference between the serial schedule and the serializable schedule is that in serial schedule , no concurrency is allowed  whereas in serializable schedule , concurrency is allowed . In serial schedule , if there are two transaction executing at the same time and if no interleaving of operations is permitted , then there are only two possible outcomes : Execute all the operations of transaction T1 (in sequence) followed by all the operations of transaction T2 (in sequence). Execute all the operations of transaction T2 (in sequence) followed by all the operations of transaction T1 (in sequence ). In Serializable Schedule , if there are two transaction executing at the same time and if interleaving of operations is allowed , there will be many possible orders in which the system can execute the individual operations of the transactions.

5. 3. In serializable schedule, the concurrent execution of schedule should be equal to any serial schedule so that schedules are always considered to be correct, when transaction executions have interleaving of their operations in the schedules.

6. Schedule 1 Let T 1 transfer $50 from A to B , and T 2 transfer 10% of the balance from A to B. A serial schedule in which T 1 is followed by T 2 :

7. Schedule 2 A serial schedule where T 2 is followed by T 1

8. Schedule 3 Let T 1 and T 2 be the transactions defined previously . The following schedule is not a serial schedule, but it is equivalent to Schedule 1. In Schedules 1, 2 and 3, the sum A + B is preserved.

9. Schedule 4 The following concurrent schedule does not preserve the value of ( A + B ) .

10. When are 2 schedules equivalent? There are three types of equivalence of schedules : Result equivalence Conflict equivalence View equivalence Based on the types of equivalence, we define the  types of serializability . There are accordingly three types of serializability which are: Conflict serializable View serializable Result Equivalence : In results equivalence, the end result of schedules heavily depend on input of schedules. The final values are calculated from both schedules (given and serial) and check whether they are equal.

11. Result Equivalence NOT RESULT EQUIVALENCE

12. Conflict Equivalence and Conflict Serializable Schedule Before we discuss conflict equivalence and conflict serializable schedule, you must know about conflicts. What is a conflict? A pair of Operations in a schedule such that if their order is interchanged then the behavior of at least one of the transactions may change. Operations are conflict, if they satisfy all three of the following conditions : They belong to different transactions They access the same data item At least one of the operation is a write operation.

13. for example:

14. Conflict equivalence Schedules are conflict equivalent if they can be transformed one into other by a sequence of non conflicting interchanges adjacent actions.

15. For example :

16. Conflict Serializable Schedule A Schedule is conflict serializable if it is conflict equivalent to any of serial schedule. Testing for conflict serializability Method 1 : First write the given schedule in a linear way. Find the conflict pairs (RW, WR, WW) on same variable by different transactions. Whenever conflict pairs are find, write the dependency relation like Ti → Tj , if conflict pair is from Ti to Tj . For example, (W1(A), R2(A)) ⇒ T1 → T2 Check to see if there is a cycle formed, If yes= not conflict serializable No= we get a sequence and hence are conflict serializable.

17. Method 2: To test the conflict serializability, we can draw a Graph G = (V,E) where V = Vertices = number of transactions E = Edges = for conflicting pair Steps : Create node for each transaction. Find the conflict pairs (RW, WR, WW) on same variable by different transactions. Draw edge from the schedule for each conflict pair such that for example, W2(B), R1(A) is conflict pair, draw edge from T2 to T1 i.e. T2 must be executed before T1. Testing conditions for conflict serializability of schedule If precedence graph is cyclic non conflict serializable schedule If precedence graph is a acyclic conflict serializable schedule

18. W2(B)

19. W2(B)

20. View Serializability Let S and S´ be two schedules with the same set of transactions. S and S´ are view equivalent if the following three conditions are met, for each data item Q, If in schedule S, transaction T i reads the initial value of Q , then in schedule S’ also transaction T i must read the initial value of Q. If in schedule S transaction T i executes read ( Q) , and that value was produced by transaction T j (if any), then in schedule S’ also transaction T i must read the value of Q that was produced by the same write (Q) operation of transaction T j . The transaction (if any) that performs the final write ( Q ) operation in schedule S must also perform the final write ( Q ) operation in schedule S’. As can be seen, view equivalence is also based purely on reads and writes alone.

21. View Serializability (Cont.) A schedule S is view serializable if it is view equivalent to a serial schedule. Every conflict serializable schedule is also view serializable. Below is a schedule which is view-serializable but not conflict serializable. What serial schedule is above equivalent to? Every view serializable schedule that is not conflict serializable has blind writes.