Showing posts with label Serializability. Show all posts
Showing posts with label Serializability. Show all posts

Saturday, November 18, 2017

Conflict serializability in database Transaction management

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?

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);
-
Read(B) of T1 swapped with Write(A) of T2
YES
Reason: Non-conflict
NO
Reason: instructions are interleaved

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);
-
Read(B) of T1 swapped with Read(A) of T2
YES
NO

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);
-
Write(B) of T1 swapped with Write(A) of T2
YES
NO

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);
-
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.

**************





Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery