Chapter 3 · Database Systems

Functional Dependencies & Normalization

5 topics in 1 parts

Full lessonPython Programming · Functions

Key ideas

Evaluation Parameter	Standard Relational Pattern	Production Optimization Impact
Storage Engine Layer	Disk page blocks & buffer pool cache	Minimizes random disk I/O via sequential prefetching
Index Utilization	B+ Tree logarithmic search $O(\log N)$	Avoids full table scans across millions of rows
Concurrency & Locks	Row-level shared (S) and exclusive (X) locks	Prevents race conditions while maximizing read throughput
Failure Recovery	Write-Ahead Logging (WAL) / Undo-Redo	Guarantees durability and instant crash recovery

Conceptual Foundation & Core Theory

In the Relational Model, Relational Keys are foundational constraints used to uniquely identify individual tuples (rows) within a relation (table) and enforce Referential Integrity across distinct relations.

1. The Hierarchy of Keys

Super Key (SK): Any set of one or more attributes that collectively identify each row uniquely in a table. A super key may contain extraneous or redundant attributes (e.g., {Roll_No, Phone_No} is a valid Super Key even though Roll_No alone is already unique).
Candidate Key (CK): A minimal Super Key with no redundant attributes. If any attribute is removed from a candidate key, it ceases to be unique. A table can possess multiple candidate keys (e.g., Roll_No, Registration_No, Email).
Primary Key (PK): The single Candidate Key chosen by the Database Administrator to uniquely identify tuples in the table. By standard SQL rules, a Primary Key column strictly prohibits NULL values and must contain distinct values across all rows.
Alternate (Secondary) Key: Any candidate key that was not chosen as the Primary Key.
Foreign Key (FK): An attribute (or set of attributes) in one table that references the Primary Key (or unique key) of another table, establishing a parent-child relationship and preventing orphan rows.

Executable Code Blueprint & Implementation (DBMS & SQL)

-- Relational Keys Implementation in SQL DDL
CREATE TABLE Departments (
    dept_id INT PRIMARY KEY,              -- Primary Key
    dept_name VARCHAR(50) NOT NULL UNIQUE -- Alternate Key
);

CREATE TABLE Students (
    student_id INT,                      -- Candidate Key 1
    roll_no VARCHAR(20),                 -- Candidate Key 2
    email VARCHAR(100),                  -- Candidate Key 3
    phone VARCHAR(15),
    dept_id INT,                         -- Foreign Key referencing Departments
    
    -- Designate Primary Key
    CONSTRAINT pk_student PRIMARY KEY (student_id),
    
    -- Designate Alternate Keys with UNIQUE constraints
    CONSTRAINT uq_roll UNIQUE (roll_no),
    CONSTRAINT uq_email UNIQUE (email),
    
    -- Foreign Key Constraint enforcing Referential Integrity
    CONSTRAINT fk_student_dept FOREIGN KEY (dept_id) 
        REFERENCES Departments(dept_id) 
        ON DELETE CASCADE ON UPDATE CASCADE
);

Functional Dependencies & Normalization

Relational Key Types Comparison Matrix

Key Type	Definition	Allows NULL?	Multiplicity in Table	Minimality Requirement
Super Key	Any attribute combination guaranteeing unique rows	Dependent on attributes	Unlimited possible subsets	No (can contain redundant columns)
Candidate Key	Minimal super key with zero redundant attributes	Strictly UNIQUE (rarely null)	One or more per table	Yes (Strictly minimal)
Primary Key	The designated unique identifier chosen by DBA	STRICTLY NO (NOT NULL enforced)	Exactly ONE per table	Yes (Must be a Candidate Key)
Foreign Key	References Primary Key of another relation	Yes (unless defined NOT NULL)	Zero, one, or multiple	Matches referenced parent key

Relational Design Interview Problem: Minimal Super Key Derivation

Question: Given a relation $R(A, B, C, D)$ with functional dependencies $A \to B, B \to C, C \to D$. Find all candidate keys. Answer: Compute attribute closure of $A$: $A^+ = \{A, B, C, D\}$. Since $A^+$ includes all attributes of $R$, $A$ is a Super Key. Since $A$ is a single attribute, no subset can be removed, making $A$ minimal. Therefore, $A$ is the sole Candidate Key.

Functional Dependencies & Normalization

Normal Form	Pre-requisite Condition	Anomaly / Flaw Eliminated	Mathematical Rule
1NF	Relational Table Format	Multi-valued & nested lists	All domain attribute values must be atomic
2NF	Must be in 1NF	Partial dependencies on composite keys	Non-prime attributes fully functionally dependent on whole key
3NF	Must be in 2NF	Transitive dependencies ($A \to B \to C$)	In $X \to Y$, either $X$ is a superkey or $Y$ is a prime attribute
BCNF	Must be in 3NF	All functional dependency anomalies	In every non-trivial $X \to Y$, $X$ MUST be a superkey

Database Interview Problem: Finding the Highest Normal Form

Problem: Given $R(A, B, C, D)$ with functional dependencies $AB \to CD, C \to D$. The candidate key is $AB$. Identify the highest normal form. Answer: Attributes are: prime = $\{A, B\}$, non-prime = $\{C, D\}$. In dependency $C \to D$, $C$ is NOT a superkey, and $D$ is a non-prime attribute depending on non-prime attribute $C$. This is a transitive dependency. Furthermore, $C$ does not contain $A$ or $B$, so it is not partial. Hence, $R$ is in 2NF, but fails 3NF.

Checkpoint

1. What distinguishes a Candidate Key from a general Super Key?

2. A relational table is in 2NF. Which condition is strictly required for it to also satisfy 3NF?

All 5 topics in Functional Dependencies & Normalization

Normalization
- Functional Dependencies
- Candidate Keys Algorithm
- 1NF & 2NF Rules
- 3NF vs BCNF
- Lossless Decomposition