Skip to content

Lesson 10: Keys and Relational Integrity Constraints

Superkeys, candidate keys, foreign keys — and the rules that keep data true

About this lesson

Course: Database Management Systems

Unit 3: Relational Data Model · 7 Lecture Hours

Lesson duration: 2 lectures

Reading: Elmasri & Navathe, Ch. 5.2, 5.3

Learning Outcomes

  1. Define and compute superkey, candidate key, primary key, alternate key, composite key, foreign key.
  2. Classify constraints as inherent, schema-based or application-based.
  3. State and apply the three schema-based constraints: domain, entity integrity, referential integrity.
  4. Determine which operations violate which constraint, and name the DBMS's options.
  5. Choose the correct referential action (CASCADE, SET NULL, RESTRICT, NO ACTION, SET DEFAULT).

10.1 Keys

Characteristic 4 of Lesson 1 said a relation cannot contain duplicate tuples. It follows that every relation has a key. This section makes that precise.

Superkey

Superkey

A set of attributes SK ⊆ R such that no two distinct tuples in any valid state of R can have the same values for SK.

Formally: for any two distinct tuples t1 and t2 in r(R), t1[SK] ≠ t2[SK].

Because no relation contains duplicates, the set of all attributes is always a superkey. Every relation therefore has at least one.

Candidate key

Candidate key

A minimal superkey — a superkey from which no attribute can be removed and still leave a superkey.

Minimality is a property of the set, not of its size: {A, B} is minimal if neither {A} nor {B} alone is a superkey.

Minimal is not the same as smallest

A relation may have candidate keys of different sizes — {Rollno} and {Name, Dateofbirth, Address} could both be candidate keys. Both are minimal (no attribute can be dropped from either). "Minimal" means irreducible, not shortest.

Primary key and alternate keys

Primary key

The candidate key chosen by the designer as the principal means of identifying tuples. Exactly one per relation. Its attributes are underlined in the schema notation, and it may never be NULL.

Alternate key

Any candidate key not chosen as the primary key. Declared UNIQUE in SQL.

Composite key

A key consisting of more than one attribute. ADMISSION has the composite primary key (Rollno, SID).

A complete worked example

ENROLLMENT( Rollno, SocID, Dateofenrolment, StudentName, Socname )

Business rules: a student enrols in a society at most once; Rollno determines StudentName; SocID determines Socname.

Finding the superkeys. Since a (Rollno, SocID) pair occurs at most once, {Rollno, SocID} is a superkey. Any set containing it is also a superkey:

{Rollno, SocID}
{Rollno, SocID, Dateofenrolment}
{Rollno, SocID, StudentName}
{Rollno, SocID, Socname}
{Rollno, SocID, Dateofenrolment, StudentName}
... and so on, up to all five attributes.

With three remaining attributes there are 2^3 = 8 supersets, so there are 8 superkeys.

Finding the candidate keys. Is {Rollno, SocID} minimal? Remove SocID: {Rollno} is not a superkey, because a student may join several societies. Remove Rollno: {SocID} is not a superkey, because a society has many members. Neither can be dropped, so {Rollno, SocID} is minimal — a candidate key.

Is there any other candidate key? No other set is a superkey without containing both Rollno and SocID.

Result: one candidate key {Rollno, SocID}, which is therefore the primary key (composite). There are no alternate keys.

Procedure for finding candidate keys by inspection

  1. List the attributes and the business rules stating what is unique.
  2. Test each single attribute: is it unique on its own? Each that is, is a candidate key.
  3. Test pairs built from attributes that are not already candidate keys, and so on for larger sets.
  4. Never include a set that already contains a candidate key — it cannot be minimal.
  5. Stop when every attribute has been covered.

A rigorous algorithm using functional dependencies and attribute closure is given in Unit 5, Lesson 3.

Foreign key

Foreign key

A set of attributes FK in relation R1 (the referencing or child relation) is a foreign key referencing relation R2 (the referenced or parent relation) if:

  1. The attributes of FK have the same domains as the primary key attributes PK of R2. FK is said to reference R2.
  2. For every tuple t1 in r(R1), either t1[FK] matches the value of t2[PK] for some tuple t2 in r(R2), or t1[FK] is wholly NULL.

In ADMISSION(Rollno, SID, Dateofadmission):

  • Rollno is a foreign key referencing STUDENT(Rollno).
  • SID is a foreign key referencing COURSE(SID).

Foreign keys are how the relational model represents relationships — by matching values, not by pointers. This is the source of its data independence (Unit 1).

     STUDENT (parent)                COURSE (parent)
   +--------+-------------+       +------+-----------------+
   | Rollno | Name        |       | SID  | Cname           |
   +--------+-------------+       +------+-----------------+
   | X2019  | Ankit Sharma|       | CS01 | Computer Science|
   | X2020  | Riya Verma  |       | MA02 | Mathematics     |
   +---+----+-------------+       +---+--+-----------------+
       ^                              ^
       |  referenced by               |  referenced by
       |                              |
   +---+----+------+-----------------+
   | Rollno | SID  | Dateofadmission |     ADMISSION (child)
   +--------+------+-----------------+
   | X2019  | CS01 | 2019-07-15      |  <- valid: both parents exist
   | X2019  | MA02 | 2019-08-01      |  <- valid
   | X9999  | CS01 | 2019-07-20      |  <- INVALID: no student X9999
   +--------+------+-----------------+

Figure 2.1 — Foreign keys link relations by matching values.

Three subtleties about foreign keys

  1. A foreign key may reference its own relation. EMPLOYEE(Ssn, Name, SuperSsn) where SuperSsn references EMPLOYEE(Ssn) — a recursive relationship.
  2. A foreign key may be part of the primary key. In ADMISSION, both Rollno and SID are foreign keys and together form the primary key. When this happens the foreign key cannot be NULL, because primary keys cannot be NULL.
  3. A composite foreign key must be wholly NULL or wholly matching. A partially NULL composite foreign key is not permitted under the standard's MATCH FULL semantics.

10.2 Classification of Constraints

Three categories

1. Inherent model-based (implicit) constraints — built into the definition of the relational model itself, so they need not be declared. Examples: a relation cannot contain duplicate tuples; attribute values must be atomic.

2. Schema-based (explicit) constraints — expressible in the DDL and enforced automatically by the DBMS. These are the three below, plus NOT NULL and CHECK.

3. Application-based (semantic) constraints / business rules — not expressible in the DDL, so they must be enforced by application programs or by triggers and assertions. Example: "a student may not be admitted to two full-time courses simultaneously", or "an employee's salary may not exceed that of their supervisor".

A fourth category is sometimes listed: data dependencies (functional and multivalued dependencies), which are used in normalisation rather than enforced directly. These are Unit 5.

10.3 The Three Schema-Based Constraints

Domain constraints

Domain constraint

The value of each attribute A in every tuple must be an atomic value from dom(A).

TotalSeats  INT          CHECK (TotalSeats > 0),
Coursetype  VARCHAR(10)  CHECK (Coursetype IN ('Fulltime','Parttime')),
Dateofbirth DATE         NOT NULL

Domain constraints cover the data type, the length, and any CHECK restriction. NOT NULL is also a domain-level constraint.

Key constraints and entity integrity

Key constraint

No two distinct tuples may have the same value for a candidate key. Declared PRIMARY KEY or UNIQUE.

Entity integrity constraint

No primary key value may be NULL — not even one attribute of a composite primary key.

Why? Because the primary key is the only means of identifying a tuple. A NULL means "unknown or inapplicable"; a tuple whose identifier is unknown cannot be distinguished from another such tuple, cannot be referenced by a foreign key, and cannot be updated or deleted individually. Permitting NULL primary keys would destroy the identification mechanism on which the whole model rests.

Entity integrity applies only to the primary key

Alternate keys (UNIQUE) may be NULL in SQL — and a UNIQUE column may hold several NULLs in most systems, since NULL = NULL is UNKNOWN, so two NULLs are not considered duplicates. Only the primary key is protected by entity integrity.

Referential integrity

Referential integrity constraint

A tuple in the referencing relation that refers to another relation must refer to an existing tuple in it.

Formally: for every tuple t1 in r(R1) with foreign key FK, either t1[FK] = t2[PK] for some t2 in r(R2), or t1[FK] is NULL.

Referential integrity is the constraint that prevents dangling references — an admission for a student who does not exist, an order for a customer who was deleted.

Entity integrity vs referential integrity

Entity integrity Referential integrity
Concerns The primary key The foreign key
Says PK may not be NULL FK must match an existing PK, or be NULL
Involves One relation Two relations (or one, if self-referencing)
Prevents Unidentifiable tuples Dangling references
SQL PRIMARY KEY FOREIGN KEY ... REFERENCES

10.4 Which Operations Violate Which Constraint

This is the classic examination table. Learn it by reasoning, not memorisation: an operation can only violate a constraint by creating something new that must be checked.

INSERT

Constraint Can INSERT violate it? How
Domain Yes A value outside the domain: TotalSeats = -5.
Key Yes A primary key value that already exists.
Entity integrity Yes NULL in a primary key attribute.
Referential integrity Yes A foreign key value with no matching parent tuple.

INSERT can violate all four.

DELETE

Constraint Can DELETE violate it? How
Domain No Removing a tuple creates no new value.
Key No Removing a tuple cannot create a duplicate.
Entity integrity No Removing a tuple cannot create a NULL PK.
Referential integrity Yes Deleting a parent tuple that a child still references.

DELETE can violate only referential integrity, and only when deleting from the referenced (parent) relation.

UPDATE

Attribute updated Constraints that may be violated
An ordinary attribute Domain
A primary key attribute Domain, key, entity integrity, and referential integrity (children now dangle)
A foreign key attribute Domain, referential integrity

UPDATE is effectively a DELETE followed by an INSERT, so it can violate any constraint.

What the DBMS does on violation

Three options, in order of preference:

  1. Reject the operation and return an error. The default, and almost always correct.
  2. Cascade or otherwise propagate the change automatically (Section 2.5).
  3. Inform the user and offer a choice — used by interactive tools, not by the engine.

10.5 Referential Actions

When a parent tuple is deleted or its primary key updated, SQL lets you declare what happens to the children.

CREATE TABLE ADMISSION (
    Rollno          VARCHAR(8),
    SID             VARCHAR(6),
    Dateofadmission DATE,
    PRIMARY KEY (Rollno, SID),
    FOREIGN KEY (Rollno) REFERENCES STUDENT(Rollno)
        ON DELETE CASCADE  ON UPDATE CASCADE,
    FOREIGN KEY (SID)    REFERENCES COURSE(SID)
        ON DELETE RESTRICT ON UPDATE CASCADE
);
Action On deleting/updating the parent When to use
RESTRICT Reject immediately if any child exists. The default intent. Safest: forces the user to deal with children explicitly.
NO ACTION Reject, but the check is deferred to the end of the statement. Standard default. Allows a statement that temporarily breaks and then repairs the reference.
CASCADE Delete the children too / update their FK to the new value. When the child is existence-dependent on the parent — a weak entity, an order line, an admission record. Use with care: deletions propagate.
SET NULL Set the children's FK to NULL. When the child can meaningfully exist "unassigned" — an employee whose department is dissolved. Impossible if the FK is part of the primary key.
SET DEFAULT Set the children's FK to its declared default. Rare; requires the default value to exist in the parent.

Choosing correctly — a worked judgement

ADMISSION.Rollno → STUDENT.Rollno: if a student's record is deleted, their admissions are meaningless. ON DELETE CASCADE is right.

ADMISSION.SID → COURSE.SID: if a course is deleted while students are admitted to it, cascading would silently erase those students' admission history. ON DELETE RESTRICT is right — force the administrator to transfer or explicitly remove the students first.

SET NULL is impossible for both, because Rollno and SID are part of ADMISSION's primary key, and entity integrity forbids NULL there.

ON UPDATE CASCADE is almost always right, because a primary key value changing is a renaming of the same real-world entity, and children should follow. Better still, choose primary keys that never change (Unit 2, Lesson 2).

10.6 Solved Questions

Solved Question 1

Q. For STUDENT(Rollno, AadhaarNo, Email, Name, Dateofbirth) where Rollno, AadhaarNo and Email are each unique, list five superkeys, all candidate keys, choose a primary key, and name the alternate keys.

A.

Superkeys (any set containing at least one unique attribute): {Rollno}, {AadhaarNo}, {Email}, {Rollno, Name}, {AadhaarNo, Email, Dateofbirth} — and many more, including the full attribute set.

Candidate keys — the minimal superkeys: {Rollno}, {AadhaarNo}, {Email}. Each is a single attribute and unique, hence irreducible. {Rollno, Name} is a superkey but not minimal, since {Rollno} alone suffices.

Primary key: Rollno. Justification against the five criteria of Unit 2, Lesson 2:

Criterion Rollno AadhaarNo Email
Stable (never changes) Yes Yes No — people change addresses
Always available at creation Yes No — may not be supplied yet Usually
Short and simple Yes Yes No — long string
Not privacy-sensitive Yes No — national identity number Moderately

Rollno wins on every criterion.

Alternate keys: AadhaarNo and Email. In SQL they become UNIQUE constraints:

Rollno    VARCHAR(8)  PRIMARY KEY,
AadhaarNo CHAR(12)    UNIQUE,
Email     VARCHAR(60) UNIQUE

Solved Question 2

Q. Define entity integrity and referential integrity. Why is entity integrity necessary? Give an example of each being violated.

A.

Entity integrity: no attribute of a primary key may be NULL in any tuple.

Why necessary? The primary key is the sole means of identifying a tuple. NULL means "unknown or not applicable". If a primary key could be NULL then: (i) the tuple could not be distinguished from another NULL-keyed tuple, so uniqueness would be unenforceable; (ii) no foreign key could reference it; (iii) it could not be individually updated or deleted, since there would be no way to name it. The identification mechanism on which the entire model rests would collapse.

Violation: INSERT INTO STUDENT VALUES (NULL, 'Ankit Sharma', '2001-03-14'); — rejected, because Rollno is the primary key.

Referential integrity: every non-NULL foreign key value must match an existing primary key value in the referenced relation.

Why necessary? It prevents dangling references — child tuples pointing at parents that do not exist — which would make joins lose rows and reports understate totals.

Violation: INSERT INTO ADMISSION VALUES ('X9999','CS01','2019-07-20'); when no student X9999 exists — rejected. Equally, DELETE FROM STUDENT WHERE Rollno='X2019'; while admissions for X2019 remain — rejected under RESTRICT, or cascaded under ON DELETE CASCADE.

Solved Question 3

Q. State which constraints each operation can violate, and justify.

A.

INSERT can violate all four, because it introduces a wholly new tuple, every part of which must be checked: a value may lie outside its domain; the primary key value may duplicate an existing one; a primary key attribute may be NULL; and a foreign key may name a non-existent parent.

DELETE can violate only referential integrity. Removing a tuple creates no new value, so it cannot break a domain constraint; it cannot create a duplicate, so it cannot break a key constraint; and it cannot create a NULL primary key. But deleting a tuple from a parent relation may leave children referencing a row that no longer exists.

UPDATE can violate any of the four, because it is logically a DELETE followed by an INSERT. Specifically:

Attribute updated Possible violations
Ordinary attribute Domain only
Primary key attribute Domain, key, entity integrity, and referential integrity (children left dangling)
Foreign key attribute Domain, referential integrity

On violation the DBMS may reject the operation (the default), propagate the change via a declared referential action, or report and offer options in an interactive tool.

Solved Question 4

Q. Consider STUDENT(Rollno, Name), COURSE(SID, Cname) and ADMISSION(Rollno, SID, Dateofadmission) with the obvious foreign keys. State whether each operation succeeds, and if not, which constraint is violated.

Current data: STUDENT = {(X2019,'Ankit'), (X2020,'Riya')}; COURSE = {(CS01,'CompSci')}; ADMISSION = {(X2019, CS01, 2019-07-15)}.

a. INSERT INTO ADMISSION VALUES ('X2020','CS01','2019-07-16'); b. INSERT INTO ADMISSION VALUES ('X2021','CS01','2019-07-17'); c. INSERT INTO ADMISSION VALUES ('X2019','CS01','2019-08-01'); d. DELETE FROM STUDENT WHERE Rollno = 'X2020'; e. DELETE FROM STUDENT WHERE Rollno = 'X2019'; f. UPDATE COURSE SET SID = 'CS02' WHERE SID = 'CS01'; g. INSERT INTO ADMISSION VALUES ('X2020', NULL, '2019-07-18');

A.

Result Constraint
a Succeeds Both parents exist; the pair (X2020, CS01) is new.
b Fails Referential integrity — no student X2021 in STUDENT.
c Fails Key constraint — the primary key (X2019, CS01) already exists. (Note the date differs, but it is not part of the key.)
d Succeeds X2020 has no admissions, so no child dangles.
e Depends on the declared action. Under RESTRICT/NO ACTION: fails on referential integrity, because (X2019, CS01) references it. Under ON DELETE CASCADE: succeeds, and the admission row is deleted too. Under SET NULL: fails anyway, because Rollno is part of ADMISSION's primary key and entity integrity forbids NULL there.
f Depends. Under ON UPDATE CASCADE: succeeds, and the admission row becomes (X2019,'CS02',...). Under RESTRICT: fails on referential integrity, since the child still references CS01.
g Fails Entity integrity — SID is part of ADMISSION's primary key and may not be NULL. (Were SID merely a foreign key and not part of the key, a NULL would be permitted by referential integrity.)

Solved Question 5

Q. Explain the five referential actions. For each foreign key in the college database, choose one and justify.

A. (Definitions as in the table of Section 2.5.)

ADMISSION.Rollno → STUDENT.Rollno

  • ON DELETE CASCADE. An admission record is meaningless without the student; if the student's record is removed, their admissions should go with it. The admission is existence-dependent on the student.
  • ON UPDATE CASCADE. If a roll number is corrected, all admissions must follow the same student.

ADMISSION.SID → COURSE.SID - ON DELETE RESTRICT. Deleting a course while students are admitted to it would silently destroy their admission history. The administrator must first transfer or explicitly remove those students. This is a case where the child carries information the parent's deletion should not be allowed to destroy. - ON UPDATE CASCADE, for the same reason as above.

ENROLLMENT.Rollno → STUDENT.Rollno — ON DELETE CASCADE, same reasoning as admissions.

ENROLLMENT.SocID → SOCIETY.SocID — ON DELETE CASCADE is defensible here: if a society is dissolved, its membership records have no independent meaning. (An institution that wants an audit trail would choose RESTRICT instead. The correct choice is a business decision, and the justification matters more than the answer.)

Why SET NULL is unavailable throughout: in every one of these foreign keys, the referencing column is part of the child's composite primary key, and entity integrity forbids a NULL there.

Solved Question 6

Q. Classify these constraints as inherent, schema-based or application-based, and state how each is enforced.

a. A relation cannot have two identical tuples. b. TotalSeats must be positive. c. Every admission must reference an existing student. d. A student may not be admitted to more than two full-time courses. e. Attribute values must be atomic. f. An employee's salary may not exceed their supervisor's.

A.

Category Enforcement
a Inherent (model-based) Follows from a relation being a set; requires no declaration. Note SQL only enforces it if a PRIMARY KEY or UNIQUE is declared, since SQL tables are multisets.
b Schema-based (domain) CHECK (TotalSeats > 0) — enforced automatically by the DBMS.
c Schema-based (referential integrity) FOREIGN KEY (Rollno) REFERENCES STUDENT(Rollno).
d Application-based (semantic / business rule) Not expressible as a simple column or table constraint, because it requires counting related rows in another table. Enforced by a trigger, an assertion (rarely implemented), or application code.
e Inherent Part of the definition of the relational model (1NF). The DBMS cannot detect a violation — storing '98111, 98222' in a VARCHAR is a design error, not a runtime error.
f Application-based Involves comparing two rows of the same table via a self-join. Requires a trigger.

The general principle: constraints involving one row of one table are schema-based; those spanning multiple rows or multiple tables in a computed way are application-based and need triggers.

10.7 Exercises

A. Short answer

  1. Define superkey and candidate key. Why is every relation guaranteed to have a superkey?
  2. Distinguish "minimal" from "smallest" for candidate keys.
  3. State the entity integrity constraint and give the reason for it.
  4. State the referential integrity constraint formally.
  5. Can a foreign key be NULL? Under what circumstance can it not?
  6. Name the five referential actions.
  7. Give one example each of an inherent, a schema-based and an application-based constraint.

B. Long answer

  1. Define superkey, candidate key, primary key, alternate key, composite key and foreign key, with an example of each from the college database.
  2. Explain the three schema-based constraints. For each, state the SQL that declares it and one operation that violates it.
  3. Explain which operations can violate which constraints, and justify each entry by reasoning rather than assertion.
  4. Explain the five referential actions with an example of when each is the correct choice.
  5. Distinguish entity integrity from referential integrity in a table of at least five rows of comparison.

C. Application and analytical

  1. For EMPLOYEE(Ssn, PAN, Name, Dno, SuperSsn, Salary) where Ssn and PAN are unique, Dno references DEPARTMENT(Dno) and SuperSsn references EMPLOYEE(Ssn): a. List all candidate keys. b. Identify all foreign keys, including any self-reference. c. Can SuperSsn be NULL? Justify with a business reason. d. Choose referential actions for both foreign keys and justify.
  2. For ORDER_LINE(OrderNo, LineNo, ProductNo, Qty) where line numbers restart at 1 for each order: a. What is the primary key? b. Which attributes are foreign keys? c. Which referential action should OrderNo use, and why? d. Explain why SET NULL is not available for OrderNo.
  3. Given R(A,B,C,D) where A → BCD and B → ACD (both A and B are unique): a. How many superkeys are there? Show the reasoning. b. List all candidate keys.
  4. Determine the result of each operation on the college database and name any constraint violated: a. Adding a course with TotalSeats = 0. b. Adding a second course with SID = 'CS01'. c. Deleting a course that has no admissions. d. Changing a student's Rollno when they have three admissions, with ON UPDATE CASCADE. e. Inserting an enrolment with a SocID that does not exist.
  5. A designer declares ON DELETE CASCADE on every foreign key in a system with ten tables. Describe a scenario in which deleting one row destroys most of the database. What policy would you recommend instead?
  6. Write the complete CREATE TABLE statements for STUDENT, COURSE and ADMISSION including every constraint discussed in this lesson, with justified referential actions.

D. Objective — True or False with reason

  1. Every candidate key is a superkey.
  2. Every superkey is a candidate key.
  3. A relation can have more than one primary key.
  4. A foreign key must always reference a different relation.
  5. A UNIQUE column may contain NULL.
  6. DELETE can violate the domain constraint.
  7. SET NULL is always available as a referential action.
  8. A composite key means the relation has two primary keys.

Answers to Section D

  1. True. A candidate key is by definition a minimal superkey.
  2. False. Only minimal ones are candidate keys; {Rollno, Name} is a superkey but not minimal.
  3. False. Exactly one primary key; the others are alternate keys, declared UNIQUE.
  4. False. It may reference its own relation — a self-reference, as with SuperSsn referencing Ssn.
  5. True. Entity integrity applies only to the primary key. Most systems even permit several NULLs in a UNIQUE column, since NULL = NULL is UNKNOWN.
  6. False. DELETE creates no new value, so it can violate only referential integrity, and only when deleting a parent tuple.
  7. False. It is impossible when the foreign key is part of the child's primary key, since entity integrity forbids a NULL there.
  8. False. A composite key is one key made of several attributes.

Lesson Summary

  • Superkey ⊃ candidate key (minimal superkey) → one chosen as primary key; the rest are alternate keys (UNIQUE).
  • A foreign key links relations by matching values, and may reference its own relation.
  • Constraints are inherent (built into the model), schema-based (CHECK, PRIMARY KEY, FOREIGN KEY, NOT NULL) or application-based (triggers and assertions).
  • Entity integrity: no NULL in a primary key. Referential integrity: every non-NULL foreign key matches an existing primary key.
  • INSERT can violate all four constraints; DELETE only referential integrity; UPDATE any of them.
  • Choose referential actions deliberately: CASCADE for existence-dependent children, RESTRICT where the child holds information worth protecting; SET NULL is unavailable when the foreign key is part of the primary key.