retagged by
675 views
4 votes
4 votes

Consider the relation $R(X\;Y\;W\;M\;E\;G),$

with $FD$ set $\{XY \rightarrow W, E \rightarrow G, XW \rightarrow Y,  YW \rightarrow X, Y \rightarrow M, XM \rightarrow E \}.$

Following are two decompositions of $R:$

  • $P_1 = \left \{ YW, XY, EG, XYME \right \}$
  • $P_2 = \left \{ XMG , XYW, XWME \right \}$


Which of the below statements about $P_1$ and $P_2$ is TRUE?

  1. $P_2$ is lossless-join decomposition but not $P_1$.
  2. Neither $P_1$ nor $P_2$ are lossless-join decompositions.
  3. Both $P_1$ and $P_2$ are lossless-join decompositions.
  4. $P_1$ is lossless-join decomposition but not $P_2$.
retagged by

1 Answer

Best answer
10 votes
10 votes

Condition for lossless-join decomposition of a relation $R$ to $R_1$ and $R_2$ is $R_1 \cap R_2 \to R_1$ or$R_1 \cap R_2 \to R_2$. (Also the union of all the attributes in the decomposed relation must form the original relation)

Here, we have decomposition into more than $2$ relations. So, we need to ensure some join order under which we can show lossless-join property and only if no such ordering exists, decomposition is lossy.

The general algorithm for seeing this is given by Chase Algorithm. Here, I'm using a brute-force approach starting with the largest decomposed relation.

For $P_1$,

  • for $R_1 = XYME$ and $R_2 = EG,$ common attribute set is $E$ and $E$ is the key of $EG.$
  • for $R_1 = XYMEG$ and $R_2 = XY,$ common attribute set is $XY$ and $XY$ is the key of $XY.$
  • for $R_1 = XYMEG$ and $R_2 = YW,$ common attribute set is $Y$ but $Y$ is not a key of either $R_1$ nor $R_2.$
  • So, $P_1$ is not lossless-join decomposition. Even if we try any other join order we cannot get the lossless-join condition here.

For $P_2$,

  • for $R_1=XWME$ and $R_2=XYW,$ common attribute set is $XW$ and $XW$ is the key of $XWY.$
  • for $R_1=XYWME$ and $R_2=XMG,$ common attribute set is $XM$ and $XM$ is the key of $XMG.$
  • So, $P_2$ is lossless-join decomposition.
selected by
Answer: