Quick Contact

    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
    Conflict Serializable Schedule
    Solution

    Let us create a precedence graph.

    Conflict Serializable Schedule

    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.

    Conflict Serializable Schedule
    Solution

    Let us create a precedence graph.

    Conflict Serializable Schedule

    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:

      1. 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.

    Conflict Serializable Schedule

    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.

      1. 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.

    Conflict Serializable Schedule

    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.

    1. 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.

      Conflict Serializable Schedule

      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.

    1. 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.

    2. 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.

    3. 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

    Copyright 1999- Ducat Creative, All rights reserved.