Normalization

Question 1

What is normalization in relational schemas?

Answer 1

A process to eliminate redundancies and anomalies by decomposing schemas into smaller, well-structured relations

Question 2

Main types of anomalies in relational schemas

Answer 2

1. Redundancy
2. Update Anomaly
3. Deleyion anomaly
4. Insertion anomaly

Question 3

Functional dependency (FD)

Answer 3

Constraint where one attribute uniquely determines another

EmployeeID —> Salary

Question 4

Candidate Key

Answer 4

Minimal set of attributes that uniquely identifies a tuple (row) in a relation (table)

EMPLOYEE(EmployeeID, Name, Department)

EmployeeID is a candidate key because it uniquely identifies employees.

Question 5

Transitive Dependency

Answer 5

Non-prime attribute depends on another non-prime attribute indirectly through a candiate key

EmployeeID depends on Department, Department depends on manager, manager is transitively dependent on EmployeeID

Question 6

1NF

Answer 6

A relation is in 1NF is all attributes contain atomic values (No nested or multivalued attributes)

NO: City: Boston, Cambridge

Question 7

2NF

Answer 7

A relation is in 2NF if it is in 1NF and has no non-prime attribute partially dependent on a candidate key

Remove partial dependencies from attributes

If we have StudentID, StudentName, CourseID, CourseName, and Grade:

Remove:
StudentName and CourseName

2NF:
StudentID, CourseID and Grade because

• StudentName is non-prime
• CourseName is non-prime

And they are both depend partially on the composite key (one of the keys in the composite key group)

Question 8

3NF

Answer 8

A relation is in 3NF if it is in 2NF and has no transitive dependency of non-prime attributes on any candidate key

Remove transitive dependencies from attributes

EmployeeID, Name, DepartmentID, DepartmentName

DepartmentName depends on EmployeeID indirectly

Solution

Remove DepartName

EmployeeID, Name DepartmentID

this is why we only see what is absolutely necessary to identify

Question 9

How do you normalize a relation with multivalued attributes (1NF violation)

Answer 9

Split multivalued attribute into a separate relation (table) with a foreign key referencing the original relation

Question 10

How do you resolve partial dependencies (2NF violation)

Answer 10

Move attributes that depend only on part of a composite key into a separate relation

Question 11

How do you handle transitive dependencies (3NF violation)

Answer 11

Move attributes with transitive dependencies into separate relations

Question 12

Normalize EMPLOYEES(EmployeeID, Name, Salary, Department)

Answer 12

• EMP_SALARY(EmployeeID, Salary)
• EMP_DEPARTMENT(EmployeeID, Department)

Question 13

Normalize BOOKS relation with FDs:
(Title → Author, Genre and Title, Copy → Shelf)

Answer 13

Split into:
* BOOKS(Title, Author, Genre)
* COPIES(Title, Copy, Shelf)

Question 14

Lossless Decomposition

Answer 14

Original table can be reconstructed by joining the smaller tables w/out loss of data

Question 15

What is FD preservation in decomposition?

Answer 15

Ensuring all functional dependencies in the original schema are maintained in the decomposed schema

Question 16

What is a trivial FD?

Answer 16

An FD where the right-hand side is a subset of the left-hand side

EmployeeID, Name –> Name

Question 17

HOw do decomposition algorithms work?

Answer 17

Create relations for each FD group with the same determinant and ensure lossless joins and FD preservation