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
Static hashing suffers when data size changes unpredictably: - Too few buckets → overflow chains → slow - Too many buckets → wasted space
Why Dynamic Hashing?
Static hashing suffers when data size changes unpredictably:
- Too few buckets → overflow chains → slow
- Too many buckets → wasted space
Dynamic hashing allows the hash table to grow and shrink as data changes, maintaining good performance without a fixed bucket count.
Two main forms:
- Extendible Hashing — directory-based, doubles directory on overflow
- Linear Hashing — directory-free, adds one bucket at a time
Search in Extendible Hashing
| Example | Global depth = 2, K=6, h(6) = ...10... |
| First 2 bits = "10" | index 2 → Bucket C |
| Search Bucket C for K=6 | Found! |
| Cost | 1 directory read + 1 bucket read |
Insert with Bucket Split
| Case 1 | Local depth j < Global depth i |
| Case 2 | Local depth j = Global depth i |
| Example | Insert into full Bucket A (local depth 2 = global depth 2) |
| Step 1: Double directory: global depth 2 | 3 (4 entries → 8 entries) |
| Step 2 | Split Bucket A into A and A' |
| Step 3 | Redistribute records using 3-bit prefix |
Extendible Hashing Diagram (After Split)
| BEFORE (Global depth 2) | AFTER INSERT (Global depth 3): |
| Dir | Bucket: Dir (8 entries): Bucket: |
| Insert 15 into B (full) | 101 ─► B' [15] |
Linear Hashing
Concept
Linear hashing adds one bucket at a time in a predetermined linear order, without using a directory. It uses a sequence of hash functions.
Example
At any time, two hash functions are active:
h_i(K) = K mod (2^i × N) (current level)
h_{i+1}(K) = K mod (2^{i+1} × N) (next level)
Where N = initial number of buckets
Splitting proceeds through buckets in order: 0, 1, 2, ..., n−1
tracked by a split pointer (sp)
Linear Hashing Lookup
Example
Lookup key K:
1. Compute bucket = h_i(K)
2. If bucket < split pointer (sp):
→ Bucket has been split; use h_{i+1}(K) instead
3. Access the computed bucket
This ensures records are always found correctly
even while splits are happening.
When to Split
A split is triggered when the load factor exceeds a threshold (e.g., 0.8):
Example
After each split:
- Split pointer (sp) advances by 1
- When sp reaches the end → start new round (increment level i)
- Load factor naturally stays in acceptable range
Extendible vs. Linear Hashing
| Feature | Extendible Hash | Linear Hash |
|---|---|---|
| Directory | Yes (doubles) | No (dir-free) |
| Split trigger | Bucket overflow | Load factor |
| Buckets added | One at a time | One at a time |
| Directory overhead | Can double | None |
| Implementation | Moderate | Slightly complex |
| Search cost | 1 dir + 1 bucket | O(1) — 1 bucket |
Dynamic Hashing vs. Static Hashing
Example
Static: Fixed B, fast for stable data, poor for growth
Dynamic: Grows gracefully, maintains O(1) search
at the cost of split overhead
Most modern in-memory hash tables use dynamic hashing.
Disk-based DBMS often prefer B+ trees over hashing
because B+ trees support both equality AND range queries.
Continue the lesson path
Study next in this module
01Unit 5Cost EstimationCost estimation is the process of predicting the execution cost of a query plan without actually running it. The query optimizer uses cost estimates to...02Unit 5File OrganizationFile organization refers to how data records are physically arranged and stored on disk. The choice of file organization directly impacts the performance of...03Unit 5B-TreeA B-Tree (Balanced Tree) is a self-balancing, sorted tree data structure that maintains sorted data and allows searches, insertions, and deletions in O(log...04Unit 5Hashing TechniquesHashing is a data access technique that uses a mathematical function (called a hash function) to compute the storage address of a record directly from its...