DBMS - Transaction

A transaction can be defined as a group of tasks. A single task is the

minimum processing unit which cannot be divided further.
Let’s take an example of a simple transaction. Suppose a bank employee
transfers Rs 500 from A's account to B's account. This very simple and
small transaction involves several low-level tasks.
A’s Account
Open_Account(A)
Old_Balance = A.balance
New_Balance = Old_Balance - 500
A.balance = New_Balance
Close_Account(A)
B’s Account
Open_Account(B)
Old_Balance = B.balance
New_Balance = Old_Balance + 500
B.balance = New_Balance
Close_Account(B)
ACID Properties
A transaction is a very small unit of a program and it may contain several
lowlevel tasks. A transaction in a database system must
maintain Atomicity, Consistency, Isolation, and Durability − commonly
known as ACID properties − in order to ensure accuracy, completeness,
and data integrity.
 Atomicity − This property states that a transaction must be
treated as an atomic unit, that is, either all of its operations
are executed or none. There must be no state in a database
where a transaction is left partially completed. States should
be defined either before the execution of the transaction or
after the execution/abortion/failure of the transaction.
 Consistency − The database must remain in a consistent
state after any transaction. No transaction should have any
adverse effect on the data residing in the database. If the
database was in a consistent state before the execution of a
transaction, it must remain consistent after the execution of
the transaction as well.
 Durability − The database should be durable enough to hold
all its latest updates even if the system fails or restarts. If a
transaction updates a chunk of data in a database and
commits, then the database will hold the modified data. If a
transaction commits but the system fails before the data could
be written on to the disk, then that data will be updated once
the system springs back into action.
  Isolation − In a database system where more than one
transaction are being executed simultaneously and in parallel,
the property of isolation states that all the transactions will be
carried out and executed as if it is the only transaction in the
system. No transaction will affect the existence of any other
transaction.
Serializability
nnnnnnnnnnnmultiprogramming environment, there are possibilities that
instructions of one transactions are interleaved with some other
transaction.
 Schedule − A chronological execution sequence of a
transaction is called a schedule. A schedule can have many
transactions in it, each comprising of a number of
instructions/tasks.
 Serial Schedule − It is a schedule in which transactions are
aligned in such a way that one transaction is executed first.
When the first transaction completes its cycle, then the next
transaction is executed. Transactions are ordered one after
the other. This type of schedule is called a serial schedule, as
transactions are executed in a serial manner.
In a multi-transaction environment, serial schedules are considered as a
benchmark. The execution sequence of an instruction in a transaction
cannot be changed, but two transactions can have their instructions
executed in a random fashion. This execution does no harm if two
transactions are mutually independent and working on different segments
of data; but in case these two transactions are working on the same data,
then the results may vary. This ever-varying result may bring the
database to an inconsistent state.
To resolve this problem, we allow parallel execution of a transaction
schedule, if its transactions are either serializable or have some
equivalence relation among them.

Equivalence Schedules
An equivalence schedule can be of the following types −

Result Equivalence
If two schedules produce the same result after execution, they are said to
be result equivalent. They may yield the same result for some value and
different results for another set of values. That's why this equivalence is
not generally considered significant.

View Equivalence
Two schedules would be view equivalence if the transactions in both the
schedules perform similar actions in a similar manner.
For example −
  If T reads the initial data in S1, then it also reads the initial
data in S2.
 If T reads the value written by J in S1, then it also reads the
value written by J in S2.
 If T performs the final write on the data value in S1, then it
also performs the final write on the data value in S2.
Conflict Equivalence
Two schedules would be conflicting if they have the following properties −

 Both belong to separate transactions.

 Both accesses the same data item.
 At least one of them is "write" operation.
Two schedules having multiple transactions with conflicting operations are
said to be conflict equivalent if and only if −

 Both the schedules contain the same set of Transactions.

 The order of conflicting pairs of operation is maintained in both the
schedules.
Note − View equivalent schedules are view serializable and conflict
equivalent schedules are conflict serializable. All conflict serializable
schedules are view serializable too.

States of Transactions
A transaction in a database can be in one of the following states −

 Active − In this state, the transaction is being executed. This

is the initial state of every transaction.
 Partially Committed − When a transaction executes its final
operation, it is said to be in a partially committed state.
  Failed − A transaction is said to be in a failed state if any of
the checks made by the database recovery system fails. A
failed transaction can no longer proceed further.
 Aborted − If any of the checks fails and the transaction has
reached a failed state, then the recovery manager rolls back
all its write operations on the database to bring the database
back to its original state where it was prior to the execution of
the transaction. Transactions in this state are called aborted.
The database recovery module can select one of the two
operations after a transaction aborts −
o Re-start the transaction
o Kill the transaction
 Committed − If a transaction executes all its operations
successfully, it is said to be committed. All its effects are now
permanently established on the database system.

DBMS - Concurrency Control

In a multiprogramming environment where multiple transactions can be
executed simultaneously, it is highly important to control the concurrency
of transactions. We have concurrency control protocols to ensure
atomicity, isolation, and serializability of concurrent transactions.
Concurrency control protocols can be broadly divided into two categories
−

 Lock based protocols

 Time stamp based protocols
Lock-based Protocols
Database systems equipped with lock-based protocols use a mechanism
by which any transaction cannot read or write data until it acquires an
appropriate lock on it. Locks are of two kinds −
 Binary Locks − A lock on a data item can be in two states; it
is either locked or unlocked.
 Shared/exclusive − This type of locking mechanism
differentiates the locks based on their uses. If a lock is
acquired on a data item to perform a write operation, it is an
exclusive lock. Allowing more than one transaction to write on
the same data item would lead the database into an
inconsistent state. Read locks are shared because no data
value is being changed.
There are four types of lock protocols available −

Simplistic Lock Protocol

Simplistic lock-based protocols allow transactions to obtain a lock on
every object before a 'write' operation is performed. Transactions may
unlock the data item after completing the ‘write’ operation.
Pre-claiming Lock Protocol
Pre-claiming protocols evaluate their operations and create a list of data
items on which they need locks. Before initiating an execution, the
transaction requests the system for all the locks it needs beforehand. If all
the locks are granted, the transaction executes and releases all the locks
when all its operations are over. If all the locks are not granted, the
transaction rolls back and waits until all the locks are granted.

Two-Phase Locking 2PL

This locking protocol divides the execution phase of a transaction into
three parts. In the first part, when the transaction starts executing, it
seeks permission for the locks it requires. The second part is where the
transaction acquires all the locks. As soon as the transaction releases its
first lock, the third phase starts. In this phase, the transaction cannot
demand any new locks; it only releases the acquired locks.

Two-phase locking has two phases, one is growing, where all the locks
are being acquired by the transaction; and the second phase is shrinking,
where the locks held by the transaction are being released.
To claim an exclusive (write) lock, a transaction must first acquire a
shared (read) lock and then upgrade it to an exclusive lock.

Strict Two-Phase Locking

The first phase of Strict-2PL is same as 2PL. After acquiring all the locks in
the first phase, the transaction continues to execute normally. But in
contrast to 2PL, Strict-2PL does not release a lock after using it. Strict-2PL
holds all the locks until the commit point and releases all the locks at a
time.
Strict-2PL does not have cascading abort as 2PL does.

Timestamp-based Protocols
The most commonly used concurrency protocol is the timestamp based
protocol. This protocol uses either system time or logical counter as a
timestamp.
Lock-based protocols manage the order between the conflicting pairs
among transactions at the time of execution, whereas timestamp-based
protocols start working as soon as a transaction is created.
Every transaction has a timestamp associated with it, and the ordering is
determined by the age of the transaction. A transaction created at 0002
clock time would be older than all other transactions that come after it.
For example, any transaction 'y' entering the system at 0004 is two
seconds younger and the priority would be given to the older one.
In addition, every data item is given the latest read and write-timestamp.
This lets the system know when the last ‘read and write’ operation was
performed on the data item.

Timestamp Ordering Protocol

The timestamp-ordering protocol ensures serializability among
transactions in their conflicting read and write operations. This is the
responsibility of the protocol system that the conflicting pair of tasks
should be executed according to the timestamp values of the
transactions.

 The timestamp of transaction Ti is denoted as TS(Ti).

 Read time-stamp of data-item X is denoted by R-timestamp(X).
 Write time-stamp of data-item X is denoted by W-timestamp(X).
Timestamp ordering protocol works as follows −
 If a transaction Ti issues a read(X) operation −
o If TS(Ti) < W-timestamp(X)
  Operation rejected.
o If TS(Ti) >= W-timestamp(X)
 Operation executed.
o All data-item timestamps updated.
 If a transaction Ti issues a write(X) operation −
o If TS(Ti) < R-timestamp(X)
 Operation rejected.
o If TS(Ti) < W-timestamp(X)
 Operation rejected and Ti rolled back.
o Otherwise, operation executed.
o

DBMS - Deadlock
In a multi-process system, deadlock is an unwanted situation that arises in
a shared resource environment, where a process indefinitely waits for a
resource that is held by another process.
For example, assume a set of transactions {T , T , T , ...,T }. T needs a
0 1 2 n 0

resource X to complete its task. Resource X is held by T , and T is waiting

1 1

for a resource Y, which is held by T . T is waiting for resource Z, which is

2 2

held by T . Thus, all the processes wait for each other to release
0

resources. In this situation, none of the processes can finish their task.
This situation is known as a deadlock.
Deadlocks are not healthy for a system. In case a system is stuck in a
deadlock, the transactions involved in the deadlock are either rolled back
or restarted.

Deadlock Prevention
To prevent any deadlock situation in the system, the DBMS aggressively
inspects all the operations, where transactions are about to execute. The
DBMS inspects the operations and analyzes if they can create a deadlock
situation. If it finds that a deadlock situation might occur, then that
transaction is never allowed to be executed.
There are deadlock prevention schemes that use timestamp ordering
mechanism of transactions in order to predetermine a deadlock situation.

Wait-Die Scheme
In this scheme, if a transaction requests to lock a resource (data item),
which is already held with a conflicting lock by another transaction, then
one of the two possibilities may occur −
 If TS(T ) < TS(T ) − that is T , which is requesting a conflicting
i j i

lock, is older than T − then T is allowed to wait until the data-

j i

item is available.
  If TS(T ) > TS(t ) − that is T is younger than T − then T dies. T is
i j i j i i

restarted later with a random delay but with the same

timestamp.
This scheme allows the older transaction to wait but kills the younger one.

Wound-Wait Scheme
In this scheme, if a transaction requests to lock a resource (data item),
which is already held with conflicting lock by some another transaction,
one of the two possibilities may occur −
 If TS(T ) < TS(T ), then T forces T to be rolled back − that is
i j i j

T wounds T . T is restarted later with a random delay but with

i j j

the same timestamp.

 If TS(T ) > TS(T ), then T is forced to wait until the resource is
i j i

available.
This scheme, allows the younger transaction to wait; but when an older
transaction requests an item held by a younger one, the older transaction
forces the younger one to abort and release the item.
In both the cases, the transaction that enters the system at a later stage
is aborted.

Deadlock Avoidance
Aborting a transaction is not always a practical approach. Instead,
deadlock avoidance mechanisms can be used to detect any deadlock
situation in advance. Methods like "wait-for graph" are available but they
are suitable for only those systems where transactions are lightweight
having fewer instances of resource. In a bulky system, deadlock
prevention techniques may work well.

Wait-for Graph
This is a simple method available to track if any deadlock situation may
arise. For each transaction entering into the system, a node is created.
When a transaction T requests for a lock on an item, say X, which is held
i

by some other transaction T , a directed edge is created from T to T . If

j i j

T releases item X, the edge between them is dropped and T locks the
j i

data item.
The system maintains this wait-for graph for every transaction waiting for
some data items held by others. The system keeps checking if there's any
cycle in the graph.
Here, we can use any of the two following approaches −
 First, do not allow any request for an item, which is already
locked by another transaction. This is not always feasible and
may cause starvation, where a transaction indefinitely waits
for a data item and can never acquire it.
 The second option is to roll back one of the transactions. It is
not always feasible to roll back the younger transaction, as it
may be important than the older one. With the help of some
relative algorithm, a transaction is chosen, which is to be
aborted. This transaction is known as the victim and the
process is known as victim selection.

DBMS - Data Backup

Loss of Volatile Storage
A volatile storage like RAM stores all the active logs, disk buffers, and
related data. In addition, it stores all the transactions that are being
currently executed. What happens if such a volatile storage crashes
abruptly? It would obviously take away all the logs and active copies of
the database. It makes recovery almost impossible, as everything that is
required to recover the data is lost.
Following techniques may be adopted in case of loss of volatile storage −
 We can have checkpoints at multiple stages so as to save the
contents of the database periodically.
 A state of active database in the volatile memory can be
periodically dumped onto a stable storage, which may also
contain logs and active transactions and buffer blocks.
 <dump> can be marked on a log file, whenever the database
contents are dumped from a non-volatile memory to a stable
one.
Recovery
 When the system recovers from a failure, it can restore the
latest dump.
 It can maintain a redo-list and an undo-list as checkpoints.
 It can recover the system by consulting undo-redo lists to
restore the state of all transactions up to the last checkpoint.
Database Backup & Recovery from
Catastrophic Failure
A catastrophic failure is one where a stable, secondary storage device
gets corrupt. With the storage device, all the valuable data that is stored
inside is lost. We have two different strategies to recover data from such a
catastrophic failure −
 Remote backup &minu; Here a backup copy of the database is
stored at a remote location from where it can be restored in
case of a catastrophe.
 Alternatively, database backups can be taken on magnetic
tapes and stored at a safer place. This backup can later be
transferred onto a freshly installed database to bring it to the
point of backup.
Grown-up databases are too bulky to be frequently backed up. In such
cases, we have techniques where we can restore a database just by
looking at its logs. So, all that we need to do here is to take a backup of all
the logs at frequent intervals of time. The database can be backed up
once a week, and the logs being very small can be backed up every day or
as frequently as possible.

Remote Backup
Remote backup provides a sense of security in case the primary location
where the database is located gets destroyed. Remote backup can be
offline or real-time or online. In case it is offline, it is maintained manually.
Online backup systems are more real-time and lifesavers for database
administrators and investors. An online backup system is a mechanism
where every bit of the real-time data is backed up simultaneously at two
distant places. One of them is directly connected to the system and the
other one is kept at a remote place as backup.
As soon as the primary database storage fails, the backup system senses
the failure and switches the user system to the remote storage.
Sometimes this is so instant that the users can’t even realize a failure.

DBMS - Data Recovery

Crash Recovery
DBMS is a highly complex system with hundreds of transactions being
executed every second. The durability and robustness of a DBMS depends
on its complex architecture and its underlying hardware and system
software. If it fails or crashes amid transactions, it is expected that the
system would follow some sort of algorithm or techniques to recover lost
data.

Failure Classification
To see where the problem has occurred, we generalize a failure into
various categories, as follows −

Transaction failure
A transaction has to abort when it fails to execute or when it reaches a
point from where it can’t go any further. This is called transaction failure
where only a few transactions or processes are hurt.
Reasons for a transaction failure could be −
 Logical errors − Where a transaction cannot complete
because it has some code error or any internal error condition.
 System errors − Where the database system itself terminates
an active transaction because the DBMS is not able to execute
it, or it has to stop because of some system condition. For
example, in case of deadlock or resource unavailability, the
system aborts an active transaction.
System Crash
There are problems − external to the system − that may cause the system
to stop abruptly and cause the system to crash. For example,
interruptions in power supply may cause the failure of underlying
hardware or software failure.
Examples may include operating system errors.

Disk Failure
In early days of technology evolution, it was a common problem where
hard-disk drives or storage drives used to fail frequently.
Disk failures include formation of bad sectors, unreachability to the disk,
disk head crash or any other failure, which destroys all or a part of disk
storage.

Storage Structure
We have already described the storage system. In brief, the storage
structure can be divided into two categories −
 Volatile storage − As the name suggests, a volatile storage
cannot survive system crashes. Volatile storage devices are
placed very close to the CPU; normally they are embedded
onto the chipset itself. For example, main memory and cache
memory are examples of volatile storage. They are fast but
can store only a small amount of information.
 Non-volatile storage − These memories are made to survive
system crashes. They are huge in data storage capacity, but
slower in accessibility. Examples may include hard-disks,
magnetic tapes, flash memory, and non-volatile (battery
backed up) RAM.
Recovery and Atomicity
When a system crashes, it may have several transactions being executed
and various files opened for them to modify the data items. Transactions
are made of various operations, which are atomic in nature. But according
to ACID properties of DBMS, atomicity of transactions as a whole must be
maintained, that is, either all the operations are executed or none.
When a DBMS recovers from a crash, it should maintain the following −
  It should check the states of all the transactions, which were
being executed.
 A transaction may be in the middle of some operation; the
DBMS must ensure the atomicity of the transaction in this
case.
 It should check whether the transaction can be completed now
or it needs to be rolled back.
 No transactions would be allowed to leave the DBMS in an
inconsistent state.
There are two types of techniques, which can help a DBMS in recovering
as well as maintaining the atomicity of a transaction −
 Maintaining the logs of each transaction, and writing them
onto some stable storage before actually modifying the
database.
 Maintaining shadow paging, where the changes are done on a
volatile memory, and later, the actual database is updated.
Log-based Recovery
Log is a sequence of records, which maintains the records of actions
performed by a transaction. It is important that the logs are written prior
to the actual modification and stored on a stable storage media, which is
failsafe.
Log-based recovery works as follows −
 The log file is kept on a stable storage media.
 When a transaction enters the system and starts execution, it
writes a log about it.
<T , Start>
n

 When the transaction modifies an item X, it write logs as

follows −
<T , X, V , V >
n 1 2

It reads T has changed the value of X, from V to V .

n 1 2

 When the transaction finishes, it logs −

<T , commit>
n

The database can be modified using two approaches −

 Deferred database modification − All logs are written on to
the stable storage and the database is updated when a
transaction commits.
 Immediate database modification − Each log follows an
actual database modification. That is, the database is modified
immediately after every operation.
Recovery with Concurrent Transactions
When more than one transaction are being executed in parallel, the logs
are interleaved. At the time of recovery, it would become hard for the
recovery system to backtrack all logs, and then start recovering. To ease
this situation, most modern DBMS use the concept of 'checkpoints'.

Checkpoint
Keeping and maintaining logs in real time and in real environment may fill
out all the memory space available in the system. As time passes, the log
file may grow too big to be handled at all. Checkpoint is a mechanism
where all the previous logs are removed from the system and stored
permanently in a storage disk. Checkpoint declares a point before which
the DBMS was in consistent state, and all the transactions were
committed.

Recovery
When a system with concurrent transactions crashes and recovers, it
behaves in the following manner −

 The recovery system reads the logs backwards from the end to
the last checkpoint.
 It maintains two lists, an undo-list and a redo-list.
 If the recovery system sees a log with <T , Start> and <T ,
n n

Commit> or just <T , Commit>, it puts the transaction in the

n

redo-list.
 If the recovery system sees a log with <T , Start> but no
n

commit or abort log found, it puts the transaction in undo-list.

All the transactions in the undo-list are then undone and their logs are
removed. All the transactions in the redo-list and their previous logs are
removed and then redone before saving their logs.

Explain about concurrent transactions in

DBMS
A transaction is a unit of database processing which contains a set of
operations. For example, deposit of money, balance enquiry, reservation
of tickets etc.
Every transaction starts with delimiters begin transaction and terminates
with end transaction delimiters. The set of operations within these two
delimiters constitute one transaction.
main()
{
begin transaction
} end transaction
There are three possible ways in which a transaction can be executed.
These are as follows −

 Serial execution.
 Parallel execution.
Concurrent execution.
Concurrent transaction or execution includes multiple transactions which
are executed concurrently or simultaneously in the system.

Advantages
The advantages of the concurrent transactions are as follows −
 Increases throughput which is nothing but number of
transactions completed per unit time.
 It reduces the waiting time.
Example
T1= 90sec
T2= 500sec
T3= 5sec.
If we execute serially by T1->T2->T3 then transaction T3 waits for 590
sec, so we go for non-serial or concurrent transactions to reduce waiting
time.
i.e. T3 -> T1 -> T2.

Disadvantage
The disadvantage is that the execution of concurrent transactions may
result in inconsistency.

Example 1
The concurrent execution given below is in a consistent state.
Example 2
The transaction given below is not consistent.
Concurrent schedules do not keep the database in the consistent state.
The concurrent execution of the transactions has to be carried out in a
controlled environment.
If a system consists of ‘n’ number of transactions, we will have more than
‘n!’ number of concurrent schedules, out of which only a few of them are
keeping the database in consistent state.

View Serializability-

We have discussed-
 The concept of serializability helps to identify the correct non-serial schedules
that will maintain the consistency of the database.
 There are two types of serializability-

In this article, we will discuss practice problems based on view serializability.

PRACTICE PROBLEMS BASED ON VIEW

SERIALIZABILITY-

Problem-01:

Check whether the given schedule S is view serializable or not-

Solution-

 We know, if a schedule is conflict serializable, then it is surely view

serializable.
 So, let us check whether the given schedule is conflict serializable or not.

Checking Whether S is Conflict Serializable

Or Not-

Step-01:

List all the conflicting operations and determine the dependency between the
transactions-
 W1(B) , W2(B) (T1 → T2)
 W1(B) , W3(B) (T1 → T3)
 W1(B) , W4(B) (T1 → T4)
 W2(B) , W3(B) (T2 → T3)
 W2(B) , W4(B) (T2 → T4)
  W3(B) , W4(B) (T3 → T4)

Step-02:

Draw the precedence graph-

 Clearly,there exists no cycle in the precedence graph.

 Therefore, the given schedule S is conflict serializable.
 Thus, we conclude that the given schedule is also view serializable.

Problem-02:

Check whether the given schedule S is view serializable or not-

Solution-

 We know, if a schedule is conflict serializable, then it is surely view

serializable.
 So, let us check whether the given schedule is conflict serializable or not.

Checking Whether S is Conflict Serializable

Or Not-

Step-01:

List all the conflicting operations and determine the dependency between the
transactions-
 R1(A) , W3(A) (T1 → T3)
 R2(A) , W3(A) (T2 → T3)
 R2(A) , W1(A) (T2 → T1)
 W3(A) , W1(A) (T3 → T1)

Step-02:

Draw the precedence graph-

 Clearly,there exists a cycle in the precedence graph.

 Therefore, the given schedule S is not conflict serializable.

Now,
  Since, the given schedule S is not conflict serializable, so, it may or may not
be view serializable.
 To check whether S is view serializable or not, let us use another method.
 Let us check for blind writes.

Checking for Blind Writes-

 There exists a blind write W3 (A) in the given schedule S.

 Therefore, the given schedule S may or may not be view serializable.

Now,
 To check whether S is view serializable or not, let us use another method.
 Let us derive the dependencies and then draw a dependency graph.

Drawing a Dependency Graph-

 T1 firstly reads A and T3 firstly updates A.

 So, T1 must execute before T3.
 Thus, we get the dependency T1 → T3.
 Final updation on A is made by the transaction T1.
 So, T1 must execute after all other transactions.
 Thus, we get the dependency (T2, T3) → T1.
 There exists no write-read sequence.

Now, let us draw a dependency graph using these dependencies-

 Clearly,
there exists a cycle in the dependency graph.
 Thus, we conclude that the given schedule S is not view serializable.
Problem-03:

Check whether the given schedule S is view serializable or not-

Solution-

 We know, if a schedule is conflict serializable, then it is surely view

serializable.
 So, let us check whether the given schedule is conflict serializable or not.
Checking Whether S is Conflict Serializable
Or Not-

Step-01:

List all the conflicting operations and determine the dependency between the
transactions-
 R1(A) , W2(A) (T1 → T2)
 R2(A) , W1(A) (T2 → T1)
 W1(A) , W2(A) (T1 → T2)
 R1(B) , W2(B) (T1 → T2)
 R2(B) , W1(B) (T2 → T1)

Step-02:

Draw the precedence graph-

 Clearly,there exists a cycle in the precedence graph.

 Therefore, the given schedule S is not conflict serializable.

Now,
 Since, the given schedule S is not conflict serializable, so, it may or may not
be view serializable.
 To check whether S is view serializable or not, let us use another method.
 Let us check for blind writes.

Checking for Blind Writes-

  There exists no blind write in the given schedule S.
 Therefore, it is surely not view serializable.

Alternatively,
 You could directly declare that the given schedule S is not view serializable.
 This is because there exists no blind write in the schedule.
 You need not check for conflict serializability.

Problem-04:

Check whether the given schedule S is view serializable or not. If yes, then give the
serial schedule.
S : R1(A) , W2(A) , R3(A) , W1(A) , W3(A)

Solution-

For simplicity and better understanding, we can represent the given schedule
pictorially as-

 We know, if a schedule is conflict serializable, then it is surely view

serializable.
 So, let us check whether the given schedule is conflict serializable or not.
Checking Whether S is Conflict Serializable
Or Not-

Step-01:

List all the conflicting operations and determine the dependency between the
transactions-
 R1(A) , W2(A) (T1 → T2)
 R1(A) , W3(A) (T1 → T3)
 W2(A) , R3(A) (T2 → T3)
 W2(A) , W1(A) (T2 → T1)
 W2(A) , W3(A) (T2 → T3)
 R3(A) , W1(A) (T3 → T1)
 W1(A) , W3(A) (T1 → T3)

Step-02:

Draw the precedence graph-

 Clearly,there exists a cycle in the precedence graph.

 Therefore, the given schedule S is not conflict serializable.

Now,
  Since, the given schedule S is not conflict serializable, so, it may or may not
be view serializable.
 To check whether S is view serializable or not, let us use another method.
 Let us check for blind writes.

Checking for Blind Writes-

 There exists a blind write W2 (A) in the given schedule S.

 Therefore, the given schedule S may or may not be view serializable.

Now,
 To check whether S is view serializable or not, let us use another method.
 Let us derive the dependencies and then draw a dependency graph.

Drawing a Dependency Graph-

 T1 firstly reads A and T2 firstly updates A.

 So, T1 must execute before T2.
 Thus, we get the dependency T1 → T2.
 Final updation on A is made by the transaction T3.
 So, T3 must execute after all other transactions.
 Thus, we get the dependency (T1, T2) → T3.
 From write-read sequence, we get the dependency T2 → T3

Now, let us draw a dependency graph using these dependencies-

  Clearly,there exists no cycle in the dependency graph.
 Therefore, the given schedule S is view serializable.
 The serialization order T1 → T2 → T3.

Serial Schedules Vs Serializable Schedules-

Serial Schedules Serializable Schedules

No concurrency is allowed. Concurrency is allowed.

Thus, multiple transactions can execute
Thus, all the transactions necessarily
concurrently.
execute serially one after the other.

Serial schedules lead to less resource Serializable schedules improve both

utilization and CPU throughput. resource utilization and CPU throughput.

Serial Schedules are less efficient as Serializable Schedules are always better
compared to serializable schedules. than serial schedules.
(due to above reason) (due to above reason)

Types of Serializability-

Serializability is mainly of two types-

 1. Conflict Serializability
2. View Serializability

Conflict Serializability-

If a given non-serial schedule can be converted into a serial schedule by swapping its
non-conflicting operations, then it is called as a conflict serializable schedule.

Conflicting Operations-

Two operations are called as conflicting operations if all the following conditions hold
true for them-
 Both the operations belong to different transactions
 Both the operations are on the same data item
 At least one of the two operations is a write operation

Example-

Consider the following schedule-

In this schedule,
 W1 (A) and R2 (A) are called as conflicting operations.
 This is because all the above conditions hold true for them.

Checking Whether a Schedule is Conflict

Serializable Or Not-

Follow the following steps to check whether a given non-serial schedule is conflict
serializable or not-

Step-01:
Find and list all the conflicting operations.

Step-02:
Start creating a precedence graph by drawing one node for each transaction.

Step-03:
 Draw an edge for each conflict pair such that if Xi (V) and Yj (V) forms a conflict
pair then draw an edge from Ti to Tj.
 This ensures that Ti gets executed before Tj.
Step-04:
 Check if there is any cycle formed in the graph.
 If there is no cycle found, then the schedule is conflict serializable otherwise not.

Explain about conflict serializability in DBMS

Conflict serializability orders any conflicting operations in the same way
as some serial execution. A pair of operations is said to conflict if they
operate on the same data item and one of them is a write operation.
That means
Readi(x) readj(x) - non conflict read-read operation
Readi(x) writej(x) - conflict read-write operation.
Writei(x) readj(x) - conflic t write-read operation.
Writei(x) writej(x) - conflict write-write operation.
Where I and j denote two different transactions Ti and Tj.

Precedence graph
It is used to check conflict serializability.
The steps to check conflict serializability are as follows −
 For each transaction T, put a node or vertex in the graph.
 For each conflicting pair, put an edge from Ti to T j.
 If there is a cycle in the graph then schedule is not conflict
serializable else schedule is conflict serializable.

Example 1
The cycle is present so it is not conflict serializable.

Example 2
The cycle is not present, so it is conflict serializable.
Example 3
The cycle is not present, so it is conflict serializable.

What is the term serializability in DBMS?

A schedule is serialized if it is equivalent to a serial schedule. A
concurrent schedule must ensure it is the same as if executed serially
means one after another. It refers to the sequence of actions such as
read, write, abort, commit are performed in a serial manner.

Example
Let’s take two transactions T1 and T2,
If both transactions are performed without interfering each other then it is
called as serial schedule, it can be represented as follows −
 T1 T2

READ1(A)

WRITE1(A)

READ1(B)

C1

READ2(B)

WRITE2(B)

READ2(B)

C2

Non serial schedule − When a transaction is overlapped between the

transaction T1 and T2.

Example
Consider the following example −

T1 T2

READ1(A)

WRITE1(A)

READ2(B)

WRITE2(B)

READ1(B)

WRITE1(B)

READ1(B)
Types of serializability
There are two types of serializability −

View serializability
A schedule is view-serializability if it is viewed equivalent to a serial
schedule.
The rules it follows are as follows −
 T1 is reading the initial value of A, then T2 also reads the
initial value of A.
 T1 is the reading value written by T2, then T2 also reads the
value written by T1.
 T1 is writing the final value, and then T2 also has the write
operation as the final value.
Conflict serializability
It orders any conflicting operations in the same way as some serial
execution. A pair of operations is said to conflict if they operate on the
same data item and one of them is a write operation.
That means
 Readi(x) readj(x) - non conflict read-read operation
 Readi(x) writej(x) - conflict read-write operation.
 Writei(x) readj(x) - conflict write-read operation.
 Writei(x) writej(x) - conflict write-write operation.