Keys, Constraints, Functional Dependencies, and Normalization

Keys

Keys uniquely identify tuples and establish relationships between tables.

1. Super Key

• Any set of attributes that uniquely identifies a tuple
• Can have redundant attributes
• Example: {StudentID}, {StudentID, Name}, {StudentID, Email} are all super keys

2. Candidate Key

• Minimal super key (no redundant attributes)
• Multiple candidate keys possible
• Example: {StudentID}, {Email} both uniquely identify students

3. Primary Key

• Selected candidate key
• One per table
• Cannot be NULL
• Example: StudentID chosen as primary key

4. Foreign Key

• References primary key in another table
• Establishes relationships
• Can be NULL (unless specified NOT NULL)
• Enforces referential integrity

5. Composite Key

• Primary key with multiple attributes
• Used when single attribute insufficient
• Example: {StudentID, CourseID} in Enrollment table

6. Alternate Key

• Candidate keys not chosen as primary key
• Example: If StudentID is primary, Email is alternate key

Integrity Constraints

1. Domain Constraints

• Define valid values for attributes
• Data types, CHECK constraints
• Example: Age BETWEEN 18 AND 100

2. Entity Integrity

• Primary key cannot be NULL
• Ensures each entity uniquely identifiable
• Enforced automatically by PRIMARY KEY constraint

3. Referential Integrity

• Foreign key must reference existing primary key OR be NULL
• Maintains consistency across relationships
• CASCADE options handle dependent operations

Functional Dependencies (FDs)

Definition: X → Y means if two tuples agree on X, they must agree on Y

Example: StudentID → Name (StudentID determines Name)

Properties:

• Reflexive: If Y ⊆ X, then X → Y
• Transitive: If X → Y and Y → Z, then X → Z
• Does NOT hold: If X → Y, then Y → X (not symmetric)

Armstrong's Axioms

Three fundamental rules for deriving FDs:

1. Reflexivity: If Y ⊆ X, then X → Y
Example: {StudentID, Name} → StudentID

2. Augmentation: If X → Y, then XZ → YZ
Example: If StudentID → Name, then {StudentID, CourseID} → {Name, CourseID}

3. Transitivity: If X → Y and Y → Z, then X → Z
Example: StudentID → DeptID and DeptID → DeptName, so StudentID → DeptName

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

Normalization

Process of organizing data to minimize redundancy and avoid anomalies.

Anomalies:

Update Anomaly: Same data repeated, changing one instance leaves inconsistency
Insertion Anomaly: Cannot insert data without unrelated data
Deletion Anomaly: Deleting data unintentionally deletes other data

Normal Forms:

1NF (First Normal Form):

• All attributes contain atomic (indivisible) values
• No repeating groups or arrays
• Each cell contains single value

2NF (Second Normal Form):

• In 1NF
• No partial dependencies (non-prime attribute dependent on part of candidate key)
• Only applies to tables with composite keys

3NF (Third Normal Form):

• In 2NF
• No transitive dependencies (non-prime → non-prime)
• For every X → Y: Either X is superkey OR Y is prime attribute

BCNF (Boyce-Codd Normal Form):

• Stricter than 3NF
• For every X → Y: X must be superkey
• Eliminates all anomalies due to FDs

4NF (Fourth Normal Form):

• In BCNF
• No multivalued dependencies
• MVD: X →→ Y means X determines set of Y values independently

5NF (Fifth Normal Form / PJNF):

• In 4NF
• No join dependencies
• Cannot be decomposed further without loss

COMPREHENSIVE EXAMPLES

EXAMPLE 1: Finding Keys

R(A, B, C, D, E)
FDs: {A → B, BC → E, ED → A}

Find all candidate keys:

Method: Attribute Classification

• Left side only: C, D (must be in every key)
• Right side only: B, E (never in key)
• Both sides: A
• Neither: None

Start with {C, D}:
CD+ = {C, D}
Not a key (doesn't include all attributes)

Try adding A: ACD+

• A → B: ACD+ = {A, C, D, B}
• BC → E: ACD+ = {A, C, D, B, E}
• All attributes! ACD is a candidate key.

Try adding others systematically...
Result: Candidate keys = {ACD}

EXAMPLE 2: 1NF Conversion

Unnormalized:

OrderID	CustomerName	Items
1	John	Book, Pen, Notebook
2	Jane	Laptop

Problems:

• Items column contains multiple values (not atomic)
• Can't easily search for specific item
• Can't efficiently count items per order

1NF Solution:

OrderID	CustomerName	Item
1	John	Book
1	John	Pen
1	John	Notebook
2	Jane	Laptop

EXAMPLE 3: 2NF Conversion

Table in 1NF:

StudentCourse(StudentID, CourseID, StudentName, CourseName, Instructor, Grade)

Primary Key: {StudentID, CourseID}

FDs:

• StudentID → StudentName (partial dependency!)
• CourseID → CourseName (partial dependency!)
• CourseID → Instructor (partial dependency!)
• {StudentID, CourseID} → Grade

Anomalies:

• Update: Change student name requires updating all enrollment records
• Insert: Can't add student without enrolling in a course
• Delete: Drop last course, lose student information

2NF Solution:

Student(StudentID, StudentName)
Course(CourseID, CourseName, Instructor)
Enrollment(StudentID, CourseID, Grade)

Verification:

• No partial dependencies
• All non-prime attributes fully dependent on entire primary key

EXAMPLE 4: 3NF Conversion

Table in 2NF:

Employee(EmpID, DeptID, DeptName, DeptLocation, Salary)

Primary Key: EmpID

FDs:

• EmpID → DeptID
• EmpID → Salary
• DeptID → DeptName (transitive!)
• DeptID → DeptLocation (transitive!)

Transitive Path: EmpID → DeptID → DeptName

Anomalies:

• Update: Change department name in all employee records
• Insert: Can't add department without employees
• Delete: Remove last employee, lose department info

3NF Solution:

Employee(EmpID, DeptID, Salary)
Department(DeptID, DeptName, DeptLocation)

EXAMPLE 5: BCNF Conversion

Table in 3NF:

ClassSchedule(Classroom, Period, Course, Professor)

FDs:

• {Classroom, Period} → Course
• {Classroom, Period} → Professor
• {Professor, Course} → Classroom (assuming one prof teaches one course in one room)

Candidate Keys:

• {Classroom, Period}
• {Professor, Course, Period} (need Period to uniquely identify)

Actually, let's simplify:

Better Example:

R(StudentID, Major, Advisor)

FDs:

• StudentID → Major
• Major → Advisor (each major has one advisor)

Candidate Key: StudentID

Check BCNF:

• StudentID → Major: StudentID is superkey ✓
• Major → Advisor: Major is NOT superkey ✗

Violates BCNF!

BCNF Solution:

R1(Major, Advisor)
R2(StudentID, Major)

Verification:

• R1: Major → Advisor, Major is candidate key ✓
• R2: StudentID → Major, StudentID is candidate key ✓

Note: This might not preserve the FD StudentID → Advisor directly
To check: Join R1 and R2, derive StudentID → Advisor through Major

EXAMPLE 6: 4NF Conversion

Table with MVD:

ProfessorCourseTextbook(Professor, Course, Textbook)

Professor	Course	Textbook
Smith	DB	Book A
Smith	DB	Book B
Smith	AI	Book A
Smith	AI	Book B

MVDs:

• Professor →→ Course (Smith teaches {DB, AI})
• Professor →→ Textbook (Smith uses {Book A, Book B})

Problem: Every course-textbook combination created (cross product)

4NF Solution:

ProfessorCourse(Professor, Course)
ProfessorTextbook(Professor, Textbook)

Professor	Course
Smith	DB
Smith	AI

Professor	Textbook
Smith	Book A
Smith	Book B

EXAMPLE 7: 5NF Conversion

Relation:

SupplyPartProject(Supplier, Part, Project)

Business Rules:

1. Supplier supplies specific parts
2. Project uses specific parts
3. Supplier works on specific projects
4. If conditions 1, 2, 3 met → Supplier supplies Part to Project

Data:

Supplier	Part	Project
S1	P1	J1
S1	P2	J1
S2	P1	J2

Join Dependency: Can losslessly decompose into three binary relations

5NF Solution:

SupplierPart(Supplier, Part)
PartProject(Part, Project)
SupplierProject(Supplier, Project)

Verification:

JOIN these three:
SupplierPart ⋈ PartProject ⋈ SupplierProject = Original relation

EXAMPLE 8: Lossless vs Lossy Decomposition

Lossless Example:

R(A, B, C) with FD: A → B

Decompose: R1(A, B), R2(A, C)

Test:

• R1 ∩ R2 = {A}
• A → AB (attributes of R1) ✓
• Lossless!

Lossy Example:

R(A, B, C) with FD: A → B

Decompose: R1(A, B), R2(B, C)

Original Data:

A	B	C
a1	b1	c1
a2	b1	c2

R1:

A	B
a1	b1
a2	b1

R2:

B	C
b1	c1
b1	c2

Join R1 ⋈ R2:

A	B	C
a1	b1	c1
a1	b1	c2
a2	b1	c1
a2	b1	c2

Spurious tuples created! Lossy decomposition!

EXAMPLE 9: Dependency Preservation

R(A, B, C) with FDs: {A → B, B → C, A → C}

Decomposition 1:
R1(A, B), R2(B, C)

Check:

• A → B: In R1 ✓
• B → C: In R2 ✓
• A → C: Derivable (A → B in R1, B → C in R2, transitivity)
• Dependency preserved!

Decomposition 2:
R1(A, B), R2(A, C)

Check:

• A → B: In R1 ✓
• B → C: Cannot check without JOIN ✗
• NOT dependency preserved

EXAMPLE 10: Complete Normalization Workflow

Original Relation:

R(OrderID, OrderDate, CustomerID, CustomerName, CustomerCity, ProductID, ProductName, Quantity, UnitPrice)

Sample Data:

OrderID	OrderDate	CustomerID	CustomerName	CustomerCity	ProductID	ProductName	Qty	Price
1	2024-01-01	C1	Alice	NYC	P1	Laptop	2	1000
1	2024-01-01	C1	Alice	NYC	P2	Mouse	1	25
2	2024-01-02	C2	Bob	LA	P1	Laptop	1	1000

FDs:

• OrderID → OrderDate, CustomerID
• CustomerID → CustomerName, CustomerCity
• ProductID → ProductName, UnitPrice
• {OrderID, ProductID} → Quantity

Primary Key: {OrderID, ProductID}

Check 1NF: All atomic ✓

Check 2NF:

• CustomerID → CustomerName (partial dependency on OrderID part)
• CustomerID → CustomerCity (partial dependency)
• ProductID → ProductName (partial dependency)
• ProductID → UnitPrice (partial dependency)

Violates 2NF!

Convert to 2NF:

Order(OrderID, OrderDate, CustomerID)
Customer(CustomerID, CustomerName, CustomerCity)
Product(ProductID, ProductName, UnitPrice)
OrderDetail(OrderID, ProductID, Quantity)

Check 3NF:

In Order: OrderID → CustomerID → CustomerName (transitive!)

Violates 3NF! Customer info transitively dependent

Already fixed: Customer separated in 2NF conversion

Final Schema (3NF):

• Order(OrderID, OrderDate, CustomerID)
• Customer(CustomerID, CustomerName, CustomerCity)
• Product(ProductID, ProductName, UnitPrice)
• OrderDetail(OrderID, ProductID, Quantity)

Check BCNF:
All determinants are candidate keys ✓
In BCNF!

PRACTICAL DATABASE DESIGN

Design Workflow:

1. Requirements Analysis

   • Identify entities
   • Identify attributes
   • Identify relationships
   • Document business rules

2. Conceptual Design (ER Model)

   • Create ER diagram
   • Define entities and relationships
   • Identify keys

3. Logical Design (Relational Model)

   • Convert ER to tables
   • Define FDs
   • Normalize to 3NF/BCNF

4. Physical Design

   • Choose data types
   • Create indexes
   • Consider denormalization for performance

5. Implementation

   • CREATE TABLE statements
   • Add constraints
   • Create relationships

Real-World Considerations:

When to Denormalize:

• Read-heavy applications (more SELECTs than UPDATEs)
• Performance critical queries
• Data warehouse / reporting
• Calculated columns (storing aggregates)

Example:
Instead of joining Order and OrderDetail for total:
Add TotalAmount column to Order (updated by trigger)

When to Normalize:

• Write-heavy applications
• Data integrity critical (banking, medical)
• Frequent updates
• OLTP systems

Design Patterns:

1. Lookup Tables:

-- Instead of storing country names repeatedly
Country(CountryID, CountryName)
Customer(CustomerID, Name, CountryID)

2. Type Tables:

-- For categorization
ProductType(TypeID, TypeName)
Product(ProductID, ProductName, TypeID)

3. Audit Tables:

-- Track changes
EmployeeHistory(HistoryID, EmpID, OldSalary, NewSalary, ChangeDate)

4. Bridge Tables (Many-to-Many):

Student(StudentID, Name)
Course(CourseID, CourseName)
Enrollment(StudentID, CourseID, Grade)

Common Mistakes:

Mistake 1: Over-normalization
Bad: Separate table for every attribute
Good: Balance normalization with performance

Mistake 2: Under-normalization
Bad: All data in one table
Good: At least 3NF for OLTP

Mistake 3: Ignoring Business Rules
Bad: Generic schema ignoring domain
Good: Model specific business logic

Mistake 4: Poor Naming
Bad: Table1, Col1, FK1
Good: Employee, FirstName, DepartmentID

Mistake 5: Missing Constraints
Bad: No foreign keys, no checks
Good: Enforce referential integrity

Tools:

1. ER Diagram Tools:

   • MySQL Workbench
   • draw.io
   • ERDPlus
   • Lucidchart

2. Normalization Tools:

   • Paper and pencil (best for learning!)
   • Spreadsheet for FD analysis

3. SQL Tools:

   • MySQL Workbench
   • pgAdmin (PostgreSQL)
   • SQL Server Management Studio
   • DBeaver (multi-platform)

Performance Tips:

1. Index foreign keys for join performance
2. Index WHERE clause columns frequently queried
3. Composite indexes for multi-column queries
4. Avoid over-indexing (slows INSERT/UPDATE)
5. Analyze query plans to find bottlenecks

Documentation:

Always document:

• ER diagrams
• Table descriptions
• FDs and business rules
• Normalization decisions
• Denormalization rationale
• Index strategy

Industry Standards:

• OLTP (Banking, E-commerce): 3NF minimum, BCNF preferred
• OLAP (Data Warehouse): Star schema (denormalized for queries)
• Hybrid: 3NF for transaction tables, materialized views for reporting