Unit 5: Concurrency Control Techniques
Concurrency Control Techniques (DBMS)
Concurrency control is the DBMS mechanism that ensures correct and consistent execution of concurrent transactions while allowing maximum parallelism.
Need for Concurrency Control
- Avoid lost update problem
- Avoid dirty read
- Avoid inconsistent database state
- Ensure serializability and isolation
Locking Techniques for Concurrency Control
Locking is the most widely used concurrency control technique.
Types of Locks
| Lock Type | Symbol | Purpose |
|---|---|---|
| Shared Lock | S | Read operation |
| Exclusive Lock | X | Write operation |
Lock Compatibility Matrix
| S | X | |
|---|---|---|
| S | ✔ | ✖ |
| X | ✖ | ✖ |
Two Phase Locking Protocol (2PL)
A transaction follows two phases:
- Growing Phase – Acquire locks only
- Shrinking Phase – Release locks only
✔ Ensures conflict serializability
❌ May cause deadlocks
Types of 2PL
| Type | Description |
|---|---|
| Basic 2PL | Locks acquired then released |
| Strict 2PL | X locks released after commit |
| Rigorous 2PL | All locks released after commit |
Time Stamping Protocols for Concurrency Control
Concept
- Each transaction gets a unique timestamp
- Oldest transaction has highest priority
Timestamp Ordering Rules
Let:
- TS(T) = timestamp of transaction T
- readTS(X) = largest TS of transaction that read X
- writeTS(X) = largest TS of transaction that wrote X
Read Rule
If TS(T) < writeTS(X) → Abort T
Else → Read allowed
Write Rule
If TS(T) < readTS(X) OR TS(T) < writeTS(X) → Abort T
Else → Write allowed
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| No deadlocks | High rollback rate |
| Simple logic | Starvation possible |
Validation Based Protocol (Optimistic Concurrency Control)
This protocol assumes conflicts are rare.
Three Phases
- Read Phase – Transaction reads data, no locking
- Validation Phase – Check for conflicts
- Write Phase – Update database if validation passes
Validation Condition
Transaction T₁ must finish before T₂ writes conflicting data.
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| High concurrency | Rollbacks possible |
| No deadlock | Validation overhead |
Multiple Granularity Locking
Concept
Data items can be locked at different levels:
- Database
- Table
- Page
- Tuple
Intention Locks
| Lock | Meaning |
|---|---|
| IS | Intention Shared |
| IX | Intention Exclusive |
| SIX | Shared + Intention Exclusive |
Compatibility Matrix (Simplified)
| IS | IX | S | X | |
|---|---|---|---|---|
| IS | ✔ | ✔ | ✔ | ✖ |
| IX | ✔ | ✔ | ✖ | ✖ |
| S | ✔ | ✖ | ✔ | ✖ |
| X | ✖ | ✖ | ✖ | ✖ |
Advantages
- Improves performance
- Reduces locking overhead
- Supports hierarchical databases
Multi Version Concurrency Control (MVCC)
Concept
- Multiple versions of a data item are maintained
- Readers read old versions
- Writers create new versions
Working
- Read operation never blocks write
- Write operation never blocks read
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| High read performance | Storage overhead |
| No read-write conflict | Garbage collection needed |
Comparison: Locking vs MVCC
| Feature | Locking | MVCC |
|---|---|---|
| Blocking | Yes | No |
| Read Performance | Lower | High |
| Storage Overhead | Low | High |
Comparison of Concurrency Control Techniques
| Technique | Deadlock | Rollback | Complexity |
|---|---|---|---|
| Locking (2PL) | Possible | Low | Medium |
| Timestamp | No | High | Low |
| Validation | No | Medium | Medium |
| MVCC | No | Low | High |
Exam-Focused Summary (MCA)
- Concurrency control ensures isolation and consistency
- Locking is the most common technique
- 2PL guarantees serializability
- Timestamp protocol avoids deadlocks
- Validation protocol works best in low conflict systems
- Multiple granularity improves efficiency
- MVCC provides high concurrency for read-heavy workloads
Transaction Processing Concepts
A transaction is a logical unit of work performed on a database that must be completed entirely or not at all.
Example: Transfer ₹5,000 from Account A to Account B
- Debit from A
- Credit to B
Both must happen together.
Properties of Transaction (ACID)
| Property | Meaning |
|---|---|
| Atomicity | All or nothing execution |
| Consistency | Database remains valid |
| Isolation | Transactions do not interfere |
| Durability | Changes are permanent |
Serializability
Serializability ensures that concurrent transactions produce the same result as serial execution.
Types:
- Conflict Serializability
- View Serializability
Testing of Serializability
- Use Precedence Graph (Serialization Graph)
- Nodes → Transactions
- Edge → Conflict between transactions
If no cycle, schedule is serializable.
Conflict Serializable Schedule
Two operations conflict if:
- They belong to different transactions
- Operate on same data item
- At least one is a write
View Serializable Schedule
A schedule is view serializable if:
- Same initial reads
- Same final writes
- Same read-from relationship
Recoverability
A schedule is recoverable if:
-
A transaction commits only after all transactions it depends on have committed.
Types:
- Recoverable
- Cascadeless
- Strict Schedule
Recovery from Transaction Failures
Failures may occur due to:
- System crash
- Disk failure
- Power failure
Recovery restores database to a consistent state.
Log-Based Recovery
All changes are recorded in a log file.
Log Entry Format:
<Transaction ID, Data Item, Old Value, New Value>
Recovery Actions:
- UNDO → Rollback
- REDO → Reapply changes
Checkpoints
Checkpoint reduces recovery time.
Steps:
- Suspend transactions
- Write logs to disk
- Resume transactions
Deadlock Handling
Deadlock occurs when transactions wait indefinitely.
Methods:
| Method | Description |
|---|---|
| Prevention | Avoid deadlock conditions |
| Detection | Wait-for graph |
| Recovery | Rollback one transaction |
Distributed Database
Distributed Data Storage
Data is stored at multiple sites connected by a network.
Advantages:
- High availability
- Better performance
- Scalability
Concurrency Control in Distributed DB
Ensures data consistency across sites.
Techniques:
- Distributed locking
- Timestamp ordering
- Two-phase commit
Directory System
Directory maintains metadata about:
- Data location
- Fragmentation
- Replication
Types:
- Centralized directory
- Distributed directory
Concurrency Control Techniques
Lock-Based Protocol
Uses locks to manage access.
Types of Locks:
| Lock | Meaning |
|---|---|
| Shared (S) | Read |
| Exclusive (X) | Write |
Two Phase Locking (2PL)
Phases:
- Growing phase – acquiring locks
- Shrinking phase – releasing locks
Ensures serializability.
Timestamp Protocol
Each transaction gets a timestamp.
Rules:
- Older transaction gets priority
- Violations cause rollback
Validation-Based Protocol
Phases:
- Read phase
- Validation phase
- Write phase
No locking used.
Multiple Granularity
Locks at different levels:
- Database
- Table
- Row
Uses intention locks (IS, IX).
Multiversion Concurrency Control (MVCC)
- Multiple versions of data
- Readers never block writers
Used in Oracle, MySQL, PostgreSQL
Recovery with Concurrent Transactions
Challenges:
- Interleaved execution
- Partial failures
Solution:
- Write-ahead logging
- Checkpoints
- Strict 2PL
Case Study: Oracle Database
Oracle Features Related to DBMS Concepts
1. Concurrency Control
- Uses MVCC
- Readers do not block writers
2. Recovery Mechanism
- Redo log files
- Undo segments
- Automatic crash recovery
3. Transaction Management
- COMMIT
- ROLLBACK
- SAVEPOINT
4. Distributed Database Support
- Database links
- Two-phase commit protocol
Exam Tips for MCA Students
- Draw ER diagrams & precedence graphs
- Write definitions first
- Use tables for comparison
- Quote Oracle as real-life example