Primary Key

In the previous pages, we established that a relation may have multiple candidate keys—each capable of uniquely identifying tuples. But in practice, databases don't treat all candidate keys equally. One must be designated as the primary means of identification.

Consider an Employee table with three candidate keys: {EmployeeID}, {SSN}, and {Email}. Any of these could technically serve as the identifier, but the database system needs to know which one is primary—the one used for:

• Establishing relationships with other tables
• Clustering data for physical storage
• Default indexing strategies
• Foreign key references from other relations

This designated candidate key is called the primary key—arguably the most important concept in relational database design.

Essential properties of a primary key:

1. It is a candidate key: This means it's a superkey (uniquely identifies tuples) and it's minimal (no proper subset is a superkey).

2. It is singular: A relation has exactly one primary key. Other candidate keys become alternate keys.

3. It enforces entity integrity: The primary key cannot contain NULL values in any component attribute.

4. It is the target of foreign keys: Other relations reference this relation through its primary key.

Mathematical formalization:

Let R be a relation schema with candidate keys CK = {K₁, K₂, ..., Kₙ}. The primary key is a designated element PK ∈ CK such that:

• PK → R (superkey property)
• ∀A ∈ PK: (PK - {A})⁺ ≠ R (minimality)
• ∀t ∈ r(R), ∀A ∈ PK: t[A] ≠ NULL (entity integrity)

The selection of PK from CK is a design decision, not a mathematical determination. The relational model tells us the candidates; the designer chooses the primary.

One of the fundamental constraints of the relational model is entity integrity, and it applies specifically to primary keys.

Why entity integrity matters:

The primary key serves as the identity of each tuple. If we allowed NULL values:

1. Identity becomes ambiguous: A tuple with a NULL primary key cannot be reliably identified or referenced.

2. Comparisons fail: In SQL, NULL = NULL evaluates to UNKNOWN (not TRUE). This means we couldn't reliably determine if two tuples were 'the same'.

3. Foreign key references break: Other tables referencing this tuple would reference... nothing? The semantics become undefined.

4. Uniqueness enforcement fails: We can't guarantee uniqueness when NULL is involved, since NULL ≠ NULL.

Example: The NULL Problem

Suppose we allowed NULL in primary keys:

Problems:

• Are Jane and Bob the same employee (both have NULL ID)? No way to know.
• How do we update 'the employee with NULL ID'? Ambiguous.
• How does Payroll.EmployeeID reference Jane? It can't reliably.
• SELECT * WHERE EmployeeID = NULL returns nothing (NULL ≠ NULL in SQL).

Entity integrity prevents this chaos by requiring primary keys to always have meaningful, non-NULL values.

When a relation has multiple candidate keys, choosing the primary key is a crucial design decision. Several criteria guide this choice:

Example: Applying Selection Criteria

For an Employee table with candidate keys {EmployeeID}, {SSN}, {Email}:

Winner: EmployeeID — Best overall score across criteria.

SSN becomes an alternate key (with unique constraint). Email becomes an alternate key (with unique constraint but may change).

One of the most debated topics in database design is whether to use natural keys (derived from real-world attributes) or surrogate keys (artificially generated identifiers).

When to use natural keys:

1. The natural key is truly stable: ISBN doesn't change for a book edition. Country codes are internationally standardized.

2. External integration is critical: APIs, data exports, and external systems use the natural identifier.

3. Lookup patterns match: Users search by the natural key (e.g., find book by ISBN).

4. Uniqueness is guaranteed externally: An authority ensures no duplicates (ISBN agency, passport authority).

When to use surrogate keys:

1. No good natural key exists: People change names. Addresses change. Email changes.

2. Natural keys are composite: A 5-attribute natural key makes joins expensive.

3. Privacy matters: Don't expose SSN in every foreign key column.

4. Mergers/acquisitions are possible: Different divisions may have overlapping natural key spaces.

5. Performance is critical: Integer auto-increment outperforms string comparisons in joins.

Modern databases provide various mechanisms for automatically generating primary key values. Understanding these options is essential for practical database design.

SQL Implementation Examples:

When the natural candidate key consists of multiple attributes, we face a design decision: use the composite key as the primary key, or introduce a surrogate. Understanding the implications of composite primary keys is crucial.

Example: Order Line Items

CREATE TABLE OrderLine (
    OrderID INT NOT NULL,
    LineNumber INT NOT NULL,
    ProductID INT NOT NULL,
    Quantity INT NOT NULL,
    UnitPrice DECIMAL(10,2) NOT NULL,
    PRIMARY KEY (OrderID, LineNumber),
    FOREIGN KEY (OrderID) REFERENCES Orders(OrderID),
    FOREIGN KEY (ProductID) REFERENCES Products(ProductID)
);

Here, {OrderID, LineNumber} is the composite primary key:

• OrderID alone doesn't work (many lines per order)
• LineNumber alone doesn't work (same number in different orders)
• Together, they uniquely identify each line item

Implications of composite primary keys:

When to use composite vs surrogate:

Use composite primary key when:

• The table represents a many-to-many relationship (junction table)
• The composite key has exactly 2 attributes from foreign keys
• No other tables will reference this table (no cascade complexity)
• The attributes are stable and non-nullable

Use surrogate primary key when:

• Multiple tables will reference this table
• The natural key has 3+ attributes
• Key attributes might change
• ORM/framework compatibility is important

Different database management systems implement primary keys with subtle variations. Understanding these differences is essential for practical database work.