DBMS Notes
HubUnit 1 — Introduction to DBMS & Entity-Relationship ModelAdvantages and Disadvantages of DBMSAggregation — Database Management SystemsCharacteristics of DBMSData IndependenceData ModelsDatabase Users and AdministratorsDBMS LanguagesER DiagramsEntity-Relationship (ER) ModelIntroduction to DBMSKeys in DBMSRelationships and CardinalitySchema and InstanceSpecialization and GeneralizationDBMS Unit 1 Summary - Database FundamentalsThree-Level Architecture (ANSI/SPARC Architecture)Weak Entity SetUnit 2 — Relational Model & SQLConstraints in SQLCursorsDCL and TCL CommandsDDL CommandsDML CommandsDomain Relational Calculus (DRC) - Complete TutorialFunctions and Stored ProceduresJoins in SQLNested Queries (Subqueries)Relational AlgebraRelational Calculus in Database Management SystemsRelational ModelSQL IntroductionDBMS Unit 2 Summary - SQL and Relational ModelTriggers in SQL — Database Management SystemsTuple Relational Calculus (TRC)Views in SQL — Database Management SystemsArmstrong\Boyce-Codd Normal Form (BCNF) — Database Management SystemsClosure of AttributesDependency PreservationFifth Normal Form (5NF)First Normal Form (1NF) - Database NormalizationFourth Normal Form (4NF)Functional DependencyLossless DecompositionMultivalued DependencyNormal Forms — OverviewNormalization — IntroductionSecond Normal Form (2NF) — Database Management SystemsUnit 3 Summary — NormalizationThird Normal Form (3NF) — Database Management SystemsUnit 4 — Transaction Management & Concurrency ControlACID PropertiesCheckpointsConcurrency Control & SerializabilityDeadlock in DBMSLock-Based Protocols & Two-Phase LockingLog-Based RecoveryRecovery SystemSerializabilityShadow PagingUnit 4 Summary — Transaction Management & Concurrency ControlTimestamp-Based ProtocolTransaction ManagementTransaction StatesTwo-Phase Locking (2PL)Unit 5 — Storage & IndexingB+ TreeB-TreeCost EstimationDynamic HashingFile OrganizationHashing TechniquesIndexing — IntroductionMulti-Level IndexingQuery Optimization — Database Management SystemsQuery ProcessingSingle-Level IndexingStatic HashingUnit 5 Summary — Storage & IndexingUnit 6 — Advanced Topics in DBMSCloud DatabaseData MiningData WarehouseDatabase SecurityDistributed DatabaseDistributed Query ProcessingDistributed DBMS Architecture, Fragmentation & ReplicationMongoDB — IntroductionNoSQL DatabaseReplication in Distributed DatabasesUnit 6 Summary — Advanced Topics in DBMSViva Voce — DBMSImportant Viva Questions — DBMSInterview Questions — DBMSViva Answers — DBMSDBMS Multiple Choice Questions (MCQs)DBMS Lab Programs
This unit covered the mechanisms that keep databases reliable and correct when multiple users access data simultaneously and when system failures occur. The...
Core Concepts at a Glance
This unit covered the mechanisms that keep databases reliable and correct when multiple users access data simultaneously and when system failures occur. The three pillars are: transactions (logical units of work), concurrency control (managing simultaneous access), and recovery (restoring consistency after failures).
Concurrency Problems and Solutions
| Problem | Description | Example | Solution |
|---|---|---|---|
| Dirty Read | Reading uncommitted data | T2 reads T1's write, then T1 aborts | Strict 2PL, Read Committed isolation |
| Lost Update | Write overwritten silently | Two withdrawals from same account | Exclusive locks before write |
| Non-Repeatable Read | Same query returns different values | Balance changes between two reads in T1 | Repeatable Read isolation |
| Phantom Read | New rows appear in repeated query | New enrollment appears between two SELECTs | Serializable isolation, predicate locks |
Serializability
The correctness criterion for concurrent schedules. A schedule is correct if it is equivalent to some serial schedule (one transaction at a time).
Testing Conflict Serializability
| Step 1 | Build precedence graph |
| - Edge Ti | Tj if Ti has a conflicting operation before Tj's |
| Step 2 | Check for cycles |
| - No cycle | Conflict Serializable (correct) |
| - Cycle exists | NOT conflict serializable (incorrect schedule) |
| Conflicting operations | same data item, at least one is WRITE |
Lock-Based Protocols
Lock Types and Compatibility
| Shared (S) | Exclusive (X) | |
|---|---|---|
| Shared (S) | Compatible | NOT Compatible |
| Exclusive (X) | NOT Compatible | NOT Compatible |
- Shared lock: for reading (multiple transactions can hold simultaneously)
- Exclusive lock: for writing (only one transaction can hold)
Two-Phase Locking (2PL) Variants
| Variant | Rule | Guarantees |
|---|---|---|
| Basic 2PL | Growing then shrinking phases | Conflict serializability |
| Strict 2PL | Hold exclusive locks until commit | No dirty reads, no cascading rollbacks |
| Rigorous 2PL | Hold ALL locks until commit | Simplest to implement, strongest guarantees |
The lock point (moment of last lock acquisition) determines the transaction's position in the equivalent serial order.
Timestamp-Based Protocol
Each transaction receives a unique timestamp at start. Operations are validated against read and write timestamps of data items.
| If TS(Ti) < W-timestamp(X) | Ti is too old, ABORT and restart |
| Else | Allow read, set R-timestamp(X) = max(R-timestamp(X), TS(Ti)) |
| If TS(Ti) < R-timestamp(X) | ABORT (someone newer already read old value) |
| Basic rule | ABORT |
| Thomas Write Rule | SKIP the write (outdated write is harmless) |
| Else | Allow write, set W-timestamp(X) = TS(Ti) |
Deadlock Management
| Strategy | Mechanism | Trade-off |
|---|---|---|
| Detection | Periodically check wait-for graph for cycles | May allow deadlock to form temporarily |
| Wait-Die | Older transaction waits; younger aborts | No deadlock, but younger transactions may starve |
| Wound-Wait | Older preempts younger; younger waits | No deadlock, favors older transactions |
| Timeout | Abort if waiting too long | Simple but may abort non-deadlocked transactions |
| Prevention | Request all locks upfront or enforce ordering | No deadlock possible, but reduces concurrency |
Recovery Mechanisms
Log-Based Recovery (Write-Ahead Logging)
| WAL Rule | Log record must be written to stable storage BEFORE |
| UNDO | Rollback uncommitted transactions (restore old values) |
| REDO | Reapply committed transactions (restore new values) |
| 1. Scan log backward | UNDO all active (uncommitted) transactions |
| 2. Scan log forward | REDO all committed transactions |
Checkpoints
Reduce recovery time by recording a point of known consistency:
- Flush all modified buffers to disk
- Write checkpoint record to log listing all active transactions
- During recovery, only process log records after the last checkpoint
Shadow Paging
| - Current page table | points to modified pages |
| - Shadow page table | points to original (safe) pages |
| To commit | Make current page table the new shadow (atomic pointer swap) |
| To abort | Discard current page table, revert to shadow |
| Advantage | No UNDO/REDO needed |
| Disadvantage | Fragmentation, poor performance with large databases |
Key Formulas and Rules
| Concept | Rule |
|---|---|
| Conflict serializability | No cycle in precedence graph |
| 2PL guarantee | Growing phase + shrinking phase → serializable |
| WAL protocol | Log before data on disk |
| Checkpoint benefit | Recovery starts from last checkpoint, not beginning of log |
| Thomas Write Rule | Skip obsolete writes instead of aborting |
Comparison of Concurrency Control Methods
| Method | Approach | Deadlock? | Starvation? | Cascading Abort? |
|---|---|---|---|---|
| Basic 2PL | Lock-based | Yes | Possible | Possible |
| Strict 2PL | Lock-based | Yes | Possible | No |
| Timestamp | Timestamp ordering | No | Possible (restarts) | No |
| MVCC | Multiple versions | No | No | No |
Continue the lesson path
Study next in this module
01Unit 4Shadow PagingShadow paging is an alternative recovery technique to log-based recovery. Instead of maintaining a transaction log to undo and redo operations, it maintains...02Unit 4Timestamp-Based ProtocolThe Timestamp Ordering Protocol is a concurrency control mechanism that uses transaction timestamps — rather than locks — to determine the serialization...03Unit 4SerializabilityA concurrent schedule is serializable if its outcome (effect on the database) is equivalent to the outcome of some serial schedule of the same transactions.04Unit 4Transaction ManagementA transaction is a logical unit of work consisting of one or more database operations (reads and writes) that must execute as a single, indivisible unit....