DBMS Part 2: Database Design - E-R Diagrams & Normalization

1. E-R Diagram Components
2. Cardinality Ratios
3. Participation Constraints
4. Specialization & Generalization
5. Weak Entities
6. E-R to Relational Schema
7. Functional Dependencies
8. Closure & Candidate Keys
9. Normal Forms (1NF to BCNF)
10. Decomposition

1. E-R Diagram Components

Component	Symbol	Meaning	Example
Entity	Rectangle	Object/Thing	Student, Book
Attribute	Oval	Property	name, age, email
Relationship	Diamond	Connection	enrolls, manages
Primary Key	Underlined	Unique identifier	student_id
Multivalued	Double oval	Multiple values	phone_numbers
Derived	Dashed oval	Calculated	age (from DOB)
Composite	Nested ovals	Made of sub-parts	address (street, city)
Weak Entity	Double rectangle	Depends on another	Dependent

2. Cardinality Ratios

1:1 (One-to-One)

Each A with one B

Person → Passport

One person has one passport

1:N (One-to-Many)

One A with many B

Department → Employees

One dept has many employees

N:1 (Many-to-One)

Many A with one B

Students → Department

Many students in one dept

M:N (Many-to-Many)

Many A with many B

Students ↔ Courses

Students take many courses, courses have many students

3. Participation Constraints

Total Participation

Double line (══)

Every entity MUST participate

Example: Every student MUST enroll in at least one course

Partial Participation

Single line (─)

Entity MAY or may not participate

Example: Student MAY issue books (optional)

4. Specialization & Generalization

Hierarchy Example

        Member
          |
    ┌─────┴─────┐
    |           |
  Coach      Player
               |
          ┌────┴────┐
          |         |
      Batsman   Bowler

Disjoint (d)

Entity can be ONLY ONE subtype

Member is either Coach OR Player

Symbol: Circle with d

Overlapping (o)

Entity can be MULTIPLE subtypes

Player can be Batsman AND/OR Bowler

Symbol: Circle with o

5. Weak Entities

Definition

An entity that depends on another entity (strong entity) for its existence. Cannot be uniquely identified by its own attributes alone.

Structure

Strong Entity ═══[Identifying Relationship]═══ Weak Entity
     ║                                            ║
  Primary Key                            Partial Key (dashed)

Strong Entity
    ║
Primary Key
    ║
    ═══[Relationship]═══
                       ║
                  Weak Entity
                       ║
                Partial Key

Example

Strong Entity: Employee (emp_id, name)

Weak Entity: Dependent (name, age)

'name' alone is not unique

Combined Key: (emp_id, name) uniquely identifies dependent

6. E-R to Relational Schema Conversion

Rule 1: Strong Entity → Table

E-R Diagram

Entity: Student(sid, name, age)

Relational Schema

Student(sid, name, age)

Rule 2: Weak Entity → Table with Parent's Key

E-R Diagram

Strong: Employee(emp_id, name)
Weak: Dependent(name, age)

Relational Schema

Employee(emp_id, name)
Dependent(emp_id, name, age)
FK: emp_id → Employee

Rule 3: Multivalued Attribute → Separate Table

E-R Diagram

Student(sid, name, { phone })

Relational Schema

Student(sid, name)
Student_Phone(sid, phone)
FK: sid → Student

Rule 4: Composite Attribute → Flatten

E-R Diagram

Student(sid, name, address{street, city, zip})

Relational Schema

Student(sid, name, street, city, zip)

Rule 5: 1:1 Relationship

Add foreign key to either side

Person(pid, name)
Passport(passport_no, issue_date, pid)
FK: pid → Person

Rule 6: 1:N Relationship

Add foreign key on "many" side

Department(dept_id, dept_name)
Employee(emp_id, name, dept_id)
FK: dept_id → Department

Rule 7: M:N Relationship → Separate Table

Student(sid, name)
Course(cid, cname)
Enrolls(sid, cid, grade)
FK: sid → Student, cid → Course

7. Functional Dependencies

Notation

A → B

Read as: "A functionally determines B"
Meaning: For each value of A, there is exactly one value of B

Armstrong's Axioms

Axiom	Rule	Example
Reflexivity	If β ⊆ α, then α → β	AB → A, AB → B
Augmentation	If α → β, then γα → γβ	If A → B, then AC → BC
Transitivity	If α → β and β → γ, then α → γ	If A → B and B → C, then A → C

Additional Derived Rules

Union: If α → β and α → γ, then α → βγ
Decomposition: If α → βγ, then α → β and α → γ

8. Closure & Candidate Keys

Closure Algorithm (α⁺)

1. Start with result = α
2. For each FD X → Y in F:
   - If X ⊆ result, add Y to result
3. Repeat until no change
4. Return result

Example: Computing Closure

Given:

F = {A → B, B → C, C → D}

Find: A⁺

Step 1: A⁺ = {A}

Step 2: A → B, so A⁺ = {A, B}

Step 3: B → C, so A⁺ = {A, B, C}

Step 4: C → D, so A⁺ = {A, B, C, D}

Answer: A⁺ = {A, B, C, D}

Finding Candidate Keys

Step 1: Find attributes that never appear on RHS → Must be in every key

Step 2: Compute closure of these attributes

Step 3: If closure = all attributes → It's a candidate key

Step 4: Try combinations with other attributes

9. Normal Forms (1NF to BCNF)

Normal Form	Requirement	Violations
1NF	Atomic values only	Multi-valued or composite attributes
2NF	1NF + No partial dependency	Non-prime depends on part of key
3NF	2NF + No transitive dependency	Non-prime → Non-prime
BCNF	3NF + LHS of every FD is superkey	Prime → Prime where LHS not superkey

First Normal Form (1NF)

All attributes must contain only atomic (indivisible) values

Violations

Student(sid, name, {phones})
Student(sid, name, address(street,city))

✅ Atomic

Student(sid, name, phone)
Student(sid, name, street, city)

Second Normal Form (2NF)

1NF + No partial dependency (non-prime attribute depends on part of candidate key)

Example:

R(A, B, C, D)
Candidate Key: AB
F = {AB → CD, B → D}
B → D is partial dependency  Not 2NF

Fix: Decompose

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

Third Normal Form (3NF)

2NF + No transitive dependency (non-prime → non-prime)

Example:

R(A, B, C, D)
Candidate Key: A
F = {A → B, B → C, C → D}
B → C and C → D are transitive  Not 3NF

Fix: Decompose

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

Boyce-Codd Normal Form (BCNF)

For every FD α → β, either trivial OR α is a superkey

Example:

R(A, B, C, D, E)
Candidate Keys: AB, DE
F = {AB → CDE, D → A, E → B}
D → A: D not superkey, but A is prime ✅ 3NF
D → A: D not superkey  Not BCNF

💡 Key Difference

3NF allows prime attributes on RHS even if LHS not superkey. BCNF does NOT allow this.

10. Decomposition

Lossless Decomposition

Can reconstruct original relation without losing information

Test:

R → R1, R2 is lossless if:
R1 ∩ R2 → R1  OR
R1 ∩ R2 → R2

Lossy Decomposition

Cannot reconstruct original relation accurately

Test:

R1 ∩ R2 does not functionally
determine either R1 or R2
→ Lossy

Example: Testing Decomposition

R(A, B, C)
F = {A → B, B → C}
Decompose: R1(A, B), R2(B, C)

Test:

R1 ∩ R2 = B
B → C holds
B determines R2 ✅
→ Lossless decomposition

Quick Tips

✓ Single attribute key → Automatically 2NF

✓ All BCNF relations are in 3NF

✓ Prime attribute = Part of ANY candidate key

✓ Weak entity always includes parent's key

✓ M:N relationships need separate table

✓ Compute closure to find candidate keys

Practice Problems

Problem 1: Find closure of AB given F = {AB → C, C → D, D → E}

Show Solution

Step 1: (AB)⁺ = {A, B}
Step 2: AB → C, so (AB)⁺ = {A, B, C}
Step 3: C → D, so (AB)⁺ = {A, B, C, D}
Step 4: D → E, so (AB)⁺ = {A, B, C, D, E}

Answer: (AB)⁺ = {A, B, C, D, E}

Problem 2: What is the highest normal form? R(A,B,C,D), Key: AB, F = {AB → D, B → C}

Show Solution

Analysis:
- Candidate Key: AB
- Prime: A, B
- Non-prime: C, D

Check 2NF:
B → C is partial dependency (B is part of key AB, C is non-prime)
 Not in 2NF (so not in 3NF or BCNF either)

Answer: 1NF only

Problem 3: Convert E-R to schema: Student(sid, name, {phones})

Show Solution

Multivalued attribute needs separate table:

Student(sid, name)
  Primary Key: sid

Student_Phone(sid, phone)
  Primary Key: (sid, phone)
  Foreign Key: sid → Student

Problem 4: Is decomposition R(A,B,C) → R1(A,B), R2(A,C) lossless? Given: A → B

Show Solution

Test:
R1 ∩ R2 = A
Check if A → R1 or A → R2

Given: A → B
A determines R1(A,B) ✅

Answer: Lossless decomposition

Normal Form Decision Tree

START
  │
  ├─ All values atomic? ──NO→  Not 1NF
  │         YES
  │
  ├─ Single attribute key? ──YES→ ✅ Skip to 3NF check
  │         NO
  │
  ├─ Partial dependency exists?
  │   ├─ YES →  Not 2NF (Stop)
  │   └─ NO → ✅ In 2NF
  │
  ├─ Transitive dependency exists?
  │   ├─ YES →  Not 3NF (Stop)
  │   └─ NO → Check each FD α→β:
  │            - α not superkey AND
  │            - β not prime?
  │       ├─ YES →  Not 3NF (Stop)
  │       └─ NO → ✅ In 3NF
  │
  └─ Every FD has LHS = superkey?
      ├─ YES → ✅ In BCNF
      └─ NO →  Not BCNF (but in 3NF)

⚠ Common Mistakes

Mistake 1: Thinking 3NF = BCNF

3NF allows prime → prime where LHS not superkey. BCNF does NOT.

Mistake 2: Wrong decomposition test

Test R1 ∪ R2 = R? (Always true!) Correct: R1 ∩ R2 → R1 or R2?

Mistake 3: Missing candidate keys

Don't stop at first key! Check all attribute combinations systematically.

Mistake 4: Confusing partial and transitive

Partial = depends on PART of key. Transitive = non-prime → non-prime.

Mistake 5: Forgetting foreign keys in weak entity

Weak entity MUST include parent's primary key as foreign key.

Continue Learning

You've mastezinc database design! Next, explore application development and storage management.

Previous: Part 1 Next: Part 3 - Application & Storage

Database Design

Contents

1. E-R Diagram Components

2. Cardinality Ratios

1:1 (One-to-One)

1:N (One-to-Many)

N:1 (Many-to-One)

M:N (Many-to-Many)

3. Participation Constraints

Total Participation

Partial Participation

4. Specialization & Generalization

Hierarchy Example

Disjoint (d)

Overlapping (o)

5. Weak Entities

Definition

Structure

Example

6. E-R to Relational Schema Conversion

Rule 1: Strong Entity → Table

Rule 2: Weak Entity → Table with Parent's Key

Rule 3: Multivalued Attribute → Separate Table

Rule 4: Composite Attribute → Flatten

Rule 5: 1:1 Relationship

Rule 6: 1:N Relationship

Rule 7: M:N Relationship → Separate Table

7. Functional Dependencies

Notation

Armstrong's Axioms

Additional Derived Rules

8. Closure & Candidate Keys

Closure Algorithm (α⁺)

Example: Computing Closure

Finding Candidate Keys

9. Normal Forms (1NF to BCNF)

First Normal Form (1NF)

Second Normal Form (2NF)

Third Normal Form (3NF)

Boyce-Codd Normal Form (BCNF)

10. Decomposition

Lossless Decomposition

Lossy Decomposition

Example: Testing Decomposition

Quick Tips

Practice Problems

Normal Form Decision Tree

⚠ Common Mistakes

Continue Learning