Relational Schema Normalization (3NF & BCNF)

The "Why": Data Anomalies and Redundancy

Before diving into the "how," let's understand why normalization is necessary. Consider a poorly designed relation that stores student, course, and instructor information together:

Student_Course_Faculty(StudentID, StudentName, CourseID, CourseName, InstructorID, InstructorName)

What's wrong with this design?

• Update Anomaly: If Instructor Smith changes their name, we must find every single record of every student taught by Smith and update it. If we miss even one, the data becomes inconsistent.
• Insertion Anomaly: We cannot add a new course, say "CS402: Quantum Computing," until at least one student enrolls in it. The schema forces us to have a StudentID to create a record.
• Deletion Anomaly: If the only student enrolled in a particular course, say "EE101," drops it, their record might be the only one containing information about that course. Deleting the student record could erase the fact that "EE101" ever existed.

These problems all stem from data redundancy. The StudentName is repeated for every course a student takes, and the InstructorName is repeated for every student in their class. Normalization is the process of decomposing such relations to eliminate these anomalies. The tool we use to formalize this process is the functional dependency.

Part 1: Functional Dependencies and Armstrong's Axioms

A Functional Dependency (FD) is a constraint between two sets of attributes in a relation. For a relation R, an FD $X\to Y$ specifies that the values of the attribute set $X$ uniquely determine the values of the attribute set $Y$.

• Example: In a Students table, we would have StudentID $\to$ StudentName. This means for any given StudentID, there can only be one corresponding StudentName.

Often, a given set of FDs implies other FDs. To find all implied dependencies, we use a set of inference rules called Armstrong's Axioms.

Attribute Closure

A critical skill for any normalization problem is finding the attribute closure of a set of attributes $X$, denoted as $X^{+}$. This is the set of all attributes that are functionally determined by $X$.

Algorithm to find $X^{+}$ given a set of FDs, F:

1. Initialize result = $X$.
2. Repeatedly scan through all FDs in F. For each FD $A\to B$ in F:
3. If all attributes in $A$ are present in result, then add all attributes in $B$ to result.
4. Repeat step 2 until no new attributes can be added to result in a full pass.

Example: Let R(A, B, C, D, E) and F = {A $\to$ BC, CD $\to$ E, B $\to$ D, E $\to$ A}. Let's find $(A{)}^{+}$.

• Start: result = {A}
• Using A $\to$ BC: result = {A, B, C}
• Using B $\to$ D: result = {A, B, C, D}
• Using CD $\to$ E: result = {A, B, C, D, E}
• All attributes of R are now in the closure. So, $(A{)}^{+}$ = {A, B, C, D, E}.

Part 2: Finding Candidate Keys

With the ability to compute attribute closure, we can now find the candidate keys of a relation. A candidate key is a minimal superkey. A superkey is a set of attributes whose closure is the set of all attributes in the relation. "Minimal" means no proper subset of the candidate key is also a superkey.

A Systematic Method for Finding Candidate Keys:

1. Identify Essential Attributes: Find all attributes that do not appear on the right-hand side (RHS) of any FD. These attributes must be part of every candidate key. Let's call this set Ess.
2. Compute Closure of Essentials: Calculate $(Ess{)}^{+}$. If this closure contains all attributes of the relation, then Ess is the one and only candidate key.
3. Iterate and Add: If $(Ess{)}^{+}$ is not all attributes, you must add attributes from the set of non-essential attributes to Ess and compute the closure of the new combination. Systematically try adding one attribute at a time, then two, and so on, until the closure contains all attributes.
4. Check Minimality: Any set you find whose closure is all attributes is a superkey. You must ensure it's minimal. If you found that $(X{)}^{+}$ is all attributes, check that for any attribute $A\in X$, $(X-\{A\}{)}^{+}$ is not all attributes.

This process is algorithmic and essential for GATE. You must be fast and accurate at it.

Part 3: Normal Forms - 3NF and BCNF

Now we arrive at the core of the lesson: checking the normal form of a relation. For GATE, you'll primarily be concerned with 2NF, 3NF, and BCNF.

First, let's define two terms based on the candidate keys you just found:

• Prime Attribute: An attribute that is part of any candidate key.
• Non-Prime Attribute: An attribute that is not part of any candidate key.

The Rules

A relation is in...

• Second Normal Form (2NF): If it is in 1NF and there are no partial dependencies. A partial dependency occurs when a non-prime attribute is functionally dependent on a proper subset of a candidate key. This is only a concern if a candidate key is composite (has more than one attribute).

• Third Normal Form (3NF): If for every non-trivial FD $X\to A$:

  1. $X$ is a superkey, OR
  2. $A$ is a prime attribute.

• Boyce-Codd Normal Form (BCNF): If for every non-trivial FD $X\to A$:

  1. $X$ must be a superkey.

Notice that BCNF is stricter than 3NF. Every relation in BCNF is also in 3NF, but the reverse is not always true. The "escape clause" for 3NF is when the RHS of a dependency is a prime attribute.

The following video is an excellent guide that walks through the entire process, from finding candidate keys to checking the normal form conditions.

Part 4: Lossless-Join and Dependency-Preserving Decomposition

When a relation is not in a desired normal form, we decompose it into smaller relations. A good decomposition must have two properties:

1. Lossless-Join Decomposition: Ensures that when you join the decomposed relations back together, you get the original relation perfectly, with no extra or missing rows. If a relation R is decomposed into R1 and R2, the join is lossless if and only if the attributes common to both relations form a superkey for at least one of them. That is, $(R1\cap R2)\to R1$ or $(R1\cap R2)\to R2$.

2. Dependency-Preserving Decomposition: Ensures that all original FDs can be enforced by checking constraints within the decomposed tables. If an FD $X\to Y$ is not preserved, you would need to join tables to check it, which is inefficient.

A Crucial Fact for GATE:

• It is always possible to decompose a schema into a set of relations that are in 3NF while preserving all dependencies and ensuring a lossless join.
• It is not always possible to do the same for BCNF. Sometimes, achieving BCNF requires sacrificing dependency preservation. This is a key theoretical difference between 3NF and BCNF.

Conclusion

In this lesson, we have built a powerful framework for designing high-quality database schemas. You now have the tools to analyze any given relation and its constraints, a skill that directly translates to marks in the GATE exam.

Here are your key takeaways:

• Functional Dependencies and Armstrong's Axioms are the formal tools for expressing and reasoning about data constraints.
• Attribute Closure is the fundamental operation used to find Candidate Keys.
• The process for determining the highest normal form is algorithmic:
  1. Find all Candidate Keys.
  2. Identify Prime attributes.
  3. For each non-trivial FD $X\to Y$, check if it violates the BCNF rule ($X$ is not a superkey).
  4. If it violates the BCNF rule, check if it also violates the 3NF rule ($X$ is not a superkey AND $Y$ is not prime).
• Every BCNF relation is in 3NF, but a 3NF relation may not be in BCNF.
• Decomposition into BCNF may not preserve all dependencies, whereas decomposition into 3NF always can.

In our next lesson, we will move from the logical design of our database to its physical implementation. We'll explore how data is actually stored and organized on disk, and how critical data structures like B+ Trees are used to create indexes that make querying our well-normalized tables incredibly fast.