
Quick Contact
DBMS Tutorial
- DBMS Tutorial
- What is Database Management System (DBMS)?
- Components of DBMS
- Applications of DBMS
- Three Schema DBMS Architecture
- Difference between DBMS and RDBMS?
- Difference between File Oriented System and DBMS
- Types of Data Models
- DBMS Schema and Instances
- Data Independence and Data Abstraction
- Database Users and Administrator
- DBMS Languages and Interfaces
DBMS ER Model
DBMS Relational Data Model
DBMS Normalization
Conflict Serializable Schedule
Given non-serial schedules can be transformed into a serial schedule by changing its non-conflicting operations, then it is known as a conflict serializable schedule.
Conflicting Operations
Two instructions are said to be conflicting if they satisfy the following three conditions:
- They belong to different transactions.
- They access the same data item.
- In any case, one of the operations is a write operation.
Conflict Equivalent Schedule
Two schedules S and S^’ are said to be conflict equivalent, if, by a series of swap of non-conflicting instructions, S gets transformed into S‘.
Conclusion:A concurrent schedule S is said to be conflict serializable if it is conflict equivalent to some serial schedule S‘.
Examples of a Conflict Serializable Schedule
Schedule 1
Read and Write Instruction for T1 and T2
T1 | T2 |
---|---|
read (P); | |
write (P); | |
read (P) | |
write (P); | |
read (Q); | |
write (Q); |
The read (Q) and write (Q) instructions of T1 can be swapped with read (P) and write (P) instructions of T2, resulting in an equivalent schedule 2 (shown below), which is a serial.
Schedule 2
Conflict Serializable Schedule
T1 | T2 |
---|---|
read (P); | |
write (P); | |
read (P) | |
write (P); | |
read (Q); | |
write (Q); |
Thus, the non-serial schedule 1, is a conflict serializable schedule, since it is conflict equivalent to a serial schedule 2.
Examples of a Non-Conflict Serializable Schedule
Schedule 3
Non-Conflict Serializable Schedule
T1 | T2 |
---|---|
read (P); | |
read (P); | |
write (P); | |
write (P); | |
read (Q); | |
write (Q); |
No swapping of non-conflicting instructions will result in a serial schedule. Thus, schedule 3 is not a conflict serializable schedule.
Testing the Conflict Serializability
The precedence graph is also called a serialization graph, and the conflict graph is utilized to test conflict serializability of a schedule within the circumstances that design the putting of concurrency control in the databases.
It is also called a directed graph G=(V,E), which includes a pair of a collection of nodes V= {V1,V2,V3….Vn } and a collection of directed edges E= {E1,E2,E3….Em }where the collection of nodes V is testing to recover identical information attribute among the transactions of a schedule, and the selection of edges E has measured connections between a collection of two nodes.
Nodes: In the graph, for every transaction, Tp the graph consists of an individual node. Therefore, the schedule of a precedence diagram, and the total amount of transactions, would be equal to the total amount of nodes.
Edges: An edge is measured connections between a set of two different transactions Tq and Tr, and it’s displayed in the format Tq →Tr, where Tq is the starting of the edge, and Tr is the ending.
Algorithm for testing Conflict Serializability of a schedule
- Make a node T for every transaction participating in schedule S in the precedence graph.
- For every condition in schedule S create an edge Tp → Tq in the precedence graph if a Transaction Tq implements a read-item (Z) after Tp implements a write-item (Z). This is a read write conflict.
- For every condition in schedule S create an edge Tp → Tq in the precedence graph if a Transaction Tq implements a write-item (Z) after Ti implements a read-item (Z). This is a write read conflict.
- For each condition in schedule S make an edge Tp → Tq in the precedence diagram. If a Transaction, Tq implements a write-item (Z) after Tp implements a write-item (Z). This is a write write conflict.
- Whether that there is no cycle in the precedence structure, additionally, the schedule S is serializable.
Example

Solution
Let us create a precedence graph.

In the above precedence diagram, by subsequent correspondingly to the method, transaction Tp executes reads A before transaction Tq executes writes A. Therefore the first arrow directed from Transaction Tp towards Transaction Tq and Transaction Tq reads B before Transaction Tp writes B, therefore the second arrow directed from Transaction Tq towards transaction Tp.
Because from the above precedence graph, it is clear that the graph is cyclic. Thus, schedule S is a not-conflicted serializable.

Solution
Let us create a precedence graph.

In the above precedence graph, by subsequent correspondingly to the method, Transaction Tp executes reads A before transaction Tq executes writes A. Therefore the first arrow directed from Transaction Tp towards Transaction Tq and Transaction Tq reads B before Transaction Tr writes B, therefore the second arrow directed from Transaction Tq towards Transaction Tr and then the Transaction Tp reads C before Transaction Tr writes C, accordingly the third arrow directed from Transaction Tp towards Tr.
Because from the above precedence graph, it is clear that the graph is acyclic. Thus, schedule S is a conflicted serializable.
View Serializable Schedule
The concurrent schedule is viewing serializable, whether it is a view equivalent to the serial schedule.
Each conflict serializable schedule is also a view serializable, except the opposite is not true.
View Equivalent
Two schedules S1 and S2 are view equivalent if both fulfilled the subsequent conditions:
-
-
Initial Read
The initial read of both the schedules may be a similar transaction. Assume two schedules S1 and S2. Whether the schedule S1, given a transaction T1 is read the data element P, therefore, in S2, transaction T1 can also read P.
-

There are two schedules, which are view equivalent. T1 completes an initial reading instruction in S1, and in S2, it is also achieved by T1.
-
-
Updated Read
During a schedule S1, given the transaction, Ti is reading the data element P that is updated by transaction Tj. Therefore, in schedule S2 additionally, Ti can read data element P, which is updated by Tj.
-

The above two schedules are not viewed equally, therefore, in S1, transaction T3 is reading P updated by transaction T2, and in S2, the transaction T3 is reading P updated by T1.
-
Final Write
The final write should be similar to both the schedules. Whether a schedule S1, given a transaction, T1 updates data element P; finally therefore in schedule S2, final write transaction T1 can also complete instructions.
There are two schedules that are view equal since final write instructions in S1 are ended by T3, and in S2, the final write instructions are correspondingly ended by T3.
View Serializable
This schedule is view serializable, whether that schedule is view equivalent to the serial schedule.
Example
Schedule S1 (Non-Serial Schedule)
Time | Transaction T1 | Transaction T2 |
---|---|---|
T1 | Read (P) | |
T2 | Write (P) | |
T3 | Read (P) | |
T4 | Write (P) | |
T5 | Read (Q) | |
T6 | Write (Q) | |
T7 | Read (Q) | |
T8 | Write (Q) |
Schedule S2 (Serial Schedule)
Time | Transaction T1 | Transaction T2 |
---|---|---|
T1 | Read (P) | |
T2 | Write (P) | |
T3 | Read (Q) | |
T4 | Write (Q) | |
T5 | Read (P) | |
T6 | Write (P) | |
T7 | Read (Q) | |
T8 | Write (Q) |
Let us check the three conditions of view serializability.
-
Initial Read
Whether the S1 schedule, the T1 transaction initial reads the data element P. During schedule S2, further transaction T1 initial reads the data element P.
Now, test for Q. During a schedule S1, the T1 transaction initial reads the data element Q. Whether a schedule S2 also the initial read instructions on data element Q is implemented by T1.
We tested for both the data elements P and Q, and the initial read condition is fulfilled in both schedule S1 and S2.
-
Updated Read
Whether a Schedule S1, transaction T2 reads the value of P, which is explicit by transaction T1. In Schedule S2, the similar transaction T2 reads the data element P following T1 updates it.
Now test for Q. In Schedule S1, transaction T2 reads the value of Q, which is explicit by T1. In the schedule S2, the similar transaction T2 reads the value of data element Q subsequent T1 writes it.
An update read condition is further fulfilled for the two schedules S1 and S2.
-
Final Write
Whether the transaction T2 ends a schedule S1, the final write instructions on data element P. In the schedule, S2 further transaction T2 implements the final write instruction on P.
Now, test for data element Q. Given a schedule S1, the final write instruction on Q is ended by the T2 transaction. In schedule S2, a final write instruction on Q is ended by the T2.
We tested for the two data elements P and Q, and the final write condition is also fulfilled for twain the schedule S1 and S2.
Note: Therefore, all the three conditions are satisfied in this instance, which represent schedule S1, and S2 are view equivalent. Further, we understand that schedule S2 is the serial schedule of S1, and therefore, we can tell that S1 schedule is the view serializable schedule.
Enroll Yourself in Live Training: DBMS Training