Relations, Attributes, and Keys

A relation schema is a name paired with a fixed set of attributes, each drawn from a domain — the set of legal values for that attribute (integers, strings of bounded length, dates, and so on). Formally, a schema $R(A_1, A_2, \dots, A_n)$ names attributes $A_1,\dots,A_n$, and a relation instance $r$ on $R$ is a finite set of tuples, where each tuple $t = (v_1, \dots, v_n)$ assigns a value $v_i \in \text{dom}(A_i)$ to each attribute. Because $r$ is a mathematical set, two consequences follow immediately: tuples have no inherent order, and — crucially — no two tuples in $r$ can be identical. This second property is what forces the existence of keys: if the model guarantees no duplicate rows, there must be some subset of attributes whose values are always sufficient to tell any two distinct tuples apart. This is where keys enter. Let $K \subseteq \{A_1,\dots,A_n\}$ be a subset of attributes. $K$ is a superkey of $R$ if, for every legal instance $r$ of $R$, no two distinct tuples $t_1 \ne t_2$ in $r$ agree on all attributes of $K$. In symbols, $t_1[K] = t_2[K] \implies t_1 = t_2$. Every relation trivially has at least one superkey: the set of all its attributes, since no two tuples can be entirely identical. The interesting question is how much smaller that set can be made while preserving uniqueness. A superkey $K$ is a candidate key if it is minimal: no proper subset of $K$ is also a superkey. Minimality is the whole point — it says every single attribute in $K$ is pulling its weight in guaranteeing uniqueness, and removing any one of them breaks the guarantee. A relation may have more than one candidate key (think of a `Student` relation identified equally well by a university-issued ID or by a national ID number). Among the candidate keys, the designer designates exactly one as the primary key, chosen by convention for stability, brevity, and non-null guarantees; the others are called alternate keys (or secondary/candidate keys, terminology varies). Attributes that participate in at least one candidate key are called prime attributes; all others are non-prime attributes — a classification that becomes essential later when discussing Functional Dependencies and normal forms, since normalization rules are stated in terms of dependencies on candidate keys and the primeness of attributes. Finally, a foreign key is a different (though related) concept — an attribute set in one relation that references the primary key of another, enforcing referential integrity across relations, a topic developed under Integrity Constraints.

In practice, keys are not guessed by inspection alone — for schemas of any real size, they are derived from a declared set of functional dependencies (FDs). An FD $X \rightarrow Y$ states that whenever two tuples agree on all attributes in $X$, they must also agree on all attributes in $Y$. Given a schema $R$ and a set of FDs $F$, the standard algorithm for testing "is $K$ a superkey?" and for discovering all candidate keys relies on computing the attribute closure $K^+$: the set of all attributes functionally determined by $K$ under $F$. The closure algorithm is the computational workhorse here. Its correctness rests on Armstrong's axioms (reflexivity, augmentation, transitivity), which are sound and complete for the theory of functional dependencies — meaning the closure computed this way captures exactly the FDs logically implied by $F$, no more and no less. ``` ATTRIBUTE-CLOSURE(K, F): // K: a set of attributes; F: a set of functional dependencies X -> Y result <- K changed <- true while changed: changed <- false for each FD (X -> Y) in F: if X is a subset of result and Y is not a subset of result: result <- result union Y changed <- true return result ``` ``` IS-SUPERKEY(K, R, F): return ATTRIBUTE-CLOSURE(K, F) == all attributes of R IS-CANDIDATE-KEY(K, R, F): if not IS-SUPERKEY(K, R, F): return false for each attribute A in K: if IS-SUPERKEY(K - {A}, R, F): return false // some proper subset is already a superkey -> K not minimal return true ``` ``` FIND-ALL-CANDIDATE-KEYS(R, F): // Practical (exponential worst case, fine for typical schema sizes) candidates <- empty set for each subset S of attributes(R), in increasing order of size: if S is a superset of some already-found candidate key: continue // cannot be minimal if IS-SUPERKEY(S, R, F): candidates <- candidates union {S} return candidates ``` The three procedures compose cleanly. `ATTRIBUTE-CLOSURE` answers the atomic question "what does this attribute set determine?" `IS-SUPERKEY` reduces to checking whether that closure reaches every attribute in $R$. `IS-CANDIDATE-KEY` adds the minimality check by trying to remove each attribute one at a time and confirming the superkey property breaks. `FIND-ALL-CANDIDATE-KEYS` enumerates subsets by increasing size — smallest first — so that once a candidate key is found, any larger set containing it is automatically skipped, since it cannot be minimal. A practical shortcut speeds this up enormously: partition attributes into three classes before enumerating anything. 1. An attribute that never appears on the right-hand side of any FD must appear in every candidate key (nothing else can ever produce it). 2. An attribute that never appears on the left-hand side of any FD is useless to test as part of a candidate key's "core" (it can only ever be a passenger, determined by others). 3. Everything else needs to be tested combinatorially, but usually this remaining set is small.

Correctness of `ATTRIBUTE-CLOSURE`. The loop only ever adds attributes to `result`, never removes any, so it is monotone; since the attribute universe is finite, the loop must terminate. Termination happens exactly when a full pass over $F$ adds nothing new, at which point `result` is closed under one application of every FD — and by the transitivity/reflexivity/augmentation axioms (Armstrong's axioms, known to be sound and complete), this fixed point equals the true semantic closure $K^+$: the exact set of attributes functionally determined by $K$ given $F$. Soundness means every attribute added is genuinely implied; completeness means no implied attribute is missed. This is the standard guarantee that makes the closure test exact rather than heuristic.

Complexity of closure. Each outer iteration of the `while` loop either adds at least one attribute to `result` or terminates; since there are at most $n$ attributes, the loop body runs at most $n$ times before nothing changes. Each pass scans all $|F|$ dependencies and does a subset check costing $O(n)$, giving $O(n \cdot |F| \cdot n) = O(n^2 |F|)$ per closure computation in a naive implementation (this is commonly tightened to near-linear in the total size of $F$ with hashing/counter tricks, but the simple bound already suffices for correctness reasoning and is what's typically taught).

Correctness of superkey/candidate-key tests. `IS-SUPERKEY` is correct by definition: $K$ functionally determines every attribute of $R$ if and only if $K^+ = R$, which is precisely what distinguishes a set that pins down a unique tuple from one that doesn't. `IS-CANDIDATE-KEY` is correct because minimality is, by definition, "no proper subset is a superkey" — and it suffices to check subsets obtained by removing one attribute at a time: if some larger deficient subset failed to be minimal for a different reason, that failure would already have been detected at the single-attribute-removal level, since superkey-ness is monotone (any superset of a superkey is also a superkey). This monotonicity is exactly what justifies stopping at singleton removals rather than checking every proper subset explicitly.

Complexity of full enumeration. In the worst case, a relation can have exponentially many candidate keys relative to the number of attributes — a classical fact from FD theory — so `FIND-ALL-CANDIDATE-KEYS` is worst-case exponential, $O(2^n)$ subsets tested, each costing a closure computation. This is not a flaw in the algorithm; it reflects the genuine combinatorial richness of the candidate-key structure. In practice, real schemas have a handful of attributes with well-understood dependency structure (often driven directly from an ER Model design), so the exponential blowup rarely bites; the "attributes never on a right-hand side must be in every key" pruning rule alone eliminates most of the search space in typical textbook and industrial schemas.

Tradeoffs. Choosing a primary key is not purely mathematical — a composite natural key (e.g., `{CourseID, Semester, Section}`) may be semantically meaningful but bulky to index and awkward as a foreign key target in other relations; a surrogate key (an auto-incremented integer) is compact and stable but carries no business meaning and must still be checked against candidate keys to preserve entity integrity. The relational model itself is agnostic on this choice — it only requires that some candidate key be honored as primary, enforced via a `NOT NULL` and uniqueness constraint under Integrity Constraints.

Consider a relation for university enrollment records:

with the following functional dependencies declared by the designer:

We trace `FIND-ALL-CANDIDATE-KEYS`.

Step 1 — classify attributes. Scan the right-hand sides of all FDs: `Name`, `CourseName`, and `Grade` each appear on some right-hand side, so none of them is forced into every key. `RollNo`, `CourseID`, and `Semester` never appear on any right-hand side — by the pruning rule, all three must belong to every candidate key. Call this forced core $C = \{\text{RollNo}, \text{CourseID}, \text{Semester}\}$.

Step 2 — test the forced core as a candidate. Compute $C^+$ using `ATTRIBUTE-CLOSURE`:

$C^+ = \{\text{RollNo}, \text{CourseID}, \text{Semester}, \text{Name}, \text{CourseName}, \text{Grade}\}$, which is all six attributes of `Enroll`. So $C$ is a superkey.

Step 3 — check minimality. Try dropping each attribute of $C$ one at a time:

• Drop `Semester`: closure of {RollNo, CourseID} adds `Name` and `CourseName` via the first two FDs, but the third FD needs `Semester` too, so `Grade` is never added. Closure stalls at 4 of 6 attributes — not a superkey. Good, `Semester` is needed.
• Drop `CourseID`: closure of {RollNo, Semester} adds only `Name`; `CourseName` needs `CourseID` and `Grade` needs `CourseID` too. Stalls at 2 of 6 — not a superkey. `CourseID` is needed.
• Drop `RollNo`: closure of {CourseID, Semester} adds only `CourseName`. Stalls at 3 of 6 — not a superkey. `RollNo` is needed.

No attribute can be removed, so $C = \{\text{RollNo}, \text{CourseID}, \text{Semester}\}$ is confirmed minimal, and hence a candidate key.

Step 4 — are there other candidate keys? Since $C$ is the unique forced core and every candidate key must contain it (Step 1), and $C$ itself is already a superkey, no strictly larger set can also be minimal (any superset of a superkey is a superkey, but not minimal unless it equals $C$). So $\{\text{RollNo}, \text{CourseID}, \text{Semester}\}$ is the only candidate key of `Enroll`.

Conclusion. `{RollNo, CourseID, Semester}` becomes the primary key of `Enroll`. `Name` and `CourseName` are non-prime attributes (each functionally dependent on a proper part of the key, in fact — a partial dependency that would flag this schema as violating 2NF, foreshadowing the normalization discussion built on exactly this kind of key/dependency analysis).

The theory of keys is inseparable from the invention of the relational model itself, since keys are the mechanical device that turns "a relation is a set" into an enforceable, checkable design discipline.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — enforces primary keys as an internally indexed, uniqueness-checked structure, typically backed by a B+-tree index that both accelerates lookups and rejects duplicate insertions at write time. Object-relational mapping frameworks (Hibernate, Django ORM, ActiveRecord) generate surrogate primary keys automatically precisely because application-level natural keys are so often discovered, too late, not to be true candidate keys. Data warehouse star-schema design leans on the prime/non-prime distinction when deciding which dimension attributes belong in a dimension table's key versus its descriptive payload. Distributed databases (Cassandra, DynamoDB, CockroachDB) generalize the primary key into a partition key that determines physical data placement across nodes, meaning a poor key choice there causes not just correctness bugs but severe load-balancing hotspots. Every foreign-key relationship, every join optimization plan, and every normalization proof taught under Functional Dependencies ultimately reduces to the closure-based reasoning introduced here.

Ask the tutor: How do candidate keys and functional dependencies combine to prove a relation is in Boyce-Codd Normal Form?