Consider the relation \(R(P,Q,S,T,X,Y,Z,W)\) with the following functional dependencies:
\[ PQ \rightarrow X; P \rightarrow YX; Q \rightarrow Y; Y \rightarrow ZW \] Consider the decomposition of the relation \(R\) into the constituent relations according to the following two decomposition schemes. \[ \begin{aligned} D_1 &: R = [(P,Q,S,T);\; (P,T,X);\; (Q,Y);\; (Y,Z,W)] \\ D_2 &: R = [(P,Q,S);\; (T,X);\; (Q,Y);\; (Y,Z,W)] \end{aligned} \] Which one of the following options is correct?
Consider the relation \(R(P,Q,S,T,X,Y,Z,W)\) with the following functional dependencies:
\[ PQ \rightarrow X; P \rightarrow YX; Q \rightarrow Y; Y \rightarrow ZW \] Consider the decomposition of the relation \(R\) into the constituent relations according to the following two decomposition schemes. \[ \begin{aligned} D_1 &: R = [(P,Q,S,T);\; (P,T,X);\; (Q,Y);\; (Y,Z,W)] \\ D_2 &: R = [(P,Q,S);\; (T,X);\; (Q,Y);\; (Y,Z,W)] \end{aligned} \] Which one of the following options is correct?
Show Hint
- \(D_1\) is a lossless decomposition, but \(D_2\) is a lossy decomposition.
- \(D_1\) is a lossy decomposition, but \(D_2\) is a lossless decomposition.
- Both \(D_1\) and \(D_2\) are lossless decompositions.
- Both \(D_1\) and \(D_2\) are lossy decompositions.
The Correct Option is A
Solution and Explanation
Step 1: Identify candidate keys of \(R\).
Using the given functional dependencies:
From \(P \rightarrow YX\) and \(Y \rightarrow ZW\), we get \(P \rightarrow X,Y,Z,W\).
From \(Q \rightarrow Y\), and already having \(Y \rightarrow ZW\), we get additional attributes.
Thus, \((P,Q,S,T)\) forms a key for \(R\).
Step 2: Check decomposition \(D_1\).
The relation \((P,Q,S,T)\) contains a key of \(R\). Hence, by the lossless join test, \(D_1\) is a lossless decomposition.
Step 3: Check decomposition \(D_2\).
None of the decomposed relations in \(D_2\) contains a key of the original relation \(R\).
Therefore, joining the decomposed relations may produce spurious tuples.
Step 4: Conclusion.
Thus, \(D_1\) is lossless, while \(D_2\) is lossy.
Final Answer: (A)
Top Questions on Normal Forms
- In a relational data model, which one of the following statements is TRUE?
- Suppose the following functional dependencies hold on a relation \(U\) with attributes \(P, Q, R, S,\) and \(T\):
\[ P \rightarrow QR, RS \rightarrow T \] Which of the following functional dependencies can be inferred from the above functional dependencies?
Questions Asked in GATE CS exam
- With respect to a TCP connection between a client and a server, which of the following is true?
- GATE CS - 2026
- Computer Networks
- Let $P, Q, R, S$ be relational schemas. Let ``$\rightarrow$'' indicate a functional dependency (FD) in this context. Which of the following best describes the meaning of a functional dependency?
- GATE CS - 2026
- Database Management Systems
- Let a Non-deterministic Finite Automaton (NFA) have 6 states over a finite alphabet. Which of the following cannot be the number of states in a minimal Deterministic Finite Automaton (DFA) that is equivalent to this NFA?
- GATE CS - 2026
- Theory of Computations
- A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?
- GATE CS - 2026
- Computer Organization and Architecture
- Consider $Z = X - Y$, where $X$, $Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:
- GATE CS - 2026
- Computer Organization and Architecture