Testing for conflict serializablity using precedence graph

How to test for conflict serializability of a schedule? Testing conflict serializability using precedence graph, How to draw a precedence graph, What is precedence graph, testing conflict serializability examples

Testing for conflict serializability

Whether a schedule is conflict serializable or not can be determined using a directed graph called precedence graph.

What is precedence graph? It is a directed graph (also called as serialization graph) G with set of nodes N (T₁, T₂, T₃, …, T_n) and set of directed edges E (E₁, E₂, ..., E_m).

• the set of nodes N = the transactions of a schedule S that are trying to access same data item.

• the set of edges E = the set of directed links between two nodes (transactions).

How to construct precedence graph?

Nodes

The total numbers of transactions in a schedule S will be the number of nodes in the precedence graph. For example, if the schedule S has three transactions, then there will be three nodes in the precedence graph.

Edges

An edge is a directed link between two different transactions T_i and T_j and will look something like T_i à T_j. Only tricky point here is that the link head (arrow) will be included if one of the following is True;

• Create a directed edge T_i → T_j, if T_j reads the value of an item Q written by T_i. [Read-Write conflict]

• Create a directed edge T_i → T_j, if T_j writes a value into an item Q after it has been read by T_i. [Write-Read conflict]

• Create a directed edge T_i → T_j, if T_j writes a value into an item Q after it has been written by T_i. [Write-Write conflict]

Example 1

Let us construct the precedence graph for the schedule S given below;

Time	Transaction T1	Transaction T2
1 2 3 4 5 6 7 8 9 10 11 12 13	read(A); A := A – 50; write(A); read(B); B := B + 50; write(B);	read(A); temp := A * 0.1; A := A – temp; write(A); read(B); B := B + temp; write(B);

We have two transactions, hence two nodes namely, T1 and T2 [see figure 1(a)].

Figure 1 - Construction of precedence graph for example 1

A Write(A) instruction (instruction 3) of T1 comes before Read(A) instruction (instruction 7) of T2. That is, T2 reads A that was written by T1. Here, instruction of T1 happens first then T2. So include an edge from T1 to T2 (Green color) [see figure 1(b)].

A Write(B) instruction (instruction 6) of T1 comes before Read(B) instruction (instruction 11) of T2. That is, T2 reads B that was written by T1. Here, instruction of T1 happens first then T2. So include an edge from T1 to T2 (Blue color) [see figure 1(c)].

In the precedence graph, both the edges are directed towards T2. Hence, the final graph is the one given in figure 1(d).

How do we conclude whether schedule S is conflict serializable or not?

Very simple.

• If your precedence graph has no cycle, then the schedule is conflict serializable.

• If your precedence graph has formed a cycle, then the schedule is not conflict serializable.

Our precedence graph above has no cycle in it. Hence, schedule S is conflict serializable and the serial order is T1-T2. That is, concurrent schedule S is equivalent to a serial schedule T1-T2.

Example 2

Is the following schedule S serializable or not?

Time	Transaction T1	Transaction T2
1 2 3 4 5 6 7 8 9 10 11 12	read(A); A := A – 50; write(A); read(B); B := B + 50; write(B);	read(A); temp := A * 0.1; A := A – temp; write(A); read(B); B := B + temp; write(B);

We have two transactions in schedule S, so two nodes in the precedence graph as follows [see figure 2(a)];

Figure 2 - Construction of precedence graph for example 2

T1 reads A before T2 writes A. Hence include an edge from T1 to T2 (Green color) [figure 2(b)].

T2 reads B before T1 writes B. Hence include an edge from T2 to T1 (Red color) [figure 2(c)].

Observe from the figure that a cycle has formed. Hence the schedule S is not conflict serializable.

[You can include edges for the other conflicts also. An edge from T2 to T1 for write A of T2 comes before write A of T1. Another edge from T1 to T2 for write B of T1 occurs before write B of T2. Anyhow, we have included the edges already. So, no need to specify for multiple times]

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

Go to Conflict serializability page

Go to Transactions management in DBMS page

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.

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

Go to Testing for conflict serializability using precedence graph page

Go to Transaction Management in DBMS page

Go to Advanced DBMS concepts page