Keys in the Relational Model

Concept

Because a relation is a set, no two tuples may be identical, so every relation must have some attribute set that identifies its tuples uniquely. Keys are how that is expressed.

The formal definitions

  Minimality is the whole difference

    STUDENT ( roll_no, email, name, dob )
      roll_no unique, email unique

    {roll_no}                  super key, and MINIMAL   -> candidate
    {email}                    super key, and MINIMAL   -> candidate
    {roll_no, name}            super key, NOT minimal   -> only super
    {roll_no, email}           super key, NOT minimal   -> only super
    {roll_no, email, name, dob} super key, NOT minimal  -> only super
    {name}                     NOT a super key - names repeat
    {name, dob}                probably not - two people can match

  Number of super keys grows fast: any set containing a
  candidate key is a super key. Candidate keys are the
  interesting ones because they are irreducible.

Finding all candidate keys, worked

Given R ( A, B, C, D ) with the rule that A and B together determine C and D, and C alone determines D.

  STEP 1  which attributes never appear on the right hand
          side of any rule? Those MUST be in every key.

            rules:  A B -> C D
                    C   -> D

            right hand sides: C, D
            so A and B never appear there
            -> { A, B } must be part of every candidate key

  STEP 2  can { A, B } determine everything?

            A B -> C D  yes, directly
            so { A, B } determines A, B, C, D  = all of R

  STEP 3  is it minimal?

            { A } alone -> nothing. no
            { B } alone -> nothing. no
            so { A, B } is minimal

  ANSWER  the only candidate key is { A, B }
          C is not a candidate key: C determines only D,
          never A or B

Phase 7 turns this into a general algorithm using attribute closure. The reasoning is identical; the notation becomes formal.

Choosing the primary key

1. Unique — guaranteed, not merely likely.
2. Not null — required by entity integrity.
3. Stable — never updated, because every foreign key copies it.
4. Minimal — fewer attributes means smaller indexes and smaller foreign keys.
5. Simple — a short integer compares faster than a long string.
6. Not sensitive — a primary key is copied into every referencing table, so never use personal identifiers.

Natural and surrogate keys compared

The important rule with surrogate keys: a surrogate key does not remove the need for a uniqueness constraint on the natural key. Without it, the same real world thing is inserted twice with two different generated ids, and nothing complains.

Foreign keys

A foreign key expresses a relationship by value. Its rule, stated precisely: every non null foreign key value must exist as a primary key value in the referenced relation. That is referential integrity, covered in full in the next two notes.

  STUDENT ( roll_no, name, dept_code )
                             |
                             +--> DEPARTMENT ( dept_code, name )

  A foreign key MAY be null, unless declared otherwise. Null
  means "this student is not attached to any department" -
  which is different from referring to a department that does
  not exist, and that difference is why nulls are allowed here
  but never in a primary key.

Common mistakes

• Calling any unique attribute set a candidate key. Minimality is required.
• Assuming one relation has one candidate key. It may have several; all but one become alternate keys.
• Believing a foreign key must reference a different relation. A self reference is normal — an employee manager column references employees.
• Adding a surrogate key and no unique constraint on the natural key. Duplicates then enter silently.
• Choosing a changeable attribute as primary key. Every referencing row has to change with it.

Exam and interview questions

1. Define super, candidate, primary, alternate, composite, foreign and surrogate keys.
2. Why is every candidate key a super key but not the reverse?
3. Find all candidate keys of R(A,B,C,D) given AB determines CD and C determines D.
4. Can a foreign key be null? Can a primary key? Explain both.
5. State six criteria for choosing a primary key.

Practice

1. For EMPLOYEE ( emp_id, pan, email, name, dept ) with emp_id, pan and email each unique, list all candidate keys and choose a primary key with reasons.
2. Give a relation whose only candidate key is composite, and explain why no single attribute works.
3. Explain in three sentences why a mobile number should not be a primary key even though it looks unique.

Conclusion

Super keys identify, candidate keys identify minimally, and one candidate is chosen as the primary key. Foreign keys carry relationships by value, and the rule to remember with surrogate keys is that they never remove the need for a uniqueness constraint on the real world key.