Relational Model and Keys

In the relational model all data is stored in relations, which we usually call tables.

Terms

Because a relation is a set of tuples:

• it has no duplicate tuples, and
• the order of tuples does not matter (and neither does the order of attributes, since they are named).

SQL tables relax the first rule: a table without a key can contain duplicate rows, and SELECT keeps duplicates unless you write DISTINCT.

Keys

Take the relation Student(roll, email, name, dept) where every student has a unique roll number and a unique email.

• A superkey is any set of attributes whose values are unique for every tuple: {roll}, {email}, {roll, name}, {roll, email, name, dept} and many more.
• A candidate key is a minimal superkey: no attribute can be removed from it. Here {roll} and {email} are candidate keys, while {roll, name} is a superkey but not minimal.
• The primary key is the candidate key chosen by the designer to identify tuples (say roll). The other candidate keys are alternate keys.
• A composite key is a key with more than one attribute, such as (roll, code) in an enrolment table.
• Attributes that belong to some candidate key are prime attributes; the rest are non-prime. This matters for normal forms.
• A foreign key is an attribute set in one relation that refers to the primary key of another (or the same) relation.

Counting superkeys

GATE often asks how many superkeys a relation has. The rule: a superkey is any set of attributes that contains at least one candidate key.

For a relation with n attributes:

• With one candidate key of k attributes, the other n − k attributes may each be present or absent: 2ⁿ⁻ᵏ superkeys.
• With two candidate keys K₁ and K₂, use inclusion–exclusion: |supersets of K₁| + |supersets of K₂| − |supersets of K₁ ∪ K₂|.

Example: R(A, B, C, D, E) with candidate keys {A} and {B, C}. Supersets of {A}: 2⁴ = 16. Supersets of {B, C}: 2³ = 8. Supersets of {A, B, C}: 2² = 4. Total 16 + 8 − 4 = 20. A brute-force check over all subsets agrees:

from itertools import combinations

attrs = "ABCDE"
keys = [set("A"), set("BC")]
count = 0
for r in range(1, len(attrs) + 1):
    for subset in combinations(attrs, r):
        if any(k <= set(subset) for k in keys):
            count += 1
print(count)

20

Integrity constraints

What happens when a referenced row is deleted? The foreign key decides:

• ON DELETE RESTRICT / NO ACTION (default): the delete is rejected while rows refer to it.
• ON DELETE CASCADE: the referring rows are deleted too.
• ON DELETE SET NULL: the referring foreign keys become NULL.

CREATE TABLE dept (id INTEGER PRIMARY KEY, name TEXT);
CREATE TABLE emp (
  id      INTEGER PRIMARY KEY,
  name    TEXT,
  dept_id INTEGER REFERENCES dept(id) ON DELETE CASCADE
);
CREATE TABLE project (
  id      INTEGER PRIMARY KEY,
  title   TEXT,
  dept_id INTEGER REFERENCES dept(id) ON DELETE SET NULL
);
INSERT INTO dept VALUES (1, 'CSE'), (2, 'ECE');
INSERT INTO emp VALUES (10, 'Asha', 1), (11, 'Ravi', 2), (12, 'Meena', 1);
INSERT INTO project VALUES (100, 'Compiler', 1), (101, 'Router', 2);
DELETE FROM dept WHERE id = 1;
SELECT * FROM emp;
SELECT * FROM project;

id  name  dept_id
--  ----  -------
11  Ravi  2

id   title     dept_id
---  --------  -------
100  Compiler  NULL
101  Router    2

Deleting department 1 removed its two employees (cascade) and left project 100 without a department (set null).

Practice questions

CREATE TABLE a (id INTEGER PRIMARY KEY);
CREATE TABLE b (
  id   INTEGER PRIMARY KEY,
  a_id INTEGER REFERENCES a(id) ON DELETE CASCADE
);
INSERT INTO a VALUES (1), (2), (3);
INSERT INTO b VALUES (1, 1), (2, 1), (3, 2), (4, 3), (5, NULL);
DELETE FROM a WHERE id IN (1, 3);
SELECT COUNT(*) FROM b;