DBMS Serializability
Serializability
is the classical concurrency scheme. It ensures that a schedule for executing
concurrent transactions is equivalent to one that executes the transactions
serially in some order. When
multiple transactions are running concurrently then there is a possibility that
the database may be left in an inconsistent state. Serializability is a concept
that helps us to check which schedules are serializable.
Serializable schedule
A serializable schedule always leaves the database in
consistent state. A serial schedule is always a serializable schedule because
in serial schedule, a transaction only starts when the other transaction
finished execution. However a non-serial schedule needs to be checked for
Serializability. A non-serial schedule of
n number of transactions is said to be serializable schedule, if it is
equivalent to the serial schedule of those n transactions.
There
are two types of Serializability:
1. Conflict Serializability
2. View Serializability
1. Conflict Serializability:
Conflict Serializability is one of the type of Serializability, which can be used to
check whether a non-serial schedule is conflict serializable or not.
A
schedule is called conflict serializable if we can convert it into a serial
schedule after swapping its non-conflicting operations.
Conflicting operations
Two operations are said to be in conflict, if they
satisfy all the following three conditions:
1.
Both the operations should belong to different transactions.
2. Both the operations are working on same data item.
3. At least one of the operation is a write operation.
Example : Operation
W(X) of transaction T1 and operation R(X) of transaction T2 are conflicting
operations, because they satisfy all the three conditions mentioned above. They
belong to different transactions, they are working on same data item X, one of
the operation in write operation.
Two
schedules are said to be conflict Equivalent if one schedule can be
converted into other schedule after swapping non-conflicting operations. If a
schedule is conflict Equivalent to its serial schedule then it is called Conflict
Serializable schedule.
Example of Conflict Serializability
Consider
this schedule:
To
convert this schedule into a serial schedule we must have to swap the R(A)
operation of transaction T2 with the W(A) operation of transaction T1. However
we cannot swap these two operations because they are conflicting operations,
thus we can say that this given schedule is not Conflict Serializable.
Another Example:
Swapping
non-conflicting operations:
1.
swapping R(A) of T1 and R(A) of T2
2.
swapping R(A) of T1 and R(B) of T2
3.
swapping R(A) of T1 and W(B) of T2.
After
doing above swappings, the schedule is
This
is a serial schedule after swapping all the non-conflicting operations so the
given schedule is Conflict Serializable.
2. View Serializability
View
Serializability is a process to find out that a given schedule is view
serializable or not. A given schedule is view serializable, if the given
schedule is View Equivalent to its serial schedule.
View Equivalent
Two
schedules T1 and T2 are said to be view equivalent, if they satisfy all the following
conditions:
1. Initial
Read: Initial read of each data item in transactions must match in
both schedules. For example, if transaction T1 reads a data item X before
transaction T2 in schedule S1 then in schedule S2, T1 should read X before T2.
2. Final
Write: Final write operations on each data item must match in both the
schedules. For example, a data item X is last written by Transaction T1 in schedule
S1 then in S2, the last write operation on X should be performed by the
transaction T1.
3. Update
Read: If in schedule S1, the transaction T1 is reading a data item
updated by T2 then in schedule S2, T1 should read the value after the write
operation of T2 on same data item. For example, In schedule S1, T1 performs a
read operation on X after the write operation on X by T2 then in S2, T1 should
read the X after T2 performs write on X.
View Serializable
If
a schedule is view equivalent to its serial schedule then the given schedule is
said to be View Serializable.
Example:
Now
check the three conditions of view serializability:
Initial Read
In
schedule S1, transaction T1 first reads the data item X. In S2 also transaction
T1 first reads the data item X.
Check
for Y in schedule S1, transaction T1 first reads the data item Y. In S2 also
the first read operation on Y is performed by T1.
For
both data items X & Y, the initial read condition is
satisfied in S1 & S2.
Final Write
In
schedule S1, the final write operation on X is done by transaction T2. In S2
also transaction T2 performs the final write on X.
Checking
for Y in schedule S1, the final write operation on Y is done by transaction T2.
In schedule S2, final write on Y is done by T2.
For
both data items X & Y, the final write condition is
satisfied in S1 & S2.
Update Read
In
S1, transaction T2 reads the value of X, written by T1. In S2, the same
transaction T2 reads the X after it is written by T1.
In
S1, transaction T2 reads the value of Y, written by T1. In S2, the same
transaction T2 reads the value of Y after it is updated by T1.
The
update read condition is also satisfied for both the schedules.
Since
all the three conditions that checks whether the two schedules are view
equivalent are satisfied in this example, which means S1 and S2 are view
equivalent.