DSA, Database System & Operating System — Data Models, Normalization, and SQL, NEC licence examination syllabus (Nepal Engineering Council).
Attributes and Keys
Superkey, candidate key, primary key, alternate key, foreign key — the vocabulary that decides how every table is identified.
🌍 Where this lives: the primary-key decision is one of the few schema choices you cannot easily reverse. Choose a national ID number as the primary key and every child table stores it, so the day a citizen's ID is corrected you must update fifty tables. Choose an auto-increment integer and you have a stable key but must remember the natural key still needs a UNIQUE constraint or duplicates creep in. Every "why does this table have both an id and a code" argument on a real team is this topic. Search "natural vs surrogate primary keys"; the debate is thirty years old and both sides have real evidence.
The key hierarchy
SUPERKEY
ANY set of attributes that uniquely identifies a tuple.
May contain redundant attributes.
For student(roll, nat_id, name, dept, marks):
{roll} superkey
{roll, name} superkey (roll alone
suffices — name is
redundant)
{roll, name, marks, dept} superkey
{nat_id} superkey
{name} NOT a superkey — two
students may share a name
CANDIDATE KEY
A MINIMAL superkey — remove any attribute and it stops
being unique. Also called an IRREDUCIBLE superkey.
{roll} candidate key ✔ minimal
{nat_id} candidate key ✔ minimal
{roll, name} NOT a candidate key — not minimal
A relation may have SEVERAL candidate keys.
PRIMARY KEY
The ONE candidate key the designer chooses as the official
identifier.
· exactly one per relation
· implicitly NOT NULL
· used by foreign keys elsewhere
ALTERNATE KEY (secondary key)
Every candidate key NOT chosen as primary.
if roll is primary, then nat_id is an alternate key
→ declared with UNIQUE
COMPOSITE KEY
A key made of two or more attributes.
enrolment(roll, course_code) — neither alone is unique
FOREIGN KEY
An attribute (or set) in one relation that references the
primary key of another — possibly the same relation.
student.dept_code → department.code
SIMPLE / SURROGATE / NATURAL
natural key — has real-world meaning (nat_id, ISBN,
vehicle registration)
surrogate key — system-generated, meaningless
(SERIAL, IDENTITY, UUID)
Worked example — enumerating keys
Given: enrolment(roll, course_code, semester, grade)
with the rule "a student may take a course once per
semester".
STEP 1 — which attribute sets are unique?
{roll} ✗ a student takes many courses
{course_code} ✗ many students per course
{roll, course_code} ✗ retakes in another semester
{roll, course_code, semester} ✔ unique by the stated rule
{grade} ✗ many students share a grade
STEP 2 — superkeys are that set plus anything:
{roll, course_code, semester}
{roll, course_code, semester, grade}
→ 2 superkeys
STEP 3 — candidate keys are the MINIMAL ones:
{roll, course_code, semester} ← removing any one breaks
uniqueness, so minimal
→ exactly ONE candidate key, which therefore must be the
primary key. There are no alternate keys.
COUNTING SUPERKEYS — a standard exam calculation.
If a relation has n attributes and K is a candidate key,
every superset of K is a superkey. The remaining
(n − |K|) attributes may each be present or absent:
number of superkeys containing K = 2^(n − |K|)
enrolment: n = 4, |K| = 3
→ 2^(4−3) = 2^1 = 2 superkeys ✔ matches above
student(roll, nat_id, name, dept, marks), n = 5
with candidate keys {roll} and {nat_id}:
superkeys containing roll = 2^4 = 16
superkeys containing nat_id = 2^4 = 16
containing BOTH (counted twice) = 2^3 = 8
total distinct = 16 + 16 − 8 = 24 superkeys
(inclusion–exclusion — the standard trap is forgetting
to subtract the overlap)
keys.sql
-- roll is the PRIMARY key; nat_id and email are ALTERNATE
-- keys, declared with UNIQUE.
CREATE TABLE student (
roll INTEGER PRIMARY KEY, -- primary
nat_id CHAR(11) UNIQUE, -- alternate
email VARCHAR(80) UNIQUE, -- alternate
name VARCHAR(60) NOT NULL, -- not a key
dept_code CHAR(6) NOT NULL REFERENCES department(code),
marks NUMERIC(5,2)
);
INSERT INTO student VALUES
(101, '12345678901', 'ram@x.com', 'Ram', 'ACtE07', 87.5),
(102, NULL, NULL, 'Sita', 'ACtE07', 91.0),
(103, NULL, NULL, 'Hari', 'AExE01', 76.5);
-- === UNIQUE allows MULTIPLE NULLs ===
SELECT roll, nat_id, email FROM student ORDER BY roll;
-- roll | nat_id | email
-- -----+-------------+-----------
-- 101 | 12345678901 | ram@x.com
-- 102 | |
-- 103 | |
-- Rows 102 and 103 BOTH have NULL nat_id — and that is
-- legal, because NULL is not equal to NULL.-- === PRIMARY KEY rejects NULL === INSERT INTO student VALUES (NULL, '999', 'x@y.com', 'Ghost',
'ACtE07', 50);
-- ERROR: null value in column "roll" of relation "student"
-- violates not-null constraint-- === why: three-valued logic ===
SELECT NULL = NULL AS "null=null",
NULL IS NULL AS "null is null",
(NULL <> 1) AS "null<>1",
COUNT(*) AS total,
COUNT(nat_id) AS non_null_natid
FROM student;
-- null=null | null is null | null<>1 | total | non_null_natid
-- ----------+--------------+---------+-------+---------------
-- | t | | 3 | 1
--
-- null=null and null<>1 are both UNKNOWN (printed blank),
-- not true and not false. Only IS NULL works.
-- COUNT(*) counts rows; COUNT(col) SKIPS NULLs.
That output is the single most important practical difference
between PRIMARY KEY and UNIQUE:
PRIMARY KEY = UNIQUE + NOT NULL, one per table
UNIQUE = uniqueness only, NULLs permitted, and you
may have many UNIQUE constraints
And the reason multiple NULLs are allowed follows from SQL's
three-valued logic. A UNIQUE constraint rejects a new row
only if it is EQUAL to an existing one. Since
NULL = NULL → UNKNOWN, not TRUE
the engine cannot conclude the rows are equal, so both are
accepted.
CONSEQUENCES worth remembering:
· WHERE nat_id = NULL matches NOTHING, ever
· WHERE nat_id IS NULL is the only correct form
· WHERE nat_id <> '123' EXCLUDES rows where nat_id is
NULL, which surprises people
· COUNT(*) = 3 but COUNT(nat_id) = 1
(The SQL:2023 standard added UNIQUE NULLS NOT DISTINCT to
opt out of this, and PostgreSQL 15+ supports it — but the
default everywhere is NULLS DISTINCT, as shown.)
The WHERE nat_id <> '123' case is a genuine source of production bugs. Intuitively it means "every row whose ID is not 123", but rows with a NULL ID are excluded, because NULL <> '123' is UNKNOWN rather than TRUE. The correct form is WHERE nat_id IS DISTINCT FROM '123', or WHERE nat_id <> '123' OR nat_id IS NULL.
Natural versus surrogate primary keys
NATURAL KEY SURROGATE KEY
(nat_id, ISBN) (SERIAL, UUID)
─────────────────────────────────────────────────────────
meaning real-world none
stability can CHANGE never changes
(a corrected ID)
size often wide (CHAR(11)) narrow (4-8 bytes)
readable in FK yes — you can see no — 4718 tells you
the value nothing
joins needed fewer (the FK already more (must join to
carries the value) read the value)
privacy leaks data into every safe
child table
supply external you control it
duplicate risk none the natural key still
needs UNIQUE
THE ARGUMENT FOR SURROGATES, which most production schemas
follow:
A primary key is propagated into every referencing table.
If it can ever change, that change must cascade everywhere.
A meaningless integer can never need to change, so it never
cascades.
THE ARGUMENT FOR NATURAL KEYS:
Fewer joins, and the data is self-describing. A junction
table (roll, course_code) is immediately readable; a table
of (4718, 9902) is not.
THE RULE THAT SETTLES MOST CASES:
use a surrogate primary key AND declare the natural key
UNIQUE. You get stability and you still get the integrity
the natural key provides.
CREATE TABLE student (
id SERIAL PRIMARY KEY, -- surrogate
nat_id CHAR(11) UNIQUE NOT NULL, -- natural, still
roll INTEGER UNIQUE NOT NULL, enforced
name VARCHAR(60) NOT NULL
);
Omitting those UNIQUE constraints is the classic mistake:
the table then happily accepts two rows for the same real
person, because their surrogate ids differ.
surrogate_vs_natural.sql
-- ===== the cost of a MUTABLE natural key =====
-- Suppose nat_id is the primary key and it must be corrected.
CREATE TABLE person_nat (
nat_id CHAR(11) PRIMARY KEY,
name VARCHAR(60) NOT NULL
);
CREATE TABLE enrol_nat (
nat_id CHAR(11) REFERENCES person_nat(nat_id)
ON UPDATE CASCADE, -- REQUIRED
course CHAR(8),
PRIMARY KEY (nat_id, course)
);
CREATE TABLE fee_nat (
nat_id CHAR(11) REFERENCES person_nat(nat_id)
ON UPDATE CASCADE,
amount NUMERIC(10,2),
PRIMARY KEY (nat_id, amount)
);
INSERT INTO person_nat VALUES ('12345678901', 'Ram Bahadur');
INSERT INTO enrol_nat VALUES ('12345678901', 'ACtE0703');
INSERT INTO fee_nat VALUES ('12345678901', 15000);
-- the ID was recorded wrongly and must be correctedUPDATE person_nat SET nat_id = '99999999999'
WHERE nat_id = '12345678901';-- This works ONLY because every FK declared ON UPDATE
-- CASCADE. The update silently rewrites rows in enrol_nat
-- and fee_nat too. With 50 child tables that is 50 cascaded
-- writes, all inside one transaction, holding locks.
SELECT * FROM enrol_nat;
-- nat_id | course
-- ------------+----------
-- 99999999999 | ACtE0703 <- silently rewritten-- ===== the surrogate version: nothing cascades =====
CREATE TABLE person_sur (
id SERIAL PRIMARY KEY, -- stable
nat_id CHAR(11) UNIQUE NOT NULL, -- still enforced
name VARCHAR(60) NOT NULL
);
CREATE TABLE enrol_sur (
person_id INTEGER REFERENCES person_sur(id),
course CHAR(8),
PRIMARY KEY (person_id, course)
);
INSERT INTO person_sur (nat_id, name)
VALUES ('12345678901', 'Ram Bahadur');
INSERT INTO enrol_sur VALUES (1, 'ACtE0703');
-- correcting the ID touches ONE row in ONE table
UPDATE person_sur SET nat_id = '99999999999' WHERE id = 1;
-- enrol_sur is untouched — it references id, not nat_id.
-- and the natural key is STILL protected:
INSERT INTO person_sur (nat_id, name)
VALUES ('99999999999', 'Impostor');
-- ERROR: duplicate key value violates unique constraint
-- "person_sur_nat_id_key"
Foreign keys and referential actions
A foreign key states: this value must exist in the
referenced table (or be NULL).
REFERENTIAL INTEGRITY is the guarantee that no "dangling
reference" exists. The DBMS enforces it on every INSERT,
UPDATE and DELETE.
WHAT HAPPENS WHEN THE PARENT CHANGES — the five actions:
ON DELETE / ON UPDATE ...
NO ACTION (default) reject if children exist; the check
is deferred to the end of the statement
RESTRICT reject immediately — cannot be deferred
CASCADE delete/update the children too
SET NULL set the child's FK to NULL
(requires the column to be nullable)
SET DEFAULT set the child's FK to its DEFAULT value
(that default must itself exist in the parent)
CHOOSING CORRECTLY — the semantics decide, not convenience:
order_line → orders ON DELETE CASCADE
a line has no meaning without its order
student → department ON DELETE RESTRICT
deleting a department with students must FAIL — the
students still exist and need a department
student → advisor(professor) ON DELETE SET NULL
if the advisor leaves, the student remains but has no
advisor
Getting this wrong is destructive: CASCADE on
student → department would silently delete every student
when a department is closed.
SELF-REFERENCING foreign keys are common and legal:
CREATE TABLE employee (
emp_id INTEGER PRIMARY KEY,
name VARCHAR(60) NOT NULL,
mgr_id INTEGER REFERENCES employee(emp_id)
);
mgr_id is NULL for the top of the hierarchy. This models a
tree, and querying it needs a recursive CTE (WITH
RECURSIVE).
🌍 Go further: the surrogate-key choice has a second dimension nobody mentions in a first course: which kind of surrogate. A sequential integer is compact and index-friendly but leaks information (order id 5000 tells a competitor your volume) and cannot be generated offline. A random UUID solves both but is 16 bytes and destroys index locality, because inserts land at random points in the B-tree. That is why UUIDv7 and ULID were designed — time-ordered so they keep locality while staying unguessable. Search "UUID vs auto increment primary key performance" and "UUIDv7 time ordered".
💡 Exam angle: define superkey, candidate key, primary key, alternate key, composite key, foreign key and be able to enumerate them for a given relation — that is the standard question. Know the 2^(n−|K|) superkey count formula and use inclusion–exclusion when there are two candidate keys. State that PRIMARY KEY = UNIQUE + NOT NULL and that UNIQUE permits multiple NULLs, with three-valued logic as the reason. List the five referential actions and justify a choice from the semantics.
Syllabus points
Attribute types
Super, candidate, primary keys
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Data Models, Normalization, and SQL