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 (bfrbfr): The maximum number of records that fit into a single disk block.   Fixed-Length bfr=⌊BR⌋\text{Fixed-Length } bfr = \left\lfloor \frac{B}{R} \right\rfloor   where BB is block size in bytes and RR 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):   Unused Space=B−(bfr×R)\text{Unused Space} = B - (bfr \times R)

  • Disk Access Time: The total physical delay involved in fetching a disk block:   Disk Access Time=Seek Time+Rotational Latency\text{Disk Access Time} = \text{Seek Time} + \text{Rotational Latency}

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 O(n)O(n), where nn is the total number of blocks.

  • Insertion: Highly efficient (O(1)O(1)), as new records are appended to the last block or free space.

  • Deletion: Leaves empty slots or uses a delete-bit marker.

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 O(log⁡2n)O(\log_2 n).

  • Insertion / Deletion: Expensive (O(n)O(n)), requiring record shifting or auxiliary overflow files.

1.4 Binary Search Algorithm on an Ordered Disk File

Let bb be total file blocks, and KK be the target search key:

  1. Set lower bound l=1l = 1, upper bound u=bu = b

  2. While u≥lu \ge l:

    • Compute midpoint block i=⌊l+u2⌋i = \left\lfloor \frac{l + u}{2} \right\rfloor

    • Read block ii into memory buffer

    • If K<ordering key field value of first record in block iK < \text{ordering key field value of first record in block } i: set u=i−1u = i - 1

    • Else if K>ordering key field value of last record in block iK > \text{ordering key field value of last record in block } i: set l=i+1l = i + 1

    • Else if target record is present in buffer: return Record Found

    • Else: return Record Not Found

  3. 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

O(n)O(n) (Linear Search)

O(log⁡2n)O(\log_2 n) (Binary Search)

Insertion Complexity

O(1)O(1) (Append at end)

O(n)O(n) (Expensive reorganization)

Deletion Complexity

O(1)O(1) with delete bit

O(n)O(n) (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 (hh): Mathematical function mapping search keys k∈Kk \in K to bucket indices:   h:K→{0,1,…,m−1}h: K \rightarrow \{0, 1, \dots, m-1\}

  • Bucket: A storage unit (memory slot or disk block) holding database records.

  • Collision: Occurs when two distinct keys hash to the same bucket index (h(k1)=h(k2)h(k_1) = h(k_2)). 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 (h(k)=(2k+3)(mod10)h(k) = (2k + 3) \pmod{10}):

    • Keys to insert: 3, 2, 9, 6, 11, 13, 7, 12

    • h(3)=(2(3)+3)(mod10)=9h(3) = (2(3)+3) \pmod{10} = 9

    • h(2)=(2(2)+3)(mod10)=7h(2) = (2(2)+3) \pmod{10} = 7

    • h(9)=(2(9)+3)(mod10)=1h(9) = (2(9)+3) \pmod{10} = 1

    • h(6)=(2(6)+3)(mod10)=5h(6) = (2(6)+3) \pmod{10} = 5

    • h(11)=(2(11)+3)(mod10)=5h(11) = (2(11)+3) \pmod{10} = 5 (Collision at slot 5; chain: 6→116 \rightarrow 11)

    • h(13)=(2(13)+3)(mod10)=9h(13) = (2(13)+3) \pmod{10} = 9 (Collision at slot 9; chain: 3→133 \rightarrow 13)

    • h(7)=(2(7)+3)(mod10)=7h(7) = (2(7)+3) \pmod{10} = 7 (Collision at slot 7; chain: 2→72 \rightarrow 7)

    • h(12)=(2(12)+3)(mod10)=7h(12) = (2(12)+3) \pmod{10} = 7 (Collision at slot 7; chain: 2→7→122 \rightarrow 7 \rightarrow 12)

2. Open Addressing: Linear Probing

Probes consecutive slots sequentially upon collision: Location(i)=(h(k)+i)(modm)for i=0,1,…,m−1\text{Location}(i) = (h(k) + i) \pmod{m} \quad \text{for } i = 0, 1, \dots, m-1

  • Drawback: Primary Clustering (long contiguous blocks of occupied slots build up, slowing performance).

  • Worked Example (h(k)=(2k+3)(mod10)h(k) = (2k + 3) \pmod{10}):

    • Key 3: Slot 9

    • Key 2: Slot 7

    • Key 9: Slot 1

    • Key 6: Slot 5

    • Key 11: h=5h=5 (Full) →\rightarrow Slot 6

    • Key 13: h=9h=9 (Full) →\rightarrow Slot 0

    • Key 7: h=7h=7 (Full) →\rightarrow Slot 8

    • Key 12: h=7h=7 (Full; probes 7, 8, 9, 0, 1 occupied) →\rightarrow 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: Location(i)=(h(k)+i2)(modm)for i=0,1,…,m−1\text{Location}(i) = (h(k) + i^2) \pmod{m} \quad \text{for } i = 0, 1, \dots, m-1

  • Advantage: Eliminates Primary Clustering.

  • Drawback: Suffers from Secondary Clustering (keys hashing to identical initial positions follow identical probe paths).

  • Failed Insertion Exam Problem (h(k)=k(mod10)h(k) = k \pmod{10}):

    • 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 (h(62)=2h(62) = 2 occupied):

    • Probe sequence for 62: i=1→3i=1 \rightarrow 3, i=2→6i=2 \rightarrow 6, i=3→1i=3 \rightarrow 1, i=4→8i=4 \rightarrow 8, i=5→7i=5 \rightarrow 7, i=6→8i=6 \rightarrow 8, i=7→1i=7 \rightarrow 1, i=8→6i=8 \rightarrow 6, i=9→3i=9 \rightarrow 3.

    • 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: Location(i)=(h1(k)+i×h2(k))(modm)\text{Location}(i) = (h_1(k) + i \times h_2(k)) \pmod{m}

  • h1(k)h_1(k) gives initial position, h2(k)h_2(k) gives step size.

  • Important Rule: h2(k)h_2(k) must be coprime to mm 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 (GDGD): Number of bits used to index the directory. Directory size = 2GD2^{GD}.

  • Local Depth (LDLD): Number of bits used by an individual bucket (LD≤GDLD \le GD).

  • Overflow Management Rules:

    • Case 1 (LD<GDLD < GD): Split overflowing bucket into two, increment local depths (LDnew=LD+1LD_{\text{new}} = LD + 1), rehash records using new bit depth. Do NOT double directory.

    • Case 2 (LD=GDLD = GD): Double directory size (GDnew=GD+1GD_{\text{new}} = GD + 1), split overflowing bucket, increment local depth (LDnew=LD+1LD_{\text{new}} = LD + 1), 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).

  1. Insert 16, 4, 6 at GD=1GD=1 (1 LSB=01 \text{ LSB} = 0): Bucket 0 (LD=1LD=1): [16, 4, 6].

  2. Insert 22 (1 LSB=01 \text{ LSB} = 0): Bucket 0 overflows. Since LD=GD=1LD = GD = 1, double directory (GD=2GD=2: entries 00, 01, 10, 11) and split bucket (LD=2LD=2).

    • Bucket 00 (LD=2LD=2): [16, 4]

    • Bucket 10 (LD=2LD=2): [6, 22]

  3. Insert 24 (00) and 10 (10):

    • Bucket 00: [16, 4, 24]

    • Bucket 10: [6, 22, 10]

  4. Insert 31 (11), 7 (11), 9 (01): Mapped to shared bucket 01/11 (LD=1LD=1): [31, 7, 9].

  5. Insert 20 (00): Bucket 00 overflows ([16, 4, 24]). Since LD=GD=2LD = GD = 2, double directory (GD=3GD=3: 000 to 111) and split bucket (LD=3LD=3).

    • Bucket 000 (LD=3LD=3): [16, 24]

    • Bucket 100 (LD=3LD=3): [4, 20]

  6. Insert 26 (010): Maps to Bucket 10 (LD=2LD=2: [6, 22, 10]). Overflows! Since LD<GDLD < GD (2<32 < 3), split bucket only (LD=3LD=3). Do NOT double directory.

    • Bucket 010 (LD=3LD=3): [10, 26]

    • Bucket 110 (LD=3LD=3): [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 →\rightarrow Inner Index Block →\rightarrow Data Disk Block.


4. B+ Tree Index Architecture
4.1 Structural Rules for B+ Tree of Order mm
  • Order (mm): Maximum number of child pointers in an internal node.

  • Maximum Keys: m−1m - 1

  • 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 PnP_n.

4.2 Comprehensive Worked Problem: B+ Tree Construction & Deletion
  • Order m=4m = 4: Max keys = 3, Min leaf keys = 2, Min internal keys = 1.

  • Insertion Sequence: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20

  1. Insert 2, 4, 6: Leaf [2 4 6]

  2. 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]

  3. Insert 10: Right leaf becomes [6 8 10]

  4. 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]

  5. Insert 14: Right leaf becomes [10 12 14]

  6. 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]

  7. Insert 18: Right leaf becomes [14 16 18]

  8. 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

  1. 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].

  2. Delete 8: Leaf [2 4 8] becomes [2 4] (Valid).

  3. Delete 10: Leaf [10 12] becomes [12] (Underflow). Merge with sibling [2 4] into [2 4 12]. Parent internal [10] becomes empty (Underflow).

  4. 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 (L0,L1,…,LnL_0, L_1, \dots, L_n).

  • 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

σ\sigma

Unary

Filters rows matching condition

"Find tuples where…"

Projection

π\pi

Unary

Extracts specific columns

"Retrieve attributes…"

Rename

ρ\rho

Unary

Renames relation/attributes

"Rename table to…"

Union

∪\cup

Binary

Combines rows from two compatible relations

"Tuples in A or B"

Intersection

∩\cap

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

×\times

Binary

Cross-combines every row of A with B

"All pairs of…"

Theta Join

⋈θ\bowtie_\theta

Binary

Cartesian Product followed by selection

"Join tables on condition"

Natural Join

⋈\bowtie

Binary

Equi-join on common attributes

"Combine matching rows"

Division

÷\div

Binary

Evaluates universal quantification

"Find X enrolled in ALL Y"

Aggregate

F\mathcal{F}

Unary

Extended operator for COUNT, SUM, AVG

"Find total/average of…"

6.2 SQL to Relational Algebra Translation Procedure
  1. Identify Tables: Place relations listed in FROM clause inside Cartesian Product or Join operators.

  2. Identify Selection Conditions: Convert WHERE predicate into Selection (σ\sigma).

  3. Identify Projection Attributes: Convert SELECT attributes into Projection (π\pi).

Example Translation

  • SQL Query:

  SELECT S.name, E.grade
  FROM Student S, Enroll E
  WHERE S.sid = E.sid AND E.grade = 'A';
&nbsp;&nbsp;```
- **Relational Algebra Expression:**
&nbsp;&nbsp;πname,grade(σgrade=′A′(Student⋈Student.sid=Enroll.sidEnroll))\pi_{\text{name}, \text{grade}}\left(\sigma_{\text{grade}='A'}\left(\text{Student} \bowtie_{\text{Student.sid} = \text{Enroll.sid}} \text{Enroll}\right)\right)

#### 6.3 Heuristic Query Tree Optimization

##### Core Optimization Rules
1. **Push Selections Down:** Apply Selection (σ\sigma) operations early to reduce intermediate relation sizes.
2. **Combine Cartesian Product & Selection:** Replace σθ(R×S)\sigma_\theta(R \times S) with R⋈θSR \bowtie_\theta S.
3. **Push Projections Down:** Perform Projection (π\pi) 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:   πLNAME(σPNAME=′Aquarius′∧PNUMBER=PNO∧ESSN=SSN∧BDATE>′1957−12−31′(EMPLOYEE×WORKS_ON×PROJECT))\pi_{\text{LNAME}}\left(\sigma_{\text{PNAME}='Aquarius' \land \text{PNUMBER}=\text{PNO} \land \text{ESSN}=\text{SSN} \land \text{BDATE}>'1957-12-31'}\left(\text{EMPLOYEE} \times \text{WORKS\_ON} \times \text{PROJECT}\right)\right)

  • Optimized Query Tree Structure:

    1. Push σPNAME=′Aquarius′\sigma_{\text{PNAME}='Aquarius'} down directly to PROJECT.

    2. Push σBDATE>′1957−12−31′\sigma_{\text{BDATE}>'1957-12-31'} down directly to EMPLOYEE.

    3. Replace Cartesian Products with Joins: (PROJECT ⋈PNUMBER=PNO\bowtie_{\text{PNUMBER}=\text{PNO}} WORKS_ON) ⋈ESSN=SSN\bowtie_{\text{ESSN}=\text{SSN}} EMPLOYEE.

    4. Push Projections πSSN,LNAME\pi_{\text{SSN}, \text{LNAME}}, πESSN,PNO\pi_{\text{ESSN}, \text{PNO}}, πPNUMBER\pi_{\text{PNUMBER}} 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 (O(1)O(1) insertion).

"Binary search on disk blocks"

Ordered (Sequential) File

Apply formula O(log⁡2n)O(\log_2 n).

"Key mapped modulo table size"

Static Hashing

Compute h(k)=k(modm)h(k) = k \pmod m and handle collisions.

"Probing i2i^2 slot"

Quadratic Probing

Apply (h(k)+i2)(modm)(h(k) + i^2) \pmod m.

"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 mm, max keys m−1m-1, 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 (R÷SR \div S).

"Optimize SQL Query Tree"

Heuristic Optimization

Push σ\sigma and π\pi down toward leaves, replace ×\times with ⋈\bowtie.

7.2 Core Formulas Summary
  • Blocking Factor (bfrbfr): bfr=⌊BR⌋bfr = \left\lfloor \frac{B}{R} \right\rfloor

  • Unused Space per Block: B−(bfr×R)B - (bfr \times R)

  • Linear Probing: Location(i)=(h(k)+i)(modm)\text{Location}(i) = (h(k) + i) \pmod m

  • Quadratic Probing: Location(i)=(h(k)+i2)(modm)\text{Location}(i) = (h(k) + i^2) \pmod m

  • Double Hashing: Location(i)=(h1(k)+i×h2(k))(modm)\text{Location}(i) = (h_1(k) + i \times h_2(k)) \pmod m

  • Extendible Hashing Directory Size: 2GD2^{GD}

  • **