Consider a relational database schema with a relation π
(π΄, π΅, πΆ, π·). If {π΄, π΅} and
{π΄, πΆ} are the only two candidate keys of the relation π
, then the number of superkeys
of relation π
is ______. (answer in integer)
Consider a relational database schema with a relation π
(π΄, π΅, πΆ, π·). If {π΄, π΅} and
{π΄, πΆ} are the only two candidate keys of the relation π
, then the number of superkeys
of relation π
is ______. (answer in integer)
Show Hint
Correct Answer: 6
Solution and Explanation
A relation \(R(A, B, C, D)\) has candidate keys \(\{A, B\}\) and \(\{A, C\}\). We need to count the total number of superkeys of \(R\).
Step 1: Recall the definition of a superkey.
A superkey is any subset of attributes of \(R\) that contains at least one candidate key as a subset. Since \(R\) has 4 attributes, the total number of possible attribute subsets is \(2^4 = 16\). We must find how many of these 16 subsets contain \(\{A, B\}\) or contain \(\{A, C\}\).
Step 2: Count subsets containing candidate key \(\{A, B\}\).
If a subset must contain \(A\) and \(B\), the remaining attributes \(\{C, D\}\) can each be independently present or absent. This gives \(2^2 = 4\) subsets:
\[\{A,B\},\ \{A,B,C\},\ \{A,B,D\},\ \{A,B,C,D\}\]
Step 3: Count subsets containing candidate key \(\{A, C\}\).
Similarly, if a subset must contain \(A\) and \(C\), the remaining attributes \(\{B, D\}\) can each be independently present or absent, giving \(2^2 = 4\) subsets:
\[\{A,C\},\ \{A,B,C\},\ \{A,C,D\},\ \{A,B,C,D\}\]
Step 4: Apply the principle of inclusion-exclusion.
Some subsets appear in both lists (they contain both \(\{A,B\}\) and \(\{A,C\}\), i.e. they contain \(\{A,B,C\}\)). With \(D\) free to be present or absent, there are \(2^1 = 2\) such overlapping subsets: \(\{A,B,C\}\) and \(\{A,B,C,D\}\).
Using inclusion-exclusion, the total number of distinct superkeys is:
\[|S_{AB} \cup S_{AC}| = |S_{AB}| + |S_{AC}| - |S_{AB} \cap S_{AC}| = 4 + 4 - 2 = 6\]
Step 5: List all superkeys to verify.
\[\{A,B\},\ \{A,C\},\ \{A,B,C\},\ \{A,B,D\},\ \{A,C,D\},\ \{A,B,C,D\}\]
This confirms exactly 6 superkeys.
Final Answer:
\[\boxed{6}\]
Top GATE CS Computer Science and IT Engineering Questions
- Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:
(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT sequence of steps? - Which ONE of the following statements is FALSE regarding the symbol table?
- Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
A schedule of three database transactions \(T_1\), \(T_2\), and \(T_3\) is shown. \(R_i(A)\) and \(W_i(A)\) denote read and write of data item A by transaction \(T_i\), \(i = 1, 2, 3\). The transaction \(T_1\) aborts at the end. Which other transaction(s) will be required to be rolled back?
Top GATE CS Functional Dependency Questions
Let π, π, π and π be the attributes of a relation in a relational schema. Let π βΆπ
indicate functional dependency in the context of a relational database, where
π, π β{π, π, π , π}.
Which of the following options is/are always true?In the context of schema normalization in relational DBMS, consider a set F of
functional dependencies. The set of all functional dependencies implied by F is
called the closure of F. To compute the closure of F, Armstrongβs Axioms can be
applied. Consider π, π, and π as sets of attributes over a relational schema. The three
rules of Armstrongβs Axioms are described as follows.
Reflexivity: If πβπ , then πβπ
Augmentation: If πβπ, then ππβππ for any Z
Transitivity: If πβπ and πβπ, then πβπ
The additional rule of Union is defined as follows.
Union: If πβπ and πβπ, then πβππ
It can be proved that the additional rule of Union is also implied by the three rules
of Armstrongβs Axioms. Listed below are four combinations of these three rules.
Which one of these combinations is both necessary and sufficient for the proof ?
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Lnβ1 + Lnβ2, for n β₯ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 Γ 10^8\) meter per second. What is the minimum frame size in bits ?