GATE CS 2021 Set 1 Q33 — Normal Forms

To determine whether the decompositions $D_1$ and $D_2$ are lossless or lossy, we analyze their join properties using the given functional dependencies (FDs):

$$PQ\rightarrow X;\quad P\rightarrow YX;\quad Q\rightarrow Y;\quad Y\rightarrow ZW$$

1. Analysis of $D_1 = \{R_1(P,Q,S,T), R_2(P,T,X), R_3(Q,Y), R_4(Y,Z,W)\}$:

• Join $R_3(Q,Y)$ and $R_4(Y,Z,W)$: Their intersection is $R_3 \cap R_4 = \{Y\}$. Since $Y \rightarrow ZW$, $Y$ is a superkey for $R_4$. Thus, this join is lossless, yielding $R_{34}(Q,Y,Z,W)$.
• Join $R_1(P,Q,S,T)$ and $R_{34}(Q,Y,Z,W)$: Their intersection is $R_1 \cap R_{34} = \{Q\}$. Since $Q \rightarrow Y$ and $Y \rightarrow ZW$, we have $Q \rightarrow YZW$. Thus, $Q$ is a superkey for $R_{34}$, making this join lossless, yielding $R_{134}(P,Q,S,T,Y,Z,W)$.
• Join $R_2(P,T,X)$ and $R_{134}(P,Q,S,T,Y,Z,W)$: Their intersection is $R_2 \cap R_{134} = \{P, T\}$. Since $P \rightarrow YX \implies P \rightarrow X$, the attribute set $\{P, T\}$ functionally determines $X$. Thus, $\{P, T\}$ is a superkey for $R_2$, making this final join lossless.

Therefore, $D_1$ is a lossless decomposition.

2. Analysis of $D_2 = \{R_1(P,Q,S), R_2(T,X), R_3(Q,Y), R_4(Y,Z,W)\}$:

• Consider the relation $R_2(T,X)$. The set of attributes in all other relations is $R_1 \cup R_3 \cup R_4 = \{P, Q, S, Y, Z, W\}$.
• The intersection is $R_2 \cap (R_1 \cup R_3 \cup R_4) = \{T, X\} \cap \{P, Q, S, Y, Z, W\} = \emptyset$.
• Since the intersection is empty, $R_2$ cannot be joined losslessly with any other relation.

Therefore, $D_2$ is a lossy decomposition.