Relational Model and Keys

A relation is a set of tuples; its schema is R(A1,...,An) with degree = number of attributes and cardinality = number of tuples. Key terms: domain (allowed values), tuple (row), attribute (column). A relation is a SET, so duplicate tuples are not allowed and tuple ordering is immaterial. Integrity constraints: (1) Domain constraint — values from the attribute's domain. (2) Key constraint — candidate key values are unique. (3) Entity integrity — no primary key attribute may be NULL. (4) Referential integrity — a foreign key value must either match some primary key value in the referenced relation or be entirely NULL. Memory aid: PK can't be NULL (entity integrity); FK can be NULL (referential integrity allows it).

Superkey: any attribute set that uniquely identifies a tuple. Candidate key: a MINIMAL superkey (no proper subset is a superkey). Primary key: one chosen candidate key (cannot be NULL). Alternate keys: candidate keys not chosen as primary. Foreign key: attribute(s) referencing another relation's primary key. Prime attribute: an attribute that is part of SOME candidate key; non-prime otherwise. Counting superkeys: if a relation with n attributes has a single candidate key of one attribute, the number of superkeys = 2^(n-1) (the key must be present, the other n-1 attributes are optional). Shortcut: every candidate key is a superkey, but not every superkey is a candidate key (minimality fails).

Counting superkeys looks like a 30-second brain teaser, but it's also one of the most common GATE CSE multiple-mark questions in DBMS. The trick is to translate the words "candidate key" and "superkey" into a clean set-counting problem and then apply inclusion–exclusion wherever keys overlap. This lesson builds the recipe from the ground up.

Definition: Superkey — any set of attributes that uniquely identifies every tuple in a relation. Equivalently, a superkey is a candidate key together with any (possibly empty) subset of the remaining attributes.

Definition: Candidate key — a minimal superkey: removing any attribute from it would destroy uniqueness.

Counting from First Principles

Suppose a relation has n total attributes and one candidate key with k attributes. Every superkey must contain all k attributes of the candidate key (otherwise it wouldn't be a superkey). The remaining n – k attributes are independent — each one can be either present or absent. Therefore the number of superkeys is exactly 2^(n – k).

This is the master formula behind every counting problem in this topic. The candidate-key attributes are forced; the non-key attributes are free.

Why it matters: GATE often asks "How many superkeys exist?" or "How many superkeys contain attribute X?" — both are answered by counting free attributes.

Example 1 — One Candidate Key, AB in R(A, B, C, D)

Given R(A, B, C, D) with the candidate key AB:

• A and B are forced into every superkey.
• C and D are each free (include or not).
• Number of superkeys = 2^2 = 4, namely {AB, ABC, ABD, ABCD}.

Listing them keeps you honest, and the formula gives the count instantly.

Example 2 — Two Candidate Keys, Inclusion–Exclusion in Action

Now take R(A, B, C, D, E) with two candidate keys: A (single attribute) and BC (two attributes). Now any superkey must contain at least one candidate key — so we need:

|superkeys containing A| ∪ |superkeys containing BC|

A naive sum double-counts the superkeys that contain both A and BC. The correct formula is the principle of inclusion–exclusion:

|A ∪ BC| = |A| + |BC| − |A ∩ BC|

Step-by-step:

• Superkeys containing A: A is forced; B, C, D, E are free → 2^4 = 16.
• Superkeys containing BC: B and C forced; A, D, E free → 2^3 = 8.
• Superkeys containing both A and BC: A, B, C all forced; D and E free → 2^2 = 4.
• Total = 16 + 8 − 4 = 20.

Notice how the overlapping set is subtracted exactly once. If we forgot this step we'd report 24 — a very common mistake.

Why Inclusion–Exclusion?

The intuition: every "containing A" superkey and every "containing BC" superkey is a valid superkey, but a relation like ABCDE is counted twice — once because it contains A, once because it contains BC. Subtracting the intersection corrects exactly that double-count. For three candidate keys you'd extend to:

|X ∪ Y ∪ Z| = |X| + |Y| + |Z| − |X ∩ Y| − |Y ∩ Z| − |Z ∩ X| + |X ∩ Y ∩ Z|

Common misconception: Some students try to "fix" the issue by averaging or by counting only the minimal candidate keys. Both are wrong. The only safe approach is inclusion–exclusion across the candidate keys.

A Quick Recipe You Can Memorise

1. Identify all candidate keys.
2. For each candidate key, count superkeys that contain it = 2^(n − size of that key).
3. For each pair of candidate keys, count superkeys containing the union of their attributes = 2^(n − |union|).
4. Apply inclusion–exclusion.

Worked example with the recipe — R(A, B, C, D) with candidate keys A and B:

• |A| = 2^3 = 8.
• |B| = 2^3 = 8.
• |A ∪ B|-forced attributes = {A, B}, so |A ∩ B as superkey-sets| = 2^2 = 4.
• Total = 8 + 8 − 4 = 12.

Real-world example: In a real database for, say, a college's STUDENT(roll_no, aadhaar, name, branch, year) table, both roll_no and aadhaar are candidate keys. Asking "how many distinct sets of columns would still uniquely identify a student?" is exactly the superkey-counting question, and the count tells the DBA how many alternative unique indexes are theoretically possible.

Disjoint vs Overlapping Candidate Keys

If two candidate keys are completely disjoint (share no attributes), their union still gets the same |X ∩ Y| treatment — the size of the union is just |X| + |Y|. If they overlap (share some attributes), the union is smaller, so the intersection count gets bigger and the subtraction matters more. Either way, the formula is identical; only the numbers change.

Question: R(A, B, C, D, E) has candidate keys AB and CD. How many superkeys exist?

Solution:
Step 1: |AB| = forced A, B; free C, D, E → 2^3 = 8.
Step 2: |CD| = forced C, D; free A, B, E → 2^3 = 8.
Step 3: |AB ∪ CD| has forced A, B, C, D; free E → 2^1 = 2.
Step 4: Total = 8 + 8 − 2 = 14.
Conclusion: 14 superkeys in R.

Cover the answer, recall, then check. 12 cards on the relational model and keys (GATE).

Q1. Define the degree and cardinality of a relation.
A1. Degree (arity) = number of attributes (columns). Cardinality = number of tuples (rows). Don't confuse cardinality here with a relationship's cardinality ratio.

Q2. Why can a relation never contain duplicate tuples?
A2. Because a relation is defined as a set of tuples, and a set has no duplicate elements. (A multiset "relation" with duplicates is a bag, used by SQL, not the pure model.)

Q3. Define a superkey.
A3. A set of attributes whose values uniquely identify each tuple of the relation — i.e., no two distinct tuples agree on all of them. It need not be minimal.

Q4. Define a candidate key.
A4. A minimal superkey: it is a superkey, and no proper subset of it is a superkey. A relation may have several candidate keys.

Q5. Primary key vs alternate key?
A5. The primary key is the one candidate key chosen to identify tuples (and used for entity integrity). The remaining candidate keys are alternate (secondary) keys.

Q6. Prime vs non-prime attribute?
A6. A prime attribute belongs to at least one candidate key. A non-prime attribute belongs to no candidate key. This distinction drives 2NF/3NF definitions.

Q7. What is a foreign key?
A7. An attribute set in one relation that references the primary key (or a candidate key) of another (or the same) relation, enforcing referential integrity. Its value must match an existing referenced value or be NULL (if permitted).

Q8. A relation has n attributes and exactly one candidate key of size k. How many superkeys?
A8. 2^(n − k). Every superkey must contain all k key attributes; the remaining n − k attributes are each optionally included.

Q9. R(A,B,C,D) with candidate keys AB and CD. Count the superkeys.
A9. Superkeys containing AB: 2^2 = 4. Containing CD: 4. Containing both (i.e. containing ABCD): 1. By inclusion–exclusion: 4 + 4 − 1 = 7.

Q10. Can a candidate key value be NULL?
A10. The primary key cannot (entity integrity). Other candidate keys may permit NULLs depending on the DBMS, but a NULL cannot uniquely identify a tuple.

Q11. What does "atomic domain / first normal form" require?
A11. Every attribute value must be a single atomic value from its domain — no sets, lists, or repeating groups inside a cell. The relational model assumes 1NF.

Q12. Is every superkey a candidate key? Is every candidate key a superkey?
A12. Not every superkey is a candidate key (only the minimal ones are). But every candidate key is by definition a superkey.

The relational model represents data as relations (tables): a relation is a set of tuples over a schema R(A₁,…,Aₙ). Because it is a set, no two tuples are identical and tuple order is irrelevant; each attribute draws atomic values from a domain (the first-normal-form assumption). Two size measures matter: degree = number of attributes, cardinality = number of tuples.

Keys — the exam core

Keys are defined by uniqueness and minimality. Everything in normalization builds on the prime/non-prime distinction, so nail these definitions.

Key type	Definition	Minimal?	May be NULL?
Superkey	Uniquely identifies each tuple	No	—
Candidate key	Minimal superkey	Yes	—
Primary key	Chosen candidate key	Yes	No (entity integrity)
Alternate key	Candidate key not chosen as primary	Yes	Depends
Foreign key	References a PK/candidate key elsewhere	—	Yes (if allowed)

A prime attribute appears in some candidate key; a non-prime attribute appears in none. Determine candidate keys via attribute-closure (X⁺): X is a superkey iff X⁺ = all attributes, and a candidate key iff additionally no proper subset of X is a superkey.

Counting superkeys

If R has n attributes and a single candidate key of size k, the number of superkeys is 2^(n−k): every superkey must contain the whole candidate key, and each of the remaining n−k attributes is independently in or out. With multiple candidate keys, count superkeys containing each key and combine using inclusion–exclusion.

Exam Tricks & Tips

• 🎯 A superkey need not be minimal; a candidate key must be. Every candidate key is a superkey, but not vice-versa.
• 🎯 To find all candidate keys, first classify attributes that appear only on the LHS of FDs — they must be in every candidate key; attributes appearing only on the RHS are in none.
• 🎯 Single candidate key of size k in n attributes ⇒ 2^(n−k) superkeys. Memorise this; it is a repeat question.
• 🎯 For two disjoint candidate keys K1, K2 in n attributes: superkeys = 2^(n−|K1|) + 2^(n−|K2|) − 2^(n−|K1∪K2|).
• 🎯 "Number of candidate keys" ≠ "number of superkeys" — candidate keys are counted after minimality checking, superkeys are counted combinatorially.
• ❌ Common mistake: assuming the primary key is the smallest candidate key — any candidate key can be chosen as primary; size is not the deciding rule.

Expected exam pattern

1–2 marks: given a relation and a set of FDs, find all candidate keys, identify prime attributes, or count superkeys/candidate keys. Occasionally combined with a normalization sub-part. Attribute-closure computation is the workhorse skill.

Quick recap

Relation = set of atomic-valued tuples; degree = columns, cardinality = rows. Superkey ⊇ candidate key (minimal) → one becomes the primary key (non-NULL). Prime = in some candidate key. Use X⁺ to test keys; use 2^(n−k) and inclusion–exclusion to count superkeys.