Question

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 ______.

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.

Answer 1

Correct Answer: 6

Step 1 (Concept): A candidate key is a minimal attribute set that uniquely determines every attribute of the relation. A superkey is any attribute set that uniquely determines every attribute - equivalently, any set that contains at least one candidate key as a subset. So the full collection of superkeys is the union, over every candidate key, of that key together with any subset of the remaining attributes.

Step 2 (Given data): R(A, B, C, D) has 4 attributes. The only two candidate keys are {A, B} and {A, C} (no other minimal key exists).

Step 3 (Supersets of {A, B}): The attributes not in {A, B} are {C, D} (2 attributes), so there are 2^2 = 4 supersets: {A, B}, {A, B, C}, {A, B, D}, {A, B, C, D}.

Step 4 (Supersets of {A, C}): The attributes not in {A, C} are {B, D} (2 attributes), so there are 2^2 = 4 supersets: {A, C}, {A, B, C}, {A, C, D}, {A, B, C, D}.

Step 5 (Union, avoiding double counting): The sets common to both lists are exactly the ones containing {A, B, C}: {A, B, C} and {A, B, C, D} - 2 sets counted twice. By inclusion-exclusion, total distinct superkeys = 4 + 4 - 2 = 6.

Step 6 (Explicit list, for verification): {A, B}, {A, C}, {A, B, C}, {A, B, D}, {A, C, D}, {A, B, C, D} - exactly 6 distinct sets. None of the remaining 10 subsets of {A, B, C, D} contain either candidate key, so none of them are superkeys.

\[ \boxed{6} \]