20 Schedules

SCHEDULES
AGENDA
• Schedules,
• Serializability (Conflict and View),
Schedules
• Schedule - a sequences of instructions that specify the
chronological order in which instructions of concurrent
transactions are executed
- a schedule for a set of transactions must consist of all
instructions of those transactions
- must preserve the order in which the instructions appear in
each individual transaction.
• A transaction that successfully completes its execution
will have a commit instructions as the last statement
- by default transaction assumed to execute commit
instruction as its last step
• A transaction that fails to successfully complete its
execution will have an abort instruction as the last
statement
Scheduling of Transactions
• 1.Complete Schedule: A schedule that contains
either an abort or a commit for each transaction
whose actions are listed in it is called a complete
schedule.
•
• 2.Serial Schedule:
• Each serial schedule consists of a sequence of
instructions from various transactions, where the
instructions belonging to one single transaction
appear together in that schedule. If the actions of
different transactions are not interleaved , we call
that schedule a serial schedule.
Schedule 1
Schedule 2
• 3.Non-Serial Schedule : A schedule in
which the operation from a set of
concurrent transaction are interleaved is
called a non-serial schedule .
T1 T2
A=A+100
A=A*7.06
B=B-100
B=B*7.06
• 4.Equivalent Schedule:
• For any database state the effect (on the set of
objects in the database) of executing the first
schedule is identical to effect of executing the
second schedule.
• Both schedule are equivalent
T1 T2 T1 T2
A=A+100 A=A+100
B=B-100 A=A*7.06
• A) B)
A=A*7.06 B=B-100
B=B*7.06
B=B*7.06
Schedule 3
Schedule 4
• 5.Serializiable Schedule: A non-serial schedule that
is equivalent to some serial execution of transactions
is called a serializiable schedule.
• For example schedule-3 is serializable schedule,
which is equivalent to schedule-1 and schedule-2.
• The objective of serializability is to find non-serial
schedules that allow transactions to execute
concurrently without interfering with one another,
and thereby produce a database state that could be
produced by a serial execution.
CONFLICTS OF OPERATIONS
• 1.Reading Uncommitted Data(WR Conflict)

• 2.Unrepeatable Reads(RW conflict)
• 3.Overwriting Uncommitted Data(WW Conflict)
Serializability
• Basic Assumption - Each transaction preserves
database consistency.
• Thus serial execution of a set of transactions
preserves database consistency.
• A (possibly concurrent) schedule is serializable if it is
equivalent to a serial schedule. Different forms of
schedule equivalence give rise to the notions of:
1. conflict serializability
2. view serializability
Conflict Serializability
• If a schedule S can be transformed into a schedule S’

by a series of swaps of non-conflicting instructions,
we say that S and S’ are conflict equivalent.
• We say that a schedule S is conflict serializable if it is
conflict equivalent to a serial schedule.
• We need to check the conflicts between two
consecutive operations of two different
transactions in a schedule. Operations upon data
can be read or write. There are two possibilities:
- If two consecutive operations are on different data
items, then they donot conflict i.e, their order of
execution does not matter and we can swap them
without affecting their result.
- If two consecutive operations are on same data items,
then they can conflict i.e their order of execution
matters and we cannot swap them.
• Consider a schedule S in which there are two consecutive
operations Oi and Oj of two transactions Ti and Tj and both
operations refer to the same data item A. Then, there are
following four cases:
1. Oi= read(A) and Oj= read(A). Then, their order does not matter
because same value of A is read by Ti and Tj.
2. Oi= read(A) and Oj= write(A). Then, their order matters. If Oi
comes before Oj then, Oj does not read the value of A written
by Oi. If Oj comes before Oi then, Oi reads the value of A that is
written by Oj.
3. Oi= write(A) and Oj= read(A). Then, their order matters. If Oi
comes before Oj then, Oj reads the value of A written by Oi. If
Oj comes before Oi then, Oj does not read the value of A that
is written by Oi.
4. Oi= write(A) and Oj= write(A). Then, their order matters. If Oi
comes after Oj then, the value of A written by Oi is stored in
database. If Oj comes after Oi then, the value of A written by
Oj is stored in database.
Check whether the given schedule S is conflict
serializable or not-
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) ,
W2(B)
View Serializability
• A schedule is said to be view-serializable if it is view-
equivalent to some serial schedule.
• Any schedule that is conflict-serializable is also view-
serializable, but not vice versa.
• Below is a schedule which is view-serializable but not conflict
serializable.
• Every view serializable schedule that is not conflict serializable

has blind writes.
1.Initial read must be same.
S1 : T1 reads A from Database.

S2 : T1 reads A from T2.
∴ S1 ≠ S2.
• 2. There are two transactions say Ti and Tj, The schedule S1
and S2 are view equivalent if in schedule S1, Ti reads A that has
been updated by Tj, and in schedule S2, Ti must read A from
Tj. i.e. write-read(WR) sequence must be same between S1 and
S2.
• S1 : T3 reads value of A from T2.

S2 : T3 reads value of A from T1.
∴ S1 ≠ S2.
i.e. write-read sequence is not same between S1 and S2.
• 3. Final write operations should be same
between S1 and S2.
• S1 : A is finally updated by T3.

S2 : A is finally updated by T1.
∴ S1 ≠ S2.
• What is a Blind Write ??
• If there is no read operation before writing any
value then it is Blind Write. For Example :
View Serializability
Recoverable Schedules
• Need to address the effect of transaction failures on concurrently
running transactions.
• Recoverable schedule — if a transaction Tj reads a data item
previously written by a transaction Ti , then the commit
operation of Ti appears before the commit operation of Tj.
• The following schedule is not recoverable if T9 commits
immediately after the read
• If T8 should abort, T9 would have read an inconsistent database

state. Hence, database must ensure that schedules are
recoverable.
• A schedule is said to be recoverable, if for each pair of
transaction Ti and Tj such that Tj reads a data item
previously written by Ti, the commit operation of Ti
appears before the commit operation of Tj.
• Both the above schedules are recoverable .

• Schedule1 is recoverable because T2 reads the
value of A updated by T1 and also T1 commits
before T2 which makes the value read by T2
correct. Then T2 can commit itself.
• In schedule2, if T1 is aborted, T2 has to abort
because the value A it read is incorrect.
• In both cases, the database is in consistent
state.
Cascading Rollbacks
Cascadeless Schedules
• Cascadeless schedules—cascading rollbacks
cannot occur; for each pair of transactions Ti and
Tj such that Tj reads a data item previously
written by Ti, the commit operation of Ti
appears before the read operation of Tj.
• Every cascadeless schedule is also recoverable
• 1
• 2
• 3

20 Schedules

Uploaded by

Copyright:

Available Formats

20 Schedules

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

20 Schedules

Uploaded by

Copyright:

Available Formats

SCHEDULES

• 1.Reading Uncommitted Data(WR Conflict)

• If a schedule S can be transformed into a schedule S’

• Every view serializable schedule that is not conflict serializable

S1 : T1 reads A from Database.

• S1 : T3 reads value of A from T2.

• S1 : A is finally updated by T3.

• If T8 should abort, T9 would have read an inconsistent database

• Both the above schedules are recoverable .

You might also like