Relational model, keys and integrity constraints
Learning goals and assumptions
Distinguish schemas from instances, prove candidate keys from constraints, and trace updates under referential integrity. Classical relations use set semantics: no duplicate tuples and no row order. SQL tables often use bags and may contain NULL; those differences must be stated rather than imported silently into relational theory.
1. Relation schema versus instance
A schema R(A,B,C) names attributes and their domains. An instance r is the current set of tuples satisfying the constraints. Degree is the number of attributes; cardinality is the number of tuples. A relation with three attributes and seven tuples has degree 3 and cardinality 7. An empty relation still has its schema and degree. An attribute value must come from its domain; domain constraints can be stronger than a primitive type, such as credits being a positive integer.
Relational tuples are mappings from attribute names to values. A displayed column order is presentation; operations must match the intended attributes. Keys and dependencies are assertions about every legal instance, not patterns inferred with certainty from one small sample.
2. Superkeys, candidate keys and primary keys
A superkey is an attribute set that uniquely identifies each tuple in every legal instance. A candidate key is a minimal superkey: removing any attribute destroys that guaranteed identification. Minimal means inclusion-minimal, not necessarily the smallest number of attributes among all candidate keys. The primary key is one chosen candidate key; remaining candidate keys are alternate keys. Supersets of a candidate key are superkeys but usually not candidate keys.
Worked derivation: Student(sid,email,name,dept) has the rules that sid and email each uniquely identify a student and neither is NULL; no other identification rule is assumed. {sid} and {email} are candidate keys. {sid,name} is a superkey but not a candidate key because name can be removed. {name,dept} is not guaranteed to be a key even if today's rows happen to differ on it.
For Enrolment(sid,cid,grade), assume one grade per student–course pair and no rule that one student takes only one course or a course has only one student. {sid,cid} is a candidate key. Neither singleton suffices. Later functional-dependency lessons will provide a general closure algorithm for discovering keys rather than guessing from attribute names.
3. Integrity constraints
Entity integrity requires primary-key components to be non-null in the SQL implementation. Referential integrity requires a non-null foreign-key value to match an allowed referenced key. A foreign key may have multiple attributes; compare the complete corresponding tuple. Foreign-key values need not be unique in the referencing table. A foreign key can reference its own table, as in Employee.managerId referencing Employee.eid.
Use an explicit SQL-like model here: Department(did PRIMARY KEY), Student(sid PRIMARY KEY, did NOT NULL REFERENCES Department(did)). Department contains {10,20}; Student contains (1,10),(2,10). Inserting (3,20) is valid. Inserting (3,30) violates the reference; inserting (1,20) violates primary-key uniqueness; inserting (3,NULL) violates NOT NULL. There may be a department with no students, and many students may reference department 10.
4. Updates have policy-dependent consequences
If Student.did references Department.did and a department is deleted, the result depends on the declared action. Under immediate NO ACTION with no other changes in the statement, deleting a referenced department fails. CASCADE deletes referencing student rows. SET NULL requires that the referencing column permit NULL; it cannot successfully preserve a NOT NULL requirement by setting NULL. Updating a referenced key is similarly subject to its update policy. Do not assume CASCADE when the problem does not state it. Timing differences such as deferred checks are outside this immediate-check example.
Worked trace under immediate NO ACTION: Department={10,20}, Student={(1,10),(2,10)}. Deleting Department 20 succeeds because no row references it. Deleting Department 10 fails because students 1 and 2 still reference it. Deleting those students first and then deleting Department 10 succeeds. With DELETE CASCADE, the single parent deletion would remove those students automatically.
5. Logical guarantees versus accidental data
Given rows (A,B)={(1,x),(2,y)}, both columns happen to be unique. This does not prove either is a declared key for all future legal states. Conversely, two rows with the same A and different B refute A as a key for that observed instance. An instance can refute a proposed universal constraint, but a finite example normally cannot establish the business rule.
Pitfalls
- Degree is columns; cardinality is rows. Do not confuse either with key size.
- Candidate-key minimality is checked by removing attributes, not comparing only cardinalities.
- A foreign key need not be a key of its own relation and does not itself imply NOT NULL.
- A composite foreign key is a joint reference, not independent matches from unrelated parent rows.
- SQL UNIQUE and NULL behavior require care and product-specific details; do not equate every nullable UNIQUE declaration with a classical candidate key.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. A relation has 4 attributes and 9 tuples. Its degree and cardinality are:
A. (9,4) B. (4,9) C. (4,4) D. (9,9)
Answer: B
A: This reverses rows and attributes.
B: Degree counts attributes; cardinality counts tuples.
C: Cardinality is nine, not four.
D: Degree is four, not nine.
P02. If {A} is a candidate key, which statement must hold about {A,B}?
A. It is not a superkey B. It is always a candidate key C. It is a superkey but not a candidate key D. It cannot appear in a schema
Answer: C
A: Adding attributes preserves uniqueness.
B: A can identify without B, so it is not minimal.
C: It identifies tuples but B is removable.
D: There is no such schema restriction.
P03. Several Student rows have the same valid department foreign key. This is:
A. Always a primary-key violation B. Always a foreign-key violation C. Allowed unless an additional constraint forbids it D. Allowed only if the department is absent
Answer: C
A: The foreign-key column is not stated to be the primary key.
B: Repeated references to an existing parent are legal.
C: Foreign keys do not impose referencing-column uniqueness.
D: The referenced department must exist for non-null references.
P04. Under immediate NO ACTION, deleting a department still referenced by a student will:
A. Delete the student automatically B. Fail the referential-integrity check C. Set the foreign key to zero D. Rename the department
Answer: B
A: That would require DELETE CASCADE.
B: The surviving reference would lack a parent.
C: NO ACTION does not invent a default value.
D: No rename policy is implied.
P05. Which observation disproves A being a key in the observed R(A,B) instance?
A. Two rows (1,x) and (2,x) B. Two rows (1,x) and (1,y), x≠y C. No rows D. One row (1,x)
Answer: B
A: A values differ, so this does not violate A uniqueness.
B: Distinct tuples share the same A.
C: An empty instance does not violate uniqueness.
D: One row does not violate uniqueness.
P06. A composite foreign key (X,Y) references a parent key (A,B). Parent rows are (1,2),(3,4). Which non-null value matches?
A. (1,4) B. (3,2) C. (1,2) D. (2,1)
Answer: C
A: The components occur separately but the pair does not exist.
B: The complete pair is absent.
C: The complete corresponding parent key exists.
D: Attribute correspondence matters; reversing the pair does not match.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in