4.

1
Database Management Systems

UNIT
TRANSACTION
MANAGEMENT

Important Formulae
Transaction Management (1)
’ Transactions
Transactions :
’ Transaction concept Collections of operations that from a single
logical unit of work are called
’A simple Transaction Model A database transactions.
system must ensure proper
execution of transactions despite failures,
’ Storage Structure either the entire
’ Transaction Atomicity and Durability none of it does. transaction executes, or
’ Transaction Isolation A
transaction
is a, unit of
programme
’ Serializability execution that accesses and possibly updates
various data items.
’ Transaction Isolation and
Transaction Isolátion LevelsAtomicity (2) Acid Properties:
’ Implementation of Isolation Acid is a acronym which stands for
Levels
’ Atomicity
Concurrency Control:
’ Lock - Based ’ Consistency
protocols ’ Isolation
’ Multiple Granularity
’ Time Stamp - ’ Durability
Based Protocols (3)
’ Validation - Based Protocols State of transactions
’ Multi The different states of
version Schemes as follows transactions are
Recovery System - Failure
’ Storage Classification (i) Active state
(ii) Partially committed state
’ Recovery and Atomicity
’ Recovery Algorithm (ii) Failstate
’ Buffer Management (iv) Abort state
’ (v) Full committed state
Failure with loss of non
volatile storage ARIES: ARIES as
"Algorithm for Recoveryabbreviated
-’Early lock release and as
operations logical undo exploiting semantics"
and lsolation
’
Remote backup systems Serializability :Serializability is a standard
that ensures the consistency of a schedule

Warning :
XerowPhotocopying of this book is a CRIMINAL Act. Anyone
found guilty is LIABLE to face LEGAL proceedings
Database Management Systems
42
ShortQuestions with Answers
What is a Schedule ?
Q1. What is transaction ? Q4.
Ans : Ans :
Schedule is can have many
Transaction :
A transaction is a set of changes that must
it, each comprising of a number of transact
tasks schedule is a series of actions that instrreueprictoinseosensnt
in
all be made together. It is a program unit whose sequence of execution
exeCutn maN may not change the contents of a Serial schedule :
atabase Transaction is executed as a single unit.
Ê the database waz în consistent state before a It is a schedule in which
ranstion, then after exEcution of the transaction aligned in such a way that one transaction are
asn the databE must be in a consistate executed first when the first transactiontransaction is
n a transaction, database is accessed by two its cycle. then the next transaction iscompletes
executed
operations transaction are ordered one after the other. T
() Read (x
type of schedule is called a serial schedulesa
transactions are executed in serial manner.
Wite (x)
05. Give the state diagram ofa transaction?
Q2. What is ACID properties?
Ans :
Ans : Partialy Comitted
ommited

These are the properties that a transaction

should posses in order to avoid failures during
cOncurent access of a database. ACID is an
Active
acronymn which stands for Atomicity, consistency,
isolation and durability
(i) Atomicity : Failed Aborted

Atomicity ensures that the transaction is

executed completely or not executed at all.
(ü) Consistency : A transaction starts in the active state. When
The data in the database must always be in it finishes its final statement it enters the partially
a consistent state committed state. At this point, the transaction has
(iii) lsolation: completed its execution, but it is still possible that
ismay have to be aborted, since the actual output
Ail the transactions must run in isolation may stillbe temporarily residing in main memory.
from one another. A transaction enters the failed state after the system
(iv) Durability : determines that the transaction can no longer
proceed with its normal execution.
This property ensures that data remains in a
consistent state even after the failure Q6. What is Transaction lsolation ?
Q3. Explain or list different states of trans Ans :
actions ? Transaction processing systems usually allow
Ans: multiple transactions to run concurrently. Allowins
multiple transactions to update data concurrenty
The different states of transactionsare as follouws: causes reveal applications with consistency ot
(1) Active state data, there are two good reasons for allowing
(2) Partially committed state concurrency.
Improved throughput and resourc
(3) Fail state utilization : A transaction consists of maily
(4) Abort state Steps some involve /O £ctivity: other?
(i) Restart involve CPUactivity
(ii) Kill Reduced waiting time: There maysome
mix of transaction running on a System,
(5) Full committed state
short and some long.
Warning : XeroxPhotocopying of this book is a CRIMINAL Act. Anyone found guity is LIABLE to face LEGAL procee
 Database Management Systems
4.3
transaction model ? Q10. What is locking ?
07. What is simple
Ans :
Ans :
blank
The transaction concept using a simple set A lock is a variable associated with a
several accounts and
annlication consistingof database object i.e, the data item locking is a
transactions that access and update those mechanisn of manipulating the data value of lock.
af two Locks
ccounts. Transactions access data using are used when multiple users wants to accéss
operations: a database object other transactions frorm accessing
Read (x): the data items which are locked currently. The locks
Which transfers the data item x from the are granted to transaction by a component of
database to avariable, also called x, in a database management system called the lock
buffer in main memory belonging to the manager.
transaction that executed the read operation Types of lock
Write (x): (1) Shared lock(s)
Which transfers the value in the variable x (2) Exclusive lock(×)
in the main memory buffer of the transaction
that executed the write to the data item x in Q11. Write a short note on
the database Ans:
Recoverability ?
Q8. Write a short notes on storage structure ? Recoverability:
Ans :
Recoverability is a process where a
To understand how to ensure the automicity committed transaction fails. to execute the read
and durability properties of a transaction, we must instruction on a data item written by aborted
gain a better understanding how the various data transaction. When a transaction TA fails wither
items in the database may be stored and accessed. due to hardware/software failure or due to
internal
As we sam that storage media can be logic error, then the effect of this transaction needs
distinguished by their relative speed, capacity, and to
of
be undone in order to ensure
atomicity. In case
resilence to failure and classified as volatile a non concurrent execution, if a single transaction is
volatile storage. After reviewing of there terms, aborted, then all its dependent transaction must
introducing another class of storage called stable even be aborted.
storage Q12. What is time stamps ?
Volatile storage : Ans :
Information residing in volatile storage does Another category of techniques for the
not usually survive system crashes.
implementation of isolation assigns -each
Non - volatile storage: transaction a time stamp, typically when it begins.
Information residing in non volatile storage For each data item, the system keeps two time
survives system crashes. stamps the read timestamp of a data item holds
the largest timestamp of those transactions that
Stable storage : read the data item. The write time stamp of a data
Information residing in stable storage is never item holds the time stamp of the transaction that
lost. wrote the current value of the data item.
Q9. Write a short notes on Timestamps are used to ensure that transactions
Ans :
serializability ? access each data item in order of the transactions
timestamps if their accesses conflict. When this is
not possible, offering transactions are aborted and
Serializability : restarted with a new timestamp.
Serializability is the classical concurrency Q13. What is two phase locking protocol?
scheme. It ensures that a schedule for
Concurrent transactions is equivalent toexecuting
one that Ans :
executes the transactions serially in some order.
àssumes that all accesses to the database are doneIt One protocol that ensures serializability is
uSing read and write operations. A schedule is the two phase locking protocols this protocol
requires that each transaction issue lock and unlock
"Correct", if we can find a serial schedule that is requests in twophases
"Equivalent" to it.
keroxPhotocopyingof this book is a CRIMINAL Act. Anyonefound guilty is LIABLE to face LEGAL proceedings
Database Management Systems
Grewing phase Q17. Write ashort note on snapshot
A ttansaNCtion mav ohtain tocks but mav not
reiease env ok
Shrinking phase
Ans:
Snapshot isolation is a
concurrency control scheme that has
Isolaton?
particular type o
A transaton mav reease locks hut mav not aceptance in commercial and open gained
Snapshot isolation giving a source wide
htain any new locks
Q14 What is cencrency control sehemes? "snapshot" of the database at the
time
sys
transaction
a tems
Ans
begins its execution. It then
snapshot in complete isolationoperates
from on that
when
ttansactions execute
I4hen sereral
conenth in the database. the consistencv of
transactions. The data values in the
consist only of values written
transactions. This isolation is idealbyfor
concursnapshottent
ate ma n AoN be preseved It is necessary
fo the stm toontroì the interactton
among
control is transactions since they never wait and commi
read-otnevernleyd
che concure: transhons and this
aborted by the concurrency manager. ate
hieed throuch one of a varetv of mechanism
cali nure Otrol schemes Q18. What is failure classification ?
QIS Eain deadiock handling ? Ans :
There are various types of failures that ma.
Asstem s in a deadlock state if there exists occur in a system, each of which needs to be deas
a stot transactions such that every transaction in with in adifferent manner. The folowing types of
the set more. Precisely. there exists a set of waiting failure
transations (T T} such that to is waiting 1. Transaction failure :
tor data item that T, hoids, and T, is waiting for a
data item that T, oids and Tn-l is waiting for a There are two types of errors that may cause
Gata item that in holds. and Tn is waiting for a atransaction to fail
data item that to holds.
Logicalerror :
There are two principal nethods for dealing The transaction can no longer continue with
with the deadiock problem. We can use a deadlock
prevention protocol to ensure that the system will its normal execution because of some internal
Tever enter a deadiock state. Alternatively. we can condition, such as a bad input, data not
aaow thesystem to enter a deadlock state and then found, overflow. or resource limit exceeded.
y to recover by using a deadlock detection ànd
deadock recovery scheme. System error :
Q16. Write a short note on multiversion time This system has èntered an undesirable state
as a result of which a transaction cannot
stamp ordering? continue with its normal execution.
Ans :
2. System crash :
The tiTe stamp ordering protocol can be
extended to a multi version protocol with each There is a hardware malfunction or a bug
transa ct:0. Ti in the ystem, we associate a unique the database software or the operating system t
statc trTie slanp denoted by TS(Ti) The database causes the loss of the content of volatile storay
sysie) aSSigs the ime stamp before the and brings transaction processing to a half.
tÉansaclGn slarts execution with each data item 3. Disk failre :
Q e sequernce ot versins < Q,, Q,.....Qm> is
associated each version Qh contains three data Adisk block closes its content as a result of
fields: either a head crash or failure during a data transfer
Conteat: operation.
It is the value of version Qk. Give
Q19. What is write - write conflicts ?
W - timestamp (Qk): an example ?
It is the timest¡mp of the
Created version Qk.
transaction that Ans:
arises
P- timestamp (Q2) : Write - write conflicts: This conflicts
whichis
when a transaction overwrites an objeci under
It is the largest timestamp of any stillun
that successfully read version Qk.transaction
modified by another transaction,
processing. This is called blind writing
proceedings
Warning: XeroxPhotocopying of this book is a CRIMINAL Act. Anyone found guilty is LIABLE to face
LEGAL
 Database Management Systems
4.5
Example:
Consider there are two employee Pavani Vasavi. They are in: same post and so must receive same
salary. TransactionT, assign asalary of Rs 500/- and transaction T, assign a salary of Rs 1000/-.
Transaction - 1 | Transaction -2
Pavani 500 Waiting
Waiting Vabavi - 1000
Pavani 1000
Vabavi -500 Commit
Hence pavani will have 1000/- and vabavi will have Rs 500/- this situation is called lots
update.
Q20. Distinguish between lock-based concurrency control and optimistic concurrency con-
trol ?

Ans:

Lock - based concumency control Optimistic concurrency control

1. n this approach, the order of the 1. In this approach, a timestamp
conflicting actions that arises is imposed on the ordering
between different transactions are in transactions and the
validation phase checks that all
accordance with order in which the conflicting actions occurred in the
locks are obtained
oitsame order.
2. It is a pessimistic approach to 2. It is an optimistic approach for
control concurency
3. Here the locking protocols ensure concumency control.
3. The serializability order c£n be
serializability by extending the order ensured by using the value of the
of the actions to the transactions
validation timestamp

Warning : Xerox/Photocopying of this book is a CRIMINAL Act. Anyone found guilty is LIABLE to face LEGAL proceedings
 Database Management Systems
46
Essay Questions with Answers
4.1 TRANSACTION CONCEPT A:=A-100;
Q1. Bxplain Tranhs actlon Concept briefly ? Write(A);
Ans : Read(B);
Transaction Concepts: B: = B+100;
Collection of operations that from a single Write(B);
logicalunit of work are called tr¡nsactions". ACID Properties :
For example, transfer of funds from the These are the properties that a
customers checking account to a savings
account is a single operation, however it
should posses in order to avoid failures
concurrent access of a database. ACID transactdurioinn,g
consists of several operations. acronym which stands for atomicity. is pn
It is also essential that all these operations,
occur, or in case of failure non occurs.
Isolation and durability.
(1) Atomicity :
consistency,
It would be acceptable if the checking Atomicity ensures that the
either executed completely ortransaction
account were debited, but the savings i
account were not credited. not executod
at all incomplete
A transcation is a unit a program execution are not valid.
transaction consequences
that accesses and possibly updates various (2) Consistency :
data items. A program contains statements
of form begin transaction and end The data in the database must always be in
transaction. a consistent state. A transaction that is
The transaction consists of all operations carried on aconsistent data should bring the
data to another consistent state after
executed between the begin and end execution.
transaction.
(3) lsolation :
Q2. What is a transaction? Explain ACID
properties ? All transactions must run in isolation from
one another that is every transaction should
Ans : be kept, unaware of the transaction and
Transactions : execute independently. The intermediate
A transactioD is a set of results generated by the transactions should
changes that must not be available to other transactions.
all the made together. It is a programme unit whose
execution may or may not change the contents of (4) Durability :
the a database. This property ensures that data remains in a
Transaction is executed as a single unit if consistent state even after failure. This is
the database was in consistent state before a ensured by loading modified data into disk.
transaction then after execution of the transaction This task is handled by recovery management
also, the database be in a consistent. component of DBMS
In atransaction, database is accessed by two 4.2 TRANSACTION STATE
operations
Q3. Explain different states of transactions
(i) Read (x);
Ans :
(i) Write (x);
The different states of transactions are as follows:
The first one performs the reading operation
of data item from the (1) Active state
database, whereas the
second one performs the writing operation of data (2) Partially committed state
item x to the database consider a transactions Ti
(3) Fail state
which transfers $100 from 'A' account to 'B'
account. This transaction will be as follows. (4) Abort state
Ti=read(A); (5) Full committed state

Warning : XeroxJPhotocopying of this book is a CRIMINAL Act. Anyone found guity is LIABLE to face LEGAL proceeu
4.7 Database Management Systems
4.3
IMPLEMENTATION OF ATOMICITY AND
Active
DURABILITY
Q4. Explain shadow - copy
atomicity and durability ?technique for
Ans :

Partialy
Fail
Shadow - copy Technique:
ommitted There are many technique that are
by recovery employed
atomicity andmanagement component for ensuring
"shadow - copy"durability.
technique.
One such technique is
copies of database calledWhere many duplicate
shadow copies are
created. This technique assumes
ommitt Aborted (i) that
There is onlyone active
time. transactions at any
(ü) Database is
on the disk. nothing but a file which is written
Working of shadow - copy
Kill
restart
technique :
Before performing any sort of
in the modifications
database, it is necessary
FIG: State diagram of a transaction to create a copy of for the
transaction database. entire
A transaction starts in the
this point the transaction has
active state. At The operating system must
completed its that every page of new initially ensure
execution,but it is still possible that it may have disk. Once database is written onto
to be aborted, since.the actual entire database is loaded, only then
possible that it may have to be output may stillbe dptr is updated by the
database system. This
actual output may preclude its aborted, since the now points to the new copy of the database points
completion. successful then becomes the current database copy.which The
orifinal database which then deleted from disk.
(1) Active State : Once the updated obptr is written
The initial state, the the transaction is said to onto the disk
transaction
state while it is executing. stays in this committed
dbptr
(2) Partially dbptr
committed state :
After the final statement has been
(3) Failed : executed
Old data Old data New
After the discovery that base copy
no longer proceed. normal execution can base copy database
copy

(4) Aborted :
After the transaction has be rolled
back and the Figure: Before updata Figure : After Update
database has been restored to its state prior to
the start of the transaction. Shadow copy technique has the ability of
Restart : handlingtwo major issues.
If the (i) Transaction failure issue
transaction was aborted due to (ü)
hardware or software failure, System failure issue
transaction can be restarted such then the (i) Transaction failure issue:
is
considered as a new transaction.transaction The original copy of database remains
Kill : unaffected if the transaction failure occur
If the before updating dbptr
transaction was aborted due to some
internal logical error due to bad input then (ii) System failure issue :
the system can kill the
(5 transactions. The original copy of database remains
Committed state:
After successful completion.
unaffected if the system fails before writing
the updated dptr onto the disk.
Warning :
Xerox/Photocopying of. this book is a CRIMINAL Act. Anyone found guilty is LIABLEto face LEGAL proceedings
Databese Manngement Syatems
Q5, Explaln tn detall aboutthe datn structures DPT thenthe value of Rec LSNis set
current log end, but when the
of ARIES?
to the disk, then it is deleted pae is
Ana: fron the
page table, In additiorn to DPT
Following datastctures are associated with transactions checkpoint log and iy
the logvecords in ARIES record the inforrnation recorda,
record in last LSN field. about the last
(a) log sequence number (LSN)
(b) Page |SN 4.4 CONCURRENT EXECUTIONS
Explain B* tree
(c) Compensation log records Q6.
concurr-ency control locking
with used
(d)
(a)
Check point log record
Log sequence number :
Ans :
example?
suitabl,
In ARIES, everylog recond has anassoclated Concurrency control using B' - tree:
log nequence number (LSN) that is
monotontcally increasing and indicates the Concurrency control using B' tree
address of the logrecord on disk. Each LSN achieved by, can te
rorresponds to a specific change to some (i) Ignoring the structure of index
transaction. In addition, each datapage will
store the LSN of the latest log record
(ii) Considering every individual page as dats
coresponding to change for that page. A log object
record is written for any of the following (iii) Applying some version of 2PL
actions Theresult of employing B* - tree concuneres
0 Updating a transaction (write) control approach is that a high lock çontentiz
() Committing a transaction (commit) exist in the higher level nodes of the tree. Thit
(ni) Aborting a transaction (abort)
because the search process initiates from the rot
node and continues to leaf node by following a
(N) Undoing an update (undo) particular path following two observations must be
(v) Ending a transaction (end) considered while úsing any of the locking protocok
Page LSN: (i Searching is directed by the higher leved
Page LSN is an identifier, which is assigned nodes and the actual data is present in the
leaf node.
to every individual page of the databases.
The value of LSN associated with the log (ii) While inserting a data value, it is necessary
record is stored in the page LSN field of the to acquire an exclusive lock on a node, i
database page by an operation that occurred there is apossibility for a split to propagat?
on that page. Page LSN is capable of back from the modified node to reach the
ensuring idempotent property, whenever root node.
physiological redo operation is present. Before inítiating thesearch process. every
Because if this operation is applied tree node i.e, from root node to the desired lea
repeatediy. it leads to inconsistent result
node must acquire a separate shared locs
(c) Compensation log records : However, it is necessary to ensure that, wne"
These are the specialkind of log records that node acquires a shared lock, the lock acquiredb
perform only redo operation these records its parent lock is released. The purpose of releasing
lock s
are generated, when atransaction performs the lock as sons as child node acquire o
in
the rollback operation . CLR not only act as because the search process cannot propagate
aredo only log record but also as backward direction.
abort log record. operation conservative
While inserting a data value, a 'x'lock
(d) Cbeckpoint log record : locking strategy must be used in which an from
This log record contains the 0s acquired by every node being transvered| the
about dirty page table and listinformation
of active
root node to the actual node. This is because
i.e.
transactions. Dirty page Table (DPT) table split can propagate in the backward direction
acquired
stores the information regarding the pages from modified leaf to roof node. The lock thereis
that are modified in the database buffer. by the parent node is not released if
tothe
Every page isassigned a unique page LSN possibility that the split may propagate lockon
the
and ReclLSN, which helps in identifying log parent node. The process of acquiringacquired by
records that have already been reflected child node and the releasing the lock crabbing.
onto the disk, whenever a page is stored in parent node is called lock coupling or
proceeting
Warning : XeroxPhotocopying of this book ls a CRIMINAL Act. Anyone found gulty is LIABLE to
face LEGAL
 Database Management Systems
4.9 associated
a7 Discuss various anomalies 4.5 SERIALIZABILITY
execution?
with inter leaved Q8. Define serializability. Explainconflict
Ans : serializabilityand view serializability in
Anomalies in inter leaved execution :
detail?
Ans :
Inter leaved transactions result into
abnormal conditions when the actions are on same Serializability:
abiect, which involves at least one write action. Serializability is the classical concurrency
There could be three conflicts. scheme. It ensures that a schedule for executing
Write - Read Confict (WR) concurrent tran sactions is equivalent to on that
(i)
Read- Write Conflict (RW) executes the transactions serially in sorne order (or)
serializability is a standard that ensures the
() Write - Write Conflict (WW) consistency of a schedule. A schedule is consistent
()
Write -Read Conflict (WR): if and only if it is seriazable. A schedule is
OReading Uncommitted Data: Atransaction T2 serializable if it is interleaved transactions produce
could read a database object a that has bèen theresult which is equivalent to the result,produced
modihed by another transaction T1, which has byexecuting individual transaction separately.
not yet been committed such a read is called a The two different types of serializabilty are
dity read. Consider the following schedule (1) Conflict serializability
T1 T2 (2) View serializabilty
RA) (1) Conflict serializability:
WIA) Consider aschedule S1, consisting of two
R(A) successive instructions I, and belonging
W(A) to transactions T, and T, respectively. If I,
RB) and I, refer to different data item then it is
W(B) very'easy to swap these instructions. The
Commit result of swapping these instructions,doesn't
R(B) have any impact on the remaining
W(B) instructions in the schedule. On the other
commit hand if I, and I, refer to same data item
The probiem with this schedule is a
then the following four cases must be
follows: considered.
The transaction T, may write into A that () I,= Read(x), I,= Read(x)
makes the database inconsistent. As long as (iü)
I,overwrites the value with a 'correct' value =Read(x), i,=Write(x)
of A before committing no harm is done. If (ii) =Write(x), I,=Read(x)
Tand T, run in some serial order because (iv) I,=Write(x).1,=Write(x)
T, will not see the temporary Two instructions I, and I, are said to be
inconsistency
in the database. But inter leaved conflicting if and only if.
execution
can lead to an inconsistency as show in
above (1) They represent the operations pertormed by
table. The problem with this schedule is the two different transactions on the same data
value ofa written by T, is read by T, before item.
Thas completed all its changes.
(iü) Read write conflict
(2) At least one among I, and I, is a write
(RW) Or operation.
unrepeatable reads: Consider the following schedule S,
This conflict arises when one T1 T2
transaction
modifies the object that was previously
by another transaction and is still read Read(x)
This is called unrepeatable read. executing. Write(x)
Read(x)
(iii) Write - write conflict
(WW): Wite(x)
This conflict arises when a transaction over Read(y)
writes an object which is modified by another Witely)
transaction still under processing. This is called Read(y)
blind writing. Wnte(y)
proceedings
Warning : LIABLE to face LEGAL
of this book is a CRIMINAL Act. Anyone foud guitty is
Xerox/Photocopying
 Database Management Systems
(2) View Serializaiblity :
Two schedules S. and S consisting of same
2 Cascade less Schedule:
T1 T2
4.10
Set of transactions are said to be view
Read(x)
equivalent, if the following conditions are Read(y)
satisfied
(i) Write(x)
If atransaction TA in schedule S1 performs Read(x)
liie ieddopeiàtion on the initíal value of data
Write(x)
item x then the same transaction in schedule
S1, must also perform the read operation Read(x)
on the initial value of x. Transaction T, writes x that is
(ii) If atransaction TA in schedules S1 reads transaction T,. Transaction T, read
the value x, which was written by is read by transaction T writes x
Suppose at that thi
transactions TB then TA in schedule S1 must point T, fails, T, must be rolled
also read the valuex written by transaction T,is dependent on T,,T, must be back,
rolled since
ba
TB. and since T, is dependent on T,, T,must be
(iüü) If a transaction TA in schedule S1 performs rolled back.
the final write operation on data item x, the 4.7 IMPLEMENTATION OF IsoLATION
same transaction in schedule S1, must also
perform the final write operation on x. Q10. Explain lsolation Levels briefly ?
4.6 RECOVERABILITY Ans :
lsolation Levels :
9. Whatis recoverability ? Explain about
recoverable schedules and cascade less The isolation property is the most often
schedules ? relaxed ACID property in a DBMS.
Ans : This is because to maintain the highest level
Recoeverability: of isolation a DBMS usually acquires locks
on data, which may result in a loss of
Recoverability is a process where a
committed transaction fails to execute the read concurrency, or else implement multiversion
instruction on a data item written by aborted concurrency control, which may require
additional application logic to function
transaction when a transaction T, fails either due correctly.
to hardware/software failure or due to internal logic
error, then the effect of this transaction needs to There are 4 DBMS transaction levels:
be undone in order to ensure atomicity. In case of (a) Serializable read :
concurrent execution, if a single transaction is Serializable transaction assures that:
aborted, then all its dependent transaction must
even be aborted. Select queries issued during transaction
cannot read data that has been modified
(1) Recoverable Schedule: but not yet committed.
Arecoverable schedule is one where for each Other transactions cannot update/after
pair of transaction T, and T, such that if T, to data that has been read by current
readdata item previously written by T:, then transaction until current transaction
the commit operation of T, appears before complete.
the cormmit operation T.
(b) Repeatable read:
T1 T2
Read(x) Repeatable read transaction assures that:
’ Select queries cannot read data that has
Writelx)
Read(x) been modified but not committed.
Readly) Other transactions can update/alter the
data that has been read by current
Suppose after T,read (x) operation, it transaction.
commites and then some how T, fails, so
the transaction T, must be aborted so as to (c) Read Committed :
ensure atomicity. However since T, is Select queries cannot read data that ne
committed and can't be aborted. Hence a been modified but not committed.
situation arrives where it is impossible to -can be
The data read by one transcationbetween
recover. And hence its necessary that T
cormmits before T,. changed by other transaction
individual statements.
Warning : XeroxPhotocopying of this book is a CRIMINAL Act. Anyone found guity is LLABLE toface LEGAL procedi
 (d) Database Management Systems
Read Uncomnnmitte d concurrently. The main purpose of using locks is
Select queries can read rows that to block other transactions from accessing the data
bv have been
modified other transaction but not yet items which are locked currently. The locks are
committed. granted to the transaction by a component of
4.8 TESTING FOR database management system called the lock
Q11. What is Testing for SERALICABILTY manager.
Explain briefly
Ans :
serializability ? Types of locks :
There aretwo types of locks namely
Testing for Serializability : (i) Shared lock
Testing for serializability is done by (ü) Exclusive lock
directed graph, called using a ()
Shared lock:
constructed from scheduleprecedence graph,
The set of edges Shared locks are placed on resources
for which one of consists of all edges T, ’T, a read operation (select) is whenever
these conditions hold shared locks can be performed. Multiple
Texecutes write (Q) before T, executes COurse simultaneously set on a re
read (Q) (i1) Exclusive lock :
(Texecutes
write (Q
read (Q) before Texecutes
Exclusive locks are placed on resour ces
() T executes write (Q) whenever
one
a write operation are
prfomed only
read (Q) before T, executes exclusive lock can be placed on a
resource at a time i.e, the first
acquires an exclusive lock will user whoto
have the sole continue
other user ownership
of the
can acquire an resource, and
( no
Sohedule 1 Schedale 2 on that resource. exclusive lock
Consider following schedule9. Q13. Explain the Lock
briefly ? Based Protocols
T
ead (A) Ans :
A=A-50 Lock Based
read (A)
temp: = A*0.1
Protocals :
Each transaction in a
a lockingsystem should follow
A A- temp a set of rules,
write (A) called
r e A) write (B) when a
the datatransaction
items. may lock protocol,
and unlockindicating
read (B)
each of
B B+50
wte B) Granting Locks:
B:B +temp When a transaction requests a lock on a data
The precedence write (B) item in a particular mode and no other
graph for schedule has a lock on same data transaction
9 is
the look can be item in a conflicting mode,
granted.
Starvation of
granting locks in transaction
following
can be avoided by
manner.
transaction T, requests a lock on When a
4.9 LocK BASED a particular mode a data item Q in
M, the
Q12. Define the PROTOCOLS concurrency
manager grants the lock provided that control
term lock.
Ans :
types of locks ? Explain various (1) There is no other transaction holding a lock
on Q in amode that conflicts
with M.
(2) There is no other transaction that is waiting for
Locks are
Integrdataity lockingof mechanism
the is a used to ensure
data
a lock on Q, and that made its lock
before T,.
users value lock.
wants to access
mechanism of
manipulating
Locks are used when Thus, a lock request will never get blocked
by a lock request that is made later.
Harring: Xerox/Photocopying a multiple
database object
of this book is a
CRIMINAL Act. Anyone found guilty is LIABLE to face LEGAL proceedings
Database Management Systems
4.10TIME STAMP BASED PROTOcOLS Q15. a) What is Thomas write rule? 4.1)
Q14. Explain the time - stamnp ordering
protocol ?
b) Advantages and disadvantages of time
stamp ordering protocol ?
Ans : Ans :
In timestamp based protocols, the system (a) Thomas write rule:
itself tries to detect possible inconsistency during
Thomas write rule modify or
concurrent execution and recovers from it or avoid
it. In it, for every transaction the system executes, basictimestamp ordering Algorithm (BTSO1 improves
the

the system gives the timestamp to that transaction According to Basic timestamp
i.e, it provides a set of timestamps to every Algorithm (BT Algorithm) ordering
transaction Ti by unique time stamp which is When transaction Ti issues READ
denoted by TS (Ti) where TSis time stamp of Ti.
(1)
() If TS(Ti) < WTS(Q), then
operation
TS(TI) : " ROOLBACK Ti
Whenever atransaction begins to execute
that is just prior to its execution it is provided a " RESTART Ti
time stamp. This timestamp may be based a system
stamp which is on () Otherwise
related actual read time
the system time or it may jkst be a counter.
allowed to executes READ operation by
transaction Tiand
R-Time stamp (RTS) and W -time stamp
(WTS): set RTS(Q) = Max(RTS(Q), TS(Ti)
shared we
For every data item which willbe (2) When transaction Ti issues WRITE operation:
have got two timestamps:
If TS(Ti) <RTS(Q), then
W- Time stamp(Q) or WTS(Q),: ()
Write timestamp of data item Q ROLLBACK Ti;
R Timestamp(Q) or RTS(Q): " RESTART Ti
Read -time stamp of data item Q If TS(Ti) < WTS(Q), then
(ü)
W. Timestamp(Q): ROLLBACK Ti
W - timestamp(Q) denotes the largest TS or
timesta mp value of any transaction that RESTART Ti
successfully executes write(Q)
(iüi) Otherwise
R-timestamp(Q):
Allowed to execute the WRITE operation by
R- timestamp(Q) denotes the largest TS or transaction Ti and
timestamp value of any. transaçtion that
successfully executes read(Q) Set WTS(Q) = TS(Ti)
Working of timestamp ordering protocol : (b) Time Stamp ordering protocol :
(1) If T, executes read(x) instru ction then the
following two cases must be considered Advantages:
between the
(i) T,(T) < RTS(x) (1) It ensures conflict serializability
T,(T)> WTS(×) schedules.
(iü)
which is easy
Case --i) T(T,) < RTS(x): (2) It results in a serial schedule
If a transaction T, wants to read initial value of to execute.
A dead lock a
some data time x that had been overwritten by (3) It guarantees freedom from
some younger transaction then, the transaction there are no transactions waiting.
T, cannot perform the read operation. Disadvantages :
Case (ii) T,(T,)e > WTS(×) : ofthe
(1) It doesn't ensure recoverability
If a transaction T, wants to read the value of schedules. restarted
data itemx,that had not been updated then created or1
the transaction can executed the read opera (2) If larger transactions are
repeatedly, due to the execution
tion. Once the value had been read, changes thelarger
occur in the read time stamp value (RTS(x)) conflicting transaction then starvation(i.e.
which is set by the largest valueof RTS(x) and transactions can suffer from
it can never be committed).
T,(T). proceedings
LEGAL
Warning : Xerox/Photocopying of this book lsa CRIMINAL Act. Anyone found guilty is LIABLE to face
4.13 Database Management Systems
4.11VAIDATION BASED PROTOcoLs Multiple Granularity :
ain Validntion Based Protocols Multiple Granularity is the hierarchically breaking up
briefly ? the database into portions which are
Ans and maintaining the track of what to lockable
Validatton Based Protocol: how much to be lock so that it can belockde
and
In optimistic concunency contol techniques, scribed very quickly either to lock a data item
also known as validation or certification or to unlock a data item
techniques, no checking is done while the Example of multiple Gramlartty :
transaction is being executing.
Alse based on Time stamp protocol. It has DB
three phases
Read phase :
During this phase. the system executes
transaction T It reads the values of various
data items and stores them in variable local P

to T
Validation phase:
Transaction T, performs a validation test to
determine whether it can copy to database Suppose a database is divided into files, files
the temporary local variables that hold the are divided
result of wTite operations without into pages, pages are
violation. a records.
causing divided into
1f there is a
Write phase: then a transaction can need to lock a record,
If transaction T, succeeds in is need to easily lock it. But if there
lock a file the
system applies actual updatesvalidation, then
to database, firstly are the records one transaction have to lock
after another, then pages
otherwise system rolls back T,. in that file and
finally the file. So there is a need
Toperform to provide a
validation test, we need to know
when various mechanism for
which is provided by multiplelocking the files also
place. phases of transaction T, took granularity
If we allow a
(1) Start (T): mechanism
only, then to locka file, the for locking records
The time when T, have to lock all records in transaction will
that file one after
(2) Validation (T,): started its execution. another, which is a wastage of time.
If we allow a
The Time when T,
finished its read phase then for a mechanism to locking file only.
for
and started
validation phase. records, it willtransaction
have
lock only
to lock the whole five
(3) Finish (T) : and therefore no other file
The time when T, able to use that file. transaction will be

Finish (T) < startfinished its write phase. So there is a need to

files as well as records provide theby locks for
Since T, completes its(T): granularity). (provided multiple
started, the execution isbefore T,
maintained. serializability order indeed 4.13 RECOVERY & ATOMICITY
Start (T) <Finish (T) < Q18. What is recoverability? Explain
The validation phase of Validation (T) : recoverable schedules and cascadeabout
less
T finishes. T, should schedules ?
occur after
4.12 MuLTIPLE GRANULARCITY Ans :

Q17. Explain multiple Recoeverability :

Ans :
tocol? Granularity locking pro committed
Recoverability is a process where
transaction fails to execute the read
a
instruction on a, data item written by aborted
GranulGranularity
to lock
arity: is the size of transaction when a transaction T,fails either due
to hardware/software failure or due to internal logic
data item allowed error, then the effect of this transaction needs to
Warning : be undone in order to ensure atomicity. In case of

Xerox/Photocopying of this book is a

CRIMINAL Act. Anyone found guilty is LIABLE to face LLEGAL proceedings
Database Management Systems
(1) Transaction failure :
concurrent execution, if a single transaction is
aborted, then all its dependent transaction must Atransaction may fail to execute
even be aborted. operation when either logic errors or its interIde
(1) Recoverable Schedule: are encountered. Logic errors occur
following reasons.
Systdueem to he
erron
A
recoverable schedule is one where for each Incorrect input
pair of transaction T, and T, such that if T, (i)
read dataitem previously written by T:, then Absence of data that is to be
the commit operation of T, appears before
(ii)
(iii) Data stored exceed the capacity
searched
of
the commit operation T.
T1 T2 (2)
limit
System Crash :
stotag
Read(x) It is a condition in which a program
Write(x)
Read(x)
the execution of the functions and
responding tothe request made by other stoyod also halts
the system. System crash may occur
parts
Read(y)
it
hardware error, hardware malfunctioning or due to because
Suppose after T,read(x) operation,
T, fails, so
a software or operating system bug. When the
sort of situations are encountered , then tte
commites and then some how
aborted so as to information stored within the volatile storage m
the transaction T, must be T2 is
ensure atomicity. However since Hence a is lost.
committed and can't be aborted. Disk Failure :
it is impossible to (3)
situation arrives where that T, In this type of failure, the disk in which th
necessary
recover. And hence its information is stored may bedamaged or crashet
commits before T.
Cascade less Schedule :
This may be because of a head crash or a failue
(2) while performing data transfer. The only way to
is to maintain a
T1 T2 T3 recovery from the disk failure
backup copy of the information or store a copy ai
Read(x) information in other disk.
Read(y)
Atomicity ?
Write(x) Q20. What is Recovery and
Read(x)
Write(x) Ans :
Modifyingthe database without ensuring that
Read(x) databas
may leave the
the transaction will commit transaction I
Transaction T, writes x that is read by Consider
in an inconsistent state. account A to account b
transaction T,. Transaction T, writes x that that transfers $50 from modifications
at this database
is read by transaction T,. Supposeback, since goal iseither to perform all output operations
point T, fails, T, must be rolled made by T, or none at all several
be rolled back failure may occurafter
T, is dependent on T,,T, must T,, T, must be
may be required for T. A have been made bu
mnodífications
and since T, is dependent on one of these
rolled back. before all of them are made to ensure atomCy
output informatio
? despite failures, we first
Q19. What are the types of failures of a system describing the modification to
stable storas
Ans : without modifying the database itself.
There are many situations that may result 4.14 LoG-BASED RCOVERY
done do the
in system failure. The damage
information stored in the system depends on Q21. Explain log based recovery?
complexity of the failure for instance, if the failure Ans :
is because of disk crash then there is a high LogBased Recovery :
possibility of losing the entire informatíon present The loogis
recordd
Alog is kept on stable storage.
in the disk, whereas if the failure is due to power maintains a
failure then no information is lost. Basically, there sequence of log records and isel

update activities on the database.

are three different types of failures. They are registers
When transaction T, starts, it before
(1) Transaction failure
by log record
writing a <T, start>
(2) System crash writ
executes write(x), a log record <T,x,
before
the
(3) Disk failure written, where V, isthe value of x
and V, is the value to be written to x. proceedi
face LEGAL
found guity is LIABLE to
Warning: Xerox/Photocopying of this book isa CRIMINAL Act. Anyone
 Database Management Systems
performed a When a transaction partically commits, the
4.15
record notes that T, has
To value V before the write information in the log associated with the
data item xi, hasafter the write. transaction is used in executing the deferred
write value V,
d will have finishes it last statement the log writes.
When T,
commit> iswritten. Example :
rocord<T, Consider two transactions T, and T,.
Explain briefly Log-Based recovery
?
Q22. Transaction T,transfers $50 from account
Ato B. i.e..
Ans
Log-Based Recovery : To: read (B);
the most widely used
structure for
Log is The log A:=A - 50;
recording database modifications.
recording all write (A):
is a sequence of log records,
database. read (B)
the update activities in
There are severaltypes of log records such B:=B+50
as : write (B).
Update log record : Let transaction T, withdraws $100 from
It describes a single database write. It has account C i.e.,
following fields. T,: read (c);
Transaction identifier is the unique identifier C:=C- 100;
of the transaction that performed the write write (C).
operation.
Data item identifier is unique identifier of Suppose that these transactions are executed
data item written. Typically, it is the location serially, in the order T, followed by T, and
on disk of data item.
values of accounts A, B and C before the
Old value is the value of data item prior to execution are $1000, $2000 and $700
write. respectively. The log information related to
these two transactions is
New value is the value of data item that will shown-in following.
have after the write. <T,start>
<T, A, 950>
Various types of log records are
as: represented <To, B, 2050>
<T, <T,Commit>
’

’ start>:Transaction T, has
<I, X, V,, V,>: Transactionstarted. <T,start>
performed a write on data itemT,X,,hasX, <T,, C, 600>
had value V,before
V, after the write. write, and will have <T, Commit>
The state of log and database
<T, commit> :
committed. Transaction T, has to T, and T, is shown as corresponding
follows
’ <T, Log Database
aborted.abort>: Transaction T, has <T, start>
<To, A, 950>
Whenever a
log record fortransaction <T, B, 2050>
that performsa write, a
log exists, we can write is created. Once a <T,Commit>
to output the
database if that is desirable.modification A = 950
Two B= 2050
techniques that uses log to ensure
transaction <T, start>
atomicity
Deferred Database despite failure :are :
(i)
<T,, C, 600>
Thedeferred Modification
moditication
<T, Commit>
C= 600
transaction atomicity by technique ensures (iü)
database modifications in recording
the log, butall
Immediate databse Modification :
deterring
of a
the
execution of all write The immediate modification technique allows
transaction
Commits. until
transaction operations
database modifications to be output to the
partically database while the transaction is still in active
state.
Warning :
Xerox/Photocopying of this book is a
CRIMINAL Act. Anyone found guilty is LIABLE to face LEGAL proceedings
 Database Management Systeme
Example: When T, partially commits; <T, 4.16
Let us consider banking system, with written to log. Finally
used to actually execute the
are read i
the log records
and
commit>
previously
transactions T, andT,, executed in the order
followed by T,. The portion of log
writes. During recovery after a crash,
needs to be redone if and only if both
a deferioedn
tr<T,ansact
containing the relevant information
concerning these two transactions appears
and <T, commit> are there in the log.
transaction T,(redo T) sets the yalue of
sta rt
Redoiall ng
a
>
in following figure. items updated by the transactions to
crashes can occur while. the new data values
<T, start>
<T, A, 1000, 950> The transaction is executing the origin
updates or
<T, B, 2000, 2050> While recovery action is being taken
<T,Commit> Example transactions T, and (To executes
<T, start> before T1)
<T,,C, 700, 600> T,: read(A) T,;read(c)
<T, Commit> A = A-50 C:=C-100
The one possible order in which actual write (c)
outputs took place in both the log and Read(b)
database system as a result of execution of B;=B+50
T, and T, shown as follows. Write (B)
Log Database
In the belowtable we showthe log as it
<T,start> appears at three instances of time
<T,, A, 1000, 950>
A B C
<T, B, 2000, 2050>
<ToStart> < To,Start> < To,Start>
A = 950
<To,A,950> < To,A,950> <ToA,950>
B = 2050 < To,B,2050> < To.B,2050>
<To,B,2050>
<I, Commit> <To Commit> < ToCommit>
<T, start> <T1, Start> <TI, Start>
<T,, C, 700,600> <T, C,600> <T,C,600>
<T commits>
C= 600
<T, Commit> (ii) Immediate Database Modification :
4.15 RECOVERY WITH CONCURRENT The immediate database modification
TRANSACTIONS scheme allows database updates of an
uncommitted transaction to be made as thewrites
Q23. Discuss in detail how we can achieve re are issued. Update log record must be written before
covery with concurrent transactions ? database item is written.
Ans :
Q24. Write a detailed note on buffer man
There are two techniques for ensuring atomicity in agements and explain the different buft
database they are ering techniques used for implementing
(i) Deferred database modification the crash recovery scheme ?
(iü) Immediate database modification Ans :
(i) Deferred database modification : Buffer Management :
The deferred database modification scheme The buffer is the part of MM available tor
records all modifications to be log; but defers all storage of copies of disk blocks, The subsysteni
the writes to after partial commit assume that responsible for the allocation of bufer space b
transactions execute serially transaction starts by called the buffer management. The buffer manage
writing <T, Start> record to log. A write(x) handles allrequests for blocks of the database. I
operation results in a log record <T,X, V> being the block is already in MM, the address in MMB
written where V is the new value of xthe write is given to the requestor.
not perfomed on x at this time, but is deferred. The buffer manager must use some sophisticated
techniques in order to provide good service.
Warning: Xerox/Photocopying of this book ls a CRIMINAL Act. Anyone found guilty is LIABLE to face LEGAL proceeal
4.17 Database Management Systems
Replacement Strategy :
When there is no room left in the buffer, some
block must be removed to make way for the
new one typical operating system memnory
management schemes use a "Least recentlu
used" (LRU) method. This can be improved
upon for database applications
Pinned Blocks :
For the database to be able to revover from
crashes, we need to restrict times when a
block may be written back to disk it block
not allowed to bewritten is said to be pinned.
Many operating systems do not provide
support for pinned blocks, and such a feature
is essential if database is to be "crash
resistance"

Forced output of blocks :

Sometimes it is necessary to write a block
back to disk even though its buffer space is
not need. This is due to fact that Mn
contents are lost in a crash, while disk data
usually survives.
The two buffering techniques used for implementing
the crash-recovery scheme as follows:
(a) Log-record buffering
(b) Database buffering
(a) Log -record buffering :
During the creation of log records, all the
records available in the log are output to the
stable storage. Hence, at the time of system
execution, a high over head is imposed due
to the following reasons.
(i) The log records on the stable
in the form of units called storage are
blocks.
(ü) Mostly these blocks appear to be
than the records. Hence at the greater
level, a larger output of all physical
the log
records is obtained.
(b) Database Buffering:
The database is stored in a
non
storage disk and whenever needed thevolatile
of data are blocks
transferred to main memory by
the system. Typically the size of the
memory is less than the entire database.main

Warning :
Xerox/Photocopying of this book is a CRIMINAL Act. Anyone found guilty is LIABLE to face LEGAL proceedings