Question:medium
Consider a relational database schema with a relation \(R(A, B, C, D)\). If \(\{A, B\}\) and \(\{A, C\}\) are the only two candidate keys of the relation \(R\), then the number of superkeys of relation \(R\) is ______.
Consider a relational database schema with a relation \(R(A, B, C, D)\). If \(\{A, B\}\) and \(\{A, C\}\) are the only two candidate keys of the relation \(R\), then the number of superkeys of relation \(R\) is ______.
Show Hint
A superkey is any superset of a candidate key. Count the supersets of each candidate key separately, then use inclusion-exclusion to avoid double counting.
Updated On: Jul 22, 2026
Show Solution
Correct Answer: 6
Solution and Explanation
Step 1 (Alternate method - complement counting): The total number of subsets of {A, B, C, D} is 2^4 = 16 (including the empty set). Count the subsets that fail to be superkeys instead, then subtract from 16.
Step 2: A subset S is NOT a superkey exactly when it contains neither {A, B} nor {A, C} as a subset, i.e. S is missing at least one of A or B, AND S is missing at least one of A or C.
Step 3 (Case i - S does not contain A at all): Then S automatically cannot contain {A, B} or {A, C} (both require A). With A excluded and B, C, D free, this gives 2^3 = 8 such subsets.
Step 4 (Case ii - S contains A but is still not a superkey): Then S must exclude B (otherwise {A, B} would be contained) AND exclude C (otherwise {A, C} would be contained). With A included, B and C excluded, and D free, this gives 2^1 = 2 such subsets: {A} and {A, D}.
Step 5 (Total non-superkeys): 8 + 2 = 10.
Step 6 (Superkeys): Total subsets - non-superkeys = 16 - 10 = 6, matching the direct union calculation.
\[ \boxed{6} \]
Was this answer helpful?
2
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems