What is conflict serializability, what is conflict equivalent, example for conflict serializability, conflict serializability in database transaction management, purpose of conflict serializability
Conflict serializability
Before discuss about conflict
serializability, we need to understand what is important in a schedule. We need to know
what exactly a transaction is doing with a data item in a schedule.
In a schedule S, a transaction T1
may write
(update) a new value for data item A by replacing the old value of A. For
example, you withdraw money from your account. Now your account will be updated
with a new value.
In a schedule S, a transaction T2
may read
the value of a data item B. For example, you check your balance in your
account.
Hence, we need to know the following
things;
- The final operation involves a write/read operation?
- If they write/read, are they doing this operation with same data item or different data item?
- If the final operation is read/write on different data items by different transactions in a schedule then we don’t need to worry about the order in which these transactions have to be executed.
If different transactions work on the same data items in a schedule in
any of the conflict modes (say, Read-Write, Write-Read, Write-Write), then we cannot
execute them in any order that we like.
Conflict serializability
A schedule S is said to be conflict
serializable, if it is conflict equivalent to some serial schedule. Two
schedules S1 and S2 are said to be conflict equivalent if the order of any two
conflicting operations is the same in both schedules.
This matrix table is called as
equivalence matrix. It ensures the order in which the instructions are to be
executed in a concurrent schedule.
Schedule S
|
T1
|
||
R(X)
|
W(X)
|
||
T2
|
R(X)
|
OK
|
Not OK
|
W(X)
|
Not OK
|
Not OK
|
|
Following cases are possible;
- In a schedule S1, if two different transactions are trying to read the same data item, they can be permitted in any order in a equivalent schedule S2. Order is not an issue.
- In a schedule S1, if two different transactions are trying to read/write same data items in any of the conflict modes (say, Read-Write, Write-Read, Write-Write), then they cannot be permitted to execute in any order.
- In S1, if T2 reads X first and T1 writes X, then another schedule S2 is not equivalent to S1 if T1 writes X first and then T2 reads X. Here the order is important.
- In S1, if T2 writes X first and T1 reads X, then another schedule S2 is not equivalent to S1 if T1 reads X first and T2 writes X. Here, the order is important.
- In S1, if T2 writes X first and T1 writes X, then another schedule S2 is not equivalent to S1 if T1 writes X first and T2 writes X. Here, the order is important because the latest write overwrite the old one.
- If T1 read/write X and T2 read/write Y in schedule S1, then any different order in S2 is equal.
In the table given below;
Ins is Instruction.
R1(X) is Read X in transaction T1.
R2(X) is Read X in transaction T2.
W1(X) is Write X in transaction T1.
W2(X) is Write X in transaction T2.
Schedule S1
|
Schedule S2
|
Equivalent or not
|
Ins
1: R2(X);
Ins
2: W1(X);
|
Ins
1: W1(X);
Ins
2: R2(X);
|
S2 is not
equivalent to S1
|
Ins
1: W1(X);
Ins
2: R2(X);
|
Ins
1: R2(X);
Ins
2: W1(X);
|
S2 is not
equivalent to S1
|
Ins
1: R2(X);
Ins
2: W1(X);
|
Ins
1: R2(X);
Ins
2: W1(X)
|
S2 is equivalent
to S1
|
Ins
1: W2(X)
Ins
2: W1(X)
|
Ins
1: W1(X)
Ins
2: W2(X)
|
S2 is not
equivalent to S1
|
Ins
1: W2(X)
Ins
2: W1(X)
|
Ins
1: W2(X)
Ins
2: W1(X)
|
S2 is equivalent
to S1
|
Conflict
- We say that Ii and Ij conflict if they are operations by different transactions on the same data item, and at least one of these instructions is a write operation.
Conflict equivalent
- If a schedule S1 can be transformed into a schedule S2 by a series of swaps of non-conflicting instructions, we say that S1 and S2 are conflict equivalent.
If we are able to swap the instructions
in schedule S1 to form another schedule S2, and S1 and S2 produces same
consistent database then we say that the schedules are conflict equivalent.
Conflict serializable
- A schedule S1 is said to be conflict serializable if it is conflict equivalent to a serial schedule.
Example:
Find whether the following schedule
is conflict serializable or not?
Schedule S1
|
||
Time
|
Transaction T1
|
Transaction T2
|
1
2
3
4
5
6
7
8
|
1: read(A);
2: write(A);
3: read(B);
4: write(B);
|
1: read(A);
2: write(A);
3: read(B);
4: write(B);
|
In schedule S1, the instructions of
T1 and T2 are interleaved. Can we execute schedule S1 as it is? Yes. It can be
done only when S1 should be equivalent to some serial schedule. Let us use conflict
serializability to find if there is any equivalent serial schedule.
We have to swap non-conflicting
instructions of S1 until we reach a serial schedule. This has to be done with
immediate next or previous instruction in a schedule.
Can we swap the instruction 2 of T1 with
1 of T2? NO. Why? Both instructions are conflict with each other. They both are
trying to access the same data item A.
Can we swap the instruction 3 of T1
with 2 of T2? YES. Why? The instructions Read-Write may be conflict but they
are trying to access different data items. Hence, not conflict and permitted.
We can do series of swaps as follows
to arrive at a serial schedule S2;
Schedule S1
|
||
Time
|
Transaction T1
|
Transaction T2
|
1
2
3
4
5
6
7
8
|
1: read(A);
2: write(A);
3: read(B);
4: write(B);
|
1: read(A);
2: write(A);
3: read(B);
4: write(B);
|
Result schedule
|
Action Taken
|
Permitted?
|
Serial?
|
||||||
-
|
Read(B) of T1
swapped with Write(A) of T2
|
YES
Reason:
Non-conflict
|
NO
Reason:
instructions are interleaved
|
||||||
-
|
Read(B) of T1
swapped with Read(A) of T2
|
YES
|
NO
|
||||||
-
|
Write(B) of T1
swapped with Write(A) of T2
|
YES
|
NO
|
||||||
-
|
Write(B) of T1
swapped with Read(A) of T2
|
YES
|
YES
T1 then T2 is the
serial order
|
Final answer: schedule S1 is conflict serializable to the serial schedule T1-T2. that is, the concurrent schedule S1 is equivalent to executing T1 first then T2.
**************
Go to Transaction Management in DBMS page
Go to Advanced DBMS concepts page
No comments:
Post a Comment