Unit 7: Relational Database Design & Normalization

Introduction to Relational Database Design

The primary objective of relational database design is to group attributes into relations to minimize data redundancy and manage update, insertion, and deletion anomalies. Poorly designed databases often suffer from redundancy, which wastes storage space and leads to inconsistent data states.

Anomalies Caused by Redundancy

When a relation contains redundant data, three major anomalies occur:

1. Insertion Anomaly: Inability to insert certain data without introducing dummy or null values in unrelated attributes. For example, if a department's details are stored only alongside employee records, a new department cannot be added until at least one employee is assigned to it.
2. Deletion Anomaly: Unintentional loss of information due to the deletion of other data. For instance, deleting the last employee in a department deletes all details about that department.
3. Modification (Update) Anomaly: Changing data in one place but missing it in another, resulting in database inconsistency. For example, changing an employee's address in one row but leaving it unchanged in another row for the same department/employee combination.

---

Functional Dependencies (FDs)

A Functional Dependency is a constraint between two sets of attributes in a relation from a database. Let $R$ be a relation schema, and let $X$ and $Y$ be subsets of the attributes of $R$. A functional dependency, denoted by $X\to Y$ (read as "$X$ functionally determines $Y$"), specifies that for any two tuples $t_1$ and $t_2$ in any legal instance of $R$:

$$\text{If }{t}_1[X]=t_2[X],\text{ then }{t}_1[Y]=t_2[Y]$$

This means the values of the $X$ component uniquely determine the values of the $Y$ component.

Inference Rules for Functional Dependencies (Armstrong's Axioms)

Let $U$ be the universal set of attributes. Armstrong's axioms are a sound and complete set of inference rules used to infer all functional dependencies that are logically implied by a given set of functional dependencies $F$:

1. Reflexivity: If $Y\subseteq X$, then $X\to Y$.
2. Augmentation: If $X\to Y$, then $XZ\to YZ$ for any set of attributes $Z$.
3. Transitivity: If $X\to Y$ and $Y\to Z$, then $X\to Z$.

Using these three axioms, additional useful rules can be derived:

• Union: If $X\to Y$ and $X\to Z$, then $X\to YZ$.
• Decomposition: If $X\to YZ$, then $X\to Y$ and $X\to Z$.
• Pseudo-transitivity: If $X\to Y$ and $WY\to Z$, then $WX\to Z$.

Closure of a Set of Functional Dependencies ($F^{+}$)

The set of all functional dependencies that can be logically derived from a given set $F$ using Armstrong's axioms is called the closure of $F$, denoted as $F^{+}$.

Closure of a Set of Attributes ($X^{+}$)

Given a set of attributes $X$ and a set of functional dependencies $F$, the attribute closure of $X$ under $F$ (denoted as $X^{+}$) is the set of all attributes that can be functionally determined by $X$.

Algorithm to find $X^{+}$:

1. Set $X^{+}=X$.
2. Repeat until no more attributes can be added:
   • For each functional dependency $Y\to Z$ in $F$:
     • If $Y\subseteq X^{+}$, then set $X^{+}=X^{+}\cup Z$.

Example: Consider relation $R(A,B,C,D,E)$ with functional dependency set $F=\{A\to B,A\to C,CG\to H,B\to D,E\to A,E\to G\}$. Let us find the closure of attribute set $\{E{\}}^{+}$:

• Initial: $E^{+}=\{E\}$
• Using $E\to A$: $E^{+}=\{E,A\}$
• Using $E\to G$: $E^{+}=\{E,A,G\}$
• Using $A\to B$: $E^{+}=\{E,A,G,B\}$
• Using $A\to C$: $E^{+}=\{E,A,G,B,C\}$
• Using $B\to D$: $E^+ = $\{E,A,G,B,C,D\}$
• Using $CG\to H$ (since $C,G\in E^{+}$): $E^{+}=\{E,A,G,B,C,D,H\}$

Since $E^{+}$ contains all attributes of $R$, $\{E\}$ is a candidate key for $R$.

---

Decomposition of Relation Schemas

When a relation schema $R$ suffers from anomalies, it is broken down into a set of smaller relations $D=\{R_1,R_2,\dots ,R_n\}$ in a process called decomposition.

Desirable Properties of Decomposition

1. Lossless-Join Property: When relations in the decomposition are joined back together using natural joins, the original relation must be perfectly reconstructed without generating any spurious (extra, incorrect) tuples.
2. Dependency Preservation Property: Every functional dependency in the original set $F$ must be represented in at least one of the decomposed relations, or be derivable from the dependencies in the decomposed schemas.

---

Normalization

Normalization is the formal, step-by-step process of analyzing relational schemas based on their functional dependencies and primary keys to minimize redundancy and anomalies.

+-------------------------------------------------------+
| Unnormalized Form (UNF)                               |
+-------------------------------------------------------+
                           |
                           v
+-------------------------------------------------------+
| First Normal Form (1NF) - Atomic values               |
+-------------------------------------------------------+
                           |
                           v
+-------------------------------------------------------+
| Second Normal Form (2NF) - No partial dependency      |
+-------------------------------------------------------+
                           |
                           v
+-------------------------------------------------------+
| Third Normal Form (3NF) - No transitive dependency    |
+-------------------------------------------------------+
                           |
                           v
+-------------------------------------------------------+
| Boyce-Codd Normal Form (BCNF) - Every LHS is a key    |
+-------------------------------------------------------+

First Normal Form (1NF)

A relation is in 1NF if the domain of each attribute contains only atomic (indivisible) values, and the value in each cell of a relation is a single scalar value (no multi-valued or composite attributes).

Second Normal Form (2NF)

A relation is in 2NF if:

1. It is in 1NF.
2. Every non-prime attribute (an attribute not part of any candidate key) is fully functionally dependent on the primary key. This means there must be no partial dependency (no non-prime attribute depends on a proper subset of a composite candidate key).

Example: Consider relation $R(\underline{StudentID},\underline{CourseID},StudentName,CourseName,Grade)$.

• Primary Key: $\{\text{StudentID},\text{CourseID}\}$
• Partial Dependencies:
  • $\text{StudentID}\to \text{StudentName}$ (StudentName depends only on part of the key)
  • $\text{CourseID}\to \text{CourseName}$ (CourseName depends only on part of the key)
• Decomposition into 2NF:
  • $R_1(\underline{StudentID},StudentName)$
  • $R_2(\underline{CourseID},CourseName)$
  • $R_3(\underline{StudentID},\underline{CourseID},Grade)$

Third Normal Form (3NF)

A relation is in 3NF if:

1. It is in 2NF.
2. There is no transitive dependency for non-prime attributes. That is, for every non-trivial functional dependency $X\to Y$, at least one of the following conditions holds:
   • $X$ is a super key of the relation, OR
   • $Y$ is a prime attribute (each attribute in $Y$ is part of some candidate key).

Example: Consider relation $R(\underline{EmpID},EmpName,DeptID,DeptName,DeptLocation)$.

• Primary Key: $\{\text{EmpID}\}$
• Functional Dependencies:
  • $\text{EmpID}\to \text{EmpName, DeptID, DeptName, DeptLocation}$
  • $\text{DeptID}\to \text{DeptName, DeptLocation}$ (Transitive dependency: $\text{EmpID}\to \text{DeptID}\to \text{DeptName, DeptLocation}$)
• Decomposition into 3NF:
  • $R_1(\underline{EmpID},EmpName,DeptID)$
  • $R_2(\underline{DeptID},DeptName,DeptLocation)$

Boyce-Codd Normal Form (BCNF)

A relation is in BCNF if it is stricter than 3NF. A relation $R$ is in BCNF if for every non-trivial functional dependency $X\to Y$, $X$ must be a super key of $R$.

Every relation in BCNF is also in 3NF, but not every relation in 3NF is in BCNF. A 3NF relation fails BCNF if a prime attribute depends on a non-prime attribute, or if a non-prime attribute determines another non-prime attribute.

Example: Consider relation $R(\underline{StudentID},\underline{Course},Instructor)$ where a course can have multiple instructors, but a specific instructor teaches only one course.

• Candidate Keys: $\{\text{StudentID},\text{Course}\}$ and $\{\text{StudentID},\text{Instructor}\}$
• Functional Dependencies:
  • $\text{StudentID, Course}\to \text{Instructor}$
  • $\text{Instructor}\to \text{Course}$
• Here, $\text{Instructor}\to \text{Course}$ is a dependency where the left-hand side ($\text{Instructor}$) is not a super key. Thus, $R$ is not in BCNF.
• Decomposition into BCNF:
  • $R_1(\underline{Instructor},Course)$
  • $R_2(\underline{StudentID},Instructor)$

---

Comparison of Normal Forms

---

Exam Tip

Tribhuvan University (TU) board exams frequently test this unit with a numerical problem where you are given a relation with a set of functional dependencies, and asked to:

1. Find candidate keys using attribute closure.
2. Determine the highest normal form the relation satisfies.
3. Decompose the relation into 3NF or BCNF while checking for lossless-join and dependency preservation properties. Practice at least 5 numerical problems from past questions, as these carry full 8 to 10 marks.