Relational model and keys

Why it exists

Every later topic of the course (algebra, SQL, normalisation) talks about relations, tuples and keys. Keys are the most examined part: count the superkeys, find the candidate keys, say what happens when a referenced tuple is deleted. This page fixes the vocabulary.

Prerequisites

Relations are sets of tuples; the notation comes from the mathematics of relations (set theory course).

Precise definitions

• A domain is a set of atomic values (integers, strings, dates). An attribute is a name with a domain.
• A relation schema $R(A_1, \ldots, A_n)$ lists the attributes. The degree (arity) of $R$ is $n$.
• A relation instance $r(R)$ is a set of tuples, each tuple a list of $n$ values, the $i$-th from the domain of $A_i$. The cardinality of $r$ is the number of tuples.
• Because a relation is a set, it has no duplicate tuples and the order of tuples and of attributes does not matter (attributes are identified by name). A SQL table is a bag: it may contain duplicates unless a key forbids them.
• Values are atomic (first normal form). A special value NULL stands for unknown or inapplicable; any comparison with NULL is neither true nor false but unknown, and a NULL never matches anything in a join.

Keys. For a relation schema $R$ with attribute set $U$:

• a superkey is a set $K \subseteq U$ such that no two tuples of any legal instance have equal values on all of $K$;
• a candidate key is a minimal superkey (no proper subset is a superkey);
• the primary key is the candidate key chosen by the designer (it may not be NULL); the other candidate keys are alternate keys;
• an attribute is prime if it belongs to some candidate key, otherwise non-prime.

Foreign key. A set of attributes $F$ of $R_1$ is a foreign key referencing $R_2$ if its values in tuples of $R_1$ must be either NULL or equal to the values of the candidate (usually primary) key of some tuple of $R_2$. Referential integrity is this requirement. Entity integrity: no attribute of a primary key may be NULL.

A key is a statement about all legal instances (a constraint on the schema), not about the current instance: an instance can show that a set is not a key (two tuples agree), but it can never prove that it is.

How it works

Superkeys and candidate keys

For $R(A, B, C)$ with candidate key $\{A\}$ the superkeys are the subsets that contain $A$: $\{A\}, \{A, B\}, \{A, C\}, \{A, B, C\}$, four of them. With one candidate key of size $k$ among $n$ attributes there are $2^{n-k}$ superkeys (each of the other $n - k$ attributes may or may not be added). With several candidate keys count by inclusion–exclusion: the superkeys are the sets that contain at least one candidate key.

For example, in $R(A, B, C, D)$ with candidate keys $\{A, B\}$ and $\{B, C\}$: $4$ superkeys contain $\{A, B\}$, $4$ contain $\{B, C\}$, and $2$ contain both (they contain $\{A, B, C\}$), so $4 + 4 - 2 = 6$. If every single attribute is a candidate key (four attributes) every non-empty subset is a superkey: $2^4 - 1 = 15$.

Facts used constantly.

• The set of all attributes is always a superkey (rows are distinct in a relation).
• A candidate key is never a proper subset of another candidate key.
• The number of candidate keys of a schema with $n$ attributes is at most $\binom{n}{\lfloor n/2 \rfloor}$ (no candidate key contains another, so they form an antichain of subsets; Sperner's theorem, quoted).
• Different candidate keys may have different sizes.

Foreign keys and referential actions

When a tuple of the referenced relation is deleted (or its key updated) while other tuples refer to it, the system applies the referential action chosen for the foreign key:

• CASCADE: delete (update) the referencing tuples too;
• SET NULL (and SET DEFAULT): put NULL (the default) in the foreign key of the referencing tuples;
• RESTRICT / NO ACTION: refuse the operation.

These were executed on a real database engine (SQLite with foreign keys switched on). Employees reference departments; the department 10 (Sales) is deleted under each action:

Two employees worked in Sales: with CASCADE they disappear, with SET NULL they stay with no department, with RESTRICT the delete is refused and nothing changes ("FOREIGN KEY constraint failed").

A foreign key may be NULL (unless declared NOT NULL), may reference the same relation (employees and their managers) and may be part of the primary key (a weak entity's key contains the owner's key). It must reference a candidate key.

Keys in practice

• A key chosen from real data (a name, a date) is risky: it must stay unique for all future instances. Designers use surrogate keys (an artificial id).
• In standard SQL, PRIMARY KEY implies UNIQUE and NOT NULL (SQLite is a known exception for non-integer columns); UNIQUE columns may contain NULLs (several of them, in most systems) and serve as alternate keys.
• Check from the instance: if two tuples agree on $K$, then $K$ is not a key. Example: Student(sid, sname, dept) with tuples (1, Asha, CS) and (3, Chen, CS): $\{\text{dept}\}$ is not a key; $\{\text{sid}\}$ may be.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Keys come from the ER design (ER model, ER to relational mapping); relational algebra operates on these relations (relational algebra); functional dependencies generalise keys (functional dependencies).

PYQs

Consider a relational database schema with a relation R(A,
B, C, D). If {A, B} and {A, C} are the only two candidate
keys of the relation R, then the number of super keys of
relation R is ______ (answer in integer)

Which one of the options given below refers to the
degree (or arity) of a relation in relational database
systems?

Consider the following tables T1 and T2.

In table T1, P is the primary key and Q is the foreign key
referencing R in table T2 with on-delete cascade. In table
T2, R is the primary key and S is the foreign key
referencing P in table T1 with on-delete set NULL and on-
update cascade. In order to delete record (3, 8) from table
T1, the number of additional records that need to be deleted
from table T1 is _____.

Which of the following is NOT a super key in a relational
schema with attributes V, W, X, Y ,Z and primary key
VY?

Given an instance of the STUDENTS relation as shown
below.

For (StudentName, StudentAge) to be the key for

this instance, the value X should NOT be equal to______

Consider a relational table with a single record for each
registered student with the following attributes.

1.
Registration_ Num: Unique registration number of
each registered student

2.
UID: Unique identity number, unique at the
national level for each citizen

3.
BankAccount_Num: Unique account number at the
bank. A student can have multiple accounts or join
accounts. This attribute stores the primary account number.

4.
Name: Name of the student

5.
Hostel _ Room: Room number of the hostel

Which of the following options is INCORRECT?

Given the basic ER and relational models, which of the
following is INCORRECT?

The following table has two attributes A and C where A
is the primary key and C is the foreign key referencing
A with ON DELETE CASCADE.

The set of all tuples that must be additionally deleted to
preserve referential integrity when the tuple (2, 4) is
deleted is:

Consider the following statements S1 and S2 about the
relational data model:

S1: A relation scheme can have at most one foreign key.

S2: A foreign key in a relation scheme R cannot be used
to refer to tuples of R.

Which one of the following choices is correct?

Suppose R1(A, B) and R2(C, D) are two relation schemas.
Let r1 and r2 be the corresponding relation instances. B is a
foreign key that refers to C in R2. If data in r1 and r2 satisfy
referential integrity constraints, which of the following is
ALWAYS TRUE?

DATABASE MANAGEMENT  SYSTEM

Self-check

Revision card

References