DATABASE

MANAGEMENT
SYSTEM
CONTENTS

Schedules
Serial Schedules
Non-serial Schedules
Conflicting Operations
Concurrency
Serializability
Serializable Schedules
Conflict Serializabilty
View Serializability
SCHEDULE

A series of operation from one transaction to another transaction is known

as schedule. It is used to preserve the order of the operation in each of the
individual transaction.
In other words we can say that a chronological execution sequence of a
transaction is called a schedule.
When there are multiple transactions that are running in a concurrent
manner and the order of operation is needed to be set so that the operations
do not overlap each other, Scheduling is brought into play and the
transactions are timed accordingly.
EXAMPLE OF SCHEDULE

T1 T2 T1 T2
R(X)
R(X)
R(Y)
W(X)
W(X)
R(Y) R(Y)
R(Y)
R(X) R(X)
W(Y) W(Y)

S1
S2
TYPES OF SCHEDULE
On the basis of order of execution it may be of two types
⚫ Serial Schedule
⚫ Non-Serial Schedule
On the basis of recoverability it may be of four types:
⚫ Recoverable Schedules
⚫ Non-Recoverable Schedules
⚫ Cascadless Schedule
⚫ Strict Schedules
On the basis of serializability it may be of two types
⚫ Conflict Serializable Schedule
⚫ View Serializable Schedule
SERIAL SCHEDULE
The serial schedule is a type of schedule where one transaction is
executed completely before starting another transaction.
In the serial schedule, when the first transaction completes its
cycle, then the next transaction is executed.
For the below example T1,T2 and T2,T1 are two serial
schedules.
The possible combinations of execution are:-
R1W1R2W2 R2W2R1W1
R1R2W1W2 T1 R1R2W2W1
T2
R2R1W2W1 R2R1W1W2
R1 R2
W1 W2
NON-SERIAL SCHEDULE
If interleaving of operations is allowed, then there will be
non-serial schedule.
It contains many possible orders in which the system can
execute the individual operations of the transactions.
Non-serial schedule also known as concurrent schedule.
The possible combinations of execution are:-
R1W1R2W2 R2W2R1W1
R1R2W1W2 R1R2W2W1
R2R1W2W1 R2R1W1W2
T1 T2

R1 R2
W1 W2
FIND OUT THE SERIAL SCHEDULES AND
NON-SERIAL SCHEDULES?
CONTINUE…
ADVANTAGES AND DISADVANTAGES OF SERIAL SCHEDULE
Advantages :-
⚫ It always gives guarantee for data consistency.

Disadvantages:-
⚫ Limits Concurrency.
⚫ Causes CPU waste .
⚫ Low response time and low throughput could be possible.
⚫ Smaller transactions may need to wait long.
ADVANTAGES AND DISADVANTAGES OF NON-SERIAL SCHEDULE

Advantages:-
⚫ Reduce waiting time.
⚫ Improve response time and throughput.

Disadvantages:-
⚫ Possible data inconsistency.
⚫ Some time too much context switching.
NUMBER OF POSSIBLE SCHEDULES

If we have T1, T2, T3……Tm transaction and N1,N2,N3…..Nm operations respectively.

Then number of serial schedules will be m!
For example we have 2 Transaction T1 and T2 then the number of serial schedules will be
2!=2.
T1,T2 and T2, T1
For example we have 3 Transaction T1, T2 and T3 then the number of serial schedules will
be 3!=6
⚫ T1,T2,T3
⚫ T1,T3,T2
⚫ T2,T1,T3
⚫ T2,T3,T1
⚫ T3,T1,T2
⚫ T3,T2,T1
CONTINUE…

Total number of schedules will be:

(N1+N2+N3+…..+Nm)!/(N1!*N2!*N3!*……*Nm!)
Now we can calculate the non serial schedules. It will be:
Total number of schedules –number of serial schedules;
for the below example total number of schedules:= (2+2)!/2!*2! = 4!/4 =6
Number of serial schedules will be :- m! = 2!= 2
Number of non-serial schedules will be :- 6 – 2 = 4

T1 T2

R1 R2
W1 W2
CONFLICTING OPERATIONS
A pair of operations is said to be conflicting with each other if and only if they holds following
three conditions:-
⚫ They must belong to different transactions
⚫ Both the operations are accessing the same data item.
⚫ At least one of the operation must be write operation.

For example we have the schedule:

S: r1(x) w2(x) r1(y) r2(y)
CONFLICTING OPERATIONS
A pair of operations is said to be conflicting with each other if and only if they holds following
three conditions:-
⚫ They must belong to different transactions
⚫ Both the operations are accessing the same data item.
⚫ At least one of the operation must be write operation.

For example we have the schedule:

S: r1(x) w2(x) r1(y) r2(y)

1 1
2 1 3

2
 CONTINUE…
So for the below example we find out only one conflicting operation which is r1(x) w2(x).
S: r1(x) w2(x) r1(y) r2(y)

• Hence for any schedule only 3 type of conflicting operations are possible . They are:
• RW
• WR
• W W
On the basis of recoverability schedule may be of four
types:
⚫ Recoverable Schedules
⚫ Non-Recoverable Schedules
⚫ Cascadless Schedule
⚫ Strict Schedules
R1(x),R2(x),R1(z),R3(x),R3(y),W1(x),C1,W3(y),C3,R2(
y),W2(z),W2(y),C2;
⚫ Strict Schedule
R1(x),R2(x),R1(z),R3(x),R3(y),W1(x),W3(y),R2(y),W2(
z),W2(y),C1,C2,C3;
⚫ Not Recoverable Schedule
R1(x),R2(z),R3(x),R1(z),R2(y),R3(y),W1(x),C1,
W2(z),W3(y),W2(y),C3,C2;
⚫ Cascade-less Schedule
R1(x),W1(x),R2(x),R1(y),R2(y),W2(x),W1(y),A1,A2
⚫ Recoverable Schedule
R1(x),W1(x),R2(x),R1(y),W2(x),C2,A1;
⚫ Non Recoverable/irrecoverable/unrecoverable Schedule
R1(x),R2(x),W1(x),R1(y),W2(x),C2,W1(y),C1;
⚫ Cascade-less Schedule
CONCURRENCY
Data concurrency is the ability to allow multiple users to affect multiple transaction within a
database. Simply, data concurrency allows multiple users to access data all at the same time.This is
one of the main properties that separates a database from other forms of data storage, like
spreadsheets.
Concurrency Control in Database Management System is a procedure of managing simultaneous
operations without conflicting with each other. It ensures that Database transactions are performed
concurrently and accurately to produce correct results without violating data integrity of the
respective Database.
Advantages of Concurrency:-
⚫ Reduced waiting time, response time or turn around time.
⚫ Increased throughput or resource utilization.
Disadvantages of Concurrency:-
⚫ When multiple transactions are executed concurrently than some times database may become
inconsistent.
⚫ Interleaving of instruction between transactions may also lead to many problems due to which
concurrency control is required.
PROBLEMS WITH CONCURRENCY
When multiple transactions execute concurrently in an uncontrolled or unrestricted manner,
then it might lead to several problems. These problems are commonly referred to as
concurrency problems in database environment.
The five concurrency problems that can occur in database are:
⚫ Temporary update problem
⚫ Lost update problem
⚫ Incorrect summary problem
⚫ Unrepeatable read problem
⚫ Phantom read problem
 TEMPORARY UPDATE PROBLEM
Temporary update occurs when one transaction updates a database item and then transaction fails for
some reason. The updated database item is accessed by another transaction before it is changed back to
the original value.
This problem is also known as dirty read problem.
Example is as follows:-

In the example, if transaction 1 fails for

some reason then X will revert back to its
previous value. But transaction 2 has
already read the incorrect(uncommitted)
value of X.
LOST UPDATE PROBLEM

In the lost update problem, update done to a database item by a transaction is lost as it is
overwritten by the update done by another transaction.
In other words, if transactions T1 and T2 both read a record and then update it, the effects of
the first update will be overwritten by the second update.
Example is as follows:-

In this example, transaction 1

changes the value of X but it gets
overwritten by the update done by
transaction 2 on X. Therefore, the
update done by transaction 1 is lost.
INCORRECT SUMMARY PROBLEM

When one of the transactions is checking on aggregate summary function while other
transactions are updating then this problem is called incorrect summary problem.
T1 T2
Sum=0;
Example is as follows:-
Read_item(A);
Sum=Sum+A;
.
.
In this example, transaction 1 reads .
the value of P but it gets overwritten Sum=Sum+P;
.
by the update done by transaction 2 . read_item(P)
on P. Therefore, the access done by P=P+100;
transaction 1 is incorrect for P data write_item(P)
C
item.
.
Sum=Sum+Z;
AVG();
UNREPEATABLE READ

The unrepeatable read problem occurs when two or more read operations of the same
transaction read different values for the same variable..
Unrepeatable read problem is also known as inconsistent retrievals problem.
Example is as follows:-

In this example, once transaction 2

reads the variable X, a write
operation in transaction 1 changes
the value of the variable X. Thus,
when another read operation is
performed by transaction 2, it reads
the new value of X which was
updated by transaction 1.
PHANTOM READ PROBLEM

The phantom read problem occurs when a transaction reads a variable once but when it tries to
read that same variable again, an error occurs saying that the variable does not exist.
Example is as follows:-

In this example, once transaction 2

reads the variable X, transaction 1
deletes the variable X without
transaction 2’s knowledge. Thus,
when transaction 2 tries to read X, it is
not able to read it.
THANKS