Normalization
Functional Dependencies
A functional dependency $\alpha \rightarrow \beta$ holds on a relation $R$ if, for any two tuples $t_1$ and $t_2$ in $R$, whenever $t_1[\alpha] = t_2[\alpha]$, it must also be the case that $t_1[\beta] = t_2[\beta]$.
Key points:
$\alpha$ determines $\beta$ uniquely.
If $\alpha$ is a superkey, then $\alpha \rightarrow R$ holds.
Trivial FDs: $\beta \subseteq \alpha$, e.g., $A \rightarrow A$.
Consider $r(A,B)$ with the following instance of $r$. On this instance, $B \rightarrow A$ holds; $A \rightarrow B$ does NOT hold, \[ \begin{array}{|c|c|} \hline A & B \\ \hline 1 & 4 \\ 1 & 5 \\ 3 & 7 \\ \hline \end{array} \]
Consider the following instance of relation $r(A,B,C,D)$:
Step-by-step FD analysis:
Check if $A \rightarrow C$ holds:
Tuples with $A = a1$: $c1, c1$ → same → OK
Tuples with $A = a2$: $c2, c2$ → same → OK
$A = a3$: only one tuple → trivially OK
Conclusion: $A \rightarrow C$ holds
Check if $C \rightarrow A$ holds:
Tuples with $C = c2$: $A = a2, a2, a3$ → different → violates FD
Conclusion: $C \rightarrow A$ does not hold
Check if $B \rightarrow D$ holds:
$B = b2$: tuples $(a1,b2,c1,d2)$ and $(a2,b2,c2,d2)$ → D = d2 in both → holds
$B = b3$: tuples $(a2,b3,c2,d3)$ and $(a3,b3,c2,d4)$ → D = d3, d4 → violates FD
Conclusion: $B \rightarrow D$ does not hold
Trivial FDs:
$A \rightarrow A$, $B \rightarrow B$, $C \rightarrow C$, $D \rightarrow D$ always hold
Any FD $\alpha \rightarrow \beta$ where $\beta \subseteq \alpha$ is trivial
Summary:
Non-trivial FD that holds: $A \rightarrow C$
Non-trivial FDs that do not hold: $C \rightarrow A$, $B \rightarrow D$
Analysis:
sNo uniquely identifies student name and department → FD: $sNo \rightarrow sName, dNo$.
dNo uniquely identifies department name → FD: $dNo \rightarrow dName$.
Combination $sNo, dNo$ is a superkey → $sNo, dNo \rightarrow sName, dName$.
Analysis:
empID is unique → $empID \rightarrow empName, dept, salary$
dept does not determine salary (Sales has multiple salaries) → no FD $dept \rightarrow salary$
Combination empID, dept → still determines all attributes (superkey)
Analysis:
cNo uniquely identifies course → $cNo \rightarrow cName, credits$
cName does not determine credits (Math appears twice, same credits here, but could vary in other instances)
Analysis:
Combination (sNo, cNo) determines grade → $(sNo, cNo) \rightarrow grade$
sNo alone does not determine grade (student has multiple courses)
cNo alone does not determine grade (multiple students take the same course)
Analysis:
(building, roomNo) uniquely identifies capacity and type → $(building, roomNo) \rightarrow capacity, type$
roomNo alone does not determine capacity (room 101 exists in both buildings with different capacities)
Analysis:
Composite key (orderID, productID) → quantity, price
orderID alone does not determine quantity or price
productID alone does not determine quantity or price
Identify superkeys: sets of attributes that uniquely identify tuples.
Determine FDs by checking if a value of attribute(s) consistently determines other attribute(s) across all tuples.
Trivial FDs always hold: $\alpha \rightarrow \beta$ is trivial if $\beta \subseteq \alpha$.
Non-trivial FDs indicate constraints and guide normalization.
Use tables to verify candidate keys and dependent attributes.
Types of Functional Dependency
Every dependent in trivial functional dependency is a subset of the determinant. If $Y$ is a subset of $X$, the functional relationship $X \rightarrow Y$ is referred to as trivial.
\[ \begin{array}{ccc} \text{Employee\_Id} & \text{Name} & \text{Age} \\ 1 & \text{Zayn} & 24 \\ 2 & \text{Phobe} & 34 \\ 3 & \text{Hikki} & 26 \\ 4 & \text{David} & 29 \\ \end{array} \] Given that the dependent Name is a subset of the determinant Employee_Id, Name, the functional dependency between $\{ \text{Employee\_Id, Name} \}$ and $\{ \text{Name} \}$ is trivial. Additionally, Name, Age, and Employee_Id are also trivial.
The non-trivial functional dependency is opposed to the trivial one. Formally, the dependent is not a subset of the determinant. If $Y$ is not a subset of $X$, the relationship $X \rightarrow Y$ is non-trivial.
\[ \begin{array}{ccc} \text{Employee\_Id} & \text{Name} & \text{Age} \\ 1 & \text{Zayn} & 24 \\ 2 & \text{Phobe} & 34 \\ 3 & \text{Hikki} & 26 \\ 4 & \text{David} & 29 \\ 5 & \text{Phobe} & 24 \\ \end{array} \] Because Name (dependent) is not a subset of Employee_Id, there is a non-trivial functional dependency between Employee_Id and Name. The functional dependencies $\{ \text{Employee\_Id, Name} \} \rightarrow \{ \text{Age} \}$ are also non-trivial.
Attributes in the dependent set are not reliant on each other in multi-valued dependency. If there is no functional dependency between $Y$ and $Z$, the relationship $X \rightarrow Y, Z$ is referred to as multi-valued functional dependency.
\[ \begin{array}{ccc} \text{Employee\_Id} & \text{Name} & \text{Age} \\ 1 & \text{Zayn} & 24 \\ 2 & \text{Phobe} & 34 \\ 3 & \text{Hikki} & 26 \\ 4 & \text{David} & 29 \\ 4 & \text{Phobe} & 24 \\ \end{array} \] Since the dependent attributes Name and Age are not functionally dependent, $\{ \text{Employee\_Id} \} \rightarrow \{ \text{Name, Age} \}$ is a multi-valued functional dependency.
Given two functional dependencies $A \rightarrow B$ and $B \rightarrow C$, $A \rightarrow C$ must also exist according to the transitivity principle. In transitive functional dependency, the dependent is indirectly reliant on the determinant.
\[ \begin{array}{cccc} \text{Employee\_Id} & \text{Name} & \text{Department} & \text{Street Number} \\ 1 & \text{Zayn} & \text{CD} & 11 \\ 2 & \text{Phobe} & \text{AB} & 24 \\ 3 & \text{Hikki} & \text{CD} & 11 \\ 4 & \text{David} & \text{PQ} & 71 \\ 5 & \text{Phobe} & \text{LM} & 21 \\ \end{array} \] The relationships between Employee_Id, Department, and Street Number are valid. Consequently, $\{ \text{Employee\_Id} \}$ and $\{ \text{Street Number} \}$ are both valid functional dependencies according to the axiom of transitivity.
Armstrong’s axioms (Inference rules)
Armstrong’s Axioms are a set of rules that, when applied repeatedly, generate a closure of functional dependencies.
If $B \subseteq A$, then $A \rightarrow B$. This property is trivial: every set of attributes functionally determines its subsets.
Let $A = \{ \text{EmpID, Name} \}$ and $B = \{ \text{Name} \}$. Since $B \subseteq A$, by reflexivity: \[ \{ \text{EmpID, Name} \} \rightarrow \{ \text{Name} \} \] is a valid functional dependency.
If $A \rightarrow B$ holds and $C$ is any attribute set, then $AC \rightarrow BC$ also holds. Adding attributes to both sides preserves the dependency.
If $\text{EmpID} \rightarrow \text{Name}$, then by augmentation: \[ \{ \text{EmpID, Dept} \} \rightarrow \{ \text{Name, Dept} \} \] also holds.
If $A \rightarrow B$ and $B \rightarrow C$, then $A \rightarrow C$. This is similar to the transitive property in algebra.
If $\text{EmpID} \rightarrow \text{Dept}$ and $\text{Dept} \rightarrow \text{Manager}$, then $\text{EmpID} \rightarrow \text{Manager}$ also holds.
If $A \rightarrow B$ and $A \rightarrow C$, then $A \rightarrow BC$.
If $\text{EmpID} \rightarrow \text{Name}$ and $\text{EmpID} \rightarrow \text{Dept}$, then $\text{EmpID} \rightarrow \text{Name, Dept}$.
If $A \rightarrow B$ and $X \rightarrow Y$, then $AX \rightarrow BY$.
If $\text{EmpID} \rightarrow \text{Name}$ and $\text{DeptID} \rightarrow \text{DeptName}$, then $\{\text{EmpID, DeptID}\} \rightarrow \{\text{Name, DeptName}\}$.
If $A \rightarrow BC$, then $A \rightarrow B$ and $A \rightarrow C$.
If $\text{EmpID} \rightarrow \{\text{Name, Dept}\}$, then $\text{EmpID} \rightarrow \text{Name}$ and $\text{EmpID} \rightarrow \text{Dept}$.
If $A \rightarrow B$ and $BC \rightarrow D$, then $AC \rightarrow D$.
If $\text{EmpID} \rightarrow \text{Dept}$ and $\{\text{Dept, Location}\} \rightarrow \text{Manager}$, then $\{\text{EmpID, Location}\} \rightarrow \text{Manager}$.
Every attribute set functionally determines itself: $A \rightarrow A$.
$\text{EmpID} \rightarrow \text{EmpID}$ is always true.
If $AC \rightarrow A$ and $A \rightarrow B$, then $AC \rightarrow B$. Also leads to $AC \rightarrow BC$ and $ABC \rightarrow BC$.
If $\{\text{EmpID, Dept}\} \rightarrow \text{EmpID}$ and $\text{EmpID} \rightarrow \text{Name}$, then $\{\text{EmpID, Dept}\} \rightarrow \text{Name}$.
When an FD is reflexive, $Y$ is a subset of $X$ and $X$ refers to the set of attributes, then:
$Y \rightarrow X$ holds
$X \rightarrow Y$ holds
$XY \rightarrow Z$ holds
None of the above
Answer: B. $X \rightarrow Y$ holds
Explanation: When an FD is reflexive, $Y \subseteq X$, so $X \rightarrow Y$ always holds according to Armstrong's reflexivity axiom.
If $P \rightarrow Q$ and $P \rightarrow R$, then which of these would be true?
$P \rightarrow QR$
$P \rightarrow Q$
$P \rightarrow R$
All of the above
Answer: D. All of the above
Explanation: By the union rule, if $P \rightarrow Q$ and $P \rightarrow R$, then $P \rightarrow QR$ holds. Individual dependencies also hold.
Closure of attributes & Finding Candidate Keys
Closure of an Attribute
The closure of an attribute (or attribute set) is the set of all attributes that can be functionally determined from it, given a set of functional dependencies.
Purpose:
Determine candidate keys
Test dependency preservation
Normalize relations
Algorithm to Compute $X^+$ (Closure of $X$): Corrected Closure Calculation Input: A set \(F\) of functional dependencies on a relation schema \(R\), and a set of attributes \(X \subseteq R\).
$X^+ \gets X$ // Initialize closure with \(X\) itself
Repeat
$\text{oldX}^+ \gets X^+$ // Snapshot current set at the start of the loop
For each functional dependency \(Y \rightarrow Z\) in \(F\):
If $X^+ \supseteq Y$, then $X^+ \gets X^+ \cup Z$ // Add new attributes
End For
Until $X^+ = \text{oldX}^+$ // If no changes occurred in this pass, STOP
Return $X^+$
Consider relation \(R(A,B,C,D,E,F)\) with FDs: \[ F: E \rightarrow A, \; E \rightarrow D, \; A \rightarrow C, \; A \rightarrow D, \; AE \rightarrow F, \; AG \rightarrow K \]
Find \(E^+\):
\[ \begin{aligned} E^+ & = E \\ & = EA \quad \text{(from } E \rightarrow A\text{)} \\ & = EAD \quad \text{(from } E \rightarrow D\text{)} \\ & = EADC \quad \text{(from } A \rightarrow C\text{)} \\ & = EADCF \quad \text{(from } AE \rightarrow F\text{)} \\ & = EADCF \quad \text{(from } AG \rightarrow K \text{, not added since } AG \nsubseteq E^+) \end{aligned} \]
Thus, \(E^+ = \{E, A, D, C, F\}\).
Consider relation \(R(A,B,C,D,E,F,G)\) with FDs: \[ F: E \rightarrow A, \; E \rightarrow D, \; A \rightarrow C, \; A \rightarrow D, \; AE \rightarrow F, \; AG \rightarrow K, \; BC \rightarrow DE, \; D \rightarrow F, \; CF \rightarrow G \]
Compute closures:
Closure of attribute A: \[ \begin{aligned} A^+ & = \{A\} \\ & = \{A, B, C\} \quad (\text{Using } A \rightarrow BC) \\ & = \{A, B, C, D, E\} \quad (\text{Using } BC \rightarrow DE) \\ & = \{A, B, C, D, E, F\} \quad (\text{Using } D \rightarrow F) \\ & = \{A, B, C, D, E, F, G\} \quad (\text{Using } CF \rightarrow G) \end{aligned} \]
Closure of attribute D: \[ D^+ = \{D, F\} \quad (\text{Using } D \rightarrow F) \]
Closure of attribute set \(\{B,C\}\): \[ \begin{aligned} \{B,C\}^+ & = \{B, C\} \\ & = \{B, C, D, E\} \quad (\text{Using } BC \rightarrow DE) \\ & = \{B, C, D, E, F\} \quad (\text{Using } D \rightarrow F) \\ & = \{B, C, D, E, F, G\} \quad (\text{Using } CF \rightarrow G) \end{aligned} \]
Thus, \(\{B,C\}^+ = \{B,C,D,E,F,G\}\).
Finding Candidate Keys
A candidate key is defined as:
A minimal set of attributes that can uniquely identify each tuple in a relation.
Equivalently, a minimal superkey is a candidate key.
Steps to find candidate keys:
Step 1: Find essential attributes
Essential attributes are not present on the RHS of any functional dependency OR Attributes that do not appear in any dependency at all.
Essential attributes must be in every candidate key.
Step 2: Identify non-essential attributes
Remaining attributes that appear on RHS of some FD.
If essential attributes alone can determine all non-essential attributes, they form the only candidate key.
Otherwise, combine essential attributes with some non-essential attributes to form all possible candidate keys.
Let $|R| = n$ (total attributes) and $CK$ be a Candidate Key of size $k$.
Case 1: Single Candidate Key
The number of superkeys is given by: $N = 2^{n-k}$Case 2: Two Candidate Keys ($K_1$ and $K_2$)
Using the Principle of Inclusion-Exclusion: \[ |S_1 \cup S_2| = |S_1| + |S_2| - |S_1 \cap S_2| \] In terms of attributes: \[ N = 2^{n-|K_1|} + 2^{n-|K_2|} - 2^{n-|K_1 \cup K_2|} \]Case 3: Three Candidate Keys ($K_1, K_2, K_3$)
Applying the Principle of Inclusion-Exclusion (PIE): \[ N = \sum |S_i| - \sum |S_i \cap S_j| + |S_1 \cap S_2 \cap S_3| \] In terms of attributes: \[ N = (2^{n-|K_1|} + 2^{n-|K_2|} + 2^{n-|K_3|}) - (2^{n-|K_1 \cup K_2|} + 2^{n-|K_2 \cup K_3|} + 2^{n-|K_1 \cup K_3|}) + 2^{n-|K_1 \cup K_2 \cup K_3|} \]Special Case (All attributes are Essential)
If all $n$ attributes are essential, then the only candidate key is the set of all attributes ($k=n$): \[ N = 2^{n-n} = 2^0 = 1 \] In this case, the only superkey is the Relation $R$ itself.
Relation: $R(A, B, C, D, E, F)$
Functional Dependencies: \[ C \rightarrow F, \quad E \rightarrow A, \quad EC \rightarrow D, \quad A \rightarrow B \]
Step 1: Essential attributes \[ \text{Attributes not on RHS: } C, E \quad \Rightarrow \text{Essential attributes} = \{C, E\} \]
Step 2: Compute closure of essential attributes \[ \{ CE \}^+ = \{ C, E \} \xrightarrow{C \rightarrow F} \{ C, E, F \} \xrightarrow{E \rightarrow A} \{ A, C, E, F \} \xrightarrow{EC \rightarrow D} \{ A, C, D, E, F \} \xrightarrow{A \rightarrow B} \{ A, B, C, D, E, F \} \]
Conclusion: $CE$ can determine all attributes.
Candidate Key: $CE$ (only one)
Super Keys: Essential attributes = 2, Non-essential = 4
\[ \text{Number of super keys} = 2^4 = 16 \]
Relation: $R(A, B, C, D, E)$
Functional Dependencies: \[ AB \rightarrow C, \quad C \rightarrow D, \quad B \rightarrow E \]
Step 1: Essential attributes \[ \text{Attributes not on RHS: } A, B \quad \Rightarrow \text{Essential attributes} = \{A, B\} \]
Step 2: Compute closure of essential attributes \[ \{ AB \}^+ = \{ A, B \} \xrightarrow{AB \rightarrow C} \{ A, B, C \} \xrightarrow{C \rightarrow D} \{ A, B, C, D \} \xrightarrow{B \rightarrow E} \{ A, B, C, D, E \} \]
Conclusion: $AB$ can determine all attributes.
Candidate Key: $AB$ (only one)
Super Keys: Essential = 2, Non-essential = 3 \[ \text{Number of super keys} = 2^3 = 8 \]
Relation: $R(E, F, G, H, I, J, K, L, M, N)$
Functional Dependencies: \[ \{ E, F \} \rightarrow G, \quad F \rightarrow I, J, \quad \{ E, H \} \rightarrow K, L, \quad K \rightarrow M, \quad L \rightarrow N \]
Step 1: Essential attributes \[ \text{Attributes not on RHS: } E, F, H \quad \Rightarrow \text{Essential attributes} = \{ E, F, H \} \]
Step 2: Compute closure of essential attributes \begin{align*} \{ EFH \}^+ &= \{ E, F, H \} &&\xrightarrow{EF \rightarrow G} \{ E, F, G, H \} \\ &&\xrightarrow{F \rightarrow I, J} \{ E, F, G, H, I, J \} \\ &&\xrightarrow{EH \rightarrow K, L} \{ E, F, G, H, I, J, K, L \} \\ &&\xrightarrow{K \rightarrow M} \{ E, F, G, H, I, J, K, L, M \} \\ &&\xrightarrow{L \rightarrow N} \{ E, F, G, H, I, J, K, L, M, N \} \end{align*}
Candidate Key: $EFH$ (only one)
Super Keys: Essential = 3, Non-essential = 7 \[ \text{Number of super keys} = 2^7 = 128 \]
Relation: $R(A, B, C, D, E, H)$
Functional Dependencies: \[ A \rightarrow B, \quad BC \rightarrow D, \quad E \rightarrow C, \quad D \rightarrow A \]
Essential attributes: $E, H$
Candidate Keys: All options containing essential attributes that determine remaining attributes: \[ \text{Candidate Keys: } AEH, BEH, DEH \]
Answer: Option (D)
Canonical Cover
Equivalence of Functional Dependencies
Two sets of functional dependencies $E$ and $F$ are said to be equivalent if
\[ E^+ = F^+ \]
Equivalently,
\[ E \equiv F \]
iff
$E$ covers $F$
$F$ covers $E$
Let
\[ F = \{A \rightarrow C,\ AC \rightarrow D,\ E \rightarrow AD,\ E \rightarrow H\} \]
\[ G = \{A \rightarrow CD,\ E \rightarrow AH\} \]
Step 1: Check $F$ covers $G$
Check $A \rightarrow CD$
Compute $A^+$ using $F$
\[ A^+ = \{A\} \]
Using $A \rightarrow C$
\[ A^+ = \{A,C\} \]
Using $AC \rightarrow D$
\[ A^+ = \{A,C,D\} \]
Hence
\[ A \rightarrow CD \]
holds.
Check $E \rightarrow AH$
Compute $E^+$ using $F$
\[ E^+ = \{E\} \]
Using $E \rightarrow AD$
\[ E^+ = \{E,A,D\} \]
Using $A \rightarrow C$
\[ E^+ = \{E,A,D,C\} \]
Using $E \rightarrow H$
\[ E^+ = \{E,A,D,C,H\} \]
Hence
\[ E \rightarrow AH \]
holds.
\[ \therefore F \text{ covers } G \]
Step 2: Check $G$ covers $F$
Check $A \rightarrow C$
Compute $A^+$ using $G$
\[ A^+ = \{A\} \]
Using $A \rightarrow CD$
\[ A^+ = \{A,C,D\} \]
Hence
\[ A \rightarrow C \]
holds.
Check $AC \rightarrow D$
Since $A \rightarrow CD$
\[ AC \rightarrow D \]
holds.
Check $E \rightarrow AD$
Compute $E^+$ using $G$
\[ E^+ = \{E\} \]
Using $E \rightarrow AH$
\[ E^+ = \{E,A,H\} \]
Using $A \rightarrow CD$
\[ E^+ = \{E,A,H,C,D\} \]
Hence
\[ E \rightarrow AD \]
holds.
Check $E \rightarrow H$
Directly given.
\[ \therefore G \text{ covers } F \]
Conclusion
\[ F \equiv G \]
Hence the two sets of functional dependencies are equivalent.
Let
\[ F = \{a \rightarrow b,\ b \rightarrow c,\ c \rightarrow d\} \]
\[ G = \{a \rightarrow bc,\ c \rightarrow d\} \] Step 1: Check if $F$ covers $G$ We check each FD in $G$ using the rules in $F$:
Check $a \to bc$: Compute $a^+$ using $F$: $a^+ = \{a, b, c, d\}$. Since $\{b, c\} \subseteq a^+$, $a \to bc$ is Covered.
Check $c \to d$: Compute $c^+$ using $F$: $c^+ = \{c, d\}$. Since $d \in c^+$, $c \to d$ is Covered.
$\therefore F$ covers $G$.
Step 2: Check if $G$ covers $F$ We check each FD in $F$ using the rules in $G$:
Check $a \to b$: Compute $a^+$ using $G$: $a^+ = \{a, b, c, d\}$. Since $b \in a^+$, $a \to b$ is Covered.
Check $b \to c$: Compute $b^+$ using $G$: $b^+ = \{b\}$. Since $c \notin b^+$, $b \to c$ is NOT Covered.
Check $c \to d$: Compute $c^+$ using $G$: $c^+ = \{c, d\}$. Since $d \in c^+$, $c \to d$ is Covered.
$\therefore G$ does not cover $F$ (specifically due to $b \to c$).
Let
\[ F = \{a \rightarrow b,\; ab \rightarrow c,\; d \rightarrow ac,\; d \rightarrow e\} \]
\[ G = \{a \rightarrow bc,\; d \rightarrow ab\} \]
Step 1: Check whether $F$ covers $G$
Check $a \rightarrow bc$
Compute $a^+$ using $F$
\[ a^+ = \{a\} \]
Using $a \rightarrow b$
\[ a^+ = \{a,b\} \]
Using $ab \rightarrow c$
\[ a^+ = \{a,b,c\} \]
Hence
\[ a \rightarrow bc \]
holds.
Check $d \rightarrow ab$
Compute $d^+$ using $F$
\[ d^+ = \{d\} \]
Using $d \rightarrow ac$
\[ d^+ = \{d,a,c\} \]
Using $a \rightarrow b$
\[ d^+ = \{d,a,c,b\} \]
Using $d \rightarrow e$
\[ d^+ = \{d,a,c,b,e\} \]
Hence
\[ d \rightarrow ab \]
holds.
\[ \therefore F \text{ covers } G \]
Step 2: Check whether $G$ covers $F$
Check $a \rightarrow b$
Compute $a^+$ using $G$
\[ a^+ = \{a\} \]
Using $a \rightarrow bc$
\[ a^+ = \{a,b,c\} \]
Hence $a \rightarrow b$ holds.
Check $ab \rightarrow c$
Since $a \rightarrow bc$
\[ ab \rightarrow c \]
holds.
Check $d \rightarrow ac$
Compute $d^+$ using $G$
\[ d^+ = \{d\} \]
Using $d \rightarrow ab$
\[ d^+ = \{d,a,b\} \]
Using $a \rightarrow bc$
\[ d^+ = \{d,a,b,c\} \]
Hence $d \rightarrow ac$ holds.
Check $d \rightarrow e$
Compute $d^+$ using $G$
\[ d^+ = \{d,a,b,c\} \]
Attribute $e$ cannot be derived.
Hence
\[ d \rightarrow e \]
does not hold.
\[ \therefore G \text{ does not cover } F \]
Conclusion
\[ F \not\equiv G \]
Hence the two FD sets are not equivalent.
Let
\[ F = \{pq \rightarrow r,\; p \rightarrow q,\; s \rightarrow pq,\; s \rightarrow t\} \]
\[ G = \{p \rightarrow qr,\; s \rightarrow pt\} \]
Step 1: Check whether $F$ covers $G$
Check $p \rightarrow qr$
Compute $p^+$ using $F$
\[ p^+ = \{p\} \]
Using $p \rightarrow q$
\[ p^+ = \{p,q\} \]
Using $pq \rightarrow r$
\[ p^+ = \{p,q,r\} \]
Hence
\[ p \rightarrow qr \]
holds.
Check $s \rightarrow pt$
Compute $s^+$ using $F$
\[ s^+ = \{s\} \]
Using $s \rightarrow pq$
\[ s^+ = \{s,p,q\} \]
Using $pq \rightarrow r$
\[ s^+ = \{s,p,q,r\} \]
Using $s \rightarrow t$
\[ s^+ = \{s,p,q,r,t\} \]
Hence
\[ s \rightarrow pt \]
holds.
\[ \therefore F \text{ covers } G \]
Step 2: Check whether $G$ covers $F$
Check $pq \rightarrow r$
Compute $pq^+$ using $G$
\[ pq^+ = \{p,q\} \]
Using $p \rightarrow qr$
\[ pq^+ = \{p,q,r\} \]
Hence
\[ pq \rightarrow r \]
holds.
Check $p \rightarrow q$
Compute $p^+$ using $G$
\[ p^+ = \{p,q,r\} \]
Hence it holds.
Check $s \rightarrow pq$
Compute $s^+$ using $G$
\[ s^+ = \{s\} \]
Using $s \rightarrow pt$
\[ s^+ = \{s,p,t\} \]
Using $p \rightarrow qr$
\[ s^+ = \{s,p,t,q,r\} \]
Hence
\[ s \rightarrow pq \]
holds.
Check $s \rightarrow t$
Directly given in $G$.
\[ \therefore G \text{ covers } F \]
Conclusion
\[ F \equiv G \]
Hence the two sets of functional dependencies are equivalent.
Minimal Cover of Functional Dependencies
The Minimal Cover for a set of FDs $E$ is a set of FDs $F$ that satisfies the property that every dependency in $E$ is in the closure $F^+$, and $F$ contains no redundancies.
Procedure:
Step 1: Ensure every functional dependency (FD) has only a single attribute on the right-hand side.
Example: $A \to BC$ becomes $\{ A \to B, \; A \to C \}$.
Step 2: Delete Redundant FDs Check each FD against the remaining set to see if it can be inferred.
Action: For an FD $A \to B$, compute $A^+$ using all other FDs in the set.
Decision: If $B \in A^+$, the FD is Redundant and is deleted.
Step 3: Minimize Left Side (Extraneous Attributes) For FDs with multiple attributes on the left (e.g., $AB \to C$), check if one attribute is a "passenger."
Testing if $B$ is Extraneous in $AB \to C$: Compare the closure of the survivor ($A$) before and after removing $B$ from that specific FD.
Given Relation $R(A, B, C, D)$ and $FDs = \{A \to B, C \to B, D \to ABC, AC \to D\}$.
Step 1: Standard Form (Right-side Decomposition)
1) $A \to B$
2) $C \to B$
3) $D \to A$
4) $D \to B$
5) $D \to C$
6) $AC \to D$
Step 2: Delete Redundant FDs We check each FD against the remaining set:
Check $A \to B$: Compute $A^+$ from $\{2, 3, 4, 5, 6\}$. $A^+ = \{A\}$. $B \notin A^+$. (Keep)
Check $C \to B$: Compute $C^+$ from $\{1, 3, 4, 5, 6\}$. $C^+ = \{C\}$. $B \notin C^+$. (Keep)
Check $D \to B$: Compute $D^+$ from $\{1, 2, 3, 5, 6\}$. $D^+ = \{D, A, C\}$ (using 3 and 5), then $\{D, A, C, B\}$ (using 1 or 2). Since $B \in D^+$, $D \to B$ is Redundant and is deleted.
Check $D \to A$: $D^+$ from $\{1, 2, 5, 6\}$. $D^+ = \{D, C, B\}$. $A \notin D^+$. (Keep)
Check $D \to C$: $D^+$ from $\{1, 2, 3, 6\}$. $D^+ = \{D, A, B\}$. $C \notin D^+$. (Keep)
Step 3: Minimize Left Side (Extraneous Attributes) Check $AC \to D$ to see if $A$ or $C$ is redundant.
Final Irreducible Set (Minimal Cover)
The resulting set of FDs is:
$A \to B$
$C \to B$
$D \to AC$
$AC \to D$
}
Given: $F = \{ X \to YZ, \; Y \to Z, \; X \to Y, \; XY \to Z \}$
Step 1: Standard Form (Right-side Decomposition)
1) $X \to Y$
2) $X \to Z$
3) $Y \to Z$
4) $XY \to Z$
Step 2: Delete Redundant FDs Check each FD against the remaining set to see if it can be inferred:
Check $X \to Y$: $X^+$ from $\{2, 3, 4\}$. $X^+ = \{X, Z\}$. $Y \notin X^+$. (Keep)
Check $X \to Z$: $X^+$ from $\{1, 3, 4\}$. $X^+ = \{X, Y\}$ (using $X \to Y$), then $\{X, Y, Z\}$ (using $Y \to Z$). Since $Z \in X^+$, $X \to Z$ is Redundant and is deleted.
Check $Y \to Z$: $Y^+$ from $\{1, 4\}$. $Y^+ = \{Y\}$. $Z \notin Y^+$. (Keep)
Check $XY \to Z$: $(XY)^+$ from $\{1, 3\}$. $(XY)^+ = \{X, Y, Z\}$ (using $X \to Y$ and $Y \to Z$). Since $Z \in (XY)^+$, $XY \to Z$ is Redundant and is deleted.
Updated Set: $\{ X \to Y, \; Y \to Z \}$
Step 3: Minimize Left Side (Extraneous Attributes) In the updated set $\{ X \to Y, \; Y \to Z \}$, all dependencies have only a single attribute on the left side. No further minimization is required.
Final Irreducible Set (Minimal Cover)
The resulting set of FDs is:
$X \to Y$
$Y \to Z$
}
Given: $F = \{ A \to BC, \; CD \to E, \; B \to D, \; E \to A \}$
Step 1: Standard Form (Right-side Decomposition)
1) $A \to B$
2) $A \to C$
3) $CD \to E$
4) $B \to D$
5) $E \to A$
Step 2: Delete Redundant FDs We check each FD against the remaining set:
Check $A \to B$: $A^+$ from $\{2, 3, 4, 5\}$. $A^+ = \{A, C\}$. $B \notin A^+$. (Keep)
Check $A \to C$: $A^+$ from $\{1, 3, 4, 5\}$. $A^+ = \{A, B, D\}$. $C \notin A^+$. (Keep)
Check $B \to D$: $B^+$ from $\{1, 2, 3, 5\}$. $B^+ = \{B\}$. $D \notin B^+$. (Keep)
Check $E \to A$: $E^+$ from $\{1, 2, 3, 4\}$. $E^+ = \{E\}$. $A \notin E^+$. (Keep)
Check $CD \to E$: $CD^+$ from $\{1, 2, 4, 5\}$. $CD^+ = \{C, D\}$. $E \notin CD^+$. (Keep)
Current Set: $\{ A \to B, \; A \to C, \; B \to D, \; E \to A, \; CD \to E \}$
Step 3: Minimize Left Side (Extraneous Attributes) Check $CD \to E$ to see if $C$ or $D$ is redundant.
Final Irreducible Set (Minimal Cover)
The set remains unchanged as no redundancies were found.
$A \to BC$
$CD \to E$
$B \to D$
$E \to A$
}
Given Relation $R(A, B, C, D)$ and $FDs = \{ AB \to C, \; A \to C, \; C \to D, \; B \to D \}$
Step 1: Standard Form (Right-side Decomposition)
1) $AB \to C$
2) $A \to C$
3) $C \to D$
4) $B \to D$
Step 2: Delete Redundant FDs Check each FD against the remaining set to see if it can be inferred:
Check $AB \to C$: Compute $(AB)^+$ using $\{2, 3, 4\}$. $(AB)^+ = \{A, B, C, D\}$. Since $C \in (AB)^+$, $AB \to C$ is Redundant and is deleted.
Check $A \to C$: Compute $A^+$ using $\{3, 4\}$. $A^+ = \{A\}$. $C \notin A^+$. (Keep)
Check $C \to D$: Compute $C^+$ using $\{2, 4\}$. $C^+ = \{C\}$. $D \notin C^+$. (Keep)
Check $B \to D$: Compute $B^+$ using $\{2, 3\}$. $B^+ = \{B\}$. $D \notin B^+$. (Keep)
Updated Set: $\{ A \to C, \; C \to D, \; B \to D \}$
Step 3: Minimize Left Side (Extraneous Attributes) We examine the FDs in the updated set for multi-attribute left sides:
$A \to C$: Single attribute LHS. No check needed.
$C \to D$: Single attribute LHS. No check needed.
$B \to D$: Single attribute LHS. No check needed.
Note: Since the only multi-attribute FD ($AB \to C$) was removed in Step 2, no further minimization is required.
Final Irreducible Set (Minimal Cover)
The resulting set of FDs is:
$A \to C$
$C \to D$
$B \to D$
}
Given Relation $R(A, B, C, D)$ and $F = \{ A \to B, \; B \to C, \; AB \to D \}$.
Step 1: Standard Form (RHS Decomposition)
1) $A \to B$
2) $B \to C$
3) $AB \to D$
Step 2: Delete Redundant FDs Check if any entire FD can be inferred from the others:
Check $AB \to D$: $(AB)^+$ from $\{A \to B, B \to C\}$. $(AB)^+ = \{A, B, C\}$. Since $D \notin (AB)^+$, $AB \to D$ is NOT Redundant. It survives Step 2.
Step 3: Minimize Left Side (Extraneous Attributes) We check $AB \to D$ to see if $B$ is extraneous.
Note: After removing $B$, the FD $AB \to D$ simplifies to $A \to D$.
Final Irreducible Set (Minimal Cover)
$A \to B$
$B \to C$
$A \to D$
}
Decomposition
Decomposition is the process of breaking a relation \(R\) into two or more sub-relations \(R_1, R_2, \dots\).
Properties of good decomposition:
Lossless Decomposition: Joining the decomposed relations gives back the original relation; no information is lost.
Dependency Preservation: All functional dependencies in the original relation can be enforced by the decomposed relations.
Lossless/Lossy Join Decomposition
Consider a relation \(R\) which is decomposed into sub-relations \(R_1, R_2, \ldots, R_n\).
This decomposition is called lossless join decomposition when the join of the sub-relations results in the same relation \(R\) that was decomposed.
For lossless join decomposition, we always have: \[ R_1 \bowtie R_2 \bowtie R_3 \ldots \bowtie R_n = R \] where \(\bowtie\) is the natural join operator.
Consider the relation \(R(A, B, C)\):
Decompose \(R\) into \(R_1(A, B)\) and \(R_2(B, C)\):
\(R_1(A, B)\):
\(R_2(B, C)\):
Performing the natural join \(R_1 \bowtie R_2\) gives:
This is the same as the original relation \(R\), hence the decomposition is lossless.
Lossless join decomposition is also known as non-additive join decomposition because no extraneous tuples appear after joining the sub-relations.
Consider a relation \(R\) which is decomposed into sub-relations \(R_1, R_2, \ldots, R_n\).
This decomposition is called lossy join decomposition when the join of the sub-relations does not result in the same relation \(R\).
For lossy join decomposition: \[ R_1 \bowtie R_2 \bowtie R_3 \ldots \bowtie R_n \supseteq R \] where \(\bowtie\) is the natural join operator. Some extraneous tuples appear in the join result.
Consider the relation \(R(A, B, C)\):
Decompose \(R\) into \(R_1(A, C)\) and \(R_2(B, C)\):
\(R_1(A, C)\):
\(R_2(B, C)\):
Performing the natural join \(R_1 \bowtie R_2\) gives:
This relation is not the same as \(R\) and contains extraneous tuples. Hence, the decomposition is lossy.
Lossy join decomposition is also known as careless decomposition because extraneous tuples make identification of original tuples difficult.
Consider a relation \(R\) decomposed into two sub-relations \(R_1\) and \(R_2\):
Condition 1: Union of both sub-relations must contain all attributes of \(R\): \[ R_1 \cup R_2 = R \]
Condition 2: Intersection of both sub-relations must not be null: \[ R_1 \cap R_2 \neq \emptyset \]
Condition 3: Intersection of both sub-relations must be a super key of \(R_1\), \(R_2\), or both: \[ R_1 \cap R_2 = \text{Super key of } R_1 \text{ or } R_2 \]
If all three conditions are satisfied, the decomposition is lossless. If any condition fails, the decomposition is lossy.
Consider \(R(A, B, C, D)\) with functional dependencies \(A \rightarrow B\) and \(C \rightarrow D\). Decompose into \(R_1(A, B)\) and \(R_2(C, D)\).
Solution:
Condition-01: \(R_1 \cup R_2 = \{A, B, C, D\} = R\) \(\rightarrow\) satisfied
Condition-02: \(R_1 \cap R_2 = \emptyset\) \(\rightarrow\) fails
Condition-03: Not checked as Condition-02 failed
Hence, decomposition is lossy.
The Chase Algorithm
To determine if a decomposition $\{R_1, R_2, \dots, R_n\}$ is lossless:
Initialize: Build a tableau (Rows: $R_i$, Cols: Attributes).
Fill: Use real symbols ($a, b, c, \dots$) if attribute is present in $R_i$; otherwise use dummies ($a_i, b_i, c_i, \dots$).
Equate: If two rows match on an FD's LHS, equate their RHS.
Note: Always promote a dummy to a real symbol if possible.
Converge: Stop when no more changes can be made.
Any row is all real symbols $\implies$ Lossless
Otherwise $\implies$ Lossy
Consider $R(A, B, C, D)$ with FDs: $A \rightarrow B, B \rightarrow C, C \rightarrow D$. Decomposed into $R_1(A, B), R_2(B, C), R_3(C, D)$.
Step 1: Initial Tableau
Step 2: Apply $B \rightarrow C$
Rows $R_1$ and $R_2$ match on $B$ ($b$). Promote $c_1$ in $R_1$ to real symbol $c$.
Step 3: Apply $C \rightarrow D$
Now $R_1$ and $R_3$ match on $C$ ($c$). Promote $d_1$ in $R_1$ to real symbol $d$.
Row 1 is all real symbols $\implies$ Lossless.
Consider $R(A, B, C, D)$ with FDs: $A \rightarrow B, C \rightarrow D$. Decomposed into $R_1(A, B), R_2(B, C), R_3(C, D)$.
Step 1: Initial Tableau
Step 2: Apply $C \rightarrow D$
$R_2$ and $R_3$ match on $C$ ($c$). Promote $d_2$ in $R_2$ to $d$.
Step 3: Apply $A \rightarrow B$
No rows match on $A$. No further changes possible. Since no row is $(a, b, c, d)$, it is Lossy.
$R(A, B, C)$ with $A \rightarrow B, B \rightarrow A$. Decomposed into $R_1(A, C), R_2(B, C)$.
Initial Tableau:
Execution: No rows match on $A$ or $B$. However, if we added $C \rightarrow B$: Rows $R_1, R_2$ match on $C$. Promote $b_1 \rightarrow b$. Now $R_1$ is $(a, b, c) \implies$ Lossless.
Dependency Preserving Decomposition
A decomposition of a relation \(R\) into sub-relations \(R_1, R_2, \dots, R_n\) is called dependency preserving if all functional dependencies of \(R\) satisfy at least one of the following:
The dependency is fully contained in one of the sub-relations \(R_i\), or
The dependency can be derived from the FDs of the sub-relations without performing any joins.
In other words, all constraints of the original relation can be enforced locally in the sub-relations.
Ensures data integrity after decomposition.
Avoids expensive joins for enforcing constraints.
Desired in normalization (3NF or BCNF) to combine lossless join and dependency preservation.
Suppose a relation \(R\) with functional dependencies \(F\) is decomposed into sub-relations \(R_1, R_2, \dots, R_n\). To check if the decomposition is dependency preserving:
Find the functional dependencies \(F_i\) that hold in each sub-relation \(R_i\).
Compute \(F' = F_1 \cup F_2 \cup \dots \cup F_n\).
Compare \(F'\) with the original dependency set \(F\):
If all dependencies in \(F\) are in \(F'\) or derivable from \(F'\), the decomposition is dependency preserving.
If any dependency in \(F\) is missing and cannot be derived, the decomposition is not dependency preserving.
Let \(R(A, B, C, D)\) with FD set: \[ F = \{A \rightarrow B, A \rightarrow C, C \rightarrow D\} \]
Decompose \(R\) into: \[ R_1(A, B, C), \quad R_2(C, D) \]
Step 1: Find FDs in sub-relations
\(F_1 = \{A \rightarrow B, A \rightarrow C\}\) in \(R_1\)
\(F_2 = \{C \rightarrow D\}\) in \(R_2\)
Step 2: Combine FDs: \[ F' = F_1 \cup F_2 = \{A \rightarrow B, A \rightarrow C, C \rightarrow D\} = F \]
Conclusion: All original FDs are preserved. Hence, the decomposition is dependency preserving.
Let \(R(P, Q, R, S)\) with FD set: \[ F = \{PQ \rightarrow R, R \rightarrow S, S \rightarrow P\} \]
Decompose \(R\) into: \[ R_1(P, Q, R), \quad R_2(R, S) \]
Step 1: Find FDs in sub-relations
\(F_1 = \{PQ \rightarrow R, R \rightarrow P\}\) in \(R_1\)
\(F_2 = \{R \rightarrow S\}\) in \(R_2\)
Step 2: Combine FDs: \[ F' = F_1 \cup F_2 = \{PQ \rightarrow R, R \rightarrow S, R \rightarrow P\} \]
Step 3: Check original FDs
\(PQ \rightarrow R\) → present in \(F'\)
\(R \rightarrow S\) → present in \(F'\)
\(S \rightarrow P\) → missing, cannot be derived from \(F'\)
Conclusion: Not all original FDs are preserved. Hence, the decomposition is not dependency preserving.
Consider relation \(R(A, B, C, D, E)\) with functional dependencies: \[ F = \{A \rightarrow B, B \rightarrow C, C \rightarrow D, D \rightarrow E\} \]
Decompose \(R\) into: \[ R_1(A, B, C), \quad R_2(C, D, E) \]
Step 1: Find FDs in sub-relations
\(F_1 = \{A \rightarrow B, B \rightarrow C\}\) in \(R_1\)
\(F_2 = \{C \rightarrow D, D \rightarrow E\}\) in \(R_2\)
Step 2: Combine FDs: \[ F' = F_1 \cup F_2 = \{A \rightarrow B, B \rightarrow C, C \rightarrow D, D \rightarrow E\} = F \]
Step 3: Check all original FDs: All are present in \(F'\).
Conclusion: The decomposition is dependency preserving.
Consider relation \(R(P, Q, R, S, T)\) with functional dependencies: \[ F = \{P \rightarrow Q, Q \rightarrow R, R \rightarrow S, S \rightarrow T, T \rightarrow P\} \]
Decompose \(R\) into: \[ R_1(P, Q, R), \quad R_2(R, S, T) \]
Step 1: Find FDs in sub-relations
\(F_1 = \{P \rightarrow Q, Q \rightarrow R\}\) in \(R_1\)
\(F_2 = \{R \rightarrow S, S \rightarrow T\}\) in \(R_2\)
Step 2: Combine FDs: \[ F' = F_1 \cup F_2 = \{P \rightarrow Q, Q \rightarrow R, R \rightarrow S, S \rightarrow T\} \]
Step 3: Check original FDs: The dependency \(T \rightarrow P\) is missing and cannot be derived from \(F'\).
Conclusion: The decomposition is not dependency preserving.
Normal Forms
The main reason for normalizing relations is to remove anomalies in the database. Failure to eliminate anomalies can lead to data redundancy, data inconsistency, and other integrity problems as the database grows.
Normalization consists of a series of guidelines that help in creating a well-structured database.
Data modification anomalies can be categorized into three types:
Insertion Anomaly: Occurs when one cannot insert a new tuple into a relation due to lack of required data.
Deletion Anomaly: Occurs when the deletion of data unintentionally results in loss of other important data.
Update Anomaly: Occurs when updating a single data value requires multiple rows to be updated.
The standard normal forms in database design are defined as follows:
First Normal Form (1NF): A relation is in 1NF if all attributes contain atomic (indivisible) values.
Second Normal Form (2NF): A relation is in 2NF if it is in 1NF and all non-key attributes are fully functionally dependent on the candidate key.
Third Normal Form (3NF): A relation is in 3NF if it is in 2NF and has no transitive dependencies (i.e., non-key attributes depend only on candidate keys).
Boyce-Codd Normal Form (BCNF): A relation is in BCNF if it is in 3NF and for every functional dependency \(X \rightarrow Y\), \(X\) is a superkey.
Fourth Normal Form (4NF): A relation is in 4NF if it is in BCNF and does not contain any multi-valued dependencies.
Fifth Normal Form (5NF or Project-Join Normal Form): A relation is in 5NF if it is in 4NF and every join dependency is implied by the candidate keys.
First Normal Form (1NF)
A relation is said to be in First Normal Form (1NF) if:
Each attribute of every tuple contains only an atomic value, i.e., indivisible value.
Multi-valued attributes are not allowed; a single cell cannot contain a set, list, or nested table.
Attributes can be null, but must not be non-atomic (e.g., a list of values).
OR
A relation is in 1NF if the value of every attribute in each tuple is either single-valued or null.
By default, every relation in a relational database is considered to be in 1NF, because atomicity is part of the definition of a relation.
1NF is the first step in normalization, and all higher normal forms assume the relation is already in 1NF.
Problem: Check if the following relation is in 1NF and convert it if necessary.
Analysis:
The Subjects attribute contains multiple values for some students.
This violates the atomicity requirement of 1NF.
Solution: Convert to 1NF Rewrite the relation so that each cell contains a single value:
Conclusion: The above relation is now in 1NF because each attribute contains atomic values only.
Problem: Consider a relation storing employee skills:
Analysis:
The Skills attribute contains multiple values for some employees.
This violates the 1NF requirement of atomic values.
Solution: Convert to 1NF
Conclusion: Each cell now contains a single atomic value, so the relation is in 1NF.
Second Normal Form (2NF)
A partial dependency occurs when a non-prime attribute is functionally dependent on a part (subset) of a candidate key rather than the whole key.
Formal Definition: Let \(A \rightarrow B\) be a functional dependency in relation \(R\). It is a partial dependency if:
\(A\) is a proper subset of some candidate key, and
\(B\) is a non-prime attribute.
Note: - To avoid partial dependency, an incomplete candidate key must not determine any non-prime attribute. - An incomplete candidate key can determine prime attributes without violating 2NF.
A relation \(R\) is in Second Normal Form (2NF) if and only if:
\(R\) is already in 1NF.
There are no partial dependencies in \(R\).
Procedure to Decompose a Relation into 2NF
To decompose a relation \(R\) into Second Normal Form (2NF), follow these steps:
Ensure 1NF: Verify that \(R\) is already in First Normal Form (1NF), i.e., all attributes contain atomic values.
Identify Candidate Keys: Determine all candidate keys of \(R\). Identify prime attributes (attributes in any candidate key) and non-prime attributes (attributes not in any candidate key).
Identify Partial Dependencies: Find all functional dependencies where a non-prime attribute is dependent on a part (subset) of a candidate key. These are partial dependencies.
Create New Relations for Partial Dependencies: For each partial dependency \(X \rightarrow Y\), create a separate relation containing:
The determinant \(X\) (subset of candidate key)
All attributes functionally dependent on \(X\) (\(Y\))
Retain Remaining Attributes: Create a relation containing:
All candidate key attributes
Remaining non-prime attributes not included in the new relations
Verify 2NF: Check that in each resulting relation:
No non-prime attribute is partially dependent on any candidate key.
Each relation is in 1NF.
Result: The original relation \(R\) is now decomposed into a set of relations that are in 2NF.
Consider relation $R(A, B, C, D, E)$ with functional dependencies: \[ A \rightarrow B, \quad B \rightarrow E, \quad C \rightarrow D \]
Step 1: Identify Candidate Key
$(AC)^+ = \{A, C, B, E, D\}$. Candidate key = AC.
Prime attributes = $\{A, C\}$; Non-prime = $\{B, D, E\}$.
Step 2: Identify Partial Dependencies (Prime $\rightarrow$ Non-Prime)
- $A \rightarrow B$: Partial Dependency ($A \subset AC$).
- $C \rightarrow D$: Partial Dependency ($C \subset AC$).
- $B \rightarrow E$: NOT a partial dependency (Non-prime $\rightarrow$ Non-prime).
Step 3: Create New Relations for Partial Dependencies
- $R_1(A, B, E)$: Handles partial key $A$. $E$ moves here because $B \rightarrow E$ must follow $B$.
- $R_2(C, D)$: Handles partial key $C$.
Step 4: Retain the Full Candidate Key
- $R_3(A, C)$: To act as the bridge/link.
Conclusion: Decomposition $\{R_1, R_2, R_3\}$ is in 2NF.
Consider the relation $R(V, W, X, Y, Z)$ with functional dependencies: \[ VW \rightarrow XY, \quad Y \rightarrow V, \quad WX \rightarrow YZ \]
Step 1: Identify Candidate Keys
Candidate keys = VW, WX, WY.
Prime attributes = $\{V, W, X, Y\}$; Non-prime = $\{Z\}$.
Step 2: Identify Partial Dependencies
Check if any non-prime attribute depends on a proper subset of a key:
- $Z$ depends on $WX$ (Full Key).
- No non-prime attribute depends on $V, W, X,$ or $Y$ individually.
Conclusion: No partial dependency exists. Relation is in 2NF.
Consider relation $R(A, B, C, D, E)$ with functional dependencies: \[ A \rightarrow B, \quad B \rightarrow E, \quad C \rightarrow D \]
Step 1: Analysis
Candidate key = AC. Prime = $\{A, C\}$; Non-prime = $\{B, D, E\}$.
Step 2: Identify Violations
- $A \rightarrow B$: Partial Dependency ($A$ is prime, $B$ is non-prime).
- $B \rightarrow E$: Transitive Dependency (Non-prime $\rightarrow$ Non-prime). Not a 2NF violation, but must be preserved.
Step 3: Decomposition (Lossless & DP)
- $R_1(A, B, E)$ (Fixes $A \rightarrow B$ and preserves $B \rightarrow E$).
- $R_2(C, D)$ (Fixes $C \rightarrow D$).
- $R_3(A, C)$ (Bridge table for the Full Key).
Conclusion: Each sub-relation is now in 2NF.
Consider $R(A, B, C, D, E, F, G, H, I, J)$ with functional dependencies: \[ AB \rightarrow C, \quad AD \rightarrow GH, \quad BD \rightarrow EF, \quad A \rightarrow I, \quad H \rightarrow J \]
Step 1: Analysis
Candidate key = ABD.
Prime = $\{A, B, D\}$; Non-prime = $\{C, E, F, G, H, I, J\}$.
Step 2: Identify Partial Dependencies
- $AB \rightarrow C, \ AD \rightarrow GH, \ BD \rightarrow EF, \ A \rightarrow I$ are Partial ($AB, AD, BD, A \subset ABD$).
- $H \rightarrow J$ is Transitive (Non-prime $\rightarrow$ Non-prime).
Step 3: Create New Relations
- $R_1(A, B, C)$
- $R_2(A, D, G, H, J)$: $J$ moves here with $H$ to preserve dependency $H \rightarrow J$.
- $R_3(B, D, E, F)$
- $R_4(A, I)$
- $R_5(A, B, D)$: The Full Key Bridge.
Conclusion: This decomposition is Lossless, Dependency Preserving, and in 2NF.
Third Normal Form (3NF)
A transitive dependency $A \rightarrow B$ exists if and only if:
$A$ is not a super key, and
$B$ is a non-prime attribute.
NOTE: Transitive dependency must not exist for non-prime attributes. Transitive dependency can exist for prime attributes.
A relation is in Third Normal Form (3NF) if and only if:
The relation is already in 2NF, and
No non-prime attribute is transitively dependent on any candidate key.
A relation $R$ is in 3NF if for every non-trivial functional dependency $A \rightarrow B$:
$A$ is a super key, or
$B$ is a prime attribute.
To decompose a relation into 3NF, follow these steps:
Identify all candidate keys of the relation.
Identify prime attributes (attributes that are part of any candidate key) and non-prime attributes.
Examine each functional dependency $A \rightarrow B$:
If $A$ is not a super key and $B$ is a non-prime attribute, it is a transitive dependency.
For each transitive dependency, create a separate relation containing the determinant and the dependent attribute(s).
Remove the transitive dependencies from the original relation.
Repeat until no relation has transitive dependencies, ensuring all resulting relations are in 3NF.
Consider relation $R(A, B, C, D, E)$ with functional dependencies: \[ A \rightarrow BC, \quad CD \rightarrow E, \quad B \rightarrow D, \quad E \rightarrow A \]
Step 1: Identify candidate keys
Check which attribute sets determine all other attributes: \[ \text{Candidate keys: } A, E, CD, BC \]
Step 2: Identify prime and non-prime attributes
Prime attributes = $\{A, B, C, D, E\}$ (all part of some candidate key)
Non-prime attributes = $\{\}$ (none)
Step 3: Check for transitive dependency
Transitive dependency exists if $A \rightarrow B$ (A not super key) and $B$ is non-prime. Here:
No non-prime attributes exist.
Therefore, no transitive dependency exists.
Step 4: Decomposition
Not required, as the relation has no transitive dependencies.
Step 5: Remove transitive dependencies
Not applicable.
Step 6: Verify 3NF
All non-prime attributes (none) are directly dependent on candidate keys.
Conclusion: Relation is in 3NF.
Consider relation $R(A, B, C, D)$ with functional dependencies: \[ AB \rightarrow CD, \quad A \rightarrow B, \quad B \rightarrow C \]
Step 1: Identify candidate keys
- $AB$ determines $CD$ - $A$ alone does not determine all attributes - $B$ alone does not determine all attributes
\[ \text{Candidate key: } AB \]
Step 2: Identify prime and non-prime attributes
Prime attributes = $\{A, B\}$
Non-prime attributes = $\{C, D\}$
Step 3: Check for transitive dependency
- $A \rightarrow B$ (A is subset of candidate key AB) and $B \rightarrow C$ - $C$ is non-prime → transitive dependency exists ($A \rightarrow C$ indirectly)
Step 4: Decompose relation
Create separate relations for transitive dependencies:
$R_1(A, B)$ (key $A$)
$R_2(B, C, D)$ (key $B$)
Step 5: Remove transitive dependencies
- Now, $C$ and $D$ are directly dependent on $B$ in $R_2$ - $B$ is fully dependent on $A$ in $R_1$
Step 6: Verify 3NF
- $R_1(A, B)$: $A$ is super key → 3NF satisfied - $R_2(B, C, D)$: $B$ is super key → 3NF satisfied
Conclusion: Original relation violated 3NF, decomposition produces 3NF relations.
Consider relation $R(A, B, C, D, E)$ with functional dependencies: \[ A \rightarrow B, \quad B \rightarrow E, \quad C \rightarrow D \]
Step 1: Identify candidate keys
- $A$ determines $B$, $B$ determines $E$ → $A$ can determine $B$ and $E$ - $C$ determines $D$ - To cover all attributes: candidate keys = $A, C$
Step 2: Identify prime and non-prime attributes
- Prime attributes = $\{A, C\}$ - Non-prime attributes = $\{B, D, E\}$
Step 3: Check for transitive dependency
- $A \rightarrow B$ and $B \rightarrow E$ → $A \rightarrow E$ (transitive) - $E$ is non-prime → violates 3NF
Step 4: Decompose relation
- $R_1(A, B, E)$ with key $A$ - $R_2(C, D)$ with key $C$
Step 5: Remove transitive dependencies
- $R_1$: $B$ and $E$ are now fully dependent on $A$ - $R_2$: no transitive dependencies
Step 6: Verify 3NF
- $R_1(A, B, E)$: $A$ is super key → 3NF satisfied - $R_2(C, D)$: $C$ is super key → 3NF satisfied
Conclusion: Decomposition successfully converts relation into 3NF.
Boyce-Codd Normal Form (BCNF)
A relation is in BCNF if and only if:
The relation is already in 3NF.
For every non-trivial functional dependency \(A \rightarrow B\), \(A\) is a super key of the relation.
To decompose a relation \(R\) into BCNF:
Identify all candidate keys of \(R\).
Check each functional dependency \(A \rightarrow B\):
If \(A\) is a super key, it satisfies BCNF.
If \(A\) is not a super key, BCNF is violated.
For each violating dependency \(A \rightarrow B\), decompose \(R\) into:
\(R_1(A, B)\) — containing the violating dependency.
\(R_2(R - B)\) — the remaining attributes.
Repeat steps 1–3 for all decomposed relations until all relations satisfy BCNF.
Consider a relation \( R (A, B, C) \) with functional dependencies: \[ A \rightarrow B, \quad B \rightarrow C, \quad C \rightarrow A \]
Step 1: Identify candidate keys: \(A, B, C\)
Step 2: Check BCNF condition: Each determinant (\(A, B, C\)) is a candidate key.
Conclusion: The relation already satisfies BCNF.
Consider a relation \(R(A, B, C)\) with functional dependencies: \[ AB \rightarrow C, \quad C \rightarrow B \]
Step 1: Identify candidate keys: \((AB)^+ = ABC\), \((AC)^+ = ABC\) Candidate keys: \(AB, AC\) Prime attributes: \(A, B, C\) Non-prime attributes: None
Step 2: Check BCNF condition:
\(AB \rightarrow C\) is fine (AB is a super key)
\(C \rightarrow B\) violates BCNF because \(C\) is not a super key
Step 3: Decompose violating relation:
\(R_1(C, B)\) with key \(C\)
\(R_2(A, C)\) with key \(AC\)
Step 4: Check BCNF for new relations: Both \(R_1\) and \(R_2\) now satisfy BCNF.
Conclusion: Original relation decomposed into BCNF: \[ R_1(C, B), \quad R_2(A, C) \]
Original relation: \[ R(A, B, C) \] \[ \begin{array}{|c|c|c|} \hline A & B & C \\ \hline a & 1 & x \\ b & 2 & y \\ c & 2 & z \\ c & 3 & w \\ d & 3 & w \\ e & 3 & w \\ \hline \end{array} \]
Functional dependencies: \(AB \rightarrow C, C \rightarrow B\)
Step 1: Candidate keys: \(AB, AC\)
Step 2: BCNF Violation: \(C \rightarrow B\) (C not a super key)
Step 3: Decomposition: \[ R_1(C, B) = \begin{array}{|c|c|} \hline C & B \\ \hline x & 1 \\ y & 2 \\ z & 2 \\ w & 3 \\ \hline \end{array} \] \[ R_2(A, C) = \begin{array}{|c|c|} \hline A & C \\ \hline a & x \\ b & y \\ c & z \\ c & w \\ d & w \\ e & w \\ \hline \end{array} \]
Step 4: Check BCNF: Both \(R_1\) and \(R_2\) satisfy BCNF.
Conclusion: Decomposition removes redundancy and ensures BCNF.
Multi-valued Dependency and Fourth Normal Form (4NF)
The Fourth Normal Form (4NF) is satisfied if and only if:
The relation is in BCNF.
The relation contains no non-trivial multi-valued dependencies (MVDs) other than a candidate key.
A multi-valued dependency (MVD) in a relation \(R\) occurs when, for a single value of attribute \(A\), there can be multiple independent values of attribute \(B\), such that the presence of \(B\) values is independent of other attributes in \(R\).
Notation: \(A \twoheadrightarrow B\)
Example: If a student can have multiple phone numbers and multiple courses, then: \[ \text{SID} \twoheadrightarrow \text{Phone}, \quad \text{SID} \twoheadrightarrow \text{Course} \]
Here, the phone numbers and courses are independent of each other, causing a multi-valued dependency.
To decompose a relation \(R\) into 4NF:
Ensure that the relation is already in BCNF.
Identify all multi-valued dependencies \(A \twoheadrightarrow B\).
For each MVD that violates 4NF (i.e., \(A\) is not a super key):
Create a new relation \(R_1(A, B)\) for the MVD.
Create another relation \(R_2(R - B)\) for the remaining attributes.
Repeat until all relations satisfy 4NF.
Consider the following database tables:
Table R1 (Students):
Table R2 (Courses):
Step 1: Cross-product causes MVDs:
Step 2: Identify multi-valued dependencies:
\( \text{SID} \twoheadrightarrow \text{CID} \)
\( \text{SID} \twoheadrightarrow \text{CNAME} \)
Step 3: Check 4NF condition: SID is not a super key for the combined table. Hence, the relation violates 4NF.
Step 4: Decomposition into 4NF:
\(R_1(SID, CID)\)
\(R_2(SID, CNAME)\)
\(R_3(SID, SNAME)\) (to maintain student info)
Step 5: Check 4NF for new relations: All decomposed relations now satisfy 4NF.
Join Dependency and Fifth Normal Form (5NF)
A relation \(R\) is in Fifth Normal Form (5NF) if and only if:
The relation is already in 4NF.
Every join dependency in \(R\) is implied by the candidate keys.
The relation cannot be further decomposed into smaller relations without losing the lossless join property.
A decomposition of a relation is said to have a lossless join if, after decomposing the relation into two or more relations, performing a natural join on these decomposed relations reconstructs exactly the original relation without generating any spurious tuples.
To check and decompose a relation \(R\) into 5NF:
Ensure that the relation is already in 4NF.
Identify all join dependencies (JD) in the relation.
For each join dependency \(JD: R_1 \Join R_2 \Join \dots \Join R_n = R\):
Check if the decomposition is implied by the candidate keys.
If not, decompose \(R\) into smaller relations such that each decomposition satisfies the lossless join property.
Repeat until all join dependencies are satisfied by the candidate keys.
Consider the relation \(ACP(Agent, Company, Product)\) representing which agent sells which product for which company.
Table ACP:
Step 1: Identify join dependency: The relation has a natural join dependency among: \[ (Agent, Company),\quad (Agent, Product),\quad (Company, Product) \]
Step 2: Decompose into 5NF:
\(R_1(Agent, Company)\)
\(R_2(Agent, Product)\)
\(R_3(Company, Product)\)
Step 3: Check lossless join: The natural join of \(R_1, R_2, R_3\) over the common attributes reconstructs the original table \(ACP\) exactly, without generating spurious tuples.
Step 4: Conclusion: All redundancies are eliminated, and the relation now satisfies 5NF. No further non-loss decompositions are possible.