Database Management Systems

X → Y (X determines Y)
"If two tuples have the same value for X, 
 they MUST have the same value for Y"

Example: Student table
student_id → name, email, dept_id
(student_id determines all other attributes)

email → student_id, name
(email also uniquely identifies a student)

Primary Axioms (Sound and Complete):

1. Reflexivity: If Y ⊆ X, then X → Y
   Example: {A, B} → 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:

4. Union: If X → Y and X → Z, then X → YZ
5. Decomposition: If X → YZ, then X → Y and X → Z
6. Pseudotransitivity: If X → Y and WY → Z, then WX → Z

# Closure of X (denoted X+) = All attributes determined by X

def closure(X, FDs):
    """
    Find closure of attribute set X given functional dependencies
    """
    result = set(X)
    changed = True
    
    while changed:
        changed = False
        for lhs, rhs in FDs:
            if lhs.issubset(result) and not rhs.issubset(result):
                result = result.union(rhs)
                changed = True
    
    return result

# Example:
# R(A, B, C, D, E)
# FDs: A → BC, B → D, CD → E

# Find A+:
# A+ = {A}           (start)
# A+ = {A, B, C}     (apply A → BC)
# A+ = {A, B, C, D}  (apply B → D)
# A+ = {A, B, C, D, E} (apply CD → E)

# A+ contains all attributes → A is a candidate key!

# Step 1: Categorize attributes
# - L: Appears only on LEFT side of FDs → MUST be in every key
# - R: Appears only on RIGHT side → NEVER in any key
# - LR: Appears on both sides → MAY be in key
# - N: Appears in neither → MUST be in every key

# Step 2: Start with L ∪ N attributes
# Step 3: If closure = all attributes → candidate key found
# Step 4: If not, add LR attributes one by one

# Example:
# R(A, B, C, D, E)
# FDs: A → BC, CD → E, B → D

# Categorize:
# L = {A, C} (only on left)
# R = {E} (only on right)
# LR = {B, D} (both sides)

# Start with L = {A, C}
# (AC)+ = {A, C, B, D, E} = All attributes
# AC is a candidate key!

# Continue to find more keys...
# Try replacing C with other combinations

-- NOT in 1NF (multi-valued attribute)
| student_id | name  | phone_numbers      |
|------------|-------|-------------------|
| 1          | Alice | 1234567, 9876543  |  ← Violates 1NF

-- Converted to 1NF
| student_id | name  | phone_number |
|------------|-------|--------------|
| 1          | Alice | 1234567      |
| 1          | Alice | 9876543      |

-- Or better: separate table
Student(student_id, name)
StudentPhone(student_id, phone_number)  -- FK to Student

Partial Dependency: Part of candidate key determines non-prime attribute

Example NOT in 2NF:
Enrollment(student_id, course_id, student_name, course_name, grade)
Candidate Key: {student_id, course_id}

FDs:
student_id → student_name        ← PARTIAL (violates 2NF)
course_id → course_name          ← PARTIAL (violates 2NF)
student_id, course_id → grade    ← OK (full dependency)

Decomposition to 2NF:
Student(student_id, student_name)
Course(course_id, course_name)
Enrollment(student_id, course_id, grade)

Transitive Dependency: X → Y → Z where Y is not a candidate key

Example NOT in 3NF:
Student(student_id, name, dept_id, dept_name)
Candidate Key: {student_id}

FDs:
student_id → dept_id     ← OK
dept_id → dept_name      ← TRANSITIVE (violates 3NF)
(student_id → dept_id → dept_name)

Decomposition to 3NF:
Student(student_id, name, dept_id)
Department(dept_id, dept_name)

BCNF is stricter than 3NF:
- 3NF: X is superkey OR A is prime
- BCNF: X MUST be superkey (no exception)

Example in 3NF but NOT in BCNF:
Teaches(student_id, subject, teacher)
Candidate Keys: {student_id, subject}

FDs:
student_id, subject → teacher    ← OK
teacher → subject                ← Violates BCNF (teacher not superkey)

But it's in 3NF because 'subject' is a prime attribute!

Decomposition to BCNF:
TeacherSubject(teacher, subject)
StudentTeacher(student_id, teacher)

# R(A, B, C)
# FDs: AB → C, C → B

# Candidate Keys: AB, AC

# Check 3NF:
# AB → C: AB is superkey
# C → B: C not superkey, but B is prime
# Result: In 3NF

# Check BCNF:
# AB → C: AB is superkey
# C → B: C is NOT superkey
# Result: NOT in BCNF

# BCNF Decomposition:
# R1(C, B)  - from C → B
# R2(A, C)  - remaining

R decomposed into R1 and R2 is lossless if:
R1 ∩ R2 → R1  OR  R1 ∩ R2 → R2

In other words: Common attributes must be a key in at least one table.

Example:
R(A, B, C) with A → B
Decompose to: R1(A, B), R2(A, C)
Common: A
A → B means A is key of R1
Lossless!

FDs are preserved if:
Union of FDs in each sub-relation = Original FDs (or covers them)

Sometimes BCNF decomposition loses dependency preservation!

Example:
R(A, B, C) with FDs: AB → C, C → B
BCNF decomposition: R1(C, B), R2(A, C)
FD AB → C cannot be verified from R1 or R2 alone!

Multi-valued Dependency: X →→ Y
"X multi-determines Y independently of other attributes"

Example NOT in 4NF:
Employee(emp_id, skill, hobby)
emp_id →→ skill (employee has many skills)
emp_id →→ hobby (employee has many hobbies)

These are independent! Creates redundancy:
| emp_id | skill  | hobby     |
|--------|--------|-----------|
| 1      | Java   | Reading   |
| 1      | Java   | Chess     |
| 1      | Python | Reading   |
| 1      | Python | Chess     |

4NF Decomposition:
EmpSkill(emp_id, skill)
EmpHobby(emp_id, hobby)