Two-Phase Locking (2PL) Technique
Two-Phase Locking (2PL) is a concurrency control protocol used in DBMS to ensure that
multiple transactions execute concurrently without violating database consistency. It
guarantees conflict serializability, meaning the concurrent execution of transactions produces
the same result as some serial execution.
Types of Locks
Before accessing data, a transaction must acquire a lock:
1. Shared Lock (S-Lock) – Used for reading data.
○ Multiple transactions can hold shared locks on the same item simultaneously.
○ Example: SELECT operation.
2. Exclusive Lock (X-Lock) – Used for writing data.
○ No other transaction can read or write the data item.
○ Example: UPDATE, DELETE, INSERT.
Two Phases of 2PL
A transaction follows two distinct phases:
1. Growing Phase
● The transaction can acquire locks.
● It cannot release any lock.
2. Shrinking Phase
● The transaction can release locks.
● It cannot acquire any new lock.
Diagram
Growing Phase Shrinking Phase
------------- ----------------
Acquire Lock A
Acquire Lock B
Acquire Lock C
---------------------> Lock Point
Release Lock A
Release Lock B
Release Lock C
The point at which the transaction acquires its final lock is called the Lock Point.
Example
Consider two transactions:
Transaction T1
BEGIN;
LOCK-X(A);
A = A - 500;
UNLOCK(A);
LOCK-X(B);
B = B + 500;
UNLOCK(B);
COMMIT;
Transaction T2
BEGIN;
LOCK-S(A);
READ(A);
UNLOCK(A);
COMMIT;
Under strict 2PL, T2 must wait until T1 releases the exclusive lock on A.
Role of 2PL in Concurrency Control
1. Ensures Serializability
2PL guarantees that concurrent schedules are conflict-serializable.
Example:
T1: Read(A) Write(A)
T2: Read(B) Write(B)
The execution behaves as if transactions ran one after another.
2. Prevents Lost Updates
Without locking:
T1 reads A = 100
T2 reads A = 100
T1 writes A = 150
T2 writes A = 120
T1's update is lost.
With 2PL:
● T1 acquires an exclusive lock.
● T2 waits.
● Lost updates are prevented.
3. Maintains Data Consistency
Multiple users can access the database safely without corrupting data.
Example:
● Banking systems
● Airline reservation systems
● E-commerce order processing
4. Controls Concurrent Access
Locks coordinate access to shared resources and avoid conflicting operations.
Problems with 2PL
1. Deadlock
Example:
T1 locks A and waits for B
T2 locks B and waits for A
Both transactions wait indefinitely.
T1 ---> A ----> waits for B
T2 ---> B ----> waits for A
Solution:
● Wait-Die
● Wound-Wait
● Deadlock detection and recovery
2. Starvation
A transaction may wait indefinitely if higher-priority transactions continuously acquire locks.
3. Reduced Concurrency
Transactions may spend time waiting for locks, decreasing system throughput.
Variants of 2PL
1. Basic 2PL
● Follows growing and shrinking phases.
● Ensures serializability.
● Deadlocks may occur.
2. Strict 2PL
● Holds all exclusive locks until commit or rollback.
● Prevents cascading rollbacks.
● Most commonly used in DBMSs.
3. Rigorous 2PL
● Holds both shared and exclusive locks until commit.
● Stronger than Strict 2PL.
4. Conservative (Static) 2PL
● Obtains all required locks before execution starts.
● Prevents deadlocks.
● Reduces concurrency.
Banking Example
Suppose ₹1000 is transferred from Account A to Account B.
START TRANSACTION;
-- Lock Account A
UPDATE Account
SET Balance = Balance - 1000
WHERE AccountID = 102;
-- Lock Account B
UPDATE Account
SET Balance = Balance + 1000
WHERE AccountID = 105;
COMMIT;
Using Strict 2PL:
● T1 locks both accounts.
● Other transactions must wait.
● If an error occurs, the transaction rolls back safely.
● Data remains consistent.
Timestamp Ordering (TO) Protocol
Definition:
Timestamp Ordering is a concurrency control technique in DBMS where transactions are
executed according to their timestamps. The system ensures that conflicting operations occur
in the same order as the transaction timestamps.
Each transaction is assigned a unique timestamp when it starts.
TS(T1) = 10
TS(T2) = 20
Since TS(T1) < TS(T2), transaction T1 is older and must appear to execute before T2.
Basic Idea
Instead of using locks, the DBMS uses timestamps to determine whether an operation should
be allowed.
Each data item X maintains:
Read Timestamp (RTS)
RTS(X)
The largest timestamp of any transaction that has successfully read X.
Write Timestamp (WTS)
WTS(X)
The largest timestamp of any transaction that has successfully written X.
Rules
1. Read Operation
Transaction T wants to read X.
Read(X)
If:
TS(T) < WTS(X)
➡ Reject and rollback T.
Otherwise:
Allow Read
RTS(X) = max(RTS(X), TS(T))
2. Write Operation
Transaction T wants to write X.
Write(X)
If:
TS(T) < RTS(X)
or
TS(T) < WTS(X)
➡ Reject and rollback T.
Otherwise:
Allow Write
WTS(X) = TS(T)
Example
Assume:
TS(T1) = 5
TS(T2) = 10
Step 1
T2 writes X
WTS(X) = 10
Step 2
T1 tries to read X
Check:
TS(T1) = 5 < WTS(X) = 10
Since T1 is older than the latest write:
T1 is rolled back
This preserves timestamp order.
Advantages
1. Deadlock-Free
No locks are used, so deadlocks cannot occur.
2. Ensures Serializability
Transactions execute in timestamp order.
3. High Concurrency
Multiple transactions can proceed without waiting for locks.
Disadvantages
1. Frequent Rollbacks
Older transactions may be aborted repeatedly.
2. Starvation Possible
A transaction may continuously restart if newer transactions keep conflicting with it.
3. Overhead
The DBMS must maintain timestamps for every transaction and data item.
Comparison with Other Techniques
Technique Main Idea
Lock-Based Protocol Uses locks (S, X)
Timestamp Ordering Based on timestamps
MVCC Maintains multiple versions of data
Validation Technique Checks conflicts before commit
Multiversion Concurrency Control (MVCC)
Definition:
MVCC is a concurrency control technique that maintains multiple versions of a data item.
Instead of locking data, transactions read a snapshot of the database, allowing readers and
writers to work concurrently.
How it Works
Suppose a record has balance = ₹5000.
Version 1: Balance = ₹5000
Transaction T1 updates the balance:
Version 2: Balance = ₹6000
● Existing transactions continue reading Version 1.
● New transactions read Version 2 after T1 commits.
● Readers do not block writers, and writers do not block readers.
Example
T1: Updates Account Balance from 5000 → 6000
T2: Reads Account Balance
With MVCC:
T2 reads old version (5000)
T1 creates new version (6000)
No waiting occurs.
Advantages
● High concurrency
● Readers are never blocked
● Reduced locking overhead
● Better performance for read-heavy applications
Disadvantages
● Extra storage needed for multiple versions
● Version management complexity
Databases Using MVCC
● PostgreSQL
● Oracle Database
● MySQL
Validation Techniques (Optimistic Concurrency Control)
Definition:
Validation-based concurrency control assumes conflicts are rare. Transactions execute without
locks and are validated before commit to ensure serializability.
Three Phases
1. Read Phase
Transaction reads data and performs computations.
T1 reads A and B
2. Validation Phase
Before committing, the DBMS checks whether another transaction has modified the same data.
Check for conflicts
3. Write Phase
If validation succeeds:
COMMIT
Otherwise:
ROLLBACK and restart
Example
Initial:
A = 100
Transactions:
T1 reads A = 100
T2 reads A = 100
T1 updates:
A = 150
COMMIT
When T2 tries to commit:
Validation detects conflict
T2 is rolled back
This prevents inconsistent updates.
Advantages
● No locking overhead
● High concurrency when conflicts are rare
● No deadlocks
Disadvantages
● Transactions may be restarted frequently if conflicts are common
● Less suitable for high-contention environments
Comparison: MVCC vs Validation Techniques
Feature MVCC Validation Technique
Basic Idea Multiple versions of data Check conflicts before
commit
Locks Required Minimal/None for reads No locks during execution
Reader Blocking No No
Writer Blocking Reduced Reduced
Deadlocks Rare None
Storage Requirement High (multiple versions) Low
Best For Read-heavy systems Low-conflict environments
Granularity
Granularity in DBMS refers to the level or size of the data item being locked during transaction
processing.
Types of Lock Granularity
Granularity Level of Locking Description
Database Level Entire Database Locks the whole database. Lowest
concurrency.
Table Level Entire Table Locks all rows in a table.
Page/Block Level Disk Page Locks a group of rows stored in a page.
Row/Record Level Individual Row Locks only one record. Highest concurrency.
Example
Consider a Student table:
SID Name
1 Alice
2 Bob
3 Charlie
Table-Level Lock
LOCK TABLE Student;
● Entire Student table is locked.
● No other transaction can modify any row.
Row-Level Lock
SELECT * FROM Student
WHERE SID = 1
FOR UPDATE;
● Only the row with SID = 1 is locked.
● Other rows can still be accessed by other transactions.
Trade-off
Coarse Granularity Fine Granularity
Table/Database Row/Record Lock
Lock
Less lock overhead More lock overhead
Lower concurrency Higher concurrency
Easier to manage More complex
Key Point
● Coarse-grained locking → Database/Table level.
● Fine-grained locking → Page/Row level.
The choice of granularity affects performance, concurrency, and lock management overhead in
a DBMS.
Multiple Granularity Locking (MGL)
Multiple Granularity Locking (MGL) is a locking technique in DBMS that allows transactions to
lock data at different levels of a hierarchy, such as:
Database
↓
Table
↓
Page (Block)
↓
Record (Row)
Instead of locking only individual records or entire tables, MGL provides flexibility by allowing
locks at various granularities, improving both concurrency and performance.
Why Multiple Granularity Locking?
Consider a table named Student containing 10,000 records.
Case 1: Lock Entire Table
Lock(Student Table)
● Simple to manage.
● Low concurrency.
● Other transactions cannot access any row.
Case 2: Lock Individual Rows
Lock(Row 1)
Lock(Row 2)
...
Lock(Row 10000)
● High concurrency.
● Large lock management overhead.
Solution
Use Multiple Granularity Locking, where locks can be applied at:
● Database level
● Table level
● Page level
● Row level
This balances concurrency and overhead.
Lock Hierarchy
Database
|
+-- Student Table
| |
| +-- Page 1
| | |
| | +-- Row 1
| | +-- Row 2
| |
| +-- Page 2
|
+-- Course Table
A transaction can lock at any level depending on its requirements.
Intention Locks
To make MGL work correctly, Intention Locks are used.
An intention lock indicates that a transaction intends to acquire a lock at a lower level in the
hierarchy.
Types of Intention Locks
1. Intention Shared (IS)
Indicates intention to place Shared (S) locks on lower-level objects.
Example:
IS(Database)
IS(Student Table)
S(Row 10)
Transaction wants to read Row 10.
2. Intention Exclusive (IX)
Indicates intention to place Exclusive (X) locks on lower-level objects.
Example:
IX(Database)
IX(Student Table)
X(Row 20)
Transaction wants to update Row 20.
3. Shared Intention Exclusive (SIX)
Combination of:
Shared + Intention Exclusive
Meaning:
● Shared lock on current node.
● Exclusive locks may be acquired on some lower-level nodes.
Example:
SIX(Student Table)
X(Row 5)
X(Row 10)
Transaction reads the whole table but updates selected rows.
Compatibility Matrix
Lock Type IS IX S SIX X
IS ✔ ✔ ✔ ✔ ✖
IX ✔ ✔ ✖ ✖ ✖
S ✔ ✖ ✔ ✖ ✖
SIX ✔ ✖ ✖ ✖ ✖
X ✖ ✖ ✖ ✖ ✖
✔ = Compatible
✖ = Not Compatible
Implementation of Multiple Granularity Locking
Rules
Rule 1
Lock the root first.
Database
must be locked before locking lower levels.
Rule 2
To acquire:
Shared Lock (S)
Parent must have:
IS or IX
Rule 3
To acquire:
Exclusive Lock (X)
Parent must have:
IX or SIX
Rule 4
Unlocking occurs from bottom to top.
Row → Page → Table → Database
Example 1: Reading a Row
Transaction T1 wants to read Student Row 100.
Step 1
IS(Database)
Step 2
IS(Student Table)
Step 3
S(Row 100)
Hierarchy:
Database (IS)
|
Student Table (IS)
|
Row 100 (S)
Other transactions may still access different rows.
Example 2: Updating a Row
Transaction T2 wants to update Student Row 200.
Step 1
IX(Database)
Step 2
IX(Student Table)
Step 3
X(Row 200)
Hierarchy:
Database (IX)
|
Student Table (IX)
|
Row 200 (X)
Only Row 200 is blocked.
Example 3: Read Entire Table and Update Few Rows
Transaction T3:
Read all students
Update Row 5
Update Row 10
Locks:
SIX(Student Table)
X(Row 5)
X(Row 10)
This is more efficient than:
S(Table)
X(Row 5)
X(Row 10)
because conflicts are detected correctly.
Advantages of Multiple Granularity Locking
1. Improved Concurrency
Different transactions can access different rows simultaneously.
2. Reduced Locking Overhead
Avoids locking every individual record when not necessary.
3. Flexibility
Supports locking at:
● Database level
● Table level
● Page level
● Record level
4. Better Performance
Balances concurrency and lock management costs.
Disadvantages
1. Complex Implementation
Maintaining lock hierarchy and intention locks increases complexity.
2. Additional Lock Overhead
Extra intention locks must be maintained.
3. Deadlocks Can Still Occur
Improper lock acquisition may create deadlocks.
NoSQL Databases
1. Introduction to NoSQL
NoSQL (Not Only SQL) databases are non-relational databases designed to handle large
volumes of structured, semi-structured, and unstructured data. Unlike traditional relational
databases, NoSQL databases do not require a fixed schema and can scale horizontally across
multiple servers.
Features of NoSQL
● Flexible schema
● Horizontal scalability
● High availability
● Distributed architecture
● Fast read/write operations
● Suitable for Big Data and cloud applications
Examples
● MongoDB
● Apache Cassandra
● Redis
● Neo4j
Key Features of NoSQL Databases (One Line Each)
1. Flexible Schema – Data can be stored without a fixed table structure, allowing different
records to have different fields.
2. Horizontal Scalability – Capacity is increased by adding more servers instead of
upgrading a single server.
3. High Availability – Data replication ensures the system remains accessible even if some
servers fail.
4. Distributed Architecture – Data is spread across multiple machines or locations for
better performance and reliability.
5. Fast Read/Write Operations – Optimized for quick data access and updates, making
them suitable for high-traffic applications.
6. Suitable for Big Data and Cloud Applications – Efficiently handles massive volumes of
data in cloud and distributed environments.
2. CAP Theorem
The CAP Theorem, proposed by Eric Brewer, states that a distributed database system can
guarantee only two out of the following three properties at the same time:
C – Consistency
Every user sees the same data at the same time.
Example:
Node A = 100
Node B = 100
After an update, all nodes immediately show the same value.
A – Availability
Every request receives a response, even if some nodes fail.
Node A Failed
Node B Still Responds
P – Partition Tolerance
The system continues operating despite network failures between nodes.
Node A X Node B
(Network Partition)
CAP Triangle
Consistency
▲
/\
/ \
/ \
Availability-----Partition Tolerance
A distributed system typically chooses:
● CP → Consistency + Partition Tolerance
● AP → Availability + Partition Tolerance
3. Document-Based Databases
A Document Database stores data as documents, usually in JSON-like format.
Example Document
"id": 101,
"name": "Laptop",
"price": 50000
Characteristics
● Flexible schema
● Nested data structures
● Easy to store complex objects
Example
● MongoDB
Applications
● E-commerce
● Content management systems
● User profiles
4. Key-Value Stores
A Key-Value Database stores data as a simple pair:
Key → Value
Example
User101 → Shilpa
User102 → Rahul
Characteristics
● Very fast retrieval
● Simple design
● Highly scalable
Examples
● Redis
● Amazon DynamoDB
Applications
● Session management
● Caching
● Shopping carts
5. Column-Based Databases
A Column-Based (Wide-Column) Database stores data by columns instead of rows.
Example
ID Name Marks
1 Alice 90
2 Bob 85
Data is physically organized by columns.
Characteristics
● Efficient for analytics
● Handles large datasets
● High scalability
Examples
● Apache Cassandra
● Apache HBase
Applications
● Big Data processing
● Data warehousing
● Real-time analytics
6. Graph Databases
A Graph Database stores data as nodes and relationships (edges).
Example
Alice ---- Friend ---- Bob
|
Works With
|
Charlie
Components
Node
Represents an entity.
Alice
Bob
Charlie
Relationship (Edge)
Friend
Works With
Characteristics
● Efficient relationship traversal
● Ideal for highly connected data
● Flexible schema
Example
● Neo4j
Applications
● Social networks
● Recommendation systems
● Fraud detection
● Network analysis
Comparison of NoSQL Database Types
Type Storage Model Example Best Use Case
Document-Base JSON MongoDB Content management,
d Documents E-commerce
Key-Value Key → Value Redis Caching, Sessions
Column-Based Wide Columns Apache Big Data Analytics
Cassandra
Graph Database Nodes & Edges Neo4j Social Networks