Solved Problems on Keys and Super Keys

Introduction

Understanding keys and super keys is essential for mastering Database Management Systems (DBMS). These solved problems will help you grasp how to calculate the number of super keys in different scenarios, which is crucial for competitive exams like GATE, UGC NET, NIELIT, ISRO, and others.

Problem 1: Number of Super Keys for a Single Candidate Key

Given:

• A relation R with n attributes.
• A single candidate key A₁.

Question:

How many super keys are possible?

Solution:

Definition: A super key is a candidate key combined with any subset of the remaining attributes.

Key Insight:

• A₁ is already a candidate key.
• Remaining attributes: n – 1 attributes.
• Total subsets of the remaining attributes: 2^{n – 1} (since each attribute can be either included or not included).

Answer:

The total number of super keys = 2^{n – 1}.

---

Problem 2: Super Keys for Two Candidate Keys

Given:

• A relation R with n attributes.
• Two candidate keys: A₁ and A₂.

Question:

How many super keys are possible?

Solution:

Key Insight:

• Each candidate key can form super keys by combining with any subset of the remaining attributes.
• For each candidate key, the number of super keys is 2^{n – 1}.
• However, super keys formed from both candidate keys may overlap.
• The overlap occurs when both A₁ and A₂ are included, along with any subset of remaining attributes.
• Number of overlapping super keys: 2^{n – 2} (excluding both A₁ and A₂, we have n – 2 attributes).

Using the Inclusion-Exclusion Principle:

Total Super Keys = Super Keys from A₁ + Super Keys from A₂ – Overlapping Super Keys

Total Super Keys = 2^{n – 1} + 2^{n – 1} – 2^{n – 2}

Simplify:

Total Super Keys = 2 × 2^{n – 1} – 2^{n – 2} = 2ⁿ – 2^{n – 2}

Answer:

The total number of super keys = 2ⁿ – 2^{n – 2}.

---

Problem 3: Super Keys for Two Composite Candidate Keys

Given:

• A relation R with n attributes.
• Two composite candidate keys: A₁, A₂ and A₃, A₄.

Question:

How many super keys are possible?

Solution:

For each composite candidate key:

• The number of super keys is 2^{n – 2} (since each composite key has 2 attributes, leaving n – 2 remaining attributes).

Overlap:

• The overlap occurs when super keys include both composite candidate keys: A₁, A₂, A₃, A₄, plus any subset of the remaining attributes.
• Number of overlapping super keys: 2^{n – 4} (excluding the 4 attributes in both composite keys).

Using Inclusion-Exclusion Principle:

Total Super Keys = Super Keys from first composite key + Super Keys from second composite key – Overlapping Super Keys

Total Super Keys = 2^{n – 2} + 2^{n – 2} – 2^{n – 4}

Simplify:

Total Super Keys = 2 × 2^{n – 2} – 2^{n – 4} = 2^{n – 1} – 2^{n – 4}

Answer:

The total number of super keys = 2^{n – 1} – 2^{n – 4}.

---

Problem 4: Super Keys for Overlapping Candidate Keys

Given:

• A relation R with n attributes.
• Two overlapping candidate keys: A₁, A₂ and A₂, A₄.

Question:

How many super keys are possible?

Solution:

For each candidate key:

• Number of super keys: 2^{n – 2} (since each key has 2 attributes).

Overlap:

• Overlap occurs when super keys include A₁, A₂, A₄ plus any subset of the remaining attributes.
• Number of overlapping super keys: 2^{n – 3} (excluding the 3 attributes).

Using Inclusion-Exclusion Principle:

Total Super Keys = Super Keys from first candidate key + Super Keys from second candidate key – Overlapping Super Keys

Total Super Keys = 2^{n – 2} + 2^{n – 2} – 2^{n – 3}

Simplify:

Total Super Keys = 2 × 2^{n – 2} – 2^{n – 3} = 2^{n – 1} – 2^{n – 3}

Answer:

The total number of super keys = 2^{n – 1} – 2^{n – 3}.

---

Problem 5: Super Keys for Multiple Candidate Keys

Given:

• A relation R with n attributes.
• Multiple candidate keys: A₁, A₂, A₂, A₃, and A₃, A₄.

Question:

How many super keys are possible?

Solution:

Key Insight: Use the Inclusion-Exclusion Principle to account for overlaps among super keys formed from different candidate keys.

Number of super keys from each candidate key:

• Each has 2 attributes, so super keys from each = 2^{n – 2}.

Pairwise Overlaps:

• Overlap between any two candidate keys: Super keys including all attributes from both keys.
• Number of overlapping super keys between any two keys: 2^{n – 3} (since overlapping keys have 3 attributes in total).

Triple Overlap:

• Overlap among all three candidate keys: Super keys including all attributes from all candidate keys.
• Number of overlapping super keys among all three keys: 2^{n – 4} (excluding the 4 attributes).

Using Inclusion-Exclusion Principle:

Total Super Keys = Sum of super keys from each candidate key – Sum of pairwise overlaps + Triple overlap

Total Super Keys = 3 × 2^{n – 2} – 3 × 2^{n – 3} + 2^{n – 4}

Answer:

The total number of super keys = 3 × 2^{n – 2} – 3 × 2^{n – 3} + 2^{n – 4}.

---

Problem 6: Maximum Super Keys Without Candidate Key Information

Given:

• A relation R with n attributes.
• No information about candidate keys.

Question:

How many super keys are possible?

Solution:

Key Insight: In the absence of candidate keys, any non-empty subset of attributes could potentially be a super key.

Calculation:

• Total number of attributes: n.
• Total possible subsets (excluding the empty set): 2ⁿ – 1.

Answer:

The total number of super keys = 2ⁿ – 1.

Key Takeaways

• Super Key Definition: A super key is a candidate key combined with any subset of the remaining attributes.
• Counting Super Keys: Use the formula 2^{n – k}, where k is the number of attributes in the candidate key.
• Inclusion-Exclusion Principle: Essential for calculating total super keys when multiple candidate keys are present.

Conclusion

These solved problems illustrate how to calculate the number of super keys in various scenarios. Understanding these concepts is vital for database design and for tackling questions in competitive exams.