Definition of Transaction: A transaction can be defined as a group transactions T2 in a sequence.

ii) Execute all the operations of trans-

of tasks that form a single logical unit.1.read_item(X) : This is a read- actions T2 in a sequence and then execute all the operations of
ing operation in which database item named X is read into a pro- transactions T1 in a sequence. Non serial schedule: The schedule in
gramming variable. We can name the program variable as X for sim- which operations present within the transaction are intermixed. This
plification. 2.write_item(X) : This operation writes the value of pro- may lead to conflicts in the result or inconsistency in the resultant
gram variable X into the database item which is also named as X. • data. Serializability : • When multiple transactions run concurrently,
read_item(X) command includes the following steps : Step 1 : then it may lead to inconsistency of data (i.e. change in the resultant
Find the address of the disk block that contains item X. Step 2 : Copy value of data from different transactions). • Serializability is a concept
that disk block into a buffer in main memory (if that disk block is not that helps to identify which non serial schedule and find the transac-
already in some main memory buffer). Step 3 : Copy item X from the tion equivalent to serial schedule. In serializable schedule, if there
buffer to the program variable named X. • write_item(X) command are two transactions executing at the same time and interleaving of
includes the following steps : Step 1 : Find the address of the disk operations is allowed there can be different possible orders of exe-
block that contains item X. Step 2 : Copy that disk block into a buffer cuting an individual operation of the transactions. Conflict Serializa-
in main memory (if that disk block is not already in some main bility: Definition : Suppose T1 and T2 are two transactions and I1
memory buffer). Step 3 : Copy item X from the program variable and I2 are the instructions in T1 and T2 respectively. Then these two
named X into its correct location in the buffer. Step 4 : Store the up- transactions are said to be conflict serializable, if both the instruction
dated block from the buffer back to disk. Transaction States: 1) Ac- access the data item d, and at least one of the instruction is write
tive : This is the first state of transaction. For example : Insertion, operation. What is conflict ? : In the definition three conditions are
deletion or updation of record is done here. But data is not saved to specified for a conflict in conflict serializability - 1) There should be
database. 2) Partially committed : When a transaction executes its different transactions 2) The operations must be performed on same
final operation, it is said to be in a partially committed state. 3) Failed data items 3) One of the operation must be the Write (W) operation.
: A transaction is said to be in a failed state if any of the checks made • We can test a given schedule for conflict serializability by construct-
by the database recovery system fails. A failed transaction can no ing a precedence graph for the schedule, and by searching for ab-
longer proceed further. 4) Aborted : If a transaction is failed to exe- sence of cycles in the graph. • Predence graph is a directed graph,
cute, then the database recovery system will make sure that the da- consisting of G = (V,E) where V is set of vertices and E is set of
tabase is in its previous consistent state. If not, it brings the database edges. The set of vertices consists of all the transactions participat-
to consistent state by aborting or rolling back the transaction. 5) ing in the schedule. The set of edges consists of all edges Ti → Tj
Committed : If a transaction executes all its operations successfully, for which one of three conditions holds : 1. Ti executes write(Q) be-
it is said to be committed. This is the last step of a transaction, if it fore Tj executes read(Q). 2. Ti executes read(Q) before Tj executes
executes without fail. ACID Properties: 1) Atomicity : • This property write(Q). 3. Ti executes write(Q) before Tj executes write(Q). • A se-
states that each transaction must be considered as a single unit and rializability order of the transactions can be obtained by finding a lin-
must be completed fully or not completed at all. • No transaction in ear order consistent with the partial order of the precedence graph.
the database is left half completed. • Database should be in a state This process is called topological sorting. Testing for serializability •
either before the transaction execution or after the transaction exe- Following method is used for testing the serializability : To test the
cution. It should not be in a state ‘executing’. • For example - In conflict serializability we can draw a graph G = (V, E) where V = Ver-
above mentioned withdrawal of money transaction all the five steps tices which represent the number of transactions. E = Edges for con-
must be completed fully or none of the step is completed. Suppose flicting pairs. Step1: Create a node for each transaction. Step2: Find
if transaction gets failed after step 3, then the customer will get the the conflicting pairs (RW, WR, WW) on the same variable (or data
money but the balance will not be updated accordingly. The state of item) by different transactions. Step3: Draw edge for the given
database should be either at before ATM withdrawal (i.e customer schedule. Consider following cases 1. Ti executes write(Q) before Tj
without withdrawn money) or after ATM withdrawal (i.e. customer executes read(Q), then draw edge from Ti to Tj . 2. Ti executes
with money and account updated). This will make the system in con- read(Q) before Tj executes write(Q) , then draw edge from Ti to Tj .
sistent state. 2) Consistency : • The database must remain in con- 3. Ti executes write(Q) before Tj executes write(Q), , then draw edge
sistent state after performing any transaction. • For example : In ATM from Ti to Tj . Step 4 : Now, if precedence graph is cyclic then it is a
withdrawal operation, the balance must be updated appropriately af- non conflict serializable schedule and if the precedence graph is acy-
ter performing transaction. Thus the database can be in consistent clic then it is conflict serializable schedule. View Serializability: • If
state. 3) Isolation : • In a database system where more than one a given schedule is found to be view equivalent to some serial sched-
transaction are being executed simultaneously and in parallel, the ule, then it is called as a view serializable schedule. • View Equiva-
property of isolation states that all the transactions will be carried out lent Schedule : Consider two schedules S1 and S2 consisting of
and executed as if it is the only transaction in the system. • No trans- transactions T1 and T2 respectively, then schedules S1 and S2 are
action will affect the existence of any other transaction. • For exam- said to be view equivalent schedule if it satisfies following three con-
ple : If a bank manager is checking the account balance of particular ditions : o If transaction T1 reads a data item A from the database
customer, then manager should see the balance either before with- initially in schedule S2, then in schedule S2 also, T1 must perform
drawing the money or after withdrawing the money. This will make the initial read of the data item X from the database. This is same for
sure that each individual transaction is completed and any other de- all the data items. In other words - the initial reads must be same for
pendent transaction will get the consistent data out of it. Any failure all data items. o If data item A has been updated at last by transaction
to any transaction will not affect other transaction in this case. Hence Ti in schedule S1, then in schedule S2 also, the data item A must be
it makes all the transactions consistent. 4) Durability : • The database updated at last by transaction Ti. o If transaction Ti reads a data item
should be strong enough to handle any system failure. • If there is that has been updated by the transaction Tj in schedule S1, then in
any set of insert /update, then it should be able to handle and commit schedule S2 also, transaction Ti must read the same data item that
to the database. • If there is any failure, the database should be able has been updated by transaction Tj. In other words the Write-Read
to recover it to the consistent state. • For example : In ATM with- sequence must be same. Steps towhether the given schedule is
drawal example, if the system failure happens after customer getting view serializable or not stepStep 1: If the schedule is conflict seri-
the money then the system should be strong enough to update Da- alizable then it is surely view serializable because conflict serializa-
tabase with his new balance, after system recovers. For that purpose bility is a restricted form of view serializability. Step 2 : If it is not
the system has to keep the log of each transaction and its failure. So conflict serializable schedule then check whether there exist any
when the system recovers, it should be able to know when a system blind write operation. The blind write operation is a write operation
has failed and if there is any pending transaction, then it should be without reading a value. If there does not exist any blind write then
updated to Database. that means the given schedule is not view serializable. In other words
Concept of Schedule: Serial schedule: The schedule in which the if a blind write exists then that means schedule may or may not be
transactions execute one after the other is called serial schedule. In view conflict. Step 3 : Find the view equivalence schedule. Recover-
serial schedule, if there are two transactions executing at the same able and Non-recoverable Schedules: • The serializable schedule
time and no interleaving of operations is permitted, then following can be made consistent by applying conflict serializability or view se-
can be the possibilities of execution - i) Execute all the operations of rializability. • The serializable order makes a transaction isolation.
transactions T1 in a sequence and then execute all the operations of But during the execution of concurrent transactions in a given sched-
ule, some of the transaction may get failed(may be due to hardware
or software failure) • If the transaction gets failed we need to undo means in other words all the exclusive locks are unlocked only after
the effect of this transaction to ensure the atomicity property of trans- the transaction is committed. That also means that if T1 has exclu-
action. This makes the schedule acceptable even after the failure. • sive lock, then T1 will release the exclusive lock only after commit
The schedule can be made acceptable by two techniques namely - operation, then only other transaction is allowed to read or write. 2)
Recoverable Schedule and Cascadeless schedule. Recoverable Rigorous two phase locking : This is stricter two phase locking pro-
Schedule: Definition:A recoverable schedule is one where, for each tocol. Here all locks are to be held until the transaction commits. The
pair of transactions Ti and Tj such that Tj reads a data item previously transactions can be seriealized in the order in which they commit.
written by Ti , the commit operation of Ti appears before the commit Time-stamp based Protocol: • The time stamp ordering protocol is
operation of Tj. Cascadeless Schedule: Definition : If in a schedule, a scheme in which the order of transaction is decided in advance
a transaction is not allowed to read a data item until the last transac- based on their timestamps. Thus the schedules are serialized ac-
tion that has written that data item is committed or aborted, then such cording to their timestamps. • The timestamp-ordering protocol en-
a schedule is known as a cascadeless schedule. Concurrency Con- sures that any conflicting read and write operations are executed in
trol:• One of the fundamental properties of a transaction is isolation. timestamp order. • A larger timestamp indicates a more recent trans-
• When several transactions execute concurrently in the database, action or it is also called as younger transaction while lesser
however, the isolation property may no longer be preserved. • A da- timestamp indicates older transaction. • Assume a collection of data
tabase can have multiple transactions running at the same time. This items that are accessed, with read and write operations, by transac-
is called concurrency. • To preserve the isolation property, the sys- tions. • For each data item X the DBMS maintains the following val-
tem must control the interaction among the concurrent transactions; ues : – o RTS(X) : The timestamp on which object X was last read
this control is achieved through one of a variety of mechanisms (by some transaction Ti , i.e., RTS(X):=TS(Ti )) [Note that : RTS
called concurrency control schemes. • Definition of concurrency con- stands for Read Time Stamp] o WTS(X) : The timestamp on which
trol : A mechanism which ensures that simultaneous execution of object X was last written (by some transaction Tj , i.e.,
more than one transactions does not lead to any database inconsist- WTS(X):=TS(Tj )) [Note that : WTS stands for Write Time Stamp] •
For the following algorithms we use the following assumptions : A
encies is called concurrency control mechanism. • The concurrency
data item X in the database has a RTS(X) and WTS(X). These are
control can be achieved with the help of various protocols such as -
actually the timestamps of read and write operations performed on
lock based protocol, deadlock handling, multiple granularity,
data item X at latest time. • A transaction T attempts to perform some
timestamp based protocol, and validation based protocols. Need for
action (read or write) on data item X on some timestamp and we call
Concurrency: 1) Lost Update Problem: This problem occurs when
that timestamp as TS(T). • By timestamp ordering algorithm we need
two transactions that access the same database items have their op-
to decide whether transaction T has to be aborted or T can continue
erations interleaved in a way that makes the value of some database
execution. Basic Timestamp Ordering Algorithm Case 1 (Read) :
item incorrect. 2) Dirty Read or Uncommited Read Problem: The dirty
Transaction T issues a read(X) operation i) If TS(T) < WTS(X), then
read is a situation in which one transaction reads the data immedi-
ately after the write operation of previous transaction 3) Non-repeat- read(X) is rejected. T has to abort and be rejected. ii) If WTS(X) 
able read problem: This problem is also known as inconsistent anal- TS(T), then execute read(X) of T and update RTS(X). Case 2 (Write)
ysis problem. This problem occurs when a particular transaction sees : Transaction T issues a write(X) operation i) If TS(T) < RTS(X) or if
two different values for the same row within its lifetime. 4) Phantom TS(T) < WTS(X), then write is rejected ii) If RTS(X)  TS(T) or
read problem: The phantom read problem is a special case of non WTS(X)  TS(T), then execute write(X) of T and update WTS(X).
repeatable read problem. This is a problem in which one of the trans- Advantages and disadvantages of time stamp ordering Ad-
action makes the changes in the database system and due to these vantages 1) Schedules are serializable 2) No waiting for transaction
changes another transaction can not read the data item which it has and hence there is no deadlock situation. Disadvantages 1) Sched-
read just recently. Lock based Protocol: • One of the method to ules are not recoverable once transactions occur. 2) Same transac-
ensure the isolation property in transactions is to require that data tion may be continuously aborted or restarted. Log-based Recovery
items be accessed in a mutually exclusive manner. That means, : Deferred and Immediate Update: Concept of Log • Log is the
while one transaction is accessing a data item, no other transaction most commonly used structure for recording the modifications that is
can modify that data item. • The most common method used to im- to be made in the actual database. Hence during the recovery pro-
plement this requirement is to allow a transaction to access a data cedure a log file is maintained. • A log record maintains four types of
item only if it is currently holding a lock on that item. • Thus the lock operations. Depending upon the type of operations there are four
on the operation is required to ensure the isolation of transaction. types of log records - 1. Log record : It is represented as 2. Log record
Working of Lock: • Concept of protocol : The lock based protocol is 3. Log record : It is represented as 4. Log record : It is represented
a mechanism in which there is exclusive use of locks on the data as • The log contains various fields as shown in following Fig. 5.16.1.
item for current transaction. • Types of locks: i) Shared lock : The This structure is for operation. • The log must be maintained on the
shared lock is used for reading data items only. It is denoted by Lock- stable storage and the entries in the log file are maintained before
S. This is also called as read lock. ii) Exclusive lock : The exclusive actually updating the physical database. • There are two approaches
lock is used for both read and write operations. It is denoted as Lock- used for log based recovery technique - Deferred Database Modifi-
X. This is also called as write lock. • The compatibility matrix is used cation and Immediate Database Modification. REDO and UNDO Op-
while working on set of locks. The concurrency control manager eration UNDO : This is an operation in which we restore all the old
checks the compatibility matrix before granting the lock. If the two values (BFIM - BeFore Modification Image) onto the disk. This is
modes of transactions are compatible to each other then only the called roll-back operation. REDO : This is an operation in which all
lock will be granted. • In a set of locks may consists of shared or the modified values(AFIM - AFter Modification Image) are restored
exclusive locks. Following matrix represents the compatibility be- onto the disk. This is called roll-forward operation. Write Ahead Log-
tween modes of locks. Two Phase Locking Protocol: i) Growing ging Rule: • Before a block of data in main memory is output to the
phase (Locking phase) : It is a phase in which the transaction may database, all log records pertaining to data in that block must have
obtain locks but does not release any lock. ii) Shrinking phase (Un- been output to stable storage. This rule is called the Write-Ahead
locking phase) : It is a phase in which the transaction may release Logging (WAL) • This rule is necessary because - In the event of a
the locks but does not obtain any new lock. • Lock Point : The last crash or ROLLBACK, the original content contained in the rollback
lock position or first unlock position is called lock point. Advantages journal is played back into the database file to revert the database
of two phase locking (1) It ensures serializability. Disadvantages of file to its original state. Deferred Database Modification: • In this
two phase locking protocol (1) It leads to dealocks. (2) It leads to technique, the database is not updated immediately. • Only log file
cascading rollback. Problems in two phase loc1) Deadlock : The is updated on each transaction. • When the transaction reaches to
deadlock problem can not be solved by two phase locking. Deadlock its commit point, then only the database is physically updated from
is a situation in which when two or more transactions have got a lock the log file. • In this technique, if a transaction fails before reaching
and waiting for another locks currently held by one of the other trans- to its commit point, it will not have changed database anyway. Hence
actions. 2) Cascading Rollback : Cascading rollback is a situation there is no need for the UNDO operation. The REDO operation is
in which a single transaction failure leads to a series of transaction required to record the operations from log file to physical database.
rollback. Types of Two Phase Locking 1) Strict two phase locking Hence deferred database modification technique is also called as NO
: The strict 2PL protocol is a basic two phase protocol but all the UNDO/REDO algorithm.
exclusive mode locks be held until the transaction commits. That
 Study material provided by: Vishwajeet Londhe

Join Community by clicking below links

Telegram Channel

https://t.me/SPPU_TE_BE_COMP
(for all engineering Resources)

WhatsApp Channel
(for all tech updates)

https://whatsapp.com/channel/
0029ValjFriICVfpcV9HFc3b

Insta Page
(for all engg & tech updates)

https://www.instagram.com/
sppu_engineering_update