Integrity Constraints and Normal Forms

Overview

In our study of the relational model, we have thus far focused on the structural aspects of a database, such as relations, attributes, and keys. We now advance to a more critical and formal examination of database design quality. A poorly designed database schema can lead to significant operational problems, including data redundancy and update anomalies, which compromise the integrity and consistency of the stored information. This chapter provides the theoretical framework necessary to identify and rectify such design flaws, ensuring the creation of robust and efficient database schemas.

The central goal of this chapter is to equip the student with the principles of normalization, a systematic process for refining a relational schema. To undertake this process, we first require a formal language for expressing constraints between attributes. This is the role of Functional Dependencies, which serve as the mathematical foundation upon which the entire theory of normalization is built. Subsequently, we will explore a hierarchy of Normal Forms—including First, Second, Third, and Boyce-Codd Normal Form (BCNF)—each of which imposes progressively stricter conditions on the schema to eliminate specific types of undesirable data dependencies. A thorough understanding of these concepts is indispensable, as questions related to identifying functional dependencies, determining candidate keys, and assessing the normal form of a relation are a perennial and significant component of the GATE examination.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|--------------------------|-----------------------------------------------|
| 1 | Functional Dependencies | Formalizing relationships between attributes in a relation. |
| 2 | Normal Forms | A systematic process for minimizing data redundancy. |

---

Learning Objectives

---

We now turn our attention to Functional Dependencies...
## Part 1: Functional Dependencies

Introduction

In the relational model of data, a functional dependency is a fundamental constraint between two sets of attributes in a relation. These constraints are derived from the semantics of the application domain and are crucial for maintaining data integrity. The concept of functional dependency generalizes the notion of a key, providing a powerful mechanism for analyzing and refining database schemas.

A thorough understanding of functional dependencies is paramount for database design, particularly for the process of normalization. By identifying and enforcing these dependencies, we can design relations that minimize data redundancy and avoid the update, insertion, and deletion anomalies that plague poorly designed databases. This chapter will lay the theoretical groundwork for functional dependencies, exploring their formal definition, the rules that govern their inference, and the computational procedures for working with them.

---

Key Concepts

#
## 1. Types of Functional Dependencies

Functional dependencies can be classified based on the relationship between the determinant and the dependent attributes. This classification is essential for tasks such as schema refinement and identifying redundant constraints.

Trivial Functional Dependencies

A functional dependency $X \rightarrow Y$ is considered trivial if the set of dependent attributes $Y$ is a subset of the determinant attributes $X$.

Trivial FDs hold for any relation by definition and provide no new information about the constraints of the application domain. For example, in a relation with attributes `(StudentID, StudentName)`, the FD `(StudentID, StudentName) -> StudentName` is trivial.

Non-Trivial Functional Dependencies

Conversely, an FD $X \rightarrow Y$ is non-trivial if at least one attribute in $Y$ is not in $X$.

A special case of non-trivial FDs are those that are completely non-trivial, where the determinant and dependent sets are disjoint.

Non-trivial FDs represent meaningful constraints that are essential for database design. For instance, `StudentID -> StudentName` is a non-trivial FD.

#
## 2. Armstrong's Axioms: The Rules of Inference

Given a set of functional dependencies $F$, we are often interested in other FDs that are logically implied by $F$. The set of all FDs implied by $F$ is called the closure of $F$, denoted $F^+$. Armstrong's Axioms provide a sound and complete set of inference rules for deriving all FDs in $F^+$.

Primary Rules (Axioms)

Reflexivity: If $Y \subseteq X$, then $X \rightarrow Y$.

This rule formally states that any set of attributes functionally determines any of its subsets. This is the basis for all trivial FDs.

Augmentation: If $X \rightarrow Y$, then $XZ \rightarrow YZ$ for any set of attributes $Z$.

This rule states that if $X$ determines $Y$, then adding the same set of attributes $Z$ to both the determinant and the dependent does not invalidate the dependency.

Transitivity: If $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$.

This is analogous to the transitive property in algebra and allows us to chain dependencies together.

Derived Rules

From the three primary axioms, we can derive several additional rules that are convenient for practical use.

Union Rule (or Additivity): If $X \rightarrow Y$ and $X \rightarrow Z$, then $X \rightarrow YZ$.

If a set of attributes $X$ can determine $Y$ and can also determine $Z$, it follows that it can determine their union, $YZ$.

Decomposition Rule (or Projectivity): If $X \rightarrow YZ$, then $X \rightarrow Y$ and $X \rightarrow Z$.

This is the reverse of the union rule. If $X$ determines a set of attributes, it also determines any subset of those attributes.

Pseudo-transitivity Rule: If $X \rightarrow Y$ and $WY \rightarrow Z$, then $WX \rightarrow Z$.

This rule is a useful generalization of transitivity. We augment $X \rightarrow Y$ with $W$ to get $WX \rightarrow WY$. Then, by transitivity with $WY \rightarrow Z$, we obtain $WX \rightarrow Z$.

These axioms are fundamental for all reasoning about functional dependencies, including checking for FD implication and finding candidate keys.

#
## 3. Attribute Closure

A central task in working with FDs is to determine the set of all attributes that are functionally determined by a given set of attributes $X$. This set is called the attribute closure of $X$ with respect to a set of FDs $F$, and we denote it as $X^+$.

The ability to compute the attribute closure is essential for many database design algorithms. For example, to check if an FD $X \rightarrow Y$ is implied by a set of FDs $F$, we simply compute $X^+$ with respect to $F$ and check if $Y \subseteq X^+$.

Algorithm for Computing Attribute Closure $X^+$

Initialize the result set: `closure = X`.

Repeatedly scan through all FDs in $F$. For each FD $W \rightarrow Z$ in $F$:

* If $W \subseteq$ `closure`, then add all attributes in $Z$ to `closure`.
* `closure = closure` $\cup$ $Z$.

Repeat step 2 until no new attributes can be added to `closure` in a full pass.

Worked Example:

Problem:
Consider a relation with attributes $R(A, B, C, D, E, F)$ and the following set of functional dependencies $F$:
$A \rightarrow B$
$BC \rightarrow D$
$E \rightarrow F$
$AD \rightarrow E$

Calculate the attribute closure of $\{A, C\}$, denoted as $(AC)^+$.

Solution:

Step 1: Initialize the closure set with the starting attributes.

Step 2: Scan the FDs. We look for dependencies where the determinant is a subset of the current closure.

The FD $A \rightarrow B$ has its determinant $\{A\} \subseteq \{A, C\}$. We add $B$ to the closure.

Step 3: Rescan the FDs with the updated closure.

The FD $BC \rightarrow D$ has its determinant $\{B, C\} \subseteq \{A, B, C\}$. We add $D$ to the closure.

Step 4: Rescan the FDs again.

The FD $AD \rightarrow E$ has its determinant $\{A, D\} \subseteq \{A, B, C, D\}$. We add $E$ to the closure.

Step 5: Final scan.

The FD $E \rightarrow F$ has its determinant $\{E\} \subseteq \{A, B, C, D, E\}$. We add $F$ to the closure.

Step 6: A subsequent scan adds no new attributes. The algorithm terminates.

Answer: The attribute closure $(AC)^+$ is $\{A, B, C, D, E, F\}$. Since the closure contains all attributes of the relation, we can also conclude that $\{A, C\}$ is a superkey for the relation $R$.

#
## 4. Application to Lossless-Join Decomposition

Functional dependencies are the primary tool for verifying one of the two crucial properties of a database decomposition: the lossless-join property. A decomposition is lossless if the natural join of the decomposed relations results in exactly the original relation, with no spurious tuples generated.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="NAT" question="A relation schema $R$ has 5 attributes $\{A, B, C, D, E\}$. A functional dependency $X \rightarrow Y$ is defined as 'partially non-trivial' if $X \cap Y = \emptyset$ and $|X|=2$ and $|Y|=1$. How many such partially non-trivial FDs are possible on $R$?" answer="60" hint="This is a combinatorial problem. First, choose 2 attributes for X. Then, from the remaining attributes, choose 1 for Y. The order of selection matters for sets X and Y, but not within the sets." solution="
Step 1: Calculate the number of ways to choose the determinant set $X$ with 2 attributes from the 5 available attributes.

Step 2: For each choice of $X$, there are $5 - 2 = 3$ attributes remaining. The dependent set $Y$ must be chosen from these remaining attributes, as $X$ and $Y$ must be disjoint. We need to choose 1 attribute for $Y$.

Step 3: The total number of such FDs is the product of the number of ways to choose $X$ and the number of ways to choose $Y$.

Wait, the hint says "The order of selection matters for sets X and Y". This implies that we are counting the FDs themselves, not just the pairs of sets. The calculation is correct as we are forming FDs $X \to Y$. Let me re-read the question carefully. Ah, the phrasing is slightly ambiguous, but the standard interpretation is as calculated. Let me double check my reasoning.
Choose 2 for X: C(5,2) = 10.
Remaining 3 attributes. Choose 1 for Y: C(3,1) = 3.
Total = 10 * 3 = 30.

Let me re-think.
Let the attributes be {1,2,3,4,5}.
Possible X sets: {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}. (10 sets)
If X = {1,2}, remaining attributes are {3,4,5}.
Possible Y sets: {3}, {4}, {5}. (3 sets)
This gives FDs: {1,2}->{3}, {1,2}->{4}, {1,2}->{5}.
For each of the 10 X sets, there are 3 choices for Y.
Total = 10 * 3 = 30.

Let me re-read the PYQ1. It says "total number of possible useful functional dependencies". The logic seems to be to count pairs of disjoint non-empty subsets (X, Y).
For a set of size n, the number of non-empty subsets is $2^n - 1$.
Let's re-solve PYQ1 with n=4.
Total attributes = 4.
Let's partition the 4 attributes into 3 groups: those in X, those in Y, and those in neither.
For each attribute, it can be in X, in Y, or in neither. So 3 choices.
Total ways to assign 4 attributes to 3 bins = $3^4 = 81$.
This counts cases where X or Y are empty.
Case 1: X is empty. Each attribute can be in Y or neither (2 choices). So $2^4$ ways.
Case 2: Y is empty. Each attribute can be in X or neither (2 choices). So $2^4$ ways.
Case 3: X and Y are empty. Each attribute is in 'neither' (1 choice). So $1^4$ ways.
By inclusion-exclusion, number of cases where X is not empty AND Y is not empty is:
Total - (X is empty) - (Y is empty) + (X and Y are empty)
= $3^4 - 2^4 - 2^4 + 1^4 = 81 - 16 - 16 + 1 = 50$.
So the answer to PYQ1 is 50.

Now, let's re-solve my own NAT question with this correct logic.
Relation schema R has 5 attributes.
FD $X \rightarrow Y$ is 'partially non-trivial' if $X \cap Y = \emptyset$ and $|X|=2$ and $|Y|=1$.
This is a direct combinatorial calculation, not the inclusion-exclusion one.
Number of ways to choose 2 attributes for X from 5: $\binom{5}{2} = 10$.
Number of ways to choose 1 attribute for Y from the remaining 3: $\binom{3}{1} = 3$.
Total number of such FDs = $10 \times 3 = 30$.

My original calculation seems correct for the question I wrote. The PYQ was more general. Let me make my NAT question more similar to the PYQ.

New NAT question:
A relation schema $R$ has 5 attributes. A functional dependency $F: X \rightarrow Y$ is considered 'valid for analysis' if $X$, $Y$ are non-empty disjoint subsets of the attributes of $R$. The total number of FDs valid for analysis is _____.

Solution for new NAT:
Total attributes $n=5$. For each attribute, it can be in $X$, in $Y$, or in neither.
Total assignments = $3^5 = 243$.
Cases where $X$ is empty = $2^5 = 32$.
Cases where $Y$ is empty = $2^5 = 32$.
Cases where both are empty = $1^5 = 1$.
Using principle of inclusion-exclusion, the number of cases where $X \neq \emptyset$ and $Y \neq \emptyset$ is:
$3^5 - 2^5 - 2^5 + 1^5 = 243 - 32 - 32 + 1 = 180$.
This is a better question. I will use this. Answer: 180.

I will go back to my original question, it's a good variation. The answer is 30. Let me write out the solution for it.

Solution:
Step 1: The problem requires us to count the number of possible functional dependencies $X \rightarrow Y$ on a set of 5 attributes, subject to three conditions: $X \cap Y = \emptyset$, $|X|=2$, and $|Y|=1$.

Step 2: First, we calculate the number of ways to choose the determinant set $X$. We must choose 2 distinct attributes from a set of 5. This is a combination problem.

Step 3: For each chosen set $X$, we must choose the dependent set $Y$. Since $X$ and $Y$ must be disjoint, the attributes for $Y$ must be chosen from the attributes not in $X$. The number of remaining attributes is $5 - |X| = 5 - 2 = 3$. We need to choose 1 attribute for $Y$ from these 3 remaining attributes.

Step 4: The total number of possible FDs is the product of the number of ways to choose $X$ and the number of ways to choose $Y$.

Result: 30
:::

:::question type="MSQ" question="Consider a relation with attributes $A, B, C, D, E$ and the set of functional dependencies $F = \{ AB \rightarrow C, C \rightarrow D, B \rightarrow E \}$. Which of the following functional dependencies can be inferred from $F$?" options=["$AB \rightarrow D$","$AB \rightarrow E$","$A \rightarrow D$","$B \rightarrow D$"] answer="A,B" hint="Use the attribute closure algorithm to check if the dependent attributes are part of the closure of the determinant attributes. Alternatively, use Armstrong's Axioms." solution="
Let's analyze each option by computing the closure of the determinant. The full set of attributes is $\{A, B, C, D, E\}$. The given FDs are $F = \{ AB \rightarrow C, C \rightarrow D, B \rightarrow E \}$.

Option A: $AB \rightarrow D$
We compute the closure of $\{A, B\}$.

$(AB)^+ = \{A, B\}$ (Initialization)

Using $AB \rightarrow C$, we get $(AB)^+ = \{A, B, C\}$

Using $C \rightarrow D$, we get $(AB)^+ = \{A, B, C, D\}$

Using $B \rightarrow E$, we get $(AB)^+ = \{A, B, C, D, E\}$

Since $D \in (AB)^+$, the dependency $AB \rightarrow D$ can be inferred. This option is correct.
(This can also be seen by transitivity: $AB \rightarrow C$ and $C \rightarrow D$ implies $AB \rightarrow D$).

Option B: $AB \rightarrow E$
From the closure calculation above, we found $(AB)^+ = \{A, B, C, D, E\}$.
Since $E \in (AB)^+$, the dependency $AB \rightarrow E$ can be inferred. This option is correct.
(This can be seen by decomposition from $AB \rightarrow CDE$, or by noticing that $B \subseteq AB$, and since $B \rightarrow E$, by augmentation we have $AB \rightarrow AE$, and by decomposition $AB \rightarrow E$).

Option C: $A \rightarrow D$
We compute the closure of $\{A\}$.

$(A)^+ = \{A\}$ (Initialization)

No FDs in $F$ can be applied, as none have a determinant that is a subset of $\{A\}$.
The closure is just $\{A\}$. Since $D \not\in (A)^+$, the dependency $A \rightarrow D$ cannot be inferred. This option is incorrect.

Option D: $B \rightarrow D$
We compute the closure of $\{B\}$.

$(B)^+ = \{B\}$ (Initialization)

Using $B \rightarrow E$, we get $(B)^+ = \{B, E\}$

No other FDs can be applied. The determinant of $AB \rightarrow C$ is $\{A,B\}$, which is not a subset of $\{B,E\}$. The determinant of $C \rightarrow D$ is $\{C\}$, which is not in $\{B,E\}$.
Since $D \not\in (B)^+$, the dependency $B \rightarrow D$ cannot be inferred. This option is incorrect.

Therefore, only options A and B can be inferred.
"
:::

:::question type="MCQ" question="Which of the following statements about functional dependencies is FALSE, according to Armstrong's Axioms?" options=["If $A \rightarrow B$ and $A \rightarrow C$, then $A \rightarrow BC$","If $AB \rightarrow C$, then $A \rightarrow C$ and $B \rightarrow C$","If $A \rightarrow B$ and $BC \rightarrow D$, then $AC \rightarrow D$","If $A \rightarrow B$, then $AC \rightarrow BC$"] answer="If $AB \rightarrow C$, then $A \rightarrow C$ and $B \rightarrow C$" hint="Test each rule against the primary and derived axioms. Pay close attention to rules involving composite determinants." solution="
Let's evaluate each option:

A) If $A \rightarrow B$ and $A \rightarrow C$, then $A \rightarrow BC$
This is the Union Rule, which is a valid derived rule from Armstrong's Axioms. So, this statement is TRUE.

B) If $AB \rightarrow C$, then $A \rightarrow C$ and $B \rightarrow C$
This statement suggests that we can decompose the determinant (left-hand side). This is not a valid inference rule. For example, in a relation `(CourseID, StudentID, Grade)`, the FD `(CourseID, StudentID) -> Grade` holds. However, `CourseID -> Grade` does not hold (a course has many grades), and `StudentID -> Grade` does not hold (a student has many grades). Therefore, this statement is FALSE.

C) If $A \rightarrow B$ and $BC \rightarrow D$, then $AC \rightarrow D$
This is the Pseudo-transitivity Rule.

We start with $A \rightarrow B$.

Augment both sides with $C$: $AC \rightarrow BC$.

We are given $BC \rightarrow D$.

By transitivity on $AC \rightarrow BC$ and $BC \rightarrow D$, we get $AC \rightarrow D$.

So, this statement is TRUE.

D) If $A \rightarrow B$, then $AC \rightarrow BC$
This is the Augmentation Rule, where we augment the given FD $A \rightarrow B$ with the attribute set $Z = \{C\}$. This is one of the primary axioms. So, this statement is TRUE.

The only false statement is B.
"
:::

:::question type="NAT" question="A relation $R(P, Q, R, S, T, U)$ has a set of functional dependencies $F = \{P \rightarrow QR, RS \rightarrow T, Q \rightarrow S, T \rightarrow U\}$. What is the total number of attributes in the candidate key $\{P\}$'s attribute closure, $(P)^+$?" answer="6" hint="Start with the attribute P and iteratively add attributes to the closure set by applying the given FDs until no more attributes can be added." solution="
Step 1: Initialize the attribute closure for $\{P\}$.

Step 2: Scan the FDs. The determinant of $P \rightarrow QR$ is $\{P\}$, which is a subset of our current closure. Add $Q$ and $R$ to the closure.

Step 3: Rescan the FDs with the updated closure $\{P, Q, R\}$.

• The determinant of $Q \rightarrow S$ is $\{Q\}$, which is a subset of the closure. Add $S$.

Step 4: Rescan the FDs with the updated closure $\{P, Q, R, S\}$.

• The determinant of $RS \rightarrow T$ is $\{R, S\}$, which is a subset of the closure. Add $T$.

Step 5: Rescan the FDs with the updated closure $\{P, Q, R, S, T\}$.

• The determinant of $T \rightarrow U$ is $\{T\}$, which is a subset of the closure. Add $U$.

Step 6: A final scan reveals no new attributes can be added. The closure contains all 6 attributes of the relation.

Result: The total number of attributes in $(P)^+$ is 6.
:::

---

Summary

---

What's Next?

---

---

Part 2: Normal Forms

Introduction

In the design of relational databases, our primary objective is to construct a schema that faithfully represents the real-world enterprise while minimizing data redundancy and avoiding anomalies during data manipulation (insertion, deletion, and updating). Normalization is the formal process of analyzing a relational schema based on its functional dependencies and primary keys to achieve these desirable properties. It is a systematic technique for decomposing relations with anomalies into smaller, well-structured relations that are less prone to inconsistencies.

We can conceptualize the normal forms as a hierarchy of increasingly strict conditions that a relation must satisfy. A relation in a higher normal form inherently satisfies all the conditions of the lower normal forms. For the GATE examination, a thorough understanding of the First Normal Form (1NF), Second Normal Form (2NF), Third Normal Form (3NF), and Boyce-Codd Normal Form (BCNF) is essential. These forms are defined based on the constraints imposed by the functional dependencies within the relation.

This chapter will present a rigorous treatment of these normal forms, beginning with the foundational concepts of keys and functional dependencies, and proceeding to the specific rules that define each form. We will also explore the critical properties of decompositions, namely the lossless-join property and dependency preservation, which are paramount when breaking a relation into smaller components.

---

Key Concepts

Before we delve into the specific normal forms, we must first establish a firm grasp of the underlying concepts: functional dependencies and keys. The entire theory of normalization is built upon these foundations.

#
## 1. Functional Dependencies and Keys

A functional dependency (FD), denoted as $X \to Y$, between two sets of attributes $X$ and $Y$ that are subsets of a relation schema $R$, specifies a constraint on the possible tuples that can form a relation instance $r$ of $R$. The constraint states that for any two tuples $t_1$ and $t_2$ in $r$ that have $t_1[X] = t_2[X]$, they must also have $t_1[Y] = t_2[Y]$.

• Superkey: A set of attributes $SK$ of a relation schema $R$ is a superkey of $R$ if the functional dependency $SK \to U$ holds, where $U$ is the set of all attributes in $R$.
• Candidate Key: A candidate key is a minimal superkey. That is, it is a superkey $K$ such that no proper subset of $K$ is also a superkey. A relation can have multiple candidate keys.
• Prime Attribute: An attribute that is a member of any candidate key is called a prime attribute.
• Non-Prime Attribute: An attribute that is not a member of any candidate key is called a non-prime attribute.

The ability to correctly identify all candidate keys for a given relation and a set of functional dependencies is the most critical prerequisite for solving problems on normal forms.

#
## 2. First Normal Form (1NF)

The First Normal Form imposes a very basic structural requirement on a relation.

Consider a relation `Employee(EID, Name, PhoneNumbers)`. If an employee can have multiple phone numbers stored in a single `PhoneNumbers` cell (e.g., "800-555-0100, 900-555-0199"), this relation violates 1NF. To conform to 1NF, we would typically decompose this into `Employee(EID, Name)` and `EmployeePhone(EID, PhoneNumber)`.

It is important to recognize what 1NF does not restrict. A relation in 1NF:

• Can have a multi-attribute (composite) key. For example, in `Enrolment(StudentID, CourseID, Grade)`, the key is $\{StudentID, CourseID\}$.


• Can have multiple candidate keys.


• Can have foreign keys.


• Cannot have composite or multi-valued attributes in the sense that a single cell holds a structured value (like a list or set).

#
## 3. Second Normal Form (2NF)

The Second Normal Form is concerned with dependencies on composite keys.

A partial dependency exists when a non-prime attribute is functionally dependent on a proper subset of a candidate key. If a relation's candidate keys are all single attributes, the relation is automatically in 2NF if it is in 1NF.

Worked Example:

Problem: Consider the relation $R(A, B, C, D)$ with the functional dependency set $F = \{AB \to C, B \to D\}$. The candidate key is $\{A, B\}$. Determine if the relation is in 2NF.

Solution:

Step 1: Identify keys and attribute types.
The only candidate key is $\{A, B\}$.
Prime attributes: $A, B$.
Non-prime attributes: $C, D$.

Step 2: Analyze the functional dependencies.
We examine the dependencies involving non-prime attributes.
The dependency is $B \to D$.

Step 3: Check for partial dependency.
The determinant of this FD is $\{B\}$, which is a proper subset of the candidate key $\{A, B\}$. The dependent attribute, $D$, is non-prime.
Thus, $B \to D$ is a partial dependency.

Answer: The relation $R$ is not in 2NF due to the presence of the partial dependency $B \to D$.

Illustration of Partial Dependency



Candidate Key

A

B



D
Non-Prime

B → D (Partial Dependency)

#
## 4. Third Normal Form (3NF)

The Third Normal Form addresses transitive dependencies.

A transitive dependency occurs when a non-prime attribute is functionally dependent on another non-prime attribute. Formally, if we have $A \to B$ and $B \to C$, where $A$ is a superkey (or part of one), $B$ is not a superkey, and $C$ is a non-prime attribute, then we have a transitive dependency. The 3NF definition elegantly handles this and other cases.

#
## 5. Boyce-Codd Normal Form (BCNF)

BCNF is a stricter version of 3NF. It eliminates the second condition of the 3NF definition, resulting in a simpler but more restrictive rule.

Every relation in BCNF is also in 3NF. However, a relation in 3NF is not necessarily in BCNF. This occurs when a non-trivial FD $X \to Y$ exists where $X$ is not a superkey, but all attributes in $Y$ are prime. This dependency would satisfy 3NF but violate BCNF.

---

Problem-Solving Strategies

To determine the highest normal form of a relation, we follow a systematic procedure. Let us consider a relation $R$ with a set of functional dependencies $F$.

Step 1: Find all Candidate Keys

• Compute the attribute closure for various subsets of attributes in $R$ to identify sets that determine all other attributes.


• Ensure that each identified candidate key is minimal.

Step 2: Identify Prime and Non-Prime Attributes

• A prime attribute is any attribute that is part of at least one candidate key.


• All other attributes are non-prime.

Step 3: Check for Boyce-Codd Normal Form (BCNF)

• For every non-trivial FD $X \to A$ in $F$ (it is often helpful to first find the minimal cover of F), check if $X$ is a superkey of $R$.


• If this condition holds for all FDs, the relation is in BCNF. If even one FD violates this, the relation is not in BCNF.

Step 4: If Not in BCNF, Check for Third Normal Form (3NF)

• Consider only the FDs $X \to A$ that violated the BCNF condition.


• For each such FD, check if the attribute $A$ on the right-hand side is a prime attribute.


• If for every violating FD, the RHS attribute is prime, the relation is in 3NF. If there is even one violating FD where the RHS is a non-prime attribute, the relation is not in 3NF.

Step 5: If Not in 3NF, Check for Second Normal Form (2NF)

• This step is relevant only if there is at least one candidate key that is composite (has more than one attribute).


• Consider the FDs $X \to A$ that violated the 3NF condition. The RHS ($A$) must be a non-prime attribute.


• Check if the determinant $X$ is a proper subset of any candidate key. If so, this constitutes a partial dependency.


• If any partial dependency exists, the relation is not in 2NF. Otherwise, it is in 2NF.

Worked Example:

Problem: Determine the highest normal form for the relation $R(A, B, C, D)$ with FDs $F = \{A \to B, BC \to D\}$.

Solution:

Step 1: Find Candidate Keys

• Let's compute attribute closures.


• $\{A\}^+ = \{A, B\}$


• $\{C\}^+ = \{C\}$


• $\{AC\}^+ = \{A, C, B, D\}$. This covers all attributes.


• Is $\{AC\}$ minimal? Yes, neither $\{A\}$ nor $\{C\}$ alone is a superkey.


• Thus, the only candidate key is $\{A, C\}$.

Step 2: Identify Prime/Non-Prime Attributes

• Candidate Key: $\{A, C\}$


• Prime Attributes: $A, C$


• Non-Prime Attributes: $B, D$

Step 3: Check for BCNF

• Consider $A \to B$. Is $\{A\}$ a superkey? No. The relation is not in BCNF.


• Consider $BC \to D$. Is $\{B, C\}$ a superkey? No. The relation is not in BCNF.

Step 4: Check for 3NF

• We examine the FDs that violated BCNF.


• For $A \to B$: The determinant $\{A\}$ is not a superkey. Is the RHS attribute, $B$, prime? No, $B$ is non-prime. This FD violates the 3NF conditions.


• Since we found a violation, we can stop.

Step 5: Check for 2NF

• The FD that violated 3NF is $A \to B$.


• The RHS, $B$, is a non-prime attribute.


• The determinant, $\{A\}$, is a proper subset of the candidate key $\{A, C\}$.


• Therefore, $A \to B$ is a partial dependency. The relation is not in 2NF.

Answer: The highest normal form of the relation $R$ is 1NF.

---

Properties of Decomposition

When we decompose a relation $R$ into a set of relations $\{R_1, R_2, \dots, R_k\}$, we must ensure the decomposition is of high quality. Two properties are paramount.

Dependency Preservation: A decomposition is dependency-preserving if the union of the functional dependencies that hold on the individual decomposed relations is equivalent to the original set of FDs. This means no functional dependency is lost in the process. 3NF decompositions can always be made lossless and dependency-preserving. BCNF decompositions are always lossless, but may not be dependency-preserving.

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider a relation schema $R(A, B, C, D, E)$ with functional dependencies $F = \{A \to B, BC \to D, D \to E\}$. What is the highest normal form of $R$?" options=["1NF","2NF","3NF","BCNF"] answer="2NF" hint="First, find the candidate key. Then, check for partial and transitive dependencies involving non-prime attributes." solution="
Step 1: Find the candidate key.
The attribute $A$ and $C$ are not on the RHS of any FD, so they must be part of any candidate key.
Let's compute the closure of $\{A, C\}$:
$\{A, C\}^+ = \{A, C, B, D, E\}$ (since $A \to B$, then we have $A, B, C$, so $BC \to D$, then we have $A, B, C, D$, so $D \to E$).
Thus, $\{A, C\}$ is the sole candidate key.

Step 2: Identify prime and non-prime attributes.
Prime attributes: $A, C$.
Non-prime attributes: $B, D, E$.

Step 3: Check for BCNF.

• $A \to B$: Is $\{A\}$ a superkey? No. Violation.

The relation is not in BCNF.

Step 4: Check for 3NF.

• Consider the violating FD $A \to B$. Is the RHS attribute, $B$, prime? No.

This FD violates 3NF.

• Consider $BC \to D$. Is $\{B, C\}$ a superkey? No. Is $D$ prime? No. Violation.


• Consider $D \to E$. Is $\{D\}$ a superkey? No. Is $E$ prime? No. Violation.

The relation is not in 3NF.

Step 5: Check for 2NF.

• The FD $A \to B$ is a partial dependency because a non-prime attribute ($B$) is dependent on a proper subset ($\{A\}$) of the candidate key $\{A, C\}$.


• The FDs $BC \to D$ and $D \to E$ do not represent partial dependencies. However, the dependency $D \to E$ (which can be derived from the FDs as $A,C \to D \to E$) represents a transitive dependency.


• The question is about the highest normal form. Since there is a partial dependency, the relation is not in 2NF. Let's re-evaluate.

Wait, my analysis of transitive dependency was premature. Let's stick to the definitions.

• We have a partial dependency $A \to B$. This means the relation is not in 2NF.


• Let's re-read the dependencies. $A \to B, BC \to D, D \to E$.


• $A \to B$: $A$ is a proper subset of CK $\{AC\}$. $B$ is non-prime. This is a partial dependency. Therefore, the relation is not in 2NF. The highest normal form is 1NF.

Let's re-check the solution. Perhaps I made a mistake.
CK is $\{AC\}$. Primes: A, C. Non-primes: B, D, E.
FDs:

$A \to B$: Partial dependency. Violates 2NF.

$BC \to D$: Not a partial dependency. $B$ is non-prime, $C$ is prime. The determinant is not a proper subset of a CK.

$D \to E$: Transitive dependency, since $AC \to D$ and $D \to E$, and $D$ is not a superkey and $E$ is non-prime. This violates 3NF.

Since there is a partial dependency ($A \to B$), the relation is not in 2NF. The highest normal form is 1NF.
Let me check the provided answer. It says 2NF. This implies my analysis of partial dependency is wrong in this context. Why?
Let's reconsider the definition of 2NF. No non-prime attribute should be partially dependent.

• $A \to B$: $B$ is non-prime, $A$ is a proper subset of CK. This is a clear partial dependency.

Is it possible the question has an error or I am missing a nuance? Let's check my CK calculation. $\{AC\}^+ = \{A,C\} \cup \{B\} \cup \{D\} \cup \{E\} = \{A,B,C,D,E\}$. Yes, CK is $\{AC\}$.
Let's assume the question meant $R(A, B, C, D, E)$ with FDs $F = \{AB \to C, C \to D, D \to E\}$.
Then CK is $\{AB\}$. Primes: A, B. Non-primes: C, D, E.
$C \to D$ and $D \to E$ are transitive. No partial dependencies. So highest normal form is 2NF.
Let's assume the original question is correct and the answer is 2NF. How could that be?
$R(A, B, C, D, E)$ with $F = \{A \to B, BC \to D, D \to E\}$. CK is $\{AC\}$.
Partial dependency: $A \to B$. This violates 2NF.
Transitive dependency: $AC \to D$ and $D \to E$. This violates 3NF.
The only way it could be in 2NF is if there are no partial dependencies. The FD $A \to B$ is a textbook partial dependency.
There seems to be a contradiction. I will create a new question that is unambiguous.

Revised Original Question:
:::question type="MCQ" question="Consider a relation schema $R(A, B, C, D)$ with functional dependencies $F = \{A \to C, C \to D, B \to C\}$. The candidate keys are $\{A, B\}$. What is the highest normal form of $R$?" options=["1NF","2NF","3NF","BCNF"] answer="2NF" hint="Check for partial dependencies on the candidate keys {A, B} and then check for transitive dependencies." solution="
Step 1: Identify keys and attributes.
The candidate keys are given as $\{A, B\}$.
Prime attributes: $A, B$.
Non-prime attributes: $C, D$.

Step 2: Check for BCNF.

• $A \to C$: Is $\{A\}$ a superkey? No.


• $B \to C$: Is $\{B\}$ a superkey? No.


• $C \to D$: Is $\{C\}$ a superkey? No.

The relation is not in BCNF.

Step 3: Check for 3NF.

• For $A \to C$, is $C$ prime? No. Violation.


• For $B \to C$, is $C$ prime? No. Violation.


• For $C \to D$, is $D$ prime? No. Violation.

The relation is not in 3NF.

Step 4: Check for 2NF.
We need to check for partial dependencies. A partial dependency exists if a non-prime attribute depends on a proper subset of a candidate key.

• The FD $A \to C$ shows that non-prime attribute $C$ depends on $\{A\}$, which is a proper subset of candidate key $\{A, B\}$. This is a partial dependency.


• The FD $B \to C$ shows that non-prime attribute $C$ depends on $\{B\}$, which is a proper subset of candidate key $\{A, B\}$. This is also a partial dependency.

Since partial dependencies exist, the relation is not in 2NF. The highest normal form is 1NF.

It seems I'm consistently finding 1NF for these cases. Let me construct a question that is in 2NF but not 3NF.
This happens when there are no partial dependencies, but there is a transitive dependency.
For no partial dependencies, all non-prime attributes must depend on the full candidate key.

Final Revised Original Question:
:::question type="MCQ" question="Consider a relation schema $R(P, Q, R, S)$ with functional dependencies $F = \{PQ \to R, R \to S\}$. The candidate key is $\{P, Q\}$. What is the highest normal form of $R$?" options=["1NF","2NF","3NF","BCNF"] answer="2NF" hint="Check for partial dependencies first. If there are none, check for transitive dependencies." solution="
Step 1: Identify keys and attributes.
The candidate key is $\{P, Q\}$.
Prime attributes: $P, Q$.
Non-prime attributes: $R, S$.

Step 2: Check for partial dependencies (for 2NF).
A partial dependency would be a non-prime attribute depending on just $\{P\}$ or just $\{Q\}$. The given FDs are $PQ \to R$ and $R \to S$. There are no FDs of the form $P \to \text{non-prime}$ or $Q \to \text{non-prime}$. Therefore, no partial dependencies exist. The relation is at least in 2NF.

Step 3: Check for transitive dependencies (for 3NF).
We have the chain of dependencies $PQ \to R$ and $R \to S$. Here, a non-prime attribute ($S$) is dependent on another non-prime attribute ($R$). This is a transitive dependency.
Formally, using the 3NF definition, consider the FD $R \to S$.

• Is $\{R\}$ a superkey? No.


• Is the RHS attribute, $S$, prime? No.

Both conditions for 3NF fail for the FD $R \to S$. Thus, the relation is not in 3NF.

Result:
The relation has no partial dependencies, so it is in 2NF. It has a transitive dependency, so it is not in 3NF. The highest normal form is 2NF.
"
:::

:::question type="NAT" question="A relation $R(A, B, C, D, E, F)$ has the following set of functional dependencies: $F = \{A \to BC, CD \to E, B \to D, E \to A, B \to F\}$. How many candidate keys does the relation $R$ have?" answer="2" hint="Identify attributes that must be part of a key (those not on the RHS). Then compute closures of combinations involving those attributes and others." solution="
Step 1: Analyze the attributes.
Attributes on RHS: A, B, C, D, E, F. All attributes appear on the RHS of some FD.
Attributes on LHS: A, B, C, D, E. Only F does not appear on the LHS.
This gives us no immediate clues, so we must compute closures.

Step 2: Compute attribute closures to find superkeys.
Let's try attributes that determine many others, like B.

• $\{B\}^+ = \{B, D, F\}$


• $\{E\}^+ = \{E, A, B, C, D, F\}$. This is a superkey. Is it minimal? Yes, since E is on the RHS of $CD \to E$. So $\{E\}$ is not a CK on its own.

Let's trace back how we got E. From $CD$. So let's try closures with C.

• $\{C\}^+ = \{C\}$.


• $\{BC\}^+ = \{B, C, D, F, E, A\} = R$. So $\{BC\}$ is a candidate key.


• $\{CD\}^+ = \{C, D, E, A, B, F\} = R$. So $\{CD\}$ is a candidate key.


• $\{AC\}^+ = \{A, C, B, D, F, E\} = R$. So $\{AC\}$ is a candidate key.

Wait, let's re-verify.
$E \to A$ and $A \to BC$. So $E \to ABC$.
$B \to D$. So $E \to ABCD$.
$CD \to E$. This is a cycle.
$B \to F$. So $E \to ABCDF$. All attributes.
So $\{E\}$ is a candidate key.

Let's check others that determine E.
$\{C, D\}$ determines E. So $\{C, D\}$ is a candidate key.
Are there any others?
$B \to D$. So we can substitute D with B in $\{C, D\}$. Let's check $\{B, C\}$.
$\{B, C\}^+ = \{B, C, D, F, E, A\}$. Yes, $\{B, C\}$ is a candidate key.
Can we find any others?
$A \to BC$.
$\{A\}^+ = \{A, B, C, D, F, E\}$. Yes, $\{A\}$ is a candidate key.
So far we have $\{E\}, \{C, D\}, \{B, C\}, \{A\}$.

Let me be more systematic.
$E \to A \to BC \to BDF$. So $E \to ABCDF$. $\{E\}$ is a CK.
$CD \to E$. Since E is a CK, $\{C, D\}$ is a superkey. Is it minimal? Yes, neither C nor D alone is a CK. So $\{C, D\}$ is a CK.

Let's re-examine $A$.
$A \to BC \to BDF$. So $A \to BCDF$.
From $A \to BC$, we have $C$. We need $D$ to get $E$. From $B \to D$, we have $D$. So $A \to CD$.
So $A \to CD \to E$. And since $E$ is a CK, $A$ is a superkey.
Is it minimal? Yes. So $\{A\}$ is a CK.

What about $B$?
$B \to D, B \to F$. $\{B\}^+ = \{B, D, F\}$. Not a CK.
What about $\{B, C\}$?
$\{B, C\}^+ = \{B, C, D, F\}$. Using $CD \to E$, we get $\{B, C, D, F, E\}$. Using $E \to A$, we get $\{B, C, D, F, E, A\}$.
So $\{B, C\}$ is a superkey. Is it minimal? Yes. $\{B, C\}$ is a CK.

We seem to have found four: $\{A\}, \{E\}, \{CD\}, \{BC\}$. Let me re-read the FDs.
$F = \{A \to BC, CD \to E, B \to D, E \to A, B \to F\}$.
Let's verify minimality.
Is any attribute in $\{CD\}$ redundant? $\{C\}^+ = \{C\}$, $\{D\}^+ = \{D\}$. No.
Is any attribute in $\{BC\}$ redundant? $\{B\}^+ = \{B,D,F\}$, $\{C\}^+ = \{C\}$. No.
So we have 4 CKs. The question asks for 2. There must be an error in my reasoning or the question's premise.

Let's re-start.
$F = \{A \to BC, CD \to E, B \to D, E \to A, B \to F\}$.
Notice $A \leftrightarrow E$.
$E \to A$ and from $A \to BC$ and $B \to D$ we get $A \to BCD$. $CD \to E$. So $A \to E$.
So $A$ and $E$ are equivalent. If one is a CK, the other must be.
$\{A\}^+ = \{A, B, C, D, F, E\}$. So $\{A\}$ is a CK.
$\{E\}^+ = \{E, A, B, C, D, F\}$. So $\{E\}$ is a CK.
That's two already.
Now, are there any others?
Consider $CD \to E$. Since $E$ is a CK, $CD$ is a superkey. Is it minimal? Yes. So $\{CD\}$ is a CK.
Consider $A \to BC$. What about $\{B,C\}$?
$\{B,C\}^+ = \{B,C,D,F\}$. Now we have $CD$, so $CD \to E$. So $\{B,C\}^+ = \{B,C,D,F,E\}$. Now we have $E$, so $E \to A$. So $\{B,C\}^+ = \{B,C,D,F,E,A\}$.
$\{BC\}$ is a superkey. Is it minimal? Yes. So $\{BC\}$ is a CK.
There are 4 candidate keys. The NAT question is flawed. I must create a new one.

Revised Original NAT Question:
:::question type="NAT" question="A relation $R(P, Q, R, S, T)$ has functional dependencies $F = \{P \to Q, RS \to T, Q \to R\}$. How many attributes are in the candidate key for R?" answer="2" hint="Find the essential attributes that are not determined by any others. Then compute the closure of that set." solution="
Step 1: Identify essential attributes.
Attributes on the RHS: Q, R, T.
Attributes not on the RHS: P, S.
Any candidate key must contain the attributes that cannot be determined from others. Therefore, any candidate key must contain $\{P, S\}$.

Step 2: Compute the closure of the essential attributes.
Let's find $\{P, S\}^+$:

• Start with $\{P, S\}$.


• From $P \to Q$, we get $\{P, S, Q\}$.


• From $Q \to R$, we get $\{P, S, Q, R\}$.


• Now we have $R$ and $S$, so from $RS \to T$, we get $\{P, S, Q, R, T\}$.

The closure $\{P, S\}^+$ contains all attributes of the relation $R$.

Step 3: Conclude the candidate key.
Since $\{P, S\}$ determines all other attributes and is minimal (as both P and S are essential), $\{P, S\}$ is the only candidate key.

Result:
The candidate key is $\{P, S\}$. The number of attributes in the candidate key is 2.
"
:::

:::question type="MSQ" question="A relation $R(A, B, C)$ with functional dependencies $F=\{AB \to C, C \to B\}$ is decomposed into $R_1(A, C)$ and $R_2(C, B)$. Which of the following statements is/are TRUE?" options=["The relation R is in 3NF","The decomposition is lossless","The decomposition is dependency preserving","The relation $R_2$ is in BCNF"] answer="The decomposition is lossless,The decomposition is dependency preserving,The relation $R_2$ is in BCNF" hint="First, find the candidate keys of R to determine its normal form. Then, check the properties of the decomposition using standard tests. Finally, find the CK of R2 to check its normal form." solution="
Statement 1: The relation R is in 3NF

• Candidate Keys of R:

- $\{A, B\}^+ = \{A, B, C\}$. So $\{A, B\}$ is a CK.
- $\{A, C\}^+ = \{A, C, B\}$. So $\{A, C\}$ is a CK.

• Prime Attributes: A, B, C. All attributes are prime.


• Check BCNF: Consider $C \to B$. Is $\{C\}$ a superkey? No. So R is not in BCNF.


• Check 3NF: For the violating FD $C \to B$, is the RHS attribute ($B$) prime? Yes. Therefore, this FD satisfies the second condition of 3NF. The other FD, $AB \to C$, satisfies the first condition as $\{A, B\}$ is a superkey. Thus, the relation R is in 3NF.


• Wait, the option says "The relation R is in 3NF". Let me re-read my analysis. Yes, it is in 3NF. I should select this. But let me check my answer key. Ah, the answer key does not include this. Why? Is there a mistake? Let's re-verify. CKs: {AB}, {AC}. Primes: A, B, C. FD: C -> B. C is not a superkey. B is a prime attribute. Yes, R is in 3NF. This is a classic case of a 3NF relation that is not BCNF. Let's assume the provided answer is correct and this option is false. This is confusing. Perhaps there is a nuance in the problem statement I am missing. Let's assume for a moment the option is false and proceed. This is a common issue with tricky GATE questions. Let's re-evaluate all options. Maybe I am misinterpreting something. Let's proceed with the other options first.

Let's re-evaluate the question and my analysis. The analysis that R is in 3NF seems correct by definition. Let's hold this thought.

Statement 2: The decomposition is lossless

• $R_1 = \{A, C\}$, $R_2 = \{C, B\}$.


• $R_1 \cap R_2 = \{C\}$.


• $R_1 - R_2 = \{A\}$.


• $R_2 - R_1 = \{B\}$.


• We need to check if $(R_1 \cap R_2) \to (R_1 - R_2)$ or $(R_1 \cap R_2) \to (R_2 - R_1)$ holds in R.


• This means we check if $C \to A$ or $C \to B$ holds in R.


• The FD $C \to B$ is given in F.


• Therefore, the decomposition is lossless. This statement is TRUE.

Statement 3: The decomposition is dependency preserving

• The original FDs are $\{AB \to C, C \to B\}$.


• On $R_1(A, C)$, the only possible FD is $A \to C$ or $C \to A$. Neither can be inferred from F.


• On $R_2(C, B)$, the FD $C \to B$ holds.


• We need to see if we can derive the original FDs from the FDs on the decomposed relations. We have $C \to B$. Can we derive $AB \to C$? We cannot derive it from just $C \to B$. So it is not dependency preserving.


• Let me rethink. The dependencies on the decomposed tables are projections of F.


• For $R_1(A,C)$, what FDs hold? $\{A,C\}^+_{F} = \{A,C,B\}$. This closure does not give any FDs on $R_1$.


• For $R_2(C,B)$, what FDs hold? $C \to B$ is a given FD, so it holds on $R_2$.


• The union of FDs on decomposed relations is $F' = \{C \to B\}$.


• Is $F'$ equivalent to $F$? No, we lost $AB \to C$.


• Wait, the join of $R_1$ and $R_2$ is on C. If we have a tuple $(a, c)$ in $R_1$ and $(c, b)$ in $R_2$, we form $(a, b, c)$. The dependency $AB \to C$ must hold. This is a property of the join, not the individual tables.


• The definition of dependency preservation is that the union of the projections of FDs must be equivalent to F. The projection of F onto $R_1$ is empty. The projection of F onto $R_2$ is $\{C \to B\}$. The union is $\{C \to B\}$. We have lost $AB \to C$. The decomposition is NOT dependency preserving.

This is getting very confusing. Let me consult a textbook definition. A decomposition is dependency preserving if for every FD $X \to Y$ in F, its projection is logically implied by the FDs in the decomposed schemas. The projection of $AB \to C$ is not implied.

Let me try a different approach. A decomposition of R into $R_1$ and $R_2$ is dependency preserving if $(F_1 \cup F_2)^+ = F^+$.
$F_1$ (on $R_1(A,C)$) is empty. $F_2$ (on $R_2(C,B)$) is $\{C \to B\}$.
So we check if $\{C \to B\}^+ = \{AB \to C, C \to B\}^+$. This is clearly false.

There is a fundamental contradiction in my analysis versus the expected answer. Let's reconsider the original relation being in 3NF. CKs {AB, AC}. Primes A,B,C. FD C->B violates BCNF. But since B is prime, it satisfies 3NF. R is in 3NF.
Let's reconsider the whole problem with a fresh mind.
$R(A, B, C)$, $F=\{AB \to C, C \to B\}$. CKs: $\{AB\}, \{AC\}$. Primes: A, B, C.

• Is R in 3NF? Yes. $AB \to C$ is fine (LHS is superkey). $C \to B$ is fine (RHS is prime).


• Decomp: $R_1(A, C), R_2(C, B)$.


• Is it lossless? $R_1 \cap R_2 = \{C\}$. $C \to B$ is in F. Yes, it's lossless.


• Is it dependency preserving? FDs on $R_1$ are $\emptyset$. FDs on $R_2$ are $\{C \to B\}$. Union is $\{C \to B\}$. We lose $AB \to C$. It is NOT dependency preserving.


• Is $R_2(C, B)$ in BCNF? The only FD is $C \to B$. The CK for $R_2$ is $\{C\}$. The LHS of the FD is a superkey. Yes, $R_2$ is in BCNF.

My analysis:

• R is in 3NF: TRUE


• Decomp is lossless: TRUE


• Decomp is dependency preserving: FALSE


• $R_2$ is in BCNF: TRUE

The provided answer is "The decomposition is lossless, The decomposition is dependency preserving, The relation $R_2$ is in BCNF". This implies my analysis of 3NF and dependency preservation is wrong. How can the decomposition be dependency preserving? This is a known issue. Let me check the standard algorithm for 3NF synthesis. It guarantees lossless and dependency preserving. If we decompose R due to BCNF violation ($C \to B$), we get $R_1(C, B)$ and $R_2(A, C)$. This is exactly the given decomposition. This decomposition method for BCNF is always lossless, but not always dependency preserving. In this case, we lose $AB \to C$.

There must be a flaw in the question or the provided answer. I will write the solution based on my rigorous analysis, which is the correct academic approach. It's possible the source of the "answer" is incorrect. I will create a question that is less ambiguous.

Final Revised MSQ:
:::question type="MSQ" question="Consider a relation $R(P, Q, R, S)$ with FDs $F = \{P \to Q, QR \to S\}$. The relation is decomposed into $R_1(P, Q)$ and $R_2(P, R, S)$. Which of the following statements is/are TRUE?" options=["The relation R is in 2NF","The decomposition is lossless","The decomposition is not dependency preserving","The relation $R_1$ is in BCNF"] answer="The decomposition is lossless,The decomposition is not dependency preserving,The relation $R_1$ is in BCNF" hint="Find the candidate key of R. Check for partial/transitive dependencies. Then check the properties of the decomposition." solution="
Analysis of Original Relation R(P, Q, R, S)

• Candidate Key: Attributes P and R are not on the RHS, so they are essential. Let's find $\{P, R\}^+$.


• $\{P, R\}^+ = \{P, R, Q\}$ (from $P \to Q$). Now we have Q and R, so from $QR \to S$, we get $\{P, R, Q, S\}$.


• The sole candidate key is $\{P, R\}$.


• Prime attributes: P, R. Non-prime attributes: Q, S.


• Check 2NF: Consider $P \to Q$. This is a partial dependency because a non-prime attribute ($Q$) depends on a proper subset ($\{P\}$) of the candidate key $\{P, R\}$.


• Therefore, R is in 1NF, but not in 2NF. The statement "The relation R is in 2NF" is FALSE.

Analysis of the Decomposition
The decomposition is $R_1(P, Q)$ and $R_2(P, R, S)$.

Statement: The decomposition is lossless

• $R_1 = \{P, Q\}$, $R_2 = \{P, R, S\}$.


• $R_1 \cap R_2 = \{P\}$.


• $R_1 - R_2 = \{Q\}$.


• We check if $(R_1 \cap R_2) \to (R_1 - R_2)$ holds, i.e., does $P \to Q$ hold in R?


• Yes, $P \to Q$ is a given FD.


• Therefore, the decomposition is lossless. This statement is TRUE.

Statement: The decomposition is not dependency preserving

• The original FDs are $F = \{P \to Q, QR \to S\}$.


• FDs on $R_1(P, Q)$: The FD $P \to Q$ is projected onto $R_1$.


• FDs on $R_2(P, R, S)$: No non-trivial FDs from F can be projected onto $R_2$. The FD $QR \to S$ involves attributes not all in $R_2$.


• The union of FDs on the decomposed relations is $\{P \to Q\}$.


• We have lost the FD $QR \to S$. We cannot derive $QR \to S$ from just $P \to Q$.


• Therefore, the decomposition is not dependency preserving. This statement is TRUE.

Statement: The relation $R_1$ is in BCNF

• $R_1(P, Q)$ has the FD $P \to Q$.


• The candidate key for $R_1$ is $\{P\}$.


• For the only non-trivial FD $P \to Q$, the LHS $\{P\}$ is a superkey of $R_1$.


• Therefore, $R_1$ is in BCNF. This statement is TRUE.

"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider a relation schema $R(A, B, C, D, E)$ with the set of functional dependencies $F = \{A \rightarrow BC, CD \rightarrow E, B \rightarrow D, E \rightarrow A\}$. Which of the following statements is correct?" options=["The relation $R$ is in 3NF but not in BCNF.","The relation $R$ is in BCNF.","The relation $R$ is in 2NF but not in 3NF.","The candidate keys for $R$ are $\{A\}$ and $\{E\}$."] answer="A" hint="First, determine all candidate keys of the relation. Then, check the conditions for BCNF and 3NF for each functional dependency." solution="
To determine the correct statement, we must first find the candidate keys and then evaluate the normal form of the relation.

1. Find Candidate Keys:
We compute the closure of various attribute sets to find a minimal set that determines all other attributes.

• $E^+ = \{E, A\}$ (from $E \rightarrow A$)


• $E^+ = \{E, A, B, C\}$ (from $A \rightarrow BC$)


• $E^+ = \{E, A, B, C, D\}$ (from $B \rightarrow D$)

Since $E^+$ contains all attributes $\{A, B, C, D, E\}$, $E$ is a candidate key.

• $(CD)^+ = \{C, D, E\}$ (from $CD \rightarrow E$)
• $(CD)^+ = \{C, D, E, A\}$ (from $E \rightarrow A$)
• $(CD)^+ = \{C, D, E, A, B\}$ (from $A \rightarrow BC$)

Since $(CD)^+$ contains all attributes, and neither $C^+$ nor $D^+$ do, $CD$ is a candidate key.

• $(BC)^+ = \{B, C, D\}$ (from $B \rightarrow D$)
• $(BC)^+ = \{B, C, D, E\}$ (from $CD \rightarrow E$)
• $(BC)^+ = \{B, C, D, E, A\}$ (from $E \rightarrow A$)

Since $(BC)^+$ contains all attributes, and neither $B^+$ nor $C^+$ do, $BC$ is a candidate key.

The set of candidate keys is $\{E, CD, BC\}$.

2. Identify Prime Attributes:
The prime attributes are those that are part of any candidate key. The set of prime attributes is $\{A, B, C, D, E\}$.

3. Check for BCNF:
A relation is in BCNF if for every non-trivial FD $X \rightarrow Y$, $X$ is a superkey.

• Consider the FD $A \rightarrow BC$. The determinant $A$ is not a superkey (e.g., it is not $E$, $CD$, or $BC$).


• Therefore, the relation $R$ is not in BCNF.

4. Check for 3NF:
A relation is in 3NF if for every non-trivial FD $X \rightarrow Y$, either (i) $X$ is a superkey, or (ii) every attribute in $Y$ is a prime attribute.
Let us examine each FD in $F$:

• $A \rightarrow BC$: $A$ is not a superkey. However, the attributes on the RHS, $B$ and $C$, are both prime attributes. Thus, this FD does not violate 3NF.


• $CD \rightarrow E$: The determinant $CD$ is a candidate key (and thus a superkey). This FD satisfies the 3NF condition.


• $B \rightarrow D$: $B$ is not a superkey. However, the attribute $D$ is a prime attribute. Thus, this FD does not violate 3NF.


• $E \rightarrow A$: The determinant $E$ is a candidate key (and thus a superkey). This FD satisfies the 3NF condition.

Since all functional dependencies satisfy the 3NF condition, the relation $R$ is in 3NF.

Conclusion:
The relation is in 3NF but not in BCNF. Therefore, option A is the correct statement.
"
:::

:::question type="NAT" question="A relation schema $R(P, Q, R, S, T, U)$ has the functional dependencies $F = \{P \rightarrow QR, RS \rightarrow T, Q \rightarrow S, T \rightarrow P, U \rightarrow R\}$. What is the total number of candidate keys for $R$?" answer="4" hint="Identify the essential attributes that must be part of every candidate key. Then, systematically find the minimal sets of attributes that can determine all other attributes in the relation." solution="
1. Identify Essential Attributes:
An attribute is considered essential if it does not appear on the right-hand side (RHS) of any functional dependency.

• The attributes on the RHS are: $Q, R$ (from $P \rightarrow QR$), $T$ (from $RS \rightarrow T$), $S$ (from $Q \rightarrow S$), $P$ (from $T \rightarrow P$), and $R$ (from $U \rightarrow R$).


• The set of RHS attributes is $\{P, Q, R, S, T\}$.


• The attribute $U$ does not appear on the RHS of any FD. Therefore, $U$ must be a part of every candidate key.

2. Compute Closures Starting with Essential Attributes:
Let's start with the closure of $U$:
$U^+ = \{U, R\}$ (using $U \rightarrow R$).

To form a candidate key, we must add attributes to $U$ until the closure contains all attributes of the relation, i.e., $\{P, Q, R, S, T, U\}$. We need to find a way to derive $\{P, Q, S, T\}$.

Notice the dependencies among $\{P, Q, S, T\}$: $P \rightarrow Q \rightarrow S$ and $T \rightarrow P$. Also, $RS \rightarrow T$. This forms a cycle. Adding any attribute from this cycle to $U$ should allow us to derive all others. Let's test this.

• Test with P: $(UP)^+ = \{U, P\}^+ = \{U, P, Q, R, S, T\}$. This is a superkey. Since neither $U^+$ nor $P^+$ contain all attributes, $\{UP\}$ is a candidate key.
• Test with Q: $(UQ)^+ = \{U, Q\}^+ = \{U, Q, R, S, T, P\}$. This is a superkey. Since neither $U^+$ nor $Q^+$ contain all attributes, $\{UQ\}$ is a candidate key.
• Test with S: $(US)^+ = \{U, S\}^+ = \{U, S, R\} \rightarrow \{U,S,R,T\} \rightarrow \{U,S,R,T,P\} \rightarrow \{U,S,R,T,P,Q\}$. This is a superkey. Since neither $U^+$ nor $S^+$ contain all attributes, $\{US\}$ is a candidate key.
• Test with T: $(UT)^+ = \{U, T\}^+ = \{U, T, R, P, Q, S\}$. This is a superkey. Since neither $U^+$ nor $T^+$ contain all attributes, $\{UT\}$ is a candidate key.

3. Final Count: We have found four sets: $\{UP\}, \{UQ\}, \{US\}, \{UT\}$. Each is a superkey, and each is minimal. Any larger set containing one of these (e.g., $\{UPS\}$) would be a superkey but not a candidate key.

Therefore, there are a total of 4 candidate keys.
"
:::

:::question type="MCQ" question="A relational schema $R(W, X, Y, Z)$ has the functional dependencies $F = \{W \rightarrow X, Y \rightarrow Z\}$. What is the highest normal form that $R$ satisfies?" options=["1NF","2NF","3NF","BCNF"] answer="A" hint="First, find the candidate key(s). Then, check for partial and transitive dependencies to determine the normal form." solution="
1. Find the Candidate Key:

• We identify attributes that do not appear on the right-hand side (RHS) of any FD. The RHS attributes are $X$ and $Z$. The attributes not on the RHS are $W$ and $Y$.


• Let's compute the closure of $\{W, Y\}$: $(WY)^+$.


• Starting with $\{W, Y\}$, we can add $X$ using $W \rightarrow X$, and we can add $Z$ using $Y \rightarrow Z$.


• So, $(WY)^+ = \{W, X, Y, Z\}$.


• Since $(WY)^+$ contains all attributes of the relation, and neither $W^+$ nor $Y^+$ do, $\{WY\}$ is the sole candidate key.

2. Identify Prime and Non-Prime Attributes:

• Prime attributes (part of a candidate key): $\{W, Y\}$.


• Non-prime attributes (not part of any candidate key): $\{X, Z\}$.

3. Check Normal Forms:

• 1NF: The relation is in 1NF by the standard assumption of atomic attribute values.


• 2NF: A relation is in 2NF if it is in 1NF and contains no partial dependencies. A partial dependency occurs when a non-prime attribute is functionally dependent on a proper subset of a candidate key.

- Consider the FD $W \rightarrow X$. The determinant, $W$, is a proper subset of the candidate key $WY$. The dependent, $X$, is a non-prime attribute. This is a partial dependency.
- Similarly, for the FD $Y \rightarrow Z$, the determinant $Y$ is a proper subset of the candidate key $WY$, and the dependent $Z$ is a non-prime attribute. This is also a partial dependency.

• Since the relation contains partial dependencies, it is not in 2NF.

Conclusion:
The relation $R$ satisfies 1NF but fails the condition for 2NF. Therefore, the highest normal form it satisfies is 1NF.
"
:::

:::question type="NAT" question="Consider the set of functional dependencies $F = \{A \rightarrow B, B \rightarrow C, A \rightarrow C, C \rightarrow D\}$. Determine the number of functional dependencies in the canonical cover (minimal cover) of $F$." answer="3" hint="Follow the three steps to find a canonical cover: singleton right-hand sides, remove extraneous left-hand side attributes, and remove redundant dependencies." solution="
To find the canonical cover, we follow a three-step process.

Given FDs: $F = \{A \rightarrow B, B \rightarrow C, A \rightarrow C, C \rightarrow D\}$

Step 1: Ensure Singleton Right-Hand Sides
Each FD in the given set $F$ already has a single attribute on its right-hand side. This step is complete.

Step 2: Remove Extraneous Attributes from Left-Hand Sides
Each FD in the given set $F$ has only a single attribute on its left-hand side. Therefore, there are no extraneous attributes to remove. This step is complete.

Step 3: Remove Redundant Functional Dependencies
We must check if any FD in $F$ can be derived from the other FDs in the set.

• Check $A \rightarrow B$: Consider the set $F' = F - \{A \rightarrow B\} = \{B \rightarrow C, A \rightarrow C, C \rightarrow D\}$. To check if $A \rightarrow B$ is redundant, we compute $A^+$ using $F'$.

$A^+ = \{A, C, D\}$. Since $B \notin A^+$, the FD $A \rightarrow B$ is essential and not redundant.

• Check $B \rightarrow C$: Consider the set $F' = F - \{B \rightarrow C\} = \{A \rightarrow B, A \rightarrow C, C \rightarrow D\}$. We compute $B^+$ using $F'$.

$B^+ = \{B\}$. Since $C \notin B^+$, the FD $B \rightarrow C$ is essential and not redundant.

• Check $A \rightarrow C$: Consider the set $F' = F - \{A \rightarrow C\} = \{A \rightarrow B, B \rightarrow C, C \rightarrow D\}$. We compute $A^+$ using $F'$.

- From $A \rightarrow B$, we get $A^+ = \{A, B\}$. - From $B \rightarrow C$, we get $A^+ = \{A, B, C\}$. Since $C \in A^+$, the FD $A \rightarrow C$ can be derived from $\{A \rightarrow B, B \rightarrow C\}$ by transitivity. Thus, $A \rightarrow C$ is redundant.

• Check $C \rightarrow D$ (after logically removing $A \rightarrow C$): Consider the set $F' = \{A \rightarrow B, B \rightarrow C\}$. We compute $C^+$ using $F'$.

$C^+ = \{C\}$. Since $D \notin C^+$, the FD $C \rightarrow D$ is essential and not redundant.

After removing the redundant FD $A \rightarrow C$, the resulting minimal (canonical) cover is $\{A \rightarrow B, B \rightarrow C, C \rightarrow D\}$.

The number of functional dependencies in this set is 3.
"
:::

---

What's Next?