Schedule in DBMS

 Schedule

( Meaning:- program/event/task:-, a plan for carrying out a process or procedure, giving lists of intended events and times. )

    • A series or set of instructions that perform specific operations.
    • Maintain the order of the operation according to time in each transaction.

 Example: Schedule involving two transactions T1 and T2.

T1

T2

R(A)

W(A)

R(B)

W(B)

R(A)

R(B)

In this example, r and w are read and write operations which perform by schedules and A and B are databases.

================================================ 

Serial Schedules:

In serial schedules,

·         All the transactions execute serially one after the other.

·         When one transaction executes, no other transaction is allowed to execute.

 

Example: Consider the following schedule involving two transactions T1 and T2.

T1

T2

R(A)

W(A)

R(B)

commit

 

W(B)

R(A)

R(B)

 

Commit

 

 


here R(A) denotes that a read operation is performed on some data item ‘A’.

This is a serial schedule since the transactions perform serially in the 

order T1 —> T2

==============================================================================

 

1.    Non-Serial Schedule:
In non-serial schedules,

  • ·         Multiple transactions execute concurrently.
  • ·         Transactions are interleaved (mix ).
  • ·         Operations of all the transactions are interleaved or mixed with each other.
  • ·         It creates a concurrency problem.
  • ·         Other transaction proceeds without waiting for the previous transaction to complete.

  Example-01:






In this schedule,

·         There are two transactions T1 and T2 executing concurrently.

·         The operations of T1 and T2 are interleaved.

·         So, this schedule is an example of a Non-Serial Schedule.

 

Example-02:

 







In this schedule,

·         There are two transactions T1 and T2 executing concurrently.

·         The operations of T1 and T2 are interleaved.

·         So, this schedule is an example of a Non-Serial Schedule.

 

These are two types A. Serializable and B. Non-Serializable Schedule.


============================================================

 

A. Serializable:

  • Transaction to execute concurrently without interfering with one another.
  • It identifies which schedules are correct when executions of the transaction have to interleave their operations.

·         A non-serial schedule will be serializable if its result is equal to the result of its transactions executed serially.

·         This is used to maintain the consistency (uniformity/stability) of the database.

·         Since concurrency is allowed in this case thus, multiple transactions can execute concurrently.

  • Helps in improving both resource utilization and CPU throughput (flow capacity).  
  • A non-serial schedule will be serializable if its result is equal to the result of its transactions executed serially.



  • These are of two types:

    1. Conflict Serializable:
    A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Two operations are said to be conflicting if all conditions satisfy:

    ·                 They belong to different transactions

    ·                They operate on the same data item

    ·                At Least one of them is a written operation

     

    2.  View Serializable:
    A Schedule is called view serializable if it is view equal to a serial schedule (no overlapping transactions). A conflict schedule is a view serializable but if the serializability contains blind writes, then the view serializable does not conflict with serializable.

     ==========================================

    b.     Non-Serializable:
    A non-serial schedule will be serializable if its result is equal to the result of its transactions executed serially.





     

    The non-serializable schedule is divided into two types, Recoverable and Non-recoverable Schedules.

     

    Recoverable Schedule:
     Schedules in which transactions commit only after all transactions whose changes they read commit are called recoverable schedules.

     In other words, if some transaction Tj is reading value updated or written by some other transaction Ti, then the commit of Tj must occur after the commit of Ti.

    Example – Consider the following schedule involving two transactions T1 and T2.

     

    T1

    T2

    R(A)

    W(A)

    W(A)

    R(A)

    commit

    commit

    This is a recoverable schedule since T1 commits before T2, which makes the value read by T2 correct.

    There can be three types of recoverable schedules:


    Cascading (flow) Schedule:
  • Also called Avoids cascading aborts/rollbacks (ACA).

    When a failure in one transaction leads to the rolling back or aborting of other dependent transactions, then such scheduling is referred to as Cascading rollback or cascading abort.  Example:




     

    Cascade less Schedule:
    Schedules in which transactions read values only after all transactions whose changes they are going to read commit are called cascade-less schedules.

    Avoids that a single transaction abort leads to a series of transaction rollbacks.

    A strategy to prevent cascading aborts is to disallow a transaction from reading uncommitted changes from another transaction in the same schedule.

    In other words, if some transaction Tj wants to read value updated or written by some other transaction Ti, then the commit of Tj must read it after the commit of Ti.

    Example: Consider the following schedule involving two transactions T1 and T2.

     

    T1

    T2

    R(A)

    W(A)

    W(A)

    commit

    R(A)

    commit

     

    This schedule is cascading. Since the updated value of A is read by T2 only after the updating transaction i.e. T1 commits.

     

    Strict Schedule:
    A schedule is strict if for any two transactions Ti, Tj, if a write operation of Ti precedes a conflicting operation of Tj (either read or write), then the commit or abort event of Ti also precedes that conflicting operation of Tj.
    In other words, Tj can read or write updated or written values of Ti only after Ti commits/aborts.

    Example: Consider the following schedule involving two transactions T1 and T2.

     

    T1

    T2

    R(A)

    R(A)

    W(A)

    commit

    W(A)

     

    commit

    This is a strict schedule since T2 reads and writes A which is written by T1 only after the commitment of T1.

     

    Non-Recoverable Schedule:
    Example: Consider the following schedule involving two transactions T1 and T2.

    T1

    T2

    R(A)

    W(A)

    W(A)

    R(A)

    commit

    abort

    T2 read the value of A written by T1 and committed. T1 later aborted, therefore the value read by T2 is wrong, but since T2 committed, this schedule is non-recoverable.

    Note – It can be seen that:

    1. Cascade-less schedules are stricter than recoverable schedules or a subset of recoverable schedules.

    2.    Strict schedules are stricter than cascade-less schedules or are a subset of cascade-less schedules.

    3.    Serial schedules satisfy constraints of all recoverable, cascade less, and strict schedules and hence are a subset of strict schedules.

     

    Example: Consider the following schedule:

    S: R1(A), W2(A), Commit2, W1(A), W3(A), Commit3, Commit1

    Which of the following is true?
    (A) The schedule is viewed as a serializable schedule and a strict recoverable schedule
    (B) The schedule is the non-serializable schedule and strict recoverable schedule
    (C) The schedule is a non-serializable schedule and is not a strict recoverable schedule.
    (D) The Schedule is the serializable schedule and is not a strict recoverable schedule

    Solution: The schedule can be re-written as:-

     

    T1

    T2

    T3

    R(A)

    W(A)

    Commit

    W(A)

    W(A)

    Commit

    Commit

    First of all, it is a view serializable schedule as it has a view equal serial schedule T1 —> T2 —> T3 which satisfies the initial and updated reads and final write on variable A which is required for view serializability. Now we can see there is a write–write pair done by transactions T1 followed by T3 which is violating the above-mentioned condition of strict schedules as T3 is supposed to do write operation only after T1 commits which are violated in the given schedule. Hence the given schedule is serializable but not strict recoverable.
    So, option (D) is correct.

     ====================================================

Post a Comment

0 Comments