Keys in the Relational Model

In the physical world, we identify individual entities through unique characteristics—people by fingerprints or government IDs, books by ISBN numbers, vehicles by VIN codes, and buildings by addresses. This fundamental need for unique identification extends directly into the digital realm of relational databases.

Within a relational database, every tuple (row) in a relation (table) must be uniquely distinguishable from every other tuple. Without this guarantee, we lose the ability to reference specific data, update precise records, or maintain meaningful relationships between tables. The superkey is the foundational concept that makes this identification possible.

Before we can understand primary keys, foreign keys, or referential integrity, we must first master the superkey—the most general and inclusive form of a key in relational theory.

Before defining superkeys formally, let's understand the problem they solve. Consider a simple Employee relation:

Now ask yourself: How do we refer to a specific row?

• By FirstName? No—there are two 'John' entries
• By LastName? No—there are two 'Smith' entries
• By FirstName + LastName? Still no—there are two 'John Smith' entries
• By Email? Yes—each email is unique
• By EmployeeID? Yes—each ID is unique
• By EmployeeID + Email? Yes—but this is more than necessary

This simple exercise reveals a critical insight: uniqueness is an attribute (or combination of attributes) property, and some combinations are more efficient than others.

The Mathematical Formulation:

Let R be a relation schema with attributes {A₁, A₂, ..., Aₙ}. A subset K ⊆ {A₁, A₂, ..., Aₙ} has the uniqueness property if no two distinct tuples in any valid instance of R can have the same values for all attributes in K.

Formally, for any valid instance r of R and any two tuples t₁, t₂ ∈ r:

If t₁[K] = t₂[K], then t₁ = t₂

This states that if two tuples agree on all attributes in K, they must be the same tuple. Equivalently, different tuples must differ on at least one attribute in K.

This uniqueness property is the defining characteristic of a superkey.

With the uniqueness problem understood, we can now define the superkey with full mathematical precision:

Key aspects of this definition:

1. Set of attributes: A superkey can consist of one attribute or many attributes
2. Collective uniqueness: The attributes work together to provide uniqueness
3. Any valid instance: The uniqueness must hold for all possible database states, not just the current one
4. Functional determination: The superkey functionally determines every attribute in the relation

The functional dependency perspective:

If K is a superkey of R(A₁, A₂, ..., Aₙ), then:

• K → A₁
• K → A₂
• ...
• K → Aₙ

Or more concisely: K → R (K determines all of R).

This connection between superkeys and functional dependencies is profound. It means that understanding superkeys requires understanding functional dependencies—a topic we'll explore in detail later. For now, the intuition is: if you know the superkey values, you know everything about that tuple.

Superkeys exhibit several important mathematical properties that govern their behavior. Understanding these properties is essential for correctly identifying superkeys and appreciating the key hierarchy.

Proof: Superset Property

Let K be a superkey of R, and let K' ⊇ K (K' is a superset of K). We prove K' is also a superkey:

1. Since K is a superkey, for any two tuples t₁, t₂: if t₁[K] = t₂[K], then t₁ = t₂
2. If t₁[K'] = t₂[K'], then certainly t₁[K] = t₂[K] (since K ⊆ K')
3. By step 1, t₁ = t₂
4. Therefore K' satisfies the uniqueness property
5. Therefore K' is a superkey ∎

Proof: Trivial Superkey Always Exists

Let R have attribute set {A₁, A₂, ..., Aₙ}. By the definition of a relation:

• A relation is a set of tuples
• Sets cannot contain duplicate elements
• Therefore, no two tuples in R can be identical
• Therefore, the complete attribute set {A₁, A₂, ..., Aₙ} uniquely identifies each tuple
• Therefore, {A₁, A₂, ..., Aₙ} is a superkey ∎

These proofs establish fundamental guarantees about superkey existence and behavior.

Given a relation schema and its functional dependencies, we can systematically identify all superkeys. This process is fundamental to database design and analysis.

Example: Identifying Superkeys

Consider the relation schema:

Student(StudentID, Name, Email, Major, GPA)

With functional dependencies:

• StudentID → Name, Email, Major, GPA
• Email → StudentID, Name, Major, GPA

Let's verify which sets are superkeys:

Testing {StudentID}:

1. Compute closure: {StudentID}⁺
2. Apply FD: StudentID → Name, Email, Major, GPA
3. Closure becomes: {StudentID, Name, Email, Major, GPA}
4. This equals R, so {StudentID} is a superkey ✓

Testing {Email}:

1. Compute closure: {Email}⁺
2. Apply FD: Email → StudentID, Name, Major, GPA
3. Closure becomes: {Email, StudentID, Name, Major, GPA}
4. This equals R, so {Email} is a superkey ✓

Testing {Name}:

1. Compute closure: {Name}⁺
2. No FD has Name on the left side alone
3. Closure remains: {Name}
4. This does not equal R, so {Name} is NOT a superkey ✗

Testing {StudentID, Name}:

1. By the superset property, since {StudentID} is a superkey, {StudentID, Name} is also a superkey ✓

A natural question arises: How many superkeys does a relation have? The answer reveals why we need the concept of candidate keys to manage the potentially explosive number of superkeys.

Example: Counting Superkeys

Consider R(A, B, C, D, E) with candidate keys {A, B} and {C, D}:

Superkeys containing {A, B}:

• {A, B}, {A, B, C}, {A, B, D}, {A, B, E}
• {A, B, C, D}, {A, B, C, E}, {A, B, D, E}
• {A, B, C, D, E}
• Total: 2^(5-2) = 2³ = 8 superkeys

Superkeys containing {C, D}:

• {C, D}, {A, C, D}, {B, C, D}, {C, D, E}
• {A, B, C, D}, {A, C, D, E}, {B, C, D, E}
• {A, B, C, D, E}
• Total: 2^(5-2) = 2³ = 8 superkeys

But wait—we've double-counted!

Superkeys containing both {A, B} and {C, D}:

• {A, B, C, D}, {A, B, C, D, E}
• Total: 2^(5-4) = 2¹ = 2 superkeys

By inclusion-exclusion:

• Total superkeys = 8 + 8 - 2 = 14 superkeys

This example shows that even a modest relation with 5 attributes can have 14 superkeys. For larger relations with multiple candidate keys, the number explodes, making the concept of 'candidate key' (minimal superkey) essential for practical database design.

A critical distinction exists between identifying superkeys through schema analysis (using functional dependencies) versus data analysis (examining current tuples). This distinction has profound implications for database design correctness.

Example: The Danger of Data-Based Analysis

Consider this Book table:

Data analysis might suggest:

• {Title} appears unique (currently no duplicates) ❓
• {Author, Publisher} appears unique (currently no duplicates) ❓

But schema analysis reveals:

• {ISBN} is the only true superkey (ISBNs are globally unique by design)
• Different books can (and often do) share titles
• The same author frequently publishes multiple books with the same publisher

The current data is misleading! A proper superkey analysis requires understanding the real-world semantics:

• ISBN is a unique identifier assigned to each book edition
• Authors write multiple books
• Titles can be reused (especially common words)

Lesson: Always derive superkeys from semantic understanding and business rules, not from data coincidences.

Superkeys form a hierarchy based on subset relationships. Understanding this hierarchy is crucial for grasping the relationship between superkeys, candidate keys, and primary keys.

Key observations from the hierarchy:

1. The trivial superkey sits at the top: It contains all attributes and is always a superkey

2. Downward edges represent attribute removal: Moving down removes an attribute while maintaining superkey status

3. Candidate keys are at the bottom: They are minimal superkeys—removing any attribute loses superkey status

4. Paths trace superkey relationships: Any set on a path above a candidate key is also a superkey

5. Not all attribute subsets are superkeys: Only those connected to candidate keys through the hierarchy

Formal relationship:

Let SK(R) denote the set of all superkeys of R. Then:

• If K ∈ SK(R) and K ⊆ K' ⊆ R, then K' ∈ SK(R) (upward closure in the lattice)
• Candidate keys are the minimal elements of SK(R)
• The trivial superkey is the maximal element of SK(R)

This structure is called a join semi-lattice under the subset ordering, with candidate keys as the join-irreducible elements.

We've established the foundational concept of superkeys—the most general form of keys in the relational model. Let's consolidate the key insights:

What's next:

Now that we understand superkeys as the foundation, we'll explore candidate keys—the minimal superkeys that represent the most efficient way to uniquely identify tuples. The candidate key concept refines the broad superkey concept into something practical for database design.