20it403 DBMS Digital Material Unit Iii

Please read this disclaimer before proceeding:
This document is confidential and intended solely for the educational purpose of
RMK Group of Educational Institutions. If you have received this document
through email in error, please notify the system manager. This document
contains proprietary information and is intended only to the respective group /
learning community as intended. If you are not the addressee you should not
disseminate, distribute or copy through e-mail. Please notify the sender
immediately by e-mail if you have received this document by mistake and delete
this document from your system. If you are not the intended recipient you are
notified that disclosing, copying, distributing or taking any action in reliance on
the contents of this information is strictly prohibited.
20IT403
DATABASE MANAGEMENT SYSTEMS
Department: IT
Batch/Year:2020-2024/II
Created by:
R.Asha
Date:23/04/2022
1.TABLE OF CONTENTS
1. Contents
2. Course Objectives
3. Pre Requisites
4. Syllabus
5. Course outcomes
6. CO- PO/PSO Mapping
7. Lecture Plan
8. Activity based learning
9. Lecture Notes
10. Assignments
11. Part A Question & Answer
12. Part B Question & Answer
13. Supportive online Certification courses
14. Real time Applications in day to day life and to Industry
15. Contents beyond the Syllabus
16. Assessment Schedule
17. Prescribed Text Books & Reference Books
18. Mini Project suggestions

3. PRE REQUISITES
MANAGEMENT SYSTEMS
CS8492-DATABASE
CS8391-DATA
STRUCTURES
CS8251-
PROGRAMMING IN C
CS8392 – Object
Oriented Programming
2. COURSE OBJECTIVES
To understand the basic concepts of Data modeling and Database Systems.
To understand SQL and effective relational database design concepts.
To know the fundamental concepts of transaction processing, concurrency control
techniques and recovery procedure.
To understand efficient data querying and updates, with needed configuration
To learn how to efficiently design and implement various database objects and
entities
6
3. PRE REQUISITES
• 20GE101 Problem Solving and C Programming
• 20CS201 Data Structures
7
4. SYLLABUS
DATABASE MANAGEMENT SYSTEMS
UNIT I DATABASE CONCEPTS 9
Concept of Database and Overview of DBMS - Characteristics of databases, Database

Language, Types of DBMS architecture – Three-Schema Architecture - Introductions
to data models types- ER Model- ER Diagrams Extended ER Diagram reducing ER to
table Applications: ER model of University Database Application.
SQL fundamentals Views - Integrity Procedures, Functions, Cursor and Triggers
Embedded SQL Dynamic SQL.
UNIT II DATABASE DESIGN 9

Design a DB for Car Insurance Company - Draw ER diagram and convert ER model to
relational schema. Evaluating data model quality - The relational Model Schema Keys-
Relational Algebra Domain Relational Calculus- Tuple Relational Calculus -
Fundamental operations. Relational Database Design and Querying Undesirable
Properties of Relations Functional Dependency: Closures- Single Valued Dependency
Single valued Normalization (1NF, 2NF 3NF and BCNF) - Desirable properties of
Decompositions 4NF - 5NF De-normalization
UNIT III TRANSACTIONS 9
Transaction Concepts – ACID Properties – Schedules – Serializability – Concurrency

Control – Need for Concurrency – Locking Protocols – Two Phase Locking – Deadlock
– Transaction Recovery - Save Points – Isolation Levels – SQL Facilities for
Concurrency and Recovery
UNIT IV DATA STORAGE AND QUERYING 9

RAID – File Organization – Organization of Records in Files – Indexing and Hashing
–Ordered Indices – B+ tree Index Files – B tree Index Files – Static Hashing –
Dynamic Hashing – Overview of physical storage structure- stable storage, failure
classification -log based recovery, deferred database modification, check-pointing-
File Structures:-Index structures-Primary, Secondary and clustering indices. Single
and multilevel indexing.
Query Processing Overview – Algorithms for SELECT and JOIN operations – Query
optimization using Heuristics and Cost Estimation
UNIT V ADAVNCED TOPICS 9
Distributed database Implementation Concurrent transactions - Concurrency control

Lock based Time stamping-Validation based. NoSQL, NoSQL Categories - Designing
an enterprise database system - Client Server database
5. COURSE OUTCOMES
CO1: Implement SQL and effective relational database design concepts.
CO2: Map ER model to Relational model to perform database design effectively.
CO3:Compare and contrast various indexing strategies in different database systems.
CO4: Implement queries using normalization criteria and optimization techniques.
CO5: Analyse how advanced databases differ from traditional databases.
CO6: Design and deploy an efficient and scalable data storage node for varied kind of
application requirements.
6. CO- PO/PSO MAPPING
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 2 1 1 1 1 1 1 2 2 2 2 2
CO2 3 2 2 1 1 1 1 2 2 2 2 2
CO3 2 1 1 1 1 1 1 2 2 2 2 2
CO4 2 1 1 1 1 1 1 2 2 2 2 2
CO5 2 1 1 1 1 1 1 2 2 2 2 2
CO6 2 1 1 1 1 1 1 2 2 2 2 2
PSO1 PSO2 PSO3

CO1 2 2 2
CO2 2 3 2
CO3 2 2 2
CO4 2 2 2
CO5 2 2 2
CO6 2 2 2
7. LECTURE PLAN
S.No Topic No of Proposed Actual CO Taxono Mode of

Periods Date Lecture my Delivery
Date Level
1 Transaction 1 CO4 K2 PPT/ONLI

Concepts -ACID NE
LECTURE
Properties
06.04.2022 06.04.2022
2 1 CO4 K2 PPT/ONLI
Schedules NE
LECTURE
07.04.2022 07.04.2022
3 1 CO4 K2 PPT/ONLI
Serializability NE
LECTURE
09.04.2022 09.04.2022
4 1 CO4 K2 PPT/ONLI
Concurrency NE
Control LECTURE
09.04.2022 09.04.2022
5 1 CO4 K2 PPT/ONLI
Need for NE
Concurrency LECTURE
13.04.2022 13.04.2022
6 Locking 1 CO4 K2 PPT/ONLI
Protocols - Two NE
LECTURE
Phase Locking
20.04.2022 20.04.2022
7 1 CO4 K2 PPT/ONLI
Deadlock NE
LECTURE
21.04.2022 21.04.2022
8 Transaction 1 CO4 K2 PPT/ONLI
Recovery, Save NE
LECTURE
Points &
Isolation Levels 23.04.2022 23.04.2022
9 SQL Facilities for 1 CO4 K2 PPT/ONLI
Concurrency and NE
LECTURE
Recovery
23.04.2022 23.04.2022
8. Activity Based Learning
Crossword Puzzle
Transactions
8. Activity Based Learning
Brainstorming Session
Compare the following pairs of concepts/techniques:

1. Interleaved vs simultaneous concurrency
2. Serial vs serialisable schedule
3. Shared vs exclusive lock
4. Basic vs conservative 2PL
5. Wait-for vs wound-wait deadlock prevention protocol
6. Deadlock vs livelock
9. LECTURE NOTES
Unit III
9.1Transaction Concepts - ACID Properties
9.1.1 Transaction Concept:
The term transaction refers to a collection of operations that form a single logical unit of
work.
A transaction is a unit of program execution that accesses and possibly updates

various data items.
For Example, transfer of money from one account to another is a transaction consisting of
two updates, one to each account.
A transaction is delimited by statements (or function calls) of the form begin transaction
and end transaction.
The transaction consists of all operations executed between the begin transaction and end
transaction.
Since a transaction is indivisible, it either executes in its entirety or not at all.

9.1.2 A Simple Transactional Model:
Transactions access data using two operations:
read(X)
Transfers the data item X from the database to a variable X, in the main memory
buffer of the transaction that executed the read operation.
write(X)
Transfers the value in the variable X in the main-memory buffer of the
transaction that executed the write to the data item X in the database.
Let Ti be a transaction that transfers $50 from account A to account B. This transaction can
be defined as:
T i: read(A);
A := A−50;
write(A);
read(B);
B := B + 50;
write(B).
9.1 Transaction Concepts - ACID Properties
ACID Properties
(A-Atomicity, C-Consistency, I-Isolation, D-Durability)
Atomicity
“Either all operations of the transaction are reflected properly in the
database, or none are.”
Assume that, before the execution of transaction Ti, the values of accounts A and
B are $1000 and $2000, respectively.
Now suppose that, during the execution of transaction Ti, a failure happened after
the write(A) operation but before the write(B) operation.
In this case, the values of accounts A and B reflected in the database are $950
and $2000. The system destroyed $50 as a result of this failure.
The sum of A+B before and after the execution of transaction is not same and the
database is now in inconsistent state.
We must ensure that such inconsistencies are not visible in a database system.
The basic idea behind ensuring atomicity is this:
The database system keeps track (on disk) of the old values of any data on which
a transaction performs a write.
This information is written to a file called the log.
If the transaction does not complete its execution, the database system restores
the old values from the log to make it appear as though the transaction never
executed.
Ensuring Atomicity is the responsibility of the recovery system of the database.

9.1. Transaction Concepts – ACID Properties
Consistency:
“The consistency requirement here is that the sum of A and B be
unchanged by the execution of the transaction.”
Without the consistency requirement, money could be created or destroyed by

the transaction.
The consistency requirement verifies that, if the database is consistent before an

execution of the transaction, the database remains consistent after the execution
of the transaction.
Ensuring consistency for an individual transaction is the responsibility of the

Application programmer who codes the transaction.
Isolation:
“If several transactions are executed concurrently, their operations may
interleave in some undesirable way, resulting in an inconsistent state.”
For example:
If the database is temporarily inconsistent with the deducted total written to A
and the increased total yet to be written to B. (A - $950, B - $2000)
If a second concurrently running transaction reads A and B at this intermediate
point and computes A+B, it will observe an inconsistent value.
A way to avoid the problem of concurrently executing transactions is to
execute transactions serially—that is, one after the other.

Concurrent execution of transactions provides significance performance
benefits such as:
 Improved throughput and Resource utilization
 Reduced waiting time
The isolation property of a transaction ensures that the concurrent execution of

transactions results in a state that is equivalent to a state that could have been
obtained when the transactions are executed on eat a time in some order.
Ensuring Isolation property is the responsibility of Concurrency-control component

of the database system.
Durability:
“The durability property guarantees that, once a transaction completes
successfully, all the updates on the database persist, even if there is a
system failure after the transaction completes execution.”
We assume for now that a failure of the computer system may result in loss of
data in main memory, but data written to disk are never lost.
Durability is guaranteed by ensuring that either:
1. The transaction updates have been written to disk before the transaction
completes.
2. Information about the transaction updates and the data written to disk is
sufficient to enable the database to reconstruct the updates when the database
system is restarted after the failure.
Ensuring durability is the responsibility of the recovery system of the database.

9.1.3 Storage Structure:

To ensure the atomicity and durability properties of a transaction, we must
gain a better understanding of how the various data items in the database may be
stored and accessed.
Volatile storage:
Information residing in volatile storage does not usually survive system crashes.
Examples of such storage are main memory and cache memory.
Nonvolatile storage:
Information residing in nonvolatile storage survives system crashes.
Examples of nonvolatile storage include
Secondary storage devices such as magnetic disk and flash storage, used for
online storage.
Tertiary storage devices such as optical media, and magnetic tapes, used for
archival storage.
Stable storage:
Information residing in stable storage is never lost.
To implement stable storage, we replicate the information in several nonvolatile

storage media(usually disk) with independent failure modes.
Updates must be done with care to ensure that a failure during an update to
stable storage does not cause a loss of information.
For a transaction to be durable, its changes need to be written to stable storage.
Similarly, for a transaction to be atomic, log records need to be written to stable

storage before any changes are made to the database on disk.
Clearly, the degree to which a system ensures durability and atomicity depends on
how stable its implementation of stable storage really is.
9.1.4 Transaction Atomicity and Durability

A transaction may not always complete its execution successfully. Such a transaction
is termed aborted.
Once the changes caused by an aborted transaction have been undone, we say that
the transaction has been rolled back. It is part of the responsibility of the recovery
scheme to manage transaction aborts. This is done typically by maintaining a log.
A transaction that completes its execution successfully is said to be committed. Once

a transaction has committed, we cannot undo its effects by aborting it. The only way
to undo the effects of a committed transaction is to execute a Compensating
transaction.
States of a Transaction:
A transaction must be in one of the following states:
Active - the initial state; the transaction stays in this state while it is executing.
Partially committed - after the final statement has been executed.
Failed - after the discovery that normal execution can no longer proceed.
Aborted – after the transaction has been rolled back and the database has been
restored to its state prior to the start of the transaction.
Committed - after successful completion.
Fig : States of a Transaction

Active State:
A transaction is in active state when it is executing the instructions of the

transaction.
Partially committed state:
When a transaction finishes its last statement, it enters the partially committed
state.
At this point, there are two possibilities:
The transaction may complete its execution successfully.
The transaction may have some failure and aborted.
Committed state:
After completion of the transaction, consistency check is made.
If the consistency check is successful, the transaction enters the committed

state.
Once the transaction is committed, the updates of the transaction are made
permanent to the database.
Failed state:
If the consistency check fails, the transaction is aborted and rolled back.
The transaction is rolled back to undo the effect of its write operations on the
database.
Terminated state:
The terminated state corresponds to the transaction leaving the system.

9.1.5 Transaction Isolation
Allowing multiple transactions to update data concurrently causes several
complications with consistency of the data, as we saw earlier.
Ensuring consistency in spite of concurrent execution of transactions requires extra

work; it is far easier to insist that transactions run serially—that is, one at a time,
each starting only after the previous one has completed.
However, there are two good reasons for allowing concurrency:
Improved throughput and resource utilization.

A transaction consists of many steps. Some involve I/O activity; others involve CPU
activity. The CPU and the disks in a computer system can operate in parallel.
Therefore, I/O activity can be done in parallel with processing at the CPU.
The parallelism of the CPU and the I/O system can therefore be exploited to run
multiple transactions in parallel.
All of this increases the throughput of the system—that is, the number of
transactions executed in a given amount of time. Correspondingly, the processor
and disk utilization also increase.
Reduced Waiting time.
There may be a mix of transactions running on a system, some short and some
long. If transactions run serially, a short transaction may have to wait for a
preceding long transaction to complete, which can lead to unpredictable delays in
running a transaction.
Concurrent execution reduces the unpredictable delays in running transactions.

Moreover, it also reduces the average response time: the average time for a
transaction to be completed after it has been submitted.
9.2. Schedules
When several transactions run concurrently, the isolation property may be

violated, resulting in database consistency being destroyed despite the
correctness of each individual transaction.
The database system must control the interaction among the concurrent
transactions to prevent them from destroying the consistency of the database. It
does so through a variety of mechanisms called concurrency-control schemes.
The concept of schedules to help identify those executions that are guaranteed to
ensure the isolation property and thus database consistency.
Schedules represent the chronological order in which instructions are executed in

the system.
A schedule can have many transactions in it, each comprising of a number of

instructions.
A transaction that successfully completes its execution will have a commit

instruction as the last statement.
A transaction that fails to successfully complete its execution will have an

abort instruction as the last statement.
Types of Schedules:
1. Serial Schedule
2. Non-serial Schedule
3. Recoverable Schedule
4. Non-recoverable Schedule
5. Cascadeless Schedule
6. Strict Schedule
9.2. Schedules
9.2.1 Serial Schedule:
A schedule S is serial if, the transactions in the schedule are executed one after
the other(not interleaved).
Example:
Consider the schedule S with two transactions T1 and T2.
Schedule1 : T1 is followed by T2 Schedule2 : T2 is followed by T1
9.2.2 Non-Serial Schedule:

A schedule S is non-serial if, the operations of the transactions in the schedule
are interleaved.
Example:
• We can ensure consistency of the database under concurrent execution by

making sure that any concurrent schedule that is executed has the same effect as
a schedule that could have occurred in serial manner.
9.2. Schedules
9.2.3 Recoverable Schedule
A schedule S is recoverable if, each transaction commits only after all

transactions from which it has read the data has committed.
Example:
In this schedule,
• T2 reads the value of A updated by T1. (T2 is dependent on T1)
• T1 is committed before T2 gets committed.
• So, T2 is safe from rollback due to failure of T1.
• Thus, this is a recoverable schedule.
9.2.4 Non-Recoverable Schedule
A schedule S is non-recoverable if, a transaction commits only before the

transaction from which it has read the data has committed.
9.2. Schedules
Example:
In this schedule,
• T2 reads the value of A updated by T1. (T2 is dependent on T1)
• T2 is committed before T1 gets committed.
• So, T2 may suffer from inconsistency due to failure of T1 after a point where T2
commits.
• Thus, this is a non-recoverable schedule.
9.2.5 Cascadeless Schedule

Cascading Rollback:
Even if a schedule is recoverable, to recover correctly from the failure of a

transaction Ti, we may have to roll back several other transactions that read the
value produced by Ti.
This condition is called as Cascading Rollback.

9.2. Schedules
Example:
Consider the schedule S with three transactions T1,T2 and T3 for understanding
Cascading Rollback.
In this schedule,
• Transaction T1 writes a value of A that is read by transaction T2.
• Transaction T2 writes a value of A that is read by transaction T3.
• Suppose that, at this point, T1 fails. T1 must be rolled back.
• Since T2 is dependent on T1, T2 must be rolled back.
• Since T3 is dependent on T2, T3 must be rolled back.
• This phenomenon, in which a single transaction failure leads to a series of

transaction rollbacks, is called cascading rollback.
Cascadeless Schedule:
A schedule S is cascadeless if, every transaction in the schedule reads only the
data items that were written by committed transactions.
Cascading rollbacks will not occur in a cascadeless schedule since it reads committed
data items.
Example:
Consider the schedule S with three transactions T1,T2 and T3.
9.2. Schedules
In this schedule, the transaction reads the value A of a committed transaction.
There is no possibility of cascading rollback.
Thus, this is a cascadeless schedule.
9.2.6 Strict Schedule
A schedule S is strict if, the transactions in the schedule can neither read nor
write an item A until the last transaction that wrote A has committed.
Example:
• In this, the transaction T2 ,reads and writes the value A of the committed
transaction T1.
• Thus, this is a strict schedule.

9.3. Serializability
A schedule S of „n‟ transactions is serializable if it is equivalent to some

serial schedule of the same „n‟ transactions.
Different forms of schedule equivalence give rise to the notions of:
Conflict serializability
View serializability
9.3.1 CONFLICT SERIALIZABILITY
Let us consider a schedule S in which there are two consecutive instructions, I and
J, of transactions Ti and Tj, respectively ( i != j ).
If the two consecutive instructions I and J refer to different data items, then we can
swap I and J without affecting the results of any instruction in the schedule.
If the two consecutive instructions I and J refer to the same data item Q, then the
order of the two steps may matter.
Since we are dealing with only read and write instructions, there are four cases that
we need to consider:
1. I = read(Q), J = read(Q). The order of I and J does not matter, since

the same value of Q is read by Ti and Tj, regardless of the order.
2. I=write(Q), J=read(Q). The order of I and J matters.
3. I =read(Q), J =write(Q). The order of I and J matters.
4. I=write(Q), J=write(Q). The order of I and J matters.
I and J conflict (i.e. order of I and J matters) if they are operations by different
transactions on the same data item, and at least one of these instructions is a write
operation.
Conflict Equivalence:
• If a schedule S can be transformed into a schedule S’ by a series of
swaps of non-conflicting instructions, we say that S and S’ are
conflict equivalent
Conflict Serializability:
• A schedule S is conflict serializable if it is conflict equivalent to a serial
schedule.
Example for Conflict Serializability
Consider two schedules S (Concurrent Schedule) and S’ (Serial Schedule)
Schedule S can be transformed into Serial schedule S’, by a series of swaps of non-
conflicting instructions such as:
1. Read(B) of T1 and Write(A) of T2 are non-conflicting and swapped
2. Read(B) of T1 and Read(A) of T2 are non-conflicting and swapped
3. Write(B) to T1 and Write(A) of T2 are non-conflicting and swapped
4. Write(B) of T1 and Read(A) of T2 are non-conflicting and swapped
After swapping the non-conflicting instructions, the Schedule S is conflict equivalent

to Serial schedule S’.
Therefore, Schedule S is conflict serializable.

9.3.2 Testing Conflict Serializability : Precedence Graph

Let us consider a schedule S in which there are two consecutive instructions, I
and J, of transactions Ti and Tj, respectively ( i != j ).
If the two consecutive instructions I and J refer to different data items, then we
can swap I and J without affecting the results of any instruction in the schedule.
Consider a schedule S. We construct a directed graph, called a precedence

graph, from S.
This graph consists of a pair G = (V, E), where V is a set of vertices and E is a set
of edges.
The set of vertices consists of all the transactions participating in the schedule.
The set of edges consists of all edges Ti →Tj for which one of three conditions
holds:
Ti executes write(Q) before Tj executes read(Q).

Ti executes read(Q) before Tj executes write(Q).
Ti executes write(Q) before Tj executes write(Q).
If an edge Ti →Tj exists in the precedence graph, then, in any serial schedule S’
equivalent to S, Ti must appear before Tj.
If the precedence graph for S has a cycle, then schedule S is not conflict
serializable.
If the graph contains no cycles, then the schedule S is conflict serializable.
A serializability order of the transactions can be obtained by the process called

topological sorting.
The topological sorting for a directed acyclic graph is the linear ordering of
vertices. For every edge U->V of a directed graph, the vertex U will come before
vertex U in the ordering. Topological sort starts with a node which has zero
indegree (i.e) no incoming edges
Example 1:
Consider a Schedule S with three Transactions T1, T2 and T3 as follows:
Schedule S Precedence Graph for S
The Precedence Graph for the Schedule S contains the following edges:
• T3 ->T1 because, T3 executes Read(x) before T1 executes write(x)
• T2 ->T3 because, T2 executes Read(y) before T3 executes Write(y) and T2

executes Read(z) before T1 executes Write(z).
• T2 ->T1 because, T2 executes Write(z) before T1 executes Write(z)
If an edge Ti →Tj exists in the precedence graph, then, in any serial schedule S’
equivalent to S, Ti must appear before Tj.
The precedence graph for S does not form a cycle, then schedule S is conflict
serializable.
Using Topological Sorting, the serializability order of the Schedule is identified as

T2 ->T3->T1 (i.e) The schedule S is equivalent to a Serial Schedule in which T2
followed by T3 followed by T1.
Example 2:
Consider a Schedule S with two Transactions T1 and T2 as follows:
T1 ->T2 because,
•T1 executes Read(A) before T2 executes write(A)
•T1 executes write(A) before T2 executes write(A)
•T1 executes Read(B) before T2 executes write(B)
•T1 executes write(B) before T2 executes write(B)
The precedence graph for S does not form a cycle, then schedule S is conflict
serializable.
Using Topological Sorting, the serializability order of the Schedule is identified as
T1 ->T2 (i.e) The schedule S is equivalent to a Serial Schedule in which T1 followed
by T2.
Example 3:
Consider a Schedule S with two Transactions T1 and T2 as follows:
T1 ->T2 because,
•T1 executes Read(A) before T2 executes Write(A)
•T1 executes Read(B) before T2 executes Write(B)
•T1 executes Write(B) before T2 executes Write(B)
T2 ->T1 because,
•T2 executes Read(A) before T1 executes Write(A)

•T1 executes Read(B) before T2 executes Write(B)
The precedence graph for S has a cycle, then schedule S is NOT conflict
serializable.
9.3.3 VIEW SERIALIZABILITY
View equivalence:
Let S and S´ be two schedules with the same set of transactions. S and S´ are
view equivalent if the following three conditions are met, for each data item Q,
1. If a transaction Ti reads the initial value of Q in schedule S, then in schedule

S’ also transaction Ti must read the initial value of Q.
2. If a transaction Ti executes read(Q), and that value was produced by

write(Q) of transaction Tj in schedule S, then in schedule S’ also transaction
Ti must read the value of Q that was produced by the same write(Q)
operation of transaction Tj .
3. The transaction (if any) that performs the final write(Q) operation in
schedule S must also perform the final write(Q) operation in schedule S’.
Conditions 1 and 2 ensure that each transaction reads the same values in both
schedules and, therefore, performs the same computation.
Condition 3, coupled with conditions 1 and 2, ensures that both schedules result
in the same final system state.
View serializability:
A schedule S is view serializable if it is view equivalent to a serial schedule.

Example:
Schedule S is view equivalent to the serial schedule S’ since:
Read(Q) reads the initial value of Q in both the schedules.
T3 performs the final write of Q in both the schedules.
The above schedule S with three transactions T1, T2, T3 is view-serializable but not
conflict serializable because swapping of non-conflicting operations does not result in
conflict equivalence to the serial schedule.
BLIND WRITES:
Blind writes occurs in a schedule perform which does write operations without having
performed a read operation.
Example:
Blind writes appears in schedule S because, it performs write operations without having
performed a read operation.
Conflict Serializable vs. View Serializable Schedule
View Serializable
Conflict
Serializable
Every conflict serializable schedule is view serializable.

But, every view serializable schedule may not be conflict serializable.
Any view serializable schedule that is not conflict serializable must contain a blind
write.
It is easy to test conflict serializability but, it is expensive to test view
serializability.
Most of the concurrency control schemes used in practice is based on conflict
serializability.
9.4 Concurrency Control
Concurrency Control in Database Management System is a procedure of

managing simultaneous operations without conflicting with each other. It ensures
that Database transactions are performed concurrently and accurately to produce
correct results without violating data integrity of the respective Database.
Concurrency control techniques that are used to ensure the noninterference or
isolation property of concurrently executing transactions. Most of these techniques
ensure serializability of schedule. Using concurrency control protocols (sets of rules)
that guarantee serializability.
Concurrent access is quite easy if all users are just reading data. There is
no way they can interfere with one another. Though for any practical Database, it
would have a mix of READ and WRITE operations and hence the concurrency is a
challenge.
DBMS Concurrency Control is used to address such conflicts, which mostly

occur with a multi-user system. Therefore, Concurrency Control is the most
important element for proper functioning of a Database Management System where
two or more database transactions are executed simultaneously, which require
access to the same data.
Potential problems of Concurrency
Lost Updates occur when multiple transactions select the same row and update
the row based on the value selected
Uncommitted dependency issues occur when the second transaction selects a

row which is updated by another transaction (dirty read)
Non-Repeatable Read occurs when a second transaction is trying to access the

same row several times and reads different data each time.
Incorrect Summary issue occurs when one transaction takes summary over the
value of all the instances of a repeated data-item, and second transaction update
few instances of that specific data-item. In that situation, the resulting summary
does not reflect a correct result.
9.5 Need for Concurrency Control
There are two good reasons for allowing concurrency.
1. Improved throughput and resource utilization:
• A transaction consists of many steps. Some involve I/O activity; others involve CPU
activity. The CPU and the disks in a computer system can operate in parallel.
Therefore, I/O activity can be done in parallel with processing at the CPU.
• The parallelism of the CPU and the I/O system can therefore be exploited to run
multiple transactions in parallel.
• All of this increases the throughput of the system – that is, the number of
transactions executed in a given amount of time.
• Correspondingly, the processor and disk utilization also increase in other words, the
processor and disk spend less time idle, or not performing any usually work.
2. Reduced waiting time:
• There may be a mix a transactions running on a system, some short and long
transactions.
• If transactions run serially, a short transaction may have to wait for a preceding long
transaction to complete, which can lead to unpredictable delays in running a
transaction.
• If the transactions are operating on different parts of the database, it is better to let
them run concurrently, sharing the CPU cycles and disk accesses among them.
Concurrent execution reduces the unpredictable delays in running transactions.
• Moreover, it also reduces the average response time: the average time for a
transaction to be completed after it has been submitted.
9.5 Need for Concurrency Control
Some more reasons for using Concurrency control method is DBMS:
To apply Isolation through mutual exclusion between conflicting transactions
To resolve read-write and write-write conflict issues
To preserve database consistency through constantly preserving execution

obstructions
The system needs to control the interaction among the concurrent transactions. This
control is achieved using concurrent-control schemes.
Concurrency control helps to ensure serializability
Types of concurrency control protocols:
1. Lock based protocols
2. Two phase locking protocols
3. Timestamp protocols
4. Multiversion concurrency control protocols
5. Multiple granularity concurrency control protocol

9.6 Locking Protocols - Two Phase Locking
Lock based Protocols helps to overcome the issues related to accessing the DBMS
concurrently by locking the current transaction for only one user. The assumption or
more like a requirement that is necessary for implementing Lock Based Protocol is
that all the data items involved are accessed in a mutually exclusive manner i.e. when
one transaction is active by a user, no other transaction is allowed access to update or
modify that transaction at the same time. As the name suggests, the Lock based
protocols when in action, are required to acquire a lock to access the data items and
release the lock when the said transaction is completed.
Types of Locks
Several types of locks are used in concurrency control
• Binary locks
• Shared/exclusive locks also known as read/write locks
Binary Locks
A binary lock can have two states or values: locked and unlocked (or 1 and 0, for
simplicity)
A distinct lock is associated with each database item X.
If the value of the lock on X is 1, item X cannot be accessed by a database
operation that requests the item.
If the value of the lock on X is 0, the item can be accessed when requested, and
the lock value is changed to 1. We refer to the current value (or state) of the
lock associated with item X as lock(X).
Two operations are used with binary locking

• lock_item
• unlock_item
That is, A transaction requests access to an item X by first issuing a lock_item(X)
operation.
• If LOCK(X) = 1, the transaction is forced to wait.
• If LOCK(X) = 0, it is set to 1 (the transaction locks the item) and the transaction is
allowed to access item X.
Lock and unlock operations for binary locks
It is quite simple to implement a binary lock; all that is needed is a binary-valued

variable, LOCK, associated with each data item X in the database.
In its simplest form, each lock can be a record with three fields:
<Data_item_name, LOCK, Locking_Transaction> plus a queue for transactions
that are waiting to access the item.
System Lock Tables
The system needs to maintain only these records for the items that are currently
locked in a lock table, which could be organized as a hash file on the item name. Items
not in the lock table are considered to be unlocked. The DBMS has a lock manager
subsystem to keep track of and control access to locks. Every transaction must obey
the following rules:
1. A transaction T must issue the operation lock_item(X) before any read_item(X) or

write_item(X) operations are performed in T.
2. A transaction T must issue the operation unlock_item(X) after all read_item(X) and
write_item(X) operations are completed in T.
3. A transaction T will not issue a lock_item(X) operation if it already holds the lock on
item X.
4. A transaction T will not issue an unlock_item(X) operation unless it already holds the
lock on item X.
Shared/Exclusive locks
There are various modes in which a data item may be locked. Two modes are given
below:
1. Shared Mode
If a transaction Ti has obtained a shared-mode lock (denoted by S) on item Q, then Ti

can read, but cannot write, Q.
2. Exclusive Mode
If a transaction Ti has obtained an exclusive-mode lock (denoted by X) on item Q, then

Ti can both read and write Q.
Lock-compatibility
When we use the shared/exclusive locking scheme, the system must enforce the
following rules:
1. A transaction T must issue the operation read_lock (X) or write_lock (X) before any
read_item(X) operation is performed in T.
2. A transaction T must issue the operation write_lock (X) before any write_item (X)
operation is performed in T.
3. A transaction T must issue the operation unlock(X) after all read_item(X) and
write_item(X) operations are completed in T.3
4. A transaction T will not issue a read_lock (X) operation if it already holds a read
(shared) lock or a write (exclusive) lock on item X.
5. A transaction T will not issue a write_lock(X) operation if it already holds a read

(shared) lock or write (exclusive) lock on item X.
Locking and unlocking operations for two mode (read-write or shared-exclusive) locks
Banking Example
Consider again the banking example. Let A and B be two accounts that are accessed
by transactions T1 and T2. Transaction T1 transfers $50 from account B to account A
Transaction T2 displays the total amount of money in accounts A and B—that is, the
sum A + B. This scenario is shown below.
Two Phase Locking Protocol
One protocol that ensures serializability is the two-phase locking protocol. This
protocol requires that each transaction issue lock and unlock requests in two phases:
1. Growing phase:
A transaction may obtain locks, but may not release any lock.
2. Shrinking phase:
A transaction may release locks, but may not obtain any new locks.
Initially, a transaction is in the growing phase. The transaction acquires locks as

needed. Once the transaction releases a lock, it enters the shrinking phase, and it can
issue no more lock requests. Consider Transactions T1,T2,T3 and T4 given below:
For example, transactions T3 and T4 are two phase. On the other hand,
transactions T1 and T2 are not two phase.
The point in the schedule where the transaction has obtained its final lock (the end
of its growing phase) is called the lock point of the transaction.
Guaranteeing Serializability by Two-Phase Locking
A transaction is said to follow the two-phase locking protocol if all locking operations
(read_lock, write_lock) precede the first unlock operation in the transaction.
Such a transaction can be divided into two phases:
Expanding or growing (first) phase:
During the expanding phase which new locks on items can be acquired but none can
be released
Shrinking (second) phase:
During shrinking phase which existing locks can be released but no new locks can be
acquired. If lock conversion is allowed, then upgrading of locks (from read-locked to
writelocked) must be done during the expanding phase, and downgrading of locks
(from write-locked to read-locked) must be done in the shrinking phase. Hence, a
read_lock(X) operation that downgrades an already held write lock on X can appear
only in the shrinking phase.
Transactions that do not obey two-phase locking.
(a) Two transactions T1 and T2. (b) Results of possible serial schedules of T1 and
T2.
• Transactions T1 and T2 do not follow the two-phase locking protocol because the
write_lock(X) operation follows the unlock(Y) operation in T1, and similarly the
write_lock(Y) operation follows the unlock(X) operation in T2.
• The transactions can be rewritten as T1’ and T2’. Transactions T1’ and T2’, which are
the same as T1 and T2 but follow the two-phase locking protocol.
Note that the above transaction can produce a Deadlock.
It can be proved that, if every transaction in a schedule follows the two-phase locking
protocol,
• The schedule is guaranteed to be serializable, obviating the need to test for

serializability of schedules.
• The locking protocol, by enforcing two-phase locking rules, also enforces serializability.
Two-phase locking may limit the amount of concurrency that can occur in a schedule
because a transaction T may not be able to release an item X after it is through using
it if T must lock an additional item Y later; or conversely, T must lock the additional
item Y before it needs it so that it can release X.
• Hence, X must remain locked by T until all items that the transaction needs to read or
write have been locked; only then can X be released by T. Meanwhile, another
transaction seeking to access X may be forced to wait, even though T is done with X;
conversely, if Y is locked earlier than it is needed, another transaction seeking to
access Y is forced to wait even though T is not using Y yet.
• This is the price for guaranteeing serializability of all schedules without having to
check the schedules themselves.
• Although the two-phase locking protocol guarantees serializability (that is, every
schedule that is permitted is serializable), it does not permit all possible serializable
schedules (that is, some serializable schedules will be prohibited by the protocol).
Types of Two-Phase Locking:
• Basic
• Conservative
• Strict
•Rigorous Two-Phase Locking
Basic Two-Phase Locking :
There are a number of variations of two-phase locking (2PL). The technique just
described is known as basic 2PL.
Conservative 2PL :
A variation known as conservative 2PL (or static 2PL) requires a transaction to lock all
the items it accesses before the transaction begins execution, by predeclaring its read-
set and write-set. The read-set of a transaction is the set of all items that the
transaction reads, and the write-set is the set of all items that it writes. If any of the
predeclared items needed cannot be locked, the transaction does not lock any item;
instead, it waits until all the items are available for locking. Conservative 2PL is a
deadlock-free protocol
Strict two-phase locking protocol:
This protocol requires not only that locking be two phase, but also that all exclusive-
mode locks taken by a transaction be held until that transaction commits. This
requirement ensures that any data written by an uncommitted transaction are locked
in exclusive mode until the transaction commits, preventing any other transaction from
reading the data.
Strict 2PL is not deadlock-free.
Rigorous two-phase locking protocol:
A more restrictive variation of strict 2PL is rigorous 2PL, which also guarantees strict
schedules. In this variation, a transaction T does not release any of its locks (exclusive
or shared) until after it commits or aborts, and so it is easier to implement than strict
2PL.
It requires that all locks be held until the transaction commits.

Lock conversions
A transaction that already holds a lock on item X is allowed under certain conditions to
convert the lock from one locked state to another.
Types
1. Upgrade
2. Downgrade
• A mechanism can be provided for upgrading a shared lock to an exclusive lock, and
downgrading an exclusive lock to a shared lock.
• We denote conversion from shared to exclusive modes by upgrade, and from exclusive
to shared by downgrade.
• Lock conversion cannot be allowed arbitrarily. Rather, upgrading can take place in only
the growing phase, whereas downgrading can take place in only the shrinking phase.
9.7 Deadlock
Deadlock
A system is in a deadlock state if there exists a set of transactions such that every
transaction in the set is waiting for another transaction in the set. More precisely,
there exists a set of waiting transactions {T0, T1,..., Tn} such that T0 is waiting for a
data item that T1 holds, and T1 is waiting for a data item that T2 holds, and ... , and
Tn−1 is waiting for a data item that Tn holds, and Tn is waiting for a data item that T0
holds. None of the transactions can make progress in such a situation.
Deadlock occurs when each transaction T in a set of two or more transactions is

waiting for some item that is locked by some other transaction T’ in the set. Hence,
each transaction in the set is in a waiting queue, waiting for one of the other
transactions in the set to release the lock on an item. But because the other
transaction is also waiting, it will never release the lock.
There are two principal methods for dealing with the deadlock problem. We can use a
deadlock prevention protocol to ensure that the system will never enter a deadlock
state. Alternatively, we can allow the system to enter a deadlock state, and then try to
recover by using a deadlock detection and deadlock recovery scheme.
Example:
A simple example is shown in below Figure, where the two transactions T1’and T2’ are
deadlocked in a partial schedule; T1’ is in the waiting queue for X, which is locked by
T2’, while T2’ is in the waiting queue for Y, which is locked by T1’. Meanwhile, neither
T1’ nor T2’ nor any other transaction can access items X and Y.
Illustrating the deadlock problem. (a) A partial schedule of T1’ and T2’ that is in a
state of deadlock. (b) A wait-for graph for the partial schedule in (a).
9.7 Deadlock
Deadlock Handling Mechanisms:
1. Deadlock Prevention
2. Deadlock Detection
3. Deadlock Recovery
1. Deadlock Prevention
Deadlock prevention protocol to ensure that the system will never enter a deadlock
state.
a) Conservative Two phase locking Protocols:
One way to prevent deadlock is to use a deadlock prevention protocol. One deadlock
prevention protocol, which is used in conservative two-phase locking, requires that
every transaction lock all the items it needs in advance . If any of the items cannot be
obtained, none of the items are locked. Rather, the transaction waits and then tries
again to lock all the items it needs. Obviously this solution further limits concurrency.
A second protocol, which also limits concurrency, involves ordering all the items in the
database and making sure that a transaction that needs several items will lock them
according to that order. This requires that the programmer (or the system) is aware of
the chosen order of the items, which is also not practical in the database context. A
number of other deadlock prevention schemes have been proposed that make a
decision about what to do with a transaction involved in a possible deadlock situation:
• Should it be blocked and made to wait or should it be aborted, or should the

transaction preempt and abort another transaction?
b) Time stamp protocol
Some of these techniques use the concept of transaction timestamp TS(T), which is a
unique identifier assigned to each transaction. The timestamps are typically based on
the order in which transactions are started; hence, if transaction T1 starts before
transaction T2, then TS(T1) < TS(T2). Notice that the older transaction (which starts
first) has the smaller timestamp value.
9.7 Deadlock
Two different deadlock-prevention schemes using timestamps have been proposed:
A. Wait-Die Scheme
The wait–die scheme is a non-preemptive technique. When transaction Ti requests a data

item currently held by Tj , Ti is allowed to wait only if it has a timestamp smaller than
that of Tj (that is, Ti is older than Tj). Otherwise, Ti is rolled back (dies). For example,
suppose that transactions T14, T15, and T16 have timestamps 5, 10, and 15,
respectively. If T14 requests a data item held by T15, then T14 will wait. If T24 requests
a data item held by T15, then T16 will be rolled back.
B. Wound-Wait Scheme
The wound–wait scheme is a preemptive technique. It is a counterpart to the wait–die

scheme. When transaction Ti requests a data item currently held by Tj , Ti is allowed to
wait only if it has a timestamp larger than that of Tj (that is, Ti is younger than Tj).
Otherwise, Tj is rolled back (Tj is wounded by Ti).
The major problem with both of these schemes is that unnecessary rollbacks may occur.
Another simple approach to deadlock prevention is based on lock timeouts. In this
approach, a transaction that has requested a lock waits for at most a specified amount of
time. If the lock has not been granted within that time, the transaction is said to time
out, and it rolls itself back and restarts. If there was in fact a deadlock, one or more
transactions involved in the deadlock will time out and roll back, allowing the others to
proceed.
9.7 Deadlock
2. Deadlock Detection
If a system does not employ some protocol that ensures deadlock freedom, then a
detection and recovery scheme must be used. An algorithm that examines the state of
the system is invoked periodically to determine whether a deadlock has occurred. If
one has, then the system must attempt to recover from the deadlock.
To do so, the system must:
• Maintain information about the current allocation of data items to transactions, as

well as any outstanding data item requests.
• Provide an algorithm that uses this information to determine whether the system
has entered a deadlock state.
• Recover from the deadlock when the detection algorithm determines that a deadlock
exists.
Deadlock Detection - wait-for graph
Deadlocks can be described precisely in terms of a directed graph called a wait-for

graph. This graph consists of a pair G = (V, E), where V is a set of vertices and E is
a set of edges. The set of vertices consists of all the transactions in the system. Each
element in the set E of edges is an ordered pair Ti → Tj .
If Ti → Tj is in E, then there is a directed edge from transaction Ti to Tj , implying that

transaction Ti is waiting for transaction Tj to release a data item that it needs. When
transaction Ti requests a data item currently being held by transaction Tj , then the
edge Ti → Tj is inserted in the wait-for graph.
This edge is removed only when transaction Tj is no longer holding a data item
needed by transaction Ti .
A deadlock exists in the system if and only if the wait-for graph contains a cycle. Each
transaction involved in the cycle is said to be deadlocked. To detect deadlocks, the
system needs to maintain the wait-for graph, and periodically to invoke an algorithm
that searches for a cycle in the graph
9.7 Deadlock
2. Deadlock Detection - wait-for graph
Consider the wait-for graph given below:
The above which depicts the following situation:
• Transaction T17 is waiting for transactions T18 and T19.
• Transaction T19 is waiting for transaction T18.
• Transaction T18 is waiting for transaction T20.
Since the graph has no cycle, the system is not in a deadlock state.
Suppose now that transaction T20 is requesting an item held by T19.
The edge T20 → T19 is added to the wait-for graph, resulting in the new system state
shown in Figure.
This wait-for graph contains the cycle: T18 → T20 → T19 → T18.
This scenario implying that transactions T18, T19, and T20 are all deadlocked.
9.7 Deadlock
3. Deadlock Recovery
When a detection algorithm determines that a deadlock exists, the system must recover from
the deadlock. The most common solution is to roll back one or more transactions to break
the deadlock. Three actions need to be taken:
A) Selection of a victim.
Given a set of deadlocked transactions, we must determine which transaction (or

transactions) to roll back to break the deadlock. We should roll back those transactions that
will incur the minimum cost. Unfortunately, the term minimum cost is not a precise one.
Many factors may determine the cost of a rollback, including:
a. How long the transaction has computed, and how much longer the transaction will
compute before it completes its designated task.
b. How many data items the transaction has used.
c. How many more data items the transaction needs for it to complete.
d. How many transactions will be involved in the rollback.
B) Rollback.
Once we have decided that a particular transaction must be rolled back, we must determine
how far this transaction should be rolled back. The simplest solution is a total rollback:
Abort the transaction and then restart it. However, it is more effective to roll back the
transaction only as far as necessary to break the deadlock. Such partial rollback requires
the system to maintain additional information about the state of all the running transactions.
The sequence of lock requests/grants and updates performed by the transaction needs to be
recorded. The deadlock detection mechanism should decide which locks the selected
transaction needs to release in order to break the deadlock. The selected transaction must be
rolled back to the point where it obtained the first of these locks, undoing all actions it took
after that point. The recovery mechanism must be capable of performing such partial
rollbacks. Furthermore, the transactions must be capable of resuming execution after a
partial rollback.
C) Starvation.
In a system where the selection of victims is based primarily on cost factors, it may happen
that the same transaction is always picked as a victim. As a result, this transaction never
completes its designated task, thus there is starvation. We must ensure that a transaction
can be picked as a victim only a (small) finite number of times. The most common solution is
to include the number of rollbacks in the cost factor.
9.8 Transaction Recovery , Save Points & Isolation Levels
Transaction Recovery
Recovery techniques are heavily dependent upon the existence of a special file known as
a system log. It contains information about the start and end of each transaction and
any updates which occur in the transaction. The log keeps track of all transaction
operations that affect the values of database items. This information is needed to
recover from transaction failure.
The log is kept on disk start_transaction(T): This log entry records that transaction T
starts the execution.
• read_item(T, X): This log entry records that transaction T reads the value of database
item X.
• write_item(T, X, old_value, new_value): This log entry records that transaction T

changes the value of the database item X from old_value to new_value. The old value is
sometimes known as a before an image of X, and the new value is known as an
afterimage of X.
• commit(T): This log entry records that transaction T has completed all accesses to the
database successfully and its effect can be committed (recorded permanently) to the
database.
• abort(T): This records that transaction T has been aborted.
• checkpoint: 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.
A transaction T reaches its commit point when all its operations that access the database
have been executed successfully i.e. the transaction has reached the point at which it
will not abort (terminate without completing). Once committed, the transaction is
permanently recorded in the database. Commitment always involves writing a commit
entry to the log and writing the log to disk. At the time of a system crash, item is
searched back in the log for all transactions T that have written a start_transaction(T)
entry into the log but have not written a commit(T) entry yet; these transactions may
have to be rolled back to undo their effect on the database during the recovery process.
Save Points in Transaction Recovery
We can declare intermediate markers called savepoints within the context of a

transaction. Savepoints divide a long transaction into smaller parts.
A savepoint is a way of implementing transactions within a relational database

management system by indicating a point within a transaction that can be "rolled
back to" without affecting any work done by the transaction before the savepoint
was created.
Multiple savepoints can exist within a single transaction.
Savepoints are useful for implementing complex error recovery in database

applications. If an error occurs in the midst of a multiple-statement transaction,
the application may be able to recover from the error (by rolling back to a
savepoint) without needing to abort the entire transaction.
A savepoint can be declared by issuing a SAVEPOINT name statement.
All changes made after a savepoint has been declared can be undone by issuing a
ROLLBACK TO SAVEPOINT name command.
Issuing RELEASE SAVEPOINT name will cause the named savepoint to be

discarded, but will not otherwise affect anything.
Issuing the commands ROLLBACK or COMMIT will also discard any savepoints
created since the start of the main transaction.
Issuing the commands ROLLBACK or COMMIT will also discard any savepoints
created since the start of the main transaction.
Savepoints are similarly useful in application programs. If a procedure contains

several functions, then you can create a savepoint before each function begins.
Then, if a function fails, it is easy to return the data to its state before the
function began and re-run the function with revised parameters or perform a
recovery action.
After a rollback to a savepoint, Oracle releases the data locks obtained by

rolled back statements. Other transactions that were waiting for the previously
locked resources can proceed. Other transactions that want to update previously
locked rows can do so.
When a transaction is rolled back to a savepoint, the following occurs:
Oracle rolls back only the statements run after the savepoint creation.
Oracle preserves the specified savepoint, but all savepoints that were
established after the specified one are lost.
Oracle releases all table and row locks acquired since that savepoint but
retains all data locks acquired previous to the savepoint.
• Even then, the transaction remains active and can be continued.
The SAVEPOINT statement to identify a point in a transaction to which you can

later roll back.
Example : Creating Savepoints
UPDATE employees SET salary = 7000 WHERE last_name = 'Adam';
SAVEPOINT Adam_sal;
UPDATE employees SET salary = 12000 WHERE last_name = 'Mike';
SAVEPOINT Mike_sal;
SELECT SUM(salary) FROM employees;
ROLLBACK TO SAVEPOINT Adam_sal;
COMMIT;
9.9 SQL Facilities for Concurrency and Recovery
SQL Facilities for Concurrency
Different Isolation levels can be set in SQL as follow:
READ UNCOMMITTED :
In SQL, it can be set as:
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED
READ COMMITTED (default):
SET TRANSACTION ISOLATION LEVEL READ COMMITTED
REPEATABLE READ :
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ
SERIALIZABLE :
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
Example: To demonstratge Repeatable Read
Consider a table emp (ID, name, salary)
Repeatable Read : For a transaction, the data of the table cannot be modified from any
other sessions till transaction is completed
Transaction 1:
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ
BEGIN TRANSACTION
SELECT * FROM emp where ID in(1,2);
Waitfor delay ‘00:00:15’
SELECT * FROM emp where ID in (1,2);
ROLLBACK;
Transaction2:
BEGIN TRANSACTION
UPDATE emp SET salary =999 where ID=1;
END TRANSACTION
If we run the above two transactions concurrently, then the update command in
Transaction2 will wait till Transaction1 is completed because T1 has been set with
REPEATABLE READ Isolation Level.
9.9 SQL Facilities for Concurrency and Recovery
SQL Facilities for Transaction Recovery
• Transaction commit is done when all the operations should be done and recorded.
• Transaction abort is done when some failure occurs and none of the values updated
by the transaction should be reflected in the database.
In SQL, Transaction Recovery is done by:
• COMMIT
• ROLLBACK
• SAVEPOINT
Example : Creating Savepoints
UPDATE employees SET salary = 7000 WHERE last_name = 'Adam';
SAVEPOINT Adam_sal;
SAVEPOINT Mike_sal;
SELECT SUM(salary) FROM employees;
ROLLBACK TO SAVEPOINT Adam_sal; // Roll back the previous two updates
COMMIT;
10. ASSIGNMENTS
1. Consider the following schedules. The actions are listed in the order they are
scheduled, and prefixed with the transaction name.
S1: T2:R(Z), T2:R(Y), T2:W(Y), T3:R(Y), T3:R(Z), T1:R(X), T1:W(X), T3:W(Y),
T3:W(Z), T2:R(X), T1:R(Y) , T1:W(Y), T2:W(X)
S2: T3:R(Y), T3:R(Z), T1:R(X), T1:W(X), T3:W(Y), T3:W(Z), T2:R(Z), T1:R(Y),
T1:W(Y), T2:R(Y), T2:W(Y), T2:R(X), T2:W(X)
For each of the schedules, answer the following questions:
i) What is the precedence graph for the schedule?
ii) Is the schedule conflict-serializable? If so, what are all the conflict equivalent serial
schedules?
iii) Is the schedule view-serializable? If so, what are all the view equivalent serial
schedules?
Solution:
The actions listed out for Schedule S1 and S2 are be written as
Schedule S1 Schedule S2
T1 T2 T3 T1 T2 T3
R(z) R(y)
R(y) R(z)
W(y) R(x)
R(y) W(x)
R(z) W(y)
R(x) W(z)
W(x) R(z)
W(y) R(y)
W(z) W(y)
R(x) R(y)
R(y) W(y)
W(y) R(x)
W(x) W(x)
10. ASSIGNMENTS
(i) PRECEDENCE GRAPH
Schedule S1
The Precedence graph for Schedule S1 consists of the following edges
T2 ->T3 because,
T2 executes R(z) before T3 executes W(z)
T2 executes R(y) before T3 executes W(y)
T2 executes W(y) before T3 executes W(y)
T2->T1 because,
T3->T1 because,
T3 executes W(y) before T1 executes R(y)
T1->T2 because,
T1 executes R(x) before T2 executes W(x)
T1 executes W(x) before T2 executes W(x)
Schedule S2
T3 ->T1 because,
T3->T2 because,
T3 executes W(z) before T2 executes R(z)
T1->T2 because,
T1 executes W(x) before T2 executes R(x)
T1 executes R(y) before T2 executes R(y)
10. ASSIGNMENTS
ii) TEST FOR CONFLICT SERIALIZABILITY
 If the precedence graph for a schedule contains a cycle, the schedule is not
Conflict Serializable.
 If the precedence graph for a schedule does not contain cycle, the schedule is
Schedule S1
Schedule S1
The precedence graph for Schedule S1 contains cycles.

So, the Schedule S1 is not Conflict Serializable.
Schedule S2
The precedence graph for Schedule S2 does not contain cycles.

So, the Schedule S2 is Conflict Serializable.
The Conflict Equivalent Serial Schedule is T3 -> T1 -> T2 (i.e. T3 followed by T1
followed by T2)
This is determined using topological sorting (start with vertex with indegree=0)
iii) TEST FOR VIEW SERIALIZABILITY
 If a schedule is conflict serializable, then it will be view serializable

 If a schedule is not conflict serializable and contains blind writes, then it will be
view serializable
Schedule S1
The Schedule S1 is not conflict serializable and and does not contain Blind Writes,
so it is not View Serializable
Schedule S2
The Schedule S1 is Conflict Serializable. So, Schedule S2 is View Serializable.
The View Equivalent Serial Schedule is T3->T1->T2

10. ASSIGNMENTS
2. Consider the following schedules. The actions are listed in the order they are
Scheduled
S1: R1(X), R3(X), W1(X), R2(X), W3(X)
S2: R3(X), R2(X), W3(X), R1(X), W1(X)
ii) Which of the following are conflict serializable schedule , Find
the equivalent serial schedule
Solution:
The actions listed out for Schedule S1 and S2 are be written as
Schedule S1 Schedule S2
T1 T2 T3 T1 T2 T3
R(x) R(x)
R(x) R(x)
W(x)
W(x)
R(x)
R(x)
W(x) W(x)
10. ASSIGNMENTS
(i) PRECEDENCE GRAPH
Schedule S1
T1 ->T3 because,

T3->T1 because,
T1->T2 because,
T1 executes W(x) before T2 executes R(x)
T2->T3 because,
Schedule S2
T3 ->T1 because,
T2->T1 because,
T2->T3 because,
10. ASSIGNMENTS
(ii) TEST FOR CONFLICT SERIALIZABILITY
 If the precedence graph for a schedule contains a cycle, the schedule is not
 If the precedence graph for a schedule does not contain cycle, the schedule is
Schedule S1
The precedence graph for Schedule S1 contains cycles.
So, the Schedule S1 is not Conflict Serializable.
Schedule S2
The precedence graph for Schedule S2 does not contain cycles.
So, the Schedule S2 is Conflict Serializable.
The Conflict Equivalent Serial Schedule is T2 -> T3 -> T1 (i.e. T2 followed by T3

followed by T1)
This is determined using topological sorting (start with vertex with indegree=0)
10. ASSIGNMENTS
3. Which of the following schedules is conflict serializable? For each serializable

schedule, determine the equivalent serial schedules:
(a) r1(X), r3(X), w1(X), r2(X), w3(X).
(b) r1(X), r3(X), w3(X), w1(X), r2(X).
(c) r3(X), r2(X), w3(X), r1(X), w1(X).
(d) r3(X), r2(X), r1(X), w3(X), w1(X).
Solution:
(a)r1(X), r3(X), w1(X), r2(X), w3(X).
There are two cycles. It is not conflict serializable.
(b) r1(X), r3(X), w3(X), w1(X), r2(X).

There is one cycle. It is not conflict serializable.
10. ASSIGNMENTS
3. Which of the following schedules is conflict serializable? For each serializable

schedule, determine the equivalent serial schedules:
(a) r1(X), r3(X), w1(X), r2(X), w3(X).
(b) r1(X), r3(X), w3(X), w1(X), r2(X).
(c) r3(X), r2(X), w3(X), r1(X), w1(X).
(d) r3(X), r2(X), r1(X), w3(X), w1(X).
Solution:
(c ) r3(X), r2(X), w3(X), r1(X), w1(X).
There are NO cycles. This schedule is serializable
The schedule is equivalent to:

r2(X), r3(X), w3(X), r1(X), w1(X).
(T2 -> T3 -> T1)
(d) r3(X), r2(X), r1(X), w3(X), w1(X).

There is one cycle. It is not conflict serializable.
Unit – 3 TRANSACTIONS
S.No Question and Answers CO K
1 Define Transactions CO3 K1
Collections of operations that form a single logical unit of work are

called transactions. A database system must ensure proper
execution of transactions despite failures—either the entire
transaction executes, or none of it does.
2 What are various states of a transaction? CO3 K1
• Active, the initial state; the transaction stays in this state while it
is executing
• Partially committed, after the final statement has been
executed
• Failed, after the discovery that normal execution can no longer
proceed
• Aborted, after the transaction has been rolled back and the
database has been restored to its state prior to the start of the
transaction
• Committed, after successful completion
3 List the Desirable Properties of Transactions CO3 K1
• Atomicity: Either all operations of the transaction are reflected

properly in the database or none are.
• Consistency: Execution of transaction in isolation (that is, with
no other transaction executing concurrently) preserves the
consistency of the database.
• Isolation: Even though multiple transactions may execute
concurrently, the system guarantees that, for every pair of
transactions Ti and Tj, it appears to Ti that either Tj finished
execution before Ti started, or Tj started execution after Ti
finished.
• Durability: After a transaction completes successfully, the
changes it has made to the database persist, even if there are
system failures.
These properties are often called the ACID properties; the acronym
is derived from the first letter of each of the four properties.
4 What is commit point? CO3 K1
A transaction T reaches its commit point when all its operations that
access the database have been executed successfully and the effect
of all the transaction operations on the database have been
recorded in the log.
5 What are the two types of transaction? CO3 K1
The two types of transactions are

(i) global transaction
(ii) local transaction
The global transactions are those that access and update data in
several local databases. The local transactions are those that access
and update date in only one local database.
6 Define Log? CO3 K1
The log is a sequential, append-only file that is kept on disk, so it is

not affected by any type of failure except for disk or catastrophic
failure. The system maintains a log to keep track of all transaction
operations that affect the values of database items.
1. [start_transaction, T]. Indicates that transaction T has started
execution.
2. [write_item, T, X, old_value, new_value]. Indicates that
transaction T has changed the value of database item X from
old_value to new_value.
3. [read_item, T, X]. Indicates that transaction T has read the value
of database item X.
4. [commit, T]. Indicates that transaction T has completed
successfully, and affirms that its effect can be committed
(recorded permanently) to the database.
5. [abort, T]. Indicates that transaction T has been aborted.
7 What is meant by schedule in transactions ? CO3 K1
A schedule (or history) S of n transactions T1, T2, ..., Tn is an

ordering of the operations of the transactions. Operations from
different transactions can be interleaved in the schedule S. However,
for each transaction Ti that participates in the schedule S, the
operations of Ti in S must appear in the same order in which they
occur in Ti.
8 Define serializable schedule and view serializable? CO3 K1
The definition of serializable schedule is as follows: A schedule S of

n transactions is serializable if it is equivalent to some serial
schedule of the same n transactions. A schedule S is said to be view
serializable if it is view equivalent to a serial schedule.
9 When do you say that two schedules are equivalent? CO3 K1
Two schedules are said to be equivalent if their results are

equivalent and if they produce the same final state of the database.
10 Define Cascadeless schedule and strict schedule: CO3 K1
A schedule is said to be cascadeless, or to avoid cascading

rollback, if every transaction in the schedule reads only items that
were written by committed transactions.
A schedule is said to be Strict schedule in which transactions can
neither read nor write an item X until the last transaction that wrote
X has committed (or aborted).
11 Classify the types of equivalence and serializability CO3 K1
Two definitions of equivalence of schedules are generally used:

• Conflict equivalence and conflict serailizability
• View equivalence and view serailizability
12 What is meant by concurrency control? CO3 K1
Concurrent control is a mechanism to ensure that several users

trying to update database in a controlled manner so that the result
of the updates is correct.
13 List the types of concurrency control mechanism used to CO3 K1
maintain concurrency.
1. Lock based protocols

2. Two phase locking protocols
3. Timestamp protocols
4. Multi-version concurrency control protocols
5. Multiple granularity concurrency control protocol
14 Define two-phase locking protocol. CO3 K1
A transaction is said to follow the two-phase locking protocol if all

locking operations precede the first unlock operation in the
transaction. Such a transaction can be divided into two phases.
i) an expanding or growing phase during which new locks on
items can be acquired but non can be released.
ii) A shrinking phase during which existing locks can be released
but no new locks can be acquired.
15 Define – Lock. CO3 K1
A lock is a variable associated with a data item that describes the

status of the item with respect to possible operations that can be
applied to it.
16 Define Binary Locks CO3 K1
A binary lock can have two states or values: locked and unlocked (or
1 and 0, for simplicity). A distinct lock is associated with each
database item X. If the value of the lock on X is 1, item X cannot be
accessed by a database operation that requests the item. If the
value of the lock on X is 0, the item can be accessed when
requested, and the lock value is changed to 1.We refer to the
current value (or state) of the lock associated with item X as
lock(X).
17 Explain the modes in which data item may be locked. CO3 K1
There are two modes in which data item can be locked, they are:
(i) shared –if a transaction Ti obtains this lock on an item, then it
can read the item but not write
(ii) exclusive – if a transaction obtains this lock on an item, then it
can read as well as write item.
18 Define Deadlock CO3 K1
Deadlock occurs when each transaction T in a set of two or more

transactions is waiting for some item that is locked by some other
transaction T_ in the set. Hence, each transaction in the set is in a
waiting queue, waiting for one of the other transactions in the set to
release the lock on an item. But because the other transaction is
also waiting, it will never release the lock.
19 Name the schemes that prevent deadlock CO3 K1
The two schemes that use timestamps to prevent deadlock are:

(i) Wait-die
(ii) Wound –wait.
Another group of protocols that prevent deadlock but do not
require time stamps are:
(i) No waiting algorithms
(ii) Cautious waiting algorithms.
20 When does the problem of starvation occur in lock? CO3 K1
The problem of starvation occurs when a transaction cannot

proceed for an indefinite period of time while other transactions in
the system continue normally.
12. PART - B
1 Explain the ACID properties of a transaction with examples CO3 K1
2 Explain the different states of a transaction. CO3 K1
3 State and explain the three concurrency problems. CO3 K1

4 What are schedules in transaction. What are the different schedule CO3 K1
available, illustrate with neat example.
5 Explain conflict and view serializability. CO3 K1
6 Explain two-phase Locking protocol. CO3 K1
7 What is deadlock? How does it occur? How transactions be written CO3 K1
to (i) Deadlock Prevention (ii) Deadlock Detection. Illustrate with
suitable examples.
8 Explain Transaction Recovery CO3 K1
9 Explain Save Points – Isolation Levels – SQL Facilities for CO3 K1

Concurrency and Recovery.
10 Consider the following schedules. The actions are listed in the order CO3 K1
they are scheduled, and prefixed with the transaction name.
S1: T2:R(Z), T2:R(Y), T2:W(Y), T3:R(Y), T3:R(Z), T1:R(X),
T1:W(X), T3:W(Y), T3:W(Z), T2:R(X), T1:R(Y) , T1:W(Y), T2:W(X)
S2: T3:R(Y), T3:R(Z), T1:R(X), T1:W(X), T3:W(Y), T3:W(Z),
T2:R(Z), T1:R(Y), T1:W(Y), T2:R(Y), T2:W(Y), T2:R(X), T2:W(X)
ii) Is the schedule conflict-serializable? If so, what are all the
conflict equivalent serial schedules?
iii) Is the schedule view-serializable? If so, what are all the view
equivalent serial schedules?
11 Consider the following schedules. The actions are listed in the order CO3 K1
they are scheduled
S1: R1(X), R3(X), W1(X), R2(X), W3(X)
S2: R3(X), R2(X), W3(X), R1(X), W1(X)
What is the precedence graph for the schedule?
i)Which of the following are conflict serializable schedule , Find the
equivalent serial schedule
13. SUPPORTIVE ONLINE CERTIFICATION COURSES
Sl. Name of the Name of the

Website Link
No. Institute Course
Data Base
Management https://nptel.ac.in/noc/courses/noc18/S
1. NPTEL
System EM1/noc18-cs15/
Database
https://www.coursera.org/learn/databas
2. Coursera Management
e-management
Essentials
Relational
https://www.coursera.org/lear
3. Coursera database
n/relational-database
systems
Database
Management https://www.udemy.com/course/databas
4. Udemy
System e-management-system/
Introduction to
Udemy Database https://www.udemy.com/course/databas
5.
Engineering e-engines-crash-course/
Databases
6. edX Courses https://www.edx.org/learn/databases
14.REAL TIME APPLICATIONS IN DAY TO DAY LIFE AND
TO INDUSTRY
1. Finances
From the stock market to your local bank, databases are abundant across the financial
world. Tracking the vast amount of information behind the world’s daily transactions
requires extremely powerful databases. This includes financial models that analyze
that data to predict future activity.
Everyday Transactions
Most of us use databases daily and may not realize it. By understanding real-world,
daily activities, you will gain a better understanding of database usage and will be
able to better apply these concepts to understand the corporate world.
A couple of everyday transactions with which everyone is familiar are
Getting a prescription filled
Using a bank machine
Getting a Prescription Filled
The example walks you through a process everyone does at some point—having a
prescription filled.
As you are standing in your local pharmacy waiting for your prescription, you may not
think that this transaction is database intensive. But, if you were to take a closer look,
hundreds of gigabytes of data, maybe terabytes, are involved in this routine
transaction.
When you evaluate a transaction like this one, it is helpful to look at one layer of the
transaction at a time, peeling away successive layers, just like peeling an onion. Figure
shows the "layers" of this transaction that you will review.
Fig: Transaction
layers for a
prescription
purchase.
TO INDUSTRY
The Doctor's Office Databases

You can start by looking back to the beginning of this transaction—at the doctor's
office. A database must be kept of each patient, including data elements such as
name, address, phone number, insurance carrier, closest relative, medical history, and
family history. Billing records, payment receipts, appointment schedules, and
insurance filing information make up other databases that are used often.
The Pharmacy Databases
The actual pharmacy has database information that it maintains on a broad range of
subjects. The most obvious one is you—the customer. Every pharmacy will have,
minimally, a database of customer name and address information, customer date of
birth, prescribing physician and phone number, insurance carrier, and past prescription
history of each customer.
The insurance company, HMO, or PPO provides each pharmacy with another database
that must be used extensively. This database is called the formulary database. It
contains an approved list of brand drugs, approved generic substitutions, dosages,
and National Drug Code (NDC) information. Your insurance prescription card more
than likely has a specific formulary that the pharmacy must reference to ensure that
the drug used to fill your prescription, or an allowable substitution, will be covered by
your insurance. This type of database may also be used by the physician's office to
ensure that the drug they want to prescribe can be filled, without any substitution or
dosage change, when you get to the pharmacy.
Another database that is used prior to filling the prescription is the drug interaction
database. The prescribed drug may have serious interaction issues if used in
conjunction with medications currently in use. The database identifies potential
interaction problems, provides a detailed explanation of the interaction consequence,
and possibly suggests alternatives.
After the formulary and interaction databases have been utilized, the prescription is
ready to fill. The pharmacy inventory database is checked to determine whether the
NDC being requested is in stock and at what shelf location it can be found. The
inventory database must track expiration dates of each drug to prevent outdated
medication from being dispensed. After the prescription is filled, the available on-hand
inventory for your medication must be reduced by the quantity or volume of your
prescription.
If the medication is not available in stock, the pharmacy must search through its
wholesaler database to determine the best source for the drug. The wholesaler
database identifies each of the wholesalers from whom the needed drug can be
acquired, the cost from the wholesaler, and possibly the inventory availability at the
wholesaler.
TO INDUSTRY
The final database to be reviewed at the pharmacy is the order database. This
database contains all the outstanding orders that have been placed with all the
wholesalers. They may represent simple inventory replenishment orders or special
orders for drugs not normally stocked. If the orders are for narcotic items, or
Schedule 2 drugs, special order and tracking requirements must be met to satisfy the
requirements of the Drug Enforcement Administration (DEA). Figure shows the
database entities involved at the pharmacy layer.
Fig: Pharmacy layer databases.

TO INDUSTRY
The Wholesaler's Database
As you continue to peel away layers in the transaction, you see that the next layer
represents the drug wholesaler. The pharmaceutical supply chain in the United States
is typically serviced by a wholesaler that operates between the manufacturer and the
retail or hospital pharmacy.
The wholesaler layer begins with an extensive customer database. Name, address,
billing address, and accounts receivable information are maintained. A customer who
represents a large chain, such as K-Mart, may have Ship To destinations all over the
country. Each of the Ship To locations must be maintained separately for order
tracking and for sales analysis purposes.
A separate database that identifies every drug and strength is used by the wholesaler
to ensure that the customer's intent on which drug they want to purchase from the
wholesaler is clear and, in turn, to make sure the drug the wholesaler purchases from
the manufacturer is explicitly identified. This database, by NDC number, changes
frequently with new manufacturers, generic suppliers, dosage changes, and the
constant introduction of new drugs. The management of this type of database has
spawned new businesses in the pharmaceutical industry because of its complexity and
volatility. Many wholesalers purchase this database with quarterly updates to ensure
that they have an up-to-date NDC database.
Most national and regional wholesalers have multiple distribution centers, or DCs,
located throughout the country or throughout the geographical area they serve. Each
of these DCs has an inventory database that is a focal point of their operations. The
inventory database must identify each item that the DC stocks, and for each item,
many inventory management attributes are tracked. Something as simple as the
picking location can include a forward picking location, a backup picking location, a
bulk location, a backup bulk location, packaging quantities, packaging dimensions,
packaging weights, expiration dates, and lot-tracking information along with inventory
quantities at each location. With thousands of items at a DC, you can begin to see the
complexity and size of the inventory database required for each DC within a
wholesaler's operation.
The wholesaler's database will always include, among other items, a shipping and
invoicing database and an accounts receivable database. Figure shows the database
entities involved at the wholesaler layer.
TO INDUSTRY
The Manufacturer's Database
A manufacturer has many databases that are very similar to those of the wholesalers.
The supply-chain relationship between pharmacy and wholesaler is very similar to the
relationship between wholesaler and manufacturer. There are a few additional
databases, though, that are unique to the manufacturing process.
The first unique database you will look at in this layer of the transaction is the product
database. The product must contain a list of raw materials, or recipe ingredients, that
make up the product. Careful attention must also be given to the manufacturing
process. The FDA (Food and Drug Administration) expects every manufacturer to
stringently adhere to the recommended process to produce the drug. The database
has extensive instructions and quality control data for each step within the routing or
operational steps in the manufacturing process.
The other database that is unique to the manufacturer in this transaction is one that
tracks the capacity of each manufacturing process. Whether it is a material movement
operation, a mixing operation, an application of heat, or a packaging operation, each
operation has a finite limitation in terms of hours available and capacity. A complex
database is required to look at all the scheduled shop orders, retrieving the lot size of
each order, multiplying the shop order quantity by the routing quantity, and then
determining the work center or material-handling equipment necessary to complete
the operation. Each of these extended routing operations are aggregated by work
center and compared to the finite limitations noted earlier. The required due dates of
the shop orders are used as a starting point, and the entire process is backward
scheduled to determine when the shop order would need to begin to meet the
required completion date. When you factor in scheduled and unscheduled
maintenance, breakdowns, and required setups and quality inspections, the database
necessary to adequately evaluate capacity requirements and material requirements
planning is significant. Figure shows the database entities involved at the
manufacturer layer.
TO INDUSTRY
Using Your Bank Machine (ATM)
The next example involves a transaction that takes only a few minutes to complete—
you are going to look at the databases that are used when you visit a bank and use
the ATM.
When you insert your ATM card into the bank machine, the first thing that must be
completed is to identify the account number of the user. The user may be using a
local bank or may be using another bank that is part of a participating network. The
bank must search its account databases and try to find a match within their system. If
this fails, the account number can be searched against a database that represents
participating banks.
After an account record is identified, the user is prompted for a PIN, or personal
identification number. The PIN is verified against a database entry. The transaction,
for obvious reasons, is canceled if the user does not supply a matching PIN.
After the PIN verification is completed, the account details are retrieved from the
database regarding the types of accounts that you have—checking, savings, or both.
The ATM prompts you for the type of transaction you are interested in completing.
Typical transactions are deposits, withdrawals, transfer savings to checking, and check
account balances. For this transaction, you are going to withdraw cash from your
checking account.
Now it's time for you to indicate how much cash you need. A couple of databases
must be accessed at this point. The first is easy—determine how much money you
currently have in your account. The second is more involved because most ATM
systems limit your withdrawal amounts in a 24-hour period. The system issues a SQL
select statement against the database to add the transaction amounts of all
withdrawal transactions for your account within the most recent 24 hours. If the daily
limit minus the returned summed amount is greater than your transaction amount,
you get the cash. If not, you will be limited as to how much can be withdrawn, or you
may not qualify to receive any cash.
Beyond the portion of the transaction that you see, a couple more databases are
being used. The transaction must be recorded, with account number, account type
(savings or checking), date, time of day, type of transaction, and amount. This is used
to post the transaction to your account and compute your current balance. This is the
database of transactions that you see on your statement at the end of your banking
period. The transaction is also used to post to the general ledger database for the
bank. If any ATM charges apply, these annoying charges are recorded in the
transaction database described previously.
The final database is composed of ACH (Automated Clearinghouse) transactions that
are forwarded to the Federal Reserve System so that banks can clear transactions
across the country. Each of these transactions are logged to a transaction database for
reconciliation purposes in the event of a failure within banking computer systems.
15. CONTENT BEYOND THE SYLLABUS
Timestamp based Protocol for Concurrency Control
Timestamp based protocol determines the serializability order to select an ordering
among transactions in advance.
The most common method for doing so is to use a timestamp-ordering scheme.
Timestamps
With each transaction Ti in the system, we associate a unique fixed timestamp, denoted
by TS(Ti ).
This timestamp is assigned by the database system before the transaction Ti starts
execution. If a transaction Ti has been assigned timestamp TS(Ti ), and a new
transaction Tj enters the system, then TS(Ti ) < TS(Tj ).
There are two simple methods for implementing this scheme:

1. Use the value of the system clock as the timestamp
2. Use a logical counter that is incremented after a new timestamp has
been assigned;
To implement this scheme,we associate with each data item Q two timestamp
values:
• W-timestamp(Q) denotes the largest timestamp of any transaction that executed

write(Q) successfully.
• R-timestamp(Q) denotes the largest timestamp of any transaction that executed
read(Q) successfully.
These timestamps are updated whenever a new read(Q) or write(Q) instruction
is executed.
The Timestamp-Ordering Protocol
The timestamp-ordering protocol ensures that any conflicting read and write operations
are executed in timestamp order. This protocol operates as follows:
1. Suppose that transaction Ti issues read(Q).
a. If TS(Ti ) < W-timestamp(Q), then Ti needs to read a value of Q that was already
overwritten. Hence, the read operation is rejected, and Ti is rolled back.
b. If TS(Ti ) ≥ W-timestamp(Q), then the read operation is executed, and R-timestamp(Q) is

set to the maximum of R-timestamp(Q) and TS(Ti ).
2. Suppose that transaction Ti issues write(Q).
a. If TS(Ti ) < R-timestamp(Q), then the value of Q that Ti is producing was needed
previously, and the system assumed that that value would never be produced.
Hence, the system rejects the write operation and rolls Ti back.
b. If TS(Ti ) < W-timestamp(Q), then Ti is attempting to write an obsolete value of

Q. Hence, the system rejects this write operation and rolls Ti back.
c. Otherwise, the system executes the write operation and sets W-timestamp(Q) to
TS(Ti ).
If a transaction Ti is rolled back by the concurrency-control scheme as result of
issuance of either a read or write operation, the system assigns it a new timestamp
and restarts it.
The protocol can generate schedules that are not recoverable. However,
it can be extended to make the schedules recoverable, in one of several
ways:
Recoverability and cascadelessness can be ensured by performing all writes

together at the end of the transaction. The writes must be atomic in the
following sense: While the writes are in progress, no transaction is permitted
to access any of the data items that have been written.
Recoverability and cascadelessness can also be guaranteed by using a

limited form of locking, whereby reads of uncommitted items are postponed
until the transaction that updated the item commits
Recoverability alone can be ensured by tracking uncommitted writes, and

allowing a transaction Ti to commit only after the commit of any transaction
that wrote a value that Ti read.
Thomas Write Rule
The modification to the timestamp-ordering protocol, called Thomas’ write rule, is
this:
Suppose that transaction Ti issues write(Q).
1. If TS(Ti ) < R-timestamp(Q), then the value of Q that Ti is producing

was previously needed, and it had been assumed that the value would never be
produced. Hence, the system rejects the write operation and rolls Ti back.
2. If TS(Ti ) < W-timestamp(Q), then Ti is attempting to write an obsolete

value of Q. Hence, this write operation can be ignored.
3. Otherwise, the system executes the write operation and setsW-

timestamp(Q) to TS(Ti ).
Thomas Write Rule provides the guarantee of serializability order for the protocol.
It improves the Basic Timestamp Ordering Algorithm.
16. ASSESSMENT SCHEDULE
Assessment Proposed Actual Course Program Outcome

Tools Date Date Outcome (Filled Gap)
Class Test 1
Quiz 1
Assignment 1
Assessment 1
Seminar 1
Class Test 2
Quiz 2
Assignment 2
Assessment 2
Seminar 2
Mini Project
Model Exam
Online Course
Certification
17.PRESCRIBED TEXT BOOKS &REFERENCE BOOKS
TEXT BOOKS:
1. Abraham Silberschatz, Henry F. Korth, S. Sudharshan, ―Database System

Concepts, Sixth Edition, Tata McGraw Hill, 2011.
2. Ramez Elmasri, Shamkant B. Navathe, ―Fundamentals of Database Systems‖,

Sixth Edition, Pearson Education, 2011.
REFERENCES:
1. C.J.Date, A.Kannan, S.Swamynathan, ―An Introduction to Database Systems,

Eighth Edition, Pearson Education, 2006.
2. Raghu Ramakrishnan, ―Database Management Systems, Fourth Edition,

McGraw-Hill College Publications, 2015.
3. G.K.Gupta,"Database Management Systems”, Tata McGraw Hill, 2011.

18. MINI PROJECT SUGGESTIONS
Design a Relational database for the following

1) Insurance Management System
The insurance management project deals the adding new insurance schemes and managing the
clients for the insurance. The project has complete access for the crud operations that are to
create, read, update and delete the database entries. At first you need to add a branch and the
staff members for the branch then secondly add a user to the database now you can add an
insurance scheme and finally make the payments for the client to the added insurance.
2) Inventory Management
The project starts by adding a seller and by adding details of customer. the user can now
purchase new products by the desired seller and then can sell them to the customer, the
purchasing and selling of products is reflected in the inventory section. The main aim of
Inventory Management Mini DBMS project is to add new products and sell them and keep an
inventory to manage them.
3) Pharmacy management System

The project starts by adding a dealer and by adding details of customer. the user can now
purchase new medicines by the desired dealer and then can sell them to the customer added
the purchasing and selling of medicines is reflected in the inventory section.
4) Library management system

there will be an admin who will be responsible for manages the system. The admin will look
after how many books are available in the library and he can update them if any new books
brought to the library. Perform operations like adding a book to the database, view all books
which are added, search for a specific book, issue books, and retrieve the book from users.
5) Hotel management system
Add features like providing the menu of the food items that are prepared in the hotel. Provide
the menu and prices of the food in the hotel. you can add the online food ordering facility to
this which will give a good impression on the project. we can also book the tables in the
project. Add a feature that will show the collection of the day this will be only viewed by the
admin. we can also provide online booking of rooms also. Improve this with some other
features.
Thank you
Disclaimer:
This document is confidential and intended solely for the educational purpose of RMK Group of
Educational Institutions. If you have received this document through email in error, please notify the
system manager. This document contains proprietary information and is intended only to the
respective group / learning community as intended. If you are not the addressee you should not
disseminate, distribute or copy through e-mail. Please notify the sender immediately by e-mail if you
have received this document by mistake and delete this document from your system. If you are not
the intended recipient you are notified that disclosing, copying, distributing or taking any action in
reliance on the contents of this information is strictly prohibited.

20it403 DBMS Digital Material Unit Iii

Uploaded by

Copyright:

Available Formats

20it403 DBMS Digital Material Unit Iii

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

20it403 DBMS Digital Material Unit Iii

Uploaded by

Copyright:

Available Formats

Please read this disclaimer before proceeding:

6. CO- PO/PSO Mapping

8. Activity based learning

11. Part A Question & Answer

12. Part B Question & Answer

13. Supportive online Certification courses

14. Real time Applications in day to day life and to Industry

15. Contents beyond the Syllabus

16. Assessment Schedule

17. Prescribed Text Books & Reference Books

18. Mini Project suggestions

To understand the basic concepts of Data modeling and Database Systems.

To understand SQL and effective relational database design concepts.

To know the fundamental concepts of transaction processing, concurrency control

techniques and recovery procedure.

To understand efficient data querying and updates, with needed configuration

• 20GE101 Problem Solving and C Programming

• 20CS201 Data Structures

UNIT I DATABASE CONCEPTS 9

Concept of Database and Overview of DBMS - Characteristics of databases, Database

UNIT II DATABASE DESIGN 9

UNIT III TRANSACTIONS 9

Transaction Concepts – ACID Properties – Schedules – Serializability – Concurrency

UNIT IV DATA STORAGE AND QUERYING 9

UNIT V ADAVNCED TOPICS 9

Distributed database Implementation Concurrent transactions - Concurrency control

CO1: Implement SQL and effective relational database design concepts.

CO2: Map ER model to Relational model to perform database design effectively.

CO3:Compare and contrast various indexing strategies in different database systems.

CO4: Implement queries using normalization criteria and optimization techniques.

CO5: Analyse how advanced databases differ from traditional databases.

PSO1 PSO2 PSO3

S.No Topic No of Proposed Actual CO Taxono Mode of

1 Transaction 1 CO4 K2 PPT/ONLI

Compare the following pairs of concepts/techniques:

9.1.1 Transaction Concept:

A transaction is a unit of program execution that accesses and possibly updates

Since a transaction is indivisible, it either executes in its entirety or not at all.

(A-Atomicity, C-Consistency, I-Isolation, D-Durability)

The basic idea behind ensuring atomicity is this:

This information is written to a file called the log.

Ensuring Atomicity is the responsibility of the recovery system of the database.

Without the consistency requirement, money could be created or destroyed by

The consistency requirement verifies that, if the database is consistent before an

Ensuring consistency for an individual transaction is the responsibility of the

interleave in some undesirable way, resulting in an inconsistent state.”

If the database is temporarily inconsistent with the deducted total written to A

and the increased total yet to be written to B. (A - $950, B - $2000)

If a second concurrently running transaction reads A and B at this intermediate

point and computes A+B, it will observe an inconsistent value.

A way to avoid the problem of concurrently executing transactions is to

execute transactions serially—that is, one after the other.

Concurrent execution of transactions provides significance performance

benefits such as:

 Improved throughput and Resource utilization

 Reduced waiting time

The isolation property of a transaction ensures that the concurrent execution of

Ensuring Isolation property is the responsibility of Concurrency-control component

“The durability property guarantees that, once a transaction completes