Physical Database Design and Query Processing Study Guide
1. File Structures and Disk Operations
1.1 Simple Explanation
A database system stores massive datasets on secondary storage (disks). Data is transferred between disk and main memory (RAM) in fixed-size blocks. Database files consist of records (tuples), which are stored inside these blocks. DBMS physical design optimizes record arrangement to minimize costly Disk I/O operations.
1.Technical Definitions & Mathematical Formulas
Disk Block (Page): The fundamental unit of data transfer between secondary storage and primary memory.
Blocking Factor (): The maximum number of records that fit into a single disk block. where is block size in bytes and is record size in bytes.
Unused Space per Block: Space wasted when a fixed-length record cannot fit into the remaining bytes of a block (unspanned allocation):
Disk Access Time: The total physical delay involved in fetching a disk block:
1.3 Unordered (Heap) Files vs. Ordered (Sequential) Files
Unordered (Heap) Files
Structure: Records are placed in arbitrary order (typically arrival order).
Search: Requires Linear Search across disk blocks; complexity is , where is the total number of blocks.
Insertion: Highly efficient (), as new records are appended to the last block or free space.
Deletion: Leaves empty slots or uses a
delete-bitmarker.
Ordered (Sequential) Files
Structure: Records are physically sorted on disk according to a designated ordering key attribute.
Search: Supports Binary Search on disk blocks; complexity is .
Insertion / Deletion: Expensive (), requiring record shifting or auxiliary overflow files.
1.4 Binary Search Algorithm on an Ordered Disk File
Let be total file blocks, and be the target search key:
Set lower bound , upper bound
While :
Compute midpoint block
Read block into memory buffer
If : set
Else if : set
Else if target record is present in buffer: return Record Found
Else: return Record Not Found
Return Record Not Found
1.5 File Organization Comparison Table
Feature | Unordered (Heap) File | Ordered (Sequential) File |
|---|---|---|
Record Arrangement | Arrival order (Unsorted) | Sorted by key attribute |
Search Complexity | (Linear Search) | (Binary Search) |
Insertion Complexity | (Append at end) | (Expensive reorganization) |
Deletion Complexity | with delete bit | (Shifting records) |
Best Use Case | High write volume, rare searches | Frequent range queries on ordering key |
2. Hashing Techniques
2.1 Fundamental Concepts
Hash Function (): Mathematical function mapping search keys to bucket indices:
Bucket: A storage unit (memory slot or disk block) holding database records.
Collision: Occurs when two distinct keys hash to the same bucket index (). Colliding keys are called synonyms.
2.2 Static Hashing & Collision Resolution
1. Closed Addressing: Separate Chaining (Overflow Chaining)
Each hash table slot contains a pointer to a linked list of records.
Worked Example ():
Keys to insert: 3, 2, 9, 6, 11, 13, 7, 12
(Collision at slot 5; chain: )
(Collision at slot 9; chain: )
(Collision at slot 7; chain: )
(Collision at slot 7; chain: )
2. Open Addressing: Linear Probing
Probes consecutive slots sequentially upon collision:
Drawback: Primary Clustering (long contiguous blocks of occupied slots build up, slowing performance).
Worked Example ():
Key 3: Slot 9
Key 2: Slot 7
Key 9: Slot 1
Key 6: Slot 5
Key 11: (Full) Slot 6
Key 13: (Full) Slot 0
Key 7: (Full) Slot 8
Key 12: (Full; probes 7, 8, 9, 0, 1 occupied) Slot 2
Final Array:
[0: 13, 1: 9, 2: 12, 3: empty, 4: empty, 5: 6, 6: 11, 7: 2, 8: 7, 9: 3]
3. Open Addressing: Quadratic Probing
Probes slots using quadratic offsets:
Advantage: Eliminates Primary Clustering.
Drawback: Suffers from Secondary Clustering (keys hashing to identical initial positions follow identical probe paths).
Failed Insertion Exam Problem ():
Keys inserted: 42 (slot 2), 16 (slot 6), 91 (slot 1), 33 (slot 3), 18 (slot 8), 27 (slot 7), 36 (slot 0).
Insert 62 ( occupied):
Probe sequence for 62: , , , , , , , , .
Conclusion: Key 62 cannot be inserted despite empty slots existing at indices 4, 5, and 9 because quadratic probing fails to hit those indices.
4. Open Addressing: Double Hashing
Uses two independent hash functions:
gives initial position, gives step size.
Important Rule: must be coprime to to ensure all slots can be probed.
2.3 Dynamic Hashing: Extendible Hashing
Uses a directory of pointers to buckets. A hash function returns a binary string, using bits as directory offsets.
Global Depth (): Number of bits used to index the directory. Directory size = .
Local Depth (): Number of bits used by an individual bucket ().
Overflow Management Rules:
Case 1 (): Split overflowing bucket into two, increment local depths (), rehash records using new bit depth. Do NOT double directory.
Case 2 (): Double directory size (), split overflowing bucket, increment local depth (), rehash records.
Comprehensive Worked Problem (Least Significant Bits - LSB)
Bucket capacity = 3
Insert sequence: 16 (
10000), 4 (00100), 6 (00110), 22 (10110), 24 (11000), 10 (01010), 31 (11111), 7 (00111), 9 (01001), 20 (10100), 26 (11010).
Insert 16, 4, 6 at (): Bucket
0():[16, 4, 6].Insert 22 (): Bucket
0overflows. Since , double directory (: entries00, 01, 10, 11) and split bucket ().Bucket
00():[16, 4]Bucket
10():[6, 22]
Insert 24 (
00) and 10 (10):Bucket
00:[16, 4, 24]Bucket
10:[6, 22, 10]
Insert 31 (
11), 7 (11), 9 (01): Mapped to shared bucket01/11():[31, 7, 9].Insert 20 (
00): Bucket00overflows ([16, 4, 24]). Since , double directory (:000to111) and split bucket ().Bucket
000():[16, 24]Bucket
100():[4, 20]
Insert 26 (
010): Maps to Bucket10(:[6, 22, 10]). Overflows! Since (), split bucket only (). Do NOT double directory.Bucket
010():[10, 26]Bucket
110():[6, 22]
3. Indexing Structures
3.1 Single-Level Ordered Indices
Primary Index: Constructed on the ordering key field of a sorted data file.
Dense Primary Index: Contains an index entry for every single search key value in the data file.
Sparse Primary Index: Contains an index entry for only some search key values (typically one entry per disk block, storing the block anchor key).
Secondary Index (Non-Clustered Index): Constructed on a non-ordering attribute (candidate key or non-key). Must be dense. Index entries point either to data records or to buckets of record pointers.
Clustering Index: Constructed when data file records are physically ordered on a non-key field containing duplicate values (e.g.,
Department_ID). Contains one entry per distinct field value pointing to the first block of that group.
3.2 Multi-Level Indexing
When a single-level primary index becomes too large to fit in main memory, multi-level indexing builds a sparse outer index on top of the primary inner index.
Search Path: Outer Index Block Inner Index Block Data Disk Block.
4. B+ Tree Index Architecture
4.1 Structural Rules for B+ Tree of Order
Order (): Maximum number of child pointers in an internal node.
Maximum Keys:
Minimum Internal Node Children: (\lceil m/2 \rceil)
Minimum Internal Node Keys: (\lceil m/2 \rceil - 1)
Minimum Leaf Node Keys: (\lceil (m - 1)/2 \rceil)
Key Distinction: All actual data pointers reside exclusively in leaf nodes. Internal nodes store search key values solely for routing. Leaf nodes are linked sequentially via pointer .
4.2 Comprehensive Worked Problem: B+ Tree Construction & Deletion
Order : Max keys = 3, Min leaf keys = 2, Min internal keys = 1.
Insertion Sequence: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
Insert 2, 4, 6: Leaf
[2 4 6]Insert 8: Overflow
[2 4 6 8]. Split into[2 4]and[6 8]. Promote 6 to root.Root:
[6]Children:
[2 4],[6 8]
Insert 10: Right leaf becomes
[6 8 10]Insert 12: Overflow
[6 8 10 12]. Split into[6 8]and[10 12]. Promote 10 to root.Root:
[6 10]Children:
[2 4],[6 8],[10 12]
Insert 14: Right leaf becomes
[10 12 14]Insert 16: Overflow
[10 12 14 16]. Split into[10 12]and[14 16]. Promote 14.Root:
[6 10 14]Leaves:
[2 4],[6 8],[10 12],[14 16]
Insert 18: Right leaf becomes
[14 16 18]Insert 20: Overflow
[14 16 18 20]. Split into[14 16]and[18 20]. Promote 18.Root overflows:
[6 10 14 18](4 keys > Max 3).Root Split: Split root into
[6 10]and[18]. Promote 14 to new root.Tree State:
Root:
[14]Internal Level:
[6 10],[18]Leaves:
[2 4],[6 8],[10 12],[14 16],[18 20]
Deletion Sequence: Delete 6, 8, 10, 12
Delete 6: Leaf
[6 8]becomes[8](Underflow, min=2). Sibling[2 4]cannot spare keys. Merge[2 4]and[8]into[2 4 8]. Parent removes key 6. Internal[6 10]becomes[10].Delete 8: Leaf
[2 4 8]becomes[2 4](Valid).Delete 10: Leaf
[10 12]becomes[12](Underflow). Merge with sibling[2 4]into[2 4 12]. Parent internal[10]becomes empty (Underflow).Internal Node Merge: Merge empty internal node with right sibling
[18]and bring down root key 14.Final Tree State:
Root Node:
[14 18]Leaf Nodes:
[2 4 12],[14 16],[18 20]
4.3 B-Tree vs. B+ Tree Comparison
Feature | B-Tree | B+ Tree |
|---|---|---|
Data Pointer Location | In internal and leaf nodes | Exclusively in leaf nodes |
Leaf Node Connection | Leaves are isolated | Linked sequentially via linked list |
Sequential Search | Requires tree traversal | Fast linear scan across leaf linked list |
Node Key Duplication | Keys appear exactly once | Keys may repeat in internal routing nodes |
5. Log-Structured Merge-Tree (LSM Tree)
5.1 Architecture & Write Path
LSM Trees optimize high-frequency write workloads by converting expensive random disk I/O into fast sequential writes.
Write-Ahead Log (WAL): Sequential log file on disk for crash recovery.
MemTable: In-memory sorted structure (Red-Black Tree or Skip List) buffering incoming writes.
Immutable MemTable: Read-only copy of MemTable awaiting flush to disk.
SSTable (Sorted String Table): Immutable sorted files on disk across hierarchical levels ().
Bloom Filter: Memory-efficient probabilistic filter that prevents unnecessary disk reads across SSTables for non-existent keys.
Compaction: Background merge-sort process that merges SSTables, removes duplicate updates, and removes deleted records (marked by Tombstones).
5.2 LSM Variants Comparison Table
Variant | Write Speed | Read Speed | Compaction Cost | Target Workload |
|---|---|---|---|---|
Size-Tiered (STCS) | Excellent | Moderate | Low | Write-heavy applications (Cassandra) |
Leveled (LCS) | Moderate | Excellent | High | Read-heavy / Point lookup workloads (RocksDB) |
Universal | High | Good | Medium | Time-series data |
FIFO | Very High | Low | Very Low | Logging and caching systems |
5.3 B+ Tree vs. LSM Tree Comparison
Feature | B+ Tree | LSM Tree |
|---|---|---|
Primary I/O Pattern | Random Disk Writes (In-place update) | Sequential Disk Writes (Append-only) |
Write Latency | Higher due to page splits | Extremely low (buffered in RAM) |
Read Latency | Very fast (Direct leaf lookup) | Slower (Searches MemTable + SSTables) |
Secondary Storage Format | Dynamic mutable pages | Immutable SSTable files |
6. Relational Algebra and Query Optimization
6.1 Relational Algebra Operators Summary Table
Operator | Symbol | Type | Description | Exam Recognition Clue |
|---|---|---|---|---|
Selection | Unary | Filters rows matching condition | "Find tuples where…" | |
Projection | Unary | Extracts specific columns | "Retrieve attributes…" | |
Rename | Unary | Renames relation/attributes | "Rename table to…" | |
Union | Binary | Combines rows from two compatible relations | "Tuples in A or B" | |
Intersection | Binary | Retains common rows from compatible relations | "Tuples in both A and B" | |
Set Difference | Binary | Retains rows in first relation but not second | "Tuples in A but not B" | |
Cartesian Product | Binary | Cross-combines every row of A with B | "All pairs of…" | |
Theta Join | Binary | Cartesian Product followed by selection | "Join tables on condition" | |
Natural Join | Binary | Equi-join on common attributes | "Combine matching rows" | |
Division | Binary | Evaluates universal quantification | "Find X enrolled in ALL Y" | |
Aggregate | Unary | Extended operator for | "Find total/average of…" |
6.2 SQL to Relational Algebra Translation Procedure
Identify Tables: Place relations listed in
FROMclause inside Cartesian Product or Join operators.Identify Selection Conditions: Convert
WHEREpredicate into Selection ().Identify Projection Attributes: Convert
SELECTattributes into Projection ().
Example Translation
SQL Query:
SELECT S.name, E.grade
FROM Student S, Enroll E
WHERE S.sid = E.sid AND E.grade = 'A';
```
- **Relational Algebra Expression:**
#### 6.3 Heuristic Query Tree Optimization
##### Core Optimization Rules
1. **Push Selections Down:** Apply Selection () operations early to reduce intermediate relation sizes.
2. **Combine Cartesian Product & Selection:** Replace with .
3. **Push Projections Down:** Perform Projection () operations early to eliminate unneeded attributes.
4. **Execute Restrictive Selections First:** Perform most selective filtering operations first.
##### Complete Transformation Example
- **SQL:**
sql SELECT LNAME FROM EMPLOYEE, WORKS_ON, PROJECT WHERE PNAME = 'Aquarius' AND PNUMBER = PNO AND ESSN = SSN AND BDATE > '1957-12-31'; ```
Initial Canonical Tree:
Optimized Query Tree Structure:
Push down directly to
PROJECT.Push down directly to
EMPLOYEE.Replace Cartesian Products with Joins:
(PROJECTWORKS_ON)EMPLOYEE.Push Projections , , down above the leaf nodes.
7. Exam Master Revision & Problem-Solving Guide
7.1 "Question Says / Shows -> Think -> Do First" Decision Guide
Question Keyword / Pattern | Topic / Concept | First Action / Formula |
|---|---|---|
"Frequent inserts, rare key search" | Unordered (Heap) File | Recommend Heap File ( insertion). |
"Binary search on disk blocks" | Ordered (Sequential) File | Apply formula . |
"Key mapped modulo table size" | Static Hashing | Compute and handle collisions. |
"Probing slot" | Quadratic Probing | Apply . |
"Global depth vs Local depth" | Extendible Hashing | Convert keys to binary, check LSB/MSB bits. |
"Index on non-ordering attribute" | Secondary Index | Remember index MUST be dense. |
"Balanced tree, data pointers in leaves" | B+ Tree | Check order , max keys , leaf min keys. |
"MemTable, SSTable, Compaction" | LSM Tree | Trace Write/Read path and Bloom filter. |
"Find entities interacting with ALL…" | Relational Algebra Division | Use Division operator (). |
"Optimize SQL Query Tree" | Heuristic Optimization | Push and down toward leaves, replace with . |
7.2 Core Formulas Summary
Blocking Factor ():
Unused Space per Block:
Linear Probing:
Quadratic Probing:
Double Hashing:
Extendible Hashing Directory Size:
**