HIGH-YIELD REVISION GUIDE & CHEAT SHEET
SQL & Relational Database Systems
Complete Semester Guide
High-Yield Comprehensive Guide, Relational Algebra, B+ Tree Mechanics,
Normalization Decompositions, ARIES Recovery & Quick-Cram Appendix
Computer Science & Data Engineering | Course Code: CS 186 / CS 340 / DATA 100 | 2024-2025
Comprehensive Edition
📘 WHAT’S INSIDE THIS GUIDE:
✔ Relational Algebra & True SQL Execution Order with query cost optimization models
✔ Database Normalization Theory: Functional dependency closures, candidate keys, and step-
by-step 3NF/BCNF decompositions
✔ B+ Tree Indexing Deep Dive: Step-by-step worked trace of node splits, redistribution, and
height calculations
✔ Query Evaluation & Join Algorithms: Detailed disk I/O cost formulas for Page/Block Nested
Loop, Index Nested Loop, and Grace Hash Join
✔ Concurrency Control & Strict 2PL: Conflict serializability, Precedence Graphs, and 4 ANSI
Isolation Levels
✔ Crash Recovery (ARIES): Write-Ahead Logging (WAL) protocol and Analysis, Redo, and Undo
phase traces
✔ 10 Deadly Database Exam Traps covering NULL three-valued logic, subquery pitfalls, and
index scans
✔ APPENDIX: 1-Hour Emergency Pre-Exam Quick-Cram Cheat Sheet with master relational
matrix and 25 active recall flashcards
Disclaimer: This is an independently created academic study aid. It is not affiliated with, endorsed by, or sponsored by any specific
university, textbook author, or publisher.
, Computer Science & Data Engineering · CS 186 / CSSQL & Relational Database Systems Complete Semester
340 / DATA 100 Guide
1 Relational Algebra & Query Execution Mechanics
Relational algebra provides the formal foundation for declarative SQL query optimization.
1.1 Core Relational Operators
• Selection (𝜎𝑐(𝑅) ): Filters tuples satisfying predicate 𝑐.
• Projection (𝜋𝐿(𝑅) ): Extracts specified attributes 𝐿, deduplicating duplicate rows in pure relational
theory.
• Natural Join (𝑅 ⨝ 𝑆): Equi-join over all shared attributes, projecting out duplicate column names.
• Theta Join (𝑅 ⨝𝜃 𝑆): Cross-product followed by selection: 𝜎𝜃(𝑅×𝑆) .
1.2 The True SQL Logical Execution Pipeline
Unlike procedural languages, SQL executes declaratively in this strict logical sequence:
1. FROM / JOIN: Evaluates Cartesian products and evaluates ON filters to build the virtual table.
2. WHERE: Filters individual candidate rows before aggregation.
3. GROUP BY: Partitions remaining rows into aggregate groups.
4. HAVING: Filters aggregated groups based on summary predicates (e.g., COUNT(*) > 2).
5. SELECT: Evaluates projection list, mathematical expressions, and window functions.
6. DISTINCT: Eliminates duplicate rows from the projected set.
7. ORDER BY: Sorts the final result set using the specified collation.
8. LIMIT / OFFSET: Truncates output tuples for client delivery.
2 Functional Dependencies & Normalization Step-by-Step
2.1 WORKED STEP-BY-STEP PROBLEM: Candidate Keys & BCNF Decompo-
sition
Problem: Consider relation 𝑅(𝐴, 𝐵, 𝐶, 𝐷, 𝐸) with Functional Dependencies (FDs):
𝐹 = {𝐴𝐵 → 𝐶, 𝐶 → 𝐷, 𝐷 → 𝐸, 𝐸 → 𝐴}
Find all Candidate Keys of 𝑅, test whether 𝑅 is in 3NF or BCNF, and decompose into BCNF if violated.
2.1.1 Step 1: Attribute Closures & Candidate Key Derivation
• Calculate closure of (𝐴𝐵)+ :
‣ (𝐴𝐵)+ = {𝐴, 𝐵}
‣ Using 𝐴𝐵 → 𝐶: adds 𝐶 → {𝐴, 𝐵, 𝐶}
‣ Using 𝐶 → 𝐷: adds 𝐷 → {𝐴, 𝐵, 𝐶, 𝐷}
‣ Using 𝐷 → 𝐸: adds 𝐸 → {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} = 𝑅.
‣ Therefore, 𝐴𝐵 is a Candidate Key!
• Since 𝐸 → 𝐴, substitute 𝐴 with 𝐸: (𝐸𝐵)+ = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} = 𝑅 → 𝐸𝐵 is a Candidate Key.
• Since 𝐷 → 𝐸, substitute 𝐸 with 𝐷: (𝐷𝐵)+ = 𝑅 → 𝐷𝐵 is a Candidate Key.
• Since 𝐶 → 𝐷, substitute 𝐷 with 𝐶: (𝐶𝐵)+ = 𝑅 → 𝐶𝐵 is a Candidate Key.
• Prime Attributes (members of any candidate key): {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}. All attributes are prime!
Independent Study Aid. Not affiliated with or endorsed by any specific university or Page 2 of 7
publisher.
SQL & Relational Database Systems
Complete Semester Guide
High-Yield Comprehensive Guide, Relational Algebra, B+ Tree Mechanics,
Normalization Decompositions, ARIES Recovery & Quick-Cram Appendix
Computer Science & Data Engineering | Course Code: CS 186 / CS 340 / DATA 100 | 2024-2025
Comprehensive Edition
📘 WHAT’S INSIDE THIS GUIDE:
✔ Relational Algebra & True SQL Execution Order with query cost optimization models
✔ Database Normalization Theory: Functional dependency closures, candidate keys, and step-
by-step 3NF/BCNF decompositions
✔ B+ Tree Indexing Deep Dive: Step-by-step worked trace of node splits, redistribution, and
height calculations
✔ Query Evaluation & Join Algorithms: Detailed disk I/O cost formulas for Page/Block Nested
Loop, Index Nested Loop, and Grace Hash Join
✔ Concurrency Control & Strict 2PL: Conflict serializability, Precedence Graphs, and 4 ANSI
Isolation Levels
✔ Crash Recovery (ARIES): Write-Ahead Logging (WAL) protocol and Analysis, Redo, and Undo
phase traces
✔ 10 Deadly Database Exam Traps covering NULL three-valued logic, subquery pitfalls, and
index scans
✔ APPENDIX: 1-Hour Emergency Pre-Exam Quick-Cram Cheat Sheet with master relational
matrix and 25 active recall flashcards
Disclaimer: This is an independently created academic study aid. It is not affiliated with, endorsed by, or sponsored by any specific
university, textbook author, or publisher.
, Computer Science & Data Engineering · CS 186 / CSSQL & Relational Database Systems Complete Semester
340 / DATA 100 Guide
1 Relational Algebra & Query Execution Mechanics
Relational algebra provides the formal foundation for declarative SQL query optimization.
1.1 Core Relational Operators
• Selection (𝜎𝑐(𝑅) ): Filters tuples satisfying predicate 𝑐.
• Projection (𝜋𝐿(𝑅) ): Extracts specified attributes 𝐿, deduplicating duplicate rows in pure relational
theory.
• Natural Join (𝑅 ⨝ 𝑆): Equi-join over all shared attributes, projecting out duplicate column names.
• Theta Join (𝑅 ⨝𝜃 𝑆): Cross-product followed by selection: 𝜎𝜃(𝑅×𝑆) .
1.2 The True SQL Logical Execution Pipeline
Unlike procedural languages, SQL executes declaratively in this strict logical sequence:
1. FROM / JOIN: Evaluates Cartesian products and evaluates ON filters to build the virtual table.
2. WHERE: Filters individual candidate rows before aggregation.
3. GROUP BY: Partitions remaining rows into aggregate groups.
4. HAVING: Filters aggregated groups based on summary predicates (e.g., COUNT(*) > 2).
5. SELECT: Evaluates projection list, mathematical expressions, and window functions.
6. DISTINCT: Eliminates duplicate rows from the projected set.
7. ORDER BY: Sorts the final result set using the specified collation.
8. LIMIT / OFFSET: Truncates output tuples for client delivery.
2 Functional Dependencies & Normalization Step-by-Step
2.1 WORKED STEP-BY-STEP PROBLEM: Candidate Keys & BCNF Decompo-
sition
Problem: Consider relation 𝑅(𝐴, 𝐵, 𝐶, 𝐷, 𝐸) with Functional Dependencies (FDs):
𝐹 = {𝐴𝐵 → 𝐶, 𝐶 → 𝐷, 𝐷 → 𝐸, 𝐸 → 𝐴}
Find all Candidate Keys of 𝑅, test whether 𝑅 is in 3NF or BCNF, and decompose into BCNF if violated.
2.1.1 Step 1: Attribute Closures & Candidate Key Derivation
• Calculate closure of (𝐴𝐵)+ :
‣ (𝐴𝐵)+ = {𝐴, 𝐵}
‣ Using 𝐴𝐵 → 𝐶: adds 𝐶 → {𝐴, 𝐵, 𝐶}
‣ Using 𝐶 → 𝐷: adds 𝐷 → {𝐴, 𝐵, 𝐶, 𝐷}
‣ Using 𝐷 → 𝐸: adds 𝐸 → {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} = 𝑅.
‣ Therefore, 𝐴𝐵 is a Candidate Key!
• Since 𝐸 → 𝐴, substitute 𝐴 with 𝐸: (𝐸𝐵)+ = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} = 𝑅 → 𝐸𝐵 is a Candidate Key.
• Since 𝐷 → 𝐸, substitute 𝐸 with 𝐷: (𝐷𝐵)+ = 𝑅 → 𝐷𝐵 is a Candidate Key.
• Since 𝐶 → 𝐷, substitute 𝐷 with 𝐶: (𝐶𝐵)+ = 𝑅 → 𝐶𝐵 is a Candidate Key.
• Prime Attributes (members of any candidate key): {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}. All attributes are prime!
Independent Study Aid. Not affiliated with or endorsed by any specific university or Page 2 of 7
publisher.
