Skip to content

Finding the (minimal) key(s) of a relation scheme

TL;DR

  • Seed \(S\) with every attribute that never appears on the right-hand side of any FD (and any attribute that appears in no FD at all).
  • Compute \(S^+\); if it already equals \(R\), \(S\) is a key (check minimality by removing one attribute at a time).
  • If \(S^+ \neq R\), add attributes that can appear on the left of FDs to \(S\) in small combinations, recompute closures, and keep only minimal superkeys.
  • Any attribute that never appears on the left side of an FD can be omitted if it is already implied by \(S^+\); otherwise it must be in every key.
  • Repeat until all minimal superkeys (keys) are enumerated.

Visual cheat (example FD graph)

Below, \(D\) is forced into every key because it never appears on the RHS. \(A\) and \(B\) can determine \(C\), so try \(\{A,D\}\) or \(\{B,D\}\) first.

graph LR
    A((A)) --> B((B))
    B --> C((C))
    D((D)):::seed

    classDef seed fill:#f9d976,stroke:#333,stroke-width:1px;
    classDef deriv fill:#8ecae6,stroke:#333,stroke-width:1px;
    class B,C deriv

To find the key(s) of a relation scheme \(R\) with functional dependencies \(F\):

  1. Identify all attributes in \(R\) that do not appear on the right-hand side of any functional dependency in \(F\). These attributes must be included in every key.

    Example: if \(F = \{A \to B, B \to C\}\) and \(R = \{A, B, C, D\}\), then \(D\) does not appear on the right-hand side of any FD, so it must be included in every key. Every key will be in the form \(\{D, ...\}\).

  2. Attributes that never appear on the left-hand side of any FD cannot determine other attributes. If such an attribute is already implied by the seed from step 1, you do not need to add it; if nothing else implies it (for instance, the attribute never appears in any FD), then it must be included in every candidate key so that the closure can cover it.

    Example: Continuing from the previous example, \(C\) appears only on the right-hand side and is derivable from \(A\) or \(B\), so it does not have to be in the starting seed. If there were an extra attribute \(E\) that appears in no FD at all, every candidate key would need to include \(E\) because no closure can bring it in.

  3. Combine the attributes that must be present (from steps 1–2) with other attributes from \(R\) to form candidate keys.

    Example: Continuing from the previous example, we can form candidate keys like \(\{A, D\}\), \(\{B, D\}\), etc. Because \(D\) must be included and \(C\) is derivable, we only need to consider combinations of \(\{A, B\}\) with \(D\), instead of combinations of \(\{A, B, C\}\) with \(D\).

  4. For each candidate key, compute its closure using the functional dependencies in \(F\). Example: For candidate key \(\{A, D\}\), compute \((AD)^+\) using \(F\).

  5. If the closure of a candidate key includes all attributes in \(R\), then it is a superkey.

    Example: If \((AD)^+ = \{A, B, C, D\}\), then \(\{A, D\}\) is a superkey.

  6. Check if the superkey is minimal (i.e., removing any attribute from it would result in a set that is not a superkey). If it is minimal, then it is a key. Example: If removing \(D\) from \(\{A, D\}\) results in \(\{A\}\), and \((A)^+ \neq R\) and \((D)^+ \neq R\), then \(\{A, D\}\) is a key.

  7. Repeat the process until all keys are found.