Relational Model and Keys: short notes (Database Management Systems)

Introduction

The relational model stores all data as relations: tables whose rows are tuples of atomic values. It was designed so that queries could be expressed as operations on sets, independent of how the rows are laid out on disk. Relational algebra, tuple calculus, SQL and normalisation all assume these definitions.

Keys are the centre of the model. A key is the set of attributes that identifies a tuple; it is what foreign keys point to, what normal forms are defined against, and what an index is usually built on. The two kinds of result are counting superkeys and candidate keys, and the difference between "unique in this instance" and "unique in every legal instance".

Prerequisites

Sets: subsets, Cartesian product, power set and inclusion-exclusion, used to count superkeys.

Core concepts

Term	Meaning
Domain	A set of atomic values an attribute may take, for example the integers 1 to 100 or strings of length at most 20.
Relation schema $R(A_1, \ldots, A_n)$	A name with a list of attributes; $n$ is the degree (arity).
Relation instance $r(R)$	A finite set of tuples, each tuple an element of $D_1 \times \cdots \times D_n$ ; the number of tuples is the cardinality.
Tuple	One row: a function from attributes to values.
Database schema	The set of relation schemas plus integrity constraints; a database instance assigns an instance to each schema.
NULL	A special marker for "unknown" or "not applicable"; not a value of any domain.

Properties of a relation in the formal model.

A relation is a set: no two tuples are identical, and the order of tuples carries no meaning.
With named attributes, the order of attributes carries no meaning either.
Values are atomic (first normal form): no lists or nested tables in a cell.

SQL tables differ: a table without a key can hold duplicate rows (a multiset, or bag), and SELECT keeps duplicates unless DISTINCT is written. See SQL: Data Definition, Data Manipulation and Basic Queries.

Keys

Let $K \subseteq R$ be a set of attributes.

Superkey. $K$ is a superkey if no two distinct tuples of any legal instance agree on all attributes of $K$ . The full attribute set $R$ is always a superkey (a relation has no duplicate tuples).
Candidate key. A minimal superkey: $K$ is a superkey and no proper subset of $K$ is.
Primary key. The candidate key chosen by the designer to identify tuples; it may not be NULL. The other candidate keys are alternate keys.
Prime attribute. An attribute that belongs to at least one candidate key. All others are non-prime.
Foreign key. A set of attributes $F$ of $r_1$ that refers to the primary key (or another candidate key) of $r_2$ : every non-NULL value of $F$ in $r_1$ must appear as a key value in $r_2$ . Details in Integrity Constraints.
Composite key. A key with more than one attribute. A surrogate key is an artificial single attribute (a serial number) introduced instead of a long natural key.

Instance versus schema. A key is a property of the schema, meaning of all legal instances. A particular instance can show that $K$ is not a key (two tuples agree on $K$ ) but can never prove that $K$ is a key.

Nested regions over the 16 attribute subsets of R(A, B, C, D) with candidate keys A and B: the 12 superkeys contain the 2 candidate keys A and B, of which A is the primary key and B the alternate key; the other 4 subsets are not superkeys — Figure 1. Superkeys, candidate keys and the primary key of $R(A, B, C, D)$ when $A$ and $B$ are the candidate keys: 12 of the 16 attribute subsets are superkeys.

How it works: finding keys

When the constraints are given as functional dependencies, $K$ is a superkey exactly when its attribute closure $K^+$ is all of $R$ (closure is taught in Functional Dependencies, Closure and Canonical Cover). Two quick rules prune the search:

An attribute that never appears on the right side of any dependency belongs to every candidate key: nothing can determine it.
An attribute that appears only on the right side, never on the left, belongs to no candidate key: it is determined by the others and never helps determine anything.

Start from the attributes of rule 1. If their closure is $R$ , they form the only candidate key. Otherwise add the "both sides" attributes in all combinations, smallest first, and keep the minimal sets whose closure is $R$ .

Algorithms and pseudocode

Text

CANDIDATE-KEYS(R, F)
  core <- attributes of R not on any right side of F
  rest <- attributes on both a left and a right side of F
  keys <- empty list
  for k <- 0 to |rest|
      for each subset S of rest with |S| = k
          X <- core union S
          if CLOSURE(X, F) = R and no key in keys is a subset of X then add X to keys
  return keys

The loop is exponential in $|rest|$ in the worst case, which is unavoidable: the number of candidate keys itself can be exponential (see Maximum number of candidate keys in Mathematical explanation). Each closure costs $O(|F| \cdot |R|^2)$ with the simple repeated-scan algorithm (linear in the size of $F$ with the counter-based version).

Mathematical explanation

Counting superkeys. Let $n = |R|$ . Every superset of a superkey is a superkey, so the superkeys are exactly the sets that contain at least one candidate key.

One candidate key $K$ with $|K| = k$ : the other $n - k$ attributes are free, giving $2^{n-k}$ superkeys.
Two candidate keys $K_1, K_2$ : by inclusion-exclusion, $2^{n - |K_1|} + 2^{n - |K_2|} - 2^{n - |K_1 \cup K_2|}$ .
In general, the number of superkeys is $\left| \bigcup_i \{ X : X \supseteq K_i \} \right|$ , computed by inclusion-exclusion over the candidate keys.

Maximum number of candidate keys. Candidate keys form an antichain under $\subseteq$ (no candidate key contains another). By Sperner's theorem an antichain of subsets of an $n$ -set has at most $\binom{n}{\lfloor n/2 \rfloor}$ members, and that bound is reached (make every $\lfloor n/2 \rfloor$ -subset a key). For $n = 4$ this is 6.

Worked examples

Example 1. $R(A, B, C, D)$ with the single candidate key $A$ : $2^{3} = 8$ superkeys.

Example 2. $R(A, B, C, D)$ with candidate keys $A$ and $B$ : $2^3 + 2^3 - 2^2 = 12$ superkeys (Figure 1). Prime attributes: $A$ , $B$ .

Example 3. $R(A, B, C, D, E)$ with candidate keys $AB$ and $CD$ : $2^3 + 2^3 - 2^1 = 14$ superkeys.

Example 4. $R(A, B, C, D)$ with candidate keys $AB$ and $BC$ : $2^2 + 2^2 - 2^1 = 6$ superkeys. They are $AB, ABC, ABD, ABCD, BC, BCD$ .

Example 5: keys from dependencies. $R(A, B, C, D, E)$ with $A \to B$ , $BC \to E$ , $ED \to A$ .

$C$ and $D$ never appear on a right side, so every key contains $CD$ . $(CD)^+ = CD$ , not a key.
Add one attribute: $(ACD)^+ = ABCDE$ , $(BCD)^+ = BCDEA$ , $(CDE)^+ = CDEAB$ . All three are keys.
Every larger candidate contains one of these, so the candidate keys are $ACD$ , $BCD$ , $CDE$ , and every attribute is prime.
Superkeys: the sets containing $CD$ and at least one of $A$ , $B$ , $E$ : $2^3 - 1 = 7$ .

Example 6: what an instance can tell you. Instance of $R(A, B, C)$ : $(1, x, p)$ , $(2, x, q)$ , $(3, y, p)$ , $(1, y, q)$ . Sets with no repeated value combination in this instance: $AB$ , $AC$ , $BC$ , $ABC$ . So $A$ , $B$ and $C$ alone are certainly not keys, and $AB$ , $AC$ , $BC$ may be keys; the instance cannot decide which.

Example 7: a cycle of dependencies. $R(A, B, C, D)$ with $A \to B$ , $B \to C$ , $C \to A$ .

$D$ appears on no right side, so every key contains $D$ ; $D^+ = D$ is not a key.
$A$ , $B$ and $C$ determine one another: $(AD)^+ = (BD)^+ = (CD)^+ = ABCD$ .
Candidate keys: $AD$ , $BD$ , $CD$ . Every attribute is prime.
Superkeys: $D$ together with any nonempty subset of $\{A, B, C\}$ : $2^3 - 1 = 7$ .
If the cycle closes through $D$ as well ( $A \to B$ , $B \to C$ , $C \to D$ , $D \to A$ ), every single attribute is a key: four candidate keys and $2^4 - 1 = 15$ superkeys (every nonempty subset).

Example 8: three candidate keys. $R(A, B, C, D, E)$ with candidate keys $A$ , $BC$ and $CD$ . Let $S_K$ be the set of supersets of $K$ within $ABCDE$ , so $|S_K| = 2^{5 - |K|}$ .

Single terms: $|S_A| = 16$ , $|S_{BC}| = 8$ , $|S_{CD}| = 8$ .
Pairwise intersections are the supersets of the unions: $S_A \cap S_{BC} = S_{ABC}$ , $S_A \cap S_{CD} = S_{ACD}$ , $S_{BC} \cap S_{CD} = S_{BCD}$ , each of size $2^2 = 4$ .
Triple intersection $S_{ABCD}$ : size $2$ .
Superkeys: $16 + 8 + 8 - 4 - 4 - 4 + 2 = 22$ . Of these, $22 - 3 = 19$ are superkeys that are not candidate keys.

The pairwise terms use the union of the two keys, not their intersection. With two single-attribute keys $A$ and $B$ in $n$ attributes the count is $2^{n-1} + 2^{n-1} - 2^{n-2} = 3 \cdot 2^{n-2}$ , which is 12 for $n = 4$ as in Example 2.

Important properties and observations

Superset closure. Any superset of a superkey is a superkey; any subset of a non-superkey is a non-superkey.
Candidate keys may differ in size. $A$ and $BC$ can both be candidate keys of the same relation; "minimal" means no proper subset is a superkey, not "smallest size".
Primary key versus candidate key. Every primary key is a candidate key; PRIMARY KEY automatically makes all its attributes NOT NULL. UNIQUE alone does not; other columns may separately be declared NOT NULL.
Foreign keys may be NULL and may repeat; they need not be part of a key of their own table.
A relation always has at least one candidate key, because $R$ is a superkey and some subset of it is minimal.

Common misconceptions.

"The number of superkeys with candidate keys $A$ and $B$ is $2 \cdot 2^{n-1}$ ." No: sets containing both are counted twice; subtract $2^{n-2}$ .
"If a column has distinct values in the given table, it is a key." Only for that instance; a key is a schema constraint.
"Prime attributes are the primary-key attributes." Prime means "in some candidate key", not only the chosen primary key.

GATE examination perspective

Superkey counts. Given candidate keys, count superkeys with inclusion-exclusion over the sets that contain each key.
Candidate key enumeration. Given functional dependencies, use the "never on a right side" attributes as the core and grow from there.
Instance questions. "Which of the following can be a key of this relation instance?" Eliminate sets with repeated value combinations; the rest are only possible keys.
Maximum candidate keys. Consider an $n$ -attribute relation: $\binom{n}{\lfloor n/2 \rfloor}$ .
Definitions. Relation as a set (no duplicates) versus SQL table as a multiset; degree versus cardinality.

Summary

Sets: prerequisite; power sets and inclusion-exclusion.
Mapping ER Diagrams to Relations: dependent; produces the tables and keys.
Integrity Constraints: dependent; key, entity and referential integrity.
Relational Algebra: dependent; operations on relations as sets.
SQL: Data Definition, Data Manipulation and Basic Queries: dependent; PRIMARY KEY, UNIQUE and bag semantics.
Functional Dependencies, Closure and Canonical Cover: dependent; attribute closure, the tool for finding keys.

Relational Model and Keys

Introduction

Prerequisites

Core concepts

Keys

How it works: finding keys

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Keys

How it works: finding keys

Algorithms and pseudocode

Mathematical explanation

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps