4.6 Serlallzablilty : Confliclt and View
If execution of all the transactions in a concurrent schedule produces same result as in serial schedule then it is called as Seriallzable schedule. Serializability is a property of a transaction schedule which is used to keep the data in a consistent state. It relates to the isolation property of a database transaction.
In previous section we have seen which problems may occur in concurrent execution of transaction. Hence, Serializability is must while selecting the concurrent option for execution of transactions.
Difference between Serial Schedule and Serializable Schedule
A schedule is said to be Serial if all the operations of transaction are executed serially without any interference from other transaction. For example, schedule 'Sl' is a serial schedule if in it only
one transaction executes at any given time. When a non-serial schedule produced the same result as serial schedule th n it is known as Serializable schedule
2. The main difference between serial schedule and The serializable schedule is that Concurrency is not allowed in serial schedule that means multjple operations cannot be pelfonned at a time while in serializable schedule concurrency is allowed.
3. If a serial schedule includes only two transactions let's consider T, and T2, then There are only two possible orders to schedule those transactions. First is execute all the operations in transaction T1 and then executes all the operations in transaction T2 (i.e. T1 followed by T2). The second order is to execute all the operations of transaction T2 and
then execute all Lhe operations of transaction T 1 (i.e. 1"2 followed by Ti). But In Serializable Schedule, if it includes two transactions then their operations are mixed (can be executed in parallel) with each other, then there will be many possible orders in which the system can execute the individual operations of the transactions.
4. As the Serial schedule doesn't allow any concurrent execution of transactions the result of the schedule always in consistent state. But in a Serializable schedule the concurrent execution of schedule should be equal to any serial schedule so that the results of schedUles are always in consistent state.
types of Serlallzablilty :
Confliclt and View
4.6.3.1 Conflict Serlalizability
Let's say we have a scgea"ule S and we can reorder the instructions in Ji and create 2 more schedules Sl and S2.
1. Conflict equivalent schedules
If a schedule S can be transformed into a serial schedule S1 by performing series of swaps of non conflicting operations, we can say that schedule S & S' are conflict equivalent.
Thie schedule Sl and S2 are said w be contlict e4uivalent if they smisfies fol!o·,,-.ii!lg conditions :
o Same set of transactier.s {incbding sequence of opcrntioils within tD.ch rr:msactionJ are involved in both schedules Si and S2.
Order of pair of conflicting-operations i,;;
same in both the schedules.
2. Conflicting operation•
- Two operations belong to different transactions are· said to be conflicting if they performed on same data item and At Least one of them is a write operation.
Example
o Suppo se if transaction T1 has Read1(Al operation and transaction T2 has Write2(A) operation, then this pair(Read1(A), Write2(A)) is called Conflicting operations pair because they belong to two different transactions on same data item A and one of them is write operation.
o Similarly, (Write1(A), Write2(A)J and (Write1(A), Read2(A)) pairs are also know as conflicting pairs.
o On the other hand. (Read1(A), Write,(B)) pair is non <.-onflicting because they operate on different data items.
o Similarly, ((Write1(A), Write,:(B)) pair is non
conflicting.
4.6.3.2 View Serializability
View serializability of a schedule is defined hy equivalence to a serial schedule (no overiapping transactions) with the same transactions, such that respective transactions in the two schedules read and write the same data values ("view" the same data values).
- The schedules SI and S2 are view equivalent if
they follows following conditions :
o In schedule SI, for data item A if read operation is performed by transaction Ti, then in schedule S2, transaction Tj must perform read operation on data item A.
o If in schedule Sl, transaction Ti reads the data· written by Tj, then the schedule S2, must have the read operation in transaction Ti, who reads the data written 'by Tj.
o If transaction Ti writes the last value of Data item A in schedule SI then, in schedule S2 last write operation on data item A must be performed by Transaction Ti.
First two conditions ensure that no conflict occurs during reading the values of data item 'A' in both the schedules. The last condition enslltes that the final result of both the schedules is same.
The concept of view equivalence leads to view serailizability. The schedule S l is view serializable if it is view equivalent to a serial schedule.
Comments
Post a Comment