Concept of Normalization

1. Trivial and Non-Trivial Functional Dependencies

Definition of Functional Dependency

A functional dependency $X \rightarrow Y$ exists when the value of attribute $X$ determines the value of attribute $Y$.

• Trivial Dependency:
  A dependency $X \rightarrow Y$ is trivial if $Y$ is a subset of $X$.
  Example:
  Consider a relation $R(A, B)$:

  • $A, B \rightarrow A$ is trivial because $A$ is already part of the left-hand side.

• Non-Trivial Dependency:
  A dependency $X \rightarrow Y$ is non-trivial if $Y$ is not a subset of $X$.
  Example:
  In a relation $R(A, B)$, $A \rightarrow B$ is non-trivial because $B$ is not part of $A$.

Significance:

Trivial dependencies do not provide new information, whereas non-trivial dependencies are critical for normalization and reducing redundancy.

---

2. Non-Loss Decomposition and Functional Dependencies

Non-Loss Decomposition

A decomposition is non-loss if the original relation can be reconstructed using the natural join of its decomposed relations without losing data.

Condition for Non-Loss Decomposition:

• At least one of the intersecting attributes should be a superkey in one of the relations.

Example:
Relation $R(A, B, C)$ with $A \rightarrow B$:

1. Decompose into $R1(A, B)$ and $R2(A, C)$.
2. Join $R1$ and $R2$ on $A$ to reconstruct the original relation.

---

3. First, Second, and Third Normal Forms (1NF, 2NF, 3NF)

First Normal Form (1NF)

A relation is in 1NF if all attributes have atomic values (indivisible).

Example:

Violation:
Subjects column contains multiple values.
Solution:

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and there are no partial dependencies.

• Partial Dependency: A non-prime attribute depends on part of a composite key.

Example:

$(StudentID, Course)$ is the composite key. If the student’s name depended only on StudentID, it violates 2NF.
Solution: Decompose into:

Third Normal Form (3NF)

A relation is in 3NF if it is in 2NF and has no transitive dependency.

• Transitive Dependency: A non-prime attribute depends on another non-prime attribute.

Example:

EmployeeID	DepartmentID	DepartmentName

Here, $DepartmentName$ depends on $DepartmentID$, which depends on $EmployeeID$, violating 3NF.
Solution: Decompose into two relations:

---

4. Dependency Preservation

Dependency preservation ensures that all functional dependencies hold in the decomposed relations.

Example:

Relation $R(A, B, C)$ with $A \rightarrow B$ and $B \rightarrow C$:

1. Decompose $R$ into $R1(A, B)$ and $R2(B, C)$.
2. Dependencies are preserved if each original dependency can be derived from the decomposed relations.

---

5. Boyce-Codd Normal Form (BCNF)

BCNF ensures that every determinant (attribute on the left of a dependency) is a superkey.

Example:

If $Course\to Instructo\mathrm{r,\; it\; violates\; BCNF\; because\; Course\; is\; not\; a\; superkey.}$Solution: Decompose into:

1. $R1(Course, Instructor)$
   
2. $R2(StudentID, Course)$
   

---

6. Multi-Valued Dependencies and Fourth Normal Form (4NF)

A relation is in 4NF if it is in BCNF and has no multi-valued dependencies.

Multi-Valued Dependency Example:

Here, Subject and Hobby are independent of each other but depend on StudentID.
Solution: Decompose into:

---

7. Join Dependencies and Fifth Normal Form (5NF)

A relation is in 5NF if it cannot be decomposed further while preserving dependencies.

Example:

Solution: Decompose into:

1. $R1(Project, Task)$
   
2. $R2(Task,Resource)$