Relational Database Design

First Normal Form (1NF)

Definition: A relation is in 1NF if all attributes contain only atomic (indivisible) values.

Violation: Student(ID, Name, Subjects) where Subjects = "Math, Physics" (non-atomic)

Resolution: Separate rows for each subject.

Second Normal Form (2NF)

Definition: A relation is in 2NF if it's in 1NF and every non-prime attribute is fully functionally dependent on the primary key.

Violation: Grades(Student_ID, Course_ID, Professor_Name) where Professor_Name depends only on Course_ID.

Resolution: Decompose into Courses(Course_ID, Professor_Name) and Grades(Student_ID, Course_ID).

Third Normal Form (3NF)

Definition: A relation is in 3NF if it's in 2NF and no non-prime attribute is transitively dependent on the primary key.

Violation: Employee(Emp_ID, Zip_Code, City) where Emp_ID → Zip_Code → City

Resolution: Decompose into Employee(Emp_ID, Zip_Code) and Location(Zip_Code, City).

Boyce-Codd Normal Form (BCNF)

Definition: A relation is in BCNF if for every non-trivial FD X → Y, X is a superkey.

Difference from 3NF: BCNF does not allow the exception for prime attributes. It's stricter than 3NF.

Status: BCNF is the "gold standard" for eliminating all FD-based redundancy.

Normalization is needed to:

1. Eliminate Redundancy: Avoid storing the same data in multiple places, saving storage space.
2. Prevent Update Anomalies: Ensure that modifying data in one place doesn't require changes in multiple locations.
3. Prevent Insertion Anomalies: Allow adding new data without requiring unrelated data to exist.
4. Prevent Deletion Anomalies: Ensure that deleting some data doesn't unintentionally remove other important data.
5. Ensure Data Integrity: Maintain consistency and accuracy of data.
6. Simplify Queries: Well-structured tables are easier to query and maintain.

Definition: A functional dependency X → Y holds if whenever two tuples have the same value for X, they must have the same value for Y.

Examples:

• SSN → Name: Given a Social Security Number, the employee name is uniquely determined.
• Student_ID → {Name, DOB, Address}: A student ID determines all student attributes.
• {Course_ID, Semester} → Instructor: A course in a specific semester has one instructor.

Properties:

• FDs are constraints on the schema, not on specific data
• If K is a key, then K → all attributes
• FDs are derived from real-world semantics

Definition: A decomposition is lossless (non-additive) if joining the decomposed relations produces exactly the original relation without any spurious tuples.

Test for Binary Decomposition:

D = {R₁, R₂} is lossless if: (R₁ ∩ R₂) → (R₁ - R₂) OR (R₁ ∩ R₂) → (R₂ - R₁)

Example:

Original: EMPLOYEE(Emp_ID, Name, Dept_ID, Dept_Name)

FD: Dept_ID → Dept_Name

Decomposition:

• R₁ = EMPLOYEE(Emp_ID, Name, Dept_ID)
• R₂ = DEPARTMENT(Dept_ID, Dept_Name)

R₁ ∩ R₂ = {Dept_ID}

R₂ - R₁ = {Dept_Name}

Since Dept_ID → Dept_Name is in F, this is a lossless decomposition.

Step 1: Find Candidate Key

A⁺ = {A, B, C} (A determines B, B determines C)

To get D, we need {A, D}

Candidate Key = {A, D}

Step 2: Identify Prime and Non-Prime Attributes

• Prime: A, D
• Non-Prime: B, C

Step 3: Check Normal Forms

• 1NF: ✓ (Assuming atomic values)
• 2NF: ❌ A→B is a partial dependency (A is part of key {A,D})

Answer: The relation is in 1NF only.

To normalize to 3NF:

• R1(A, B)
• R2(B, C)
• R3(A, D)

Armstrong's axioms are a set of inference rules for deriving all functional dependencies:

Primary Rules (Axioms):

1. Reflexivity: If Y ⊆ X, then X → Y
   Example: ABC → AB, ABC → A
2. Augmentation: If X → Y, then XZ → YZ
   Example: If A → B, then AC → BC
3. Transitivity: If X → Y and Y → Z, then X → Z
   Example: If A → B and B → C, then A → C

Derived Rules:

• Decomposition: If X → YZ, then X → Y and X → Z
• Union: If X → Y and X → Z, then X → YZ
• Pseudotransitivity: If X → Y and WY → Z, then WX → Z

These rules are sound (derive only valid FDs) and complete (can derive all FDs in F⁺).