Relational Model and Functional Dependencies in DBMS: Keys, Closure and Minimal Cover

You may recognise tuple, key, closure and functional dependency, yet treat them as separate definitions. A seven-attribute relation connects legal rows, dependency rules, a candidate key, minimal cover and anomaly removal. Use it with GATE CS preparation courses and test series.

1. Relational model basics before functional dependencies

The schema is ENROLMENT_WIDE(StudentID, StudentName, Dept, CourseID, InstructorID, Room, Grade). A schema names attributes; an instance contains the current rows. Its degree is 7 and this instance's cardinality is 4.

Each column is an attribute and each row a tuple. Domains include IDs like S101, course codes like C201, rooms like R301, and grades in {A, A-, B+, B}.

The rules say a student ID fixes one name and department, a course has one instructor, an instructor has one room, and a student gets one grade per course. Derive keys from these rules, not accidental uniqueness in four rows.

2. What a functional dependency actually says

X -> Y means tuples agreeing on X must agree on Y in every legal instance. Both S101 tuples agree on Asha, CSE; both C201 tuples agree on I10. A sample can violate an FD, but cannot prove it. Add (S104, Neel, CSE, C201, I99, R301, A), and CourseID -> InstructorID fails because C201 gives both I10 and I99.

Start with:

• StudentID -> StudentName, Dept

• CourseID -> InstructorID

• InstructorID -> Room

• (StudentID, CourseID) -> Grade

• CourseID -> Room, included deliberately for a redundancy test

(StudentID, CourseID) -> StudentID is trivial. (StudentID, CourseID) -> Grade is fully functional because neither component determines Grade alone. Relative to the later key, the student and course FDs are partial; CourseID -> InstructorID -> Room is transitive. FDs are not causal, and arrows cannot be reversed.

3. Armstrong's axioms and dependency inference

Armstrong's sound and complete rules are:

• Reflexivity: {StudentID, CourseID} -> StudentID.

• Augmentation: from CourseID -> InstructorID, infer {StudentID, CourseID} -> {StudentID, InstructorID}.

• Transitivity: CourseID -> InstructorID and InstructorID -> Room imply CourseID -> Room.

Decomposition splits StudentID -> {StudentName, Dept}; Union recombines the two FDs. To derive Union, augment X -> Y by X to get X -> XY, augment X -> Z by Y to get XY -> YZ, then apply transitivity for X -> YZ.

F+ contains every FD implied by F; X+ contains every attribute determined by X. Test X -> Y by checking whether Y is within X+. Here, CourseID+ = {CourseID, InstructorID, Room}, so CourseID -> Room is implied.

4. Worked attribute closure and candidate-key calculation

Compute {StudentID, CourseID}+:

1. Start with {StudentID, CourseID}.

2. Add StudentName, Dept using StudentID -> StudentName, Dept.

3. Add InstructorID using CourseID -> InstructorID.

4. Add Room using InstructorID -> Room.

5. Add Grade using (StudentID, CourseID) -> Grade.

All seven attributes are present, so this is a superkey. It is minimal because StudentID+ = {StudentID, StudentName, Dept} and CourseID+ = {CourseID, InstructorID, Room} both fail. Neither determinant appears on a non-trivial FD's right side, so every key needs both. {StudentID, CourseID} is therefore the sole candidate key. Adding StudentName gives a non-minimal superkey; choosing a primary key remains a design decision.

Checkpoint: {StudentID, InstructorID}+ = {StudentID, InstructorID, StudentName, Dept, Room}. It cannot reach CourseID or Grade.

5. Worked minimal cover and equivalent FD sets

Split the first right side. The six singleton FDs are StudentID -> StudentName, StudentID -> Dept, CourseID -> InstructorID, InstructorID -> Room, (StudentID, CourseID) -> Grade, and CourseID -> Room.

Test the composite determinant. Without StudentID, CourseID+ = {CourseID, InstructorID, Room}. Without CourseID, StudentID+ = {StudentID, StudentName, Dept}. Neither contains Grade, so neither left-side attribute is extraneous.

Now remove CourseID -> Room temporarily. CourseID+ still reaches Room through CourseID -> InstructorID -> Room, so that FD is redundant. The minimal cover is:

G = {StudentID -> StudentName, StudentID -> Dept, CourseID -> InstructorID, InstructorID -> Room, (StudentID, CourseID) -> Grade}

The original set implies the split student FDs by decomposition; G implies the dropped FD by transitivity. Equivalence holds both ways.

6. Anomalies reveal why these dependencies matter

Changing I10 from R301 to R305 needs two C201 edits; missing one creates a contradiction. Course C204, taught by I40 in R501, cannot be stored before enrolment because a wide row needs a student and grade. Deleting (S103, Meera, CSE, C203, I30, R110, A-) erases all facts about C203 and I30.

The minimal cover suggests a dependency-preserving decomposition:

• STUDENT(StudentID, StudentName, Dept): (S101,Asha,CSE), (S102,Ravi,ECE), (S103,Meera,CSE)

• COURSE(CourseID, InstructorID): (C201,I10), (C202,I20), (C203,I30)

• INSTRUCTOR(InstructorID, Room): (I10,R301), (I20,R204), (I30,R110)

• RESULT(StudentID, CourseID, Grade): (S101,C201,A), (S101,C202,B+), (S102,C201,B), (S103,C203,A-)

The respective keys are StudentID, CourseID, InstructorID, and {StudentID, CourseID}. Every FD in G is locally enforceable. The goals are reduced redundancy, lossless reconstruction and dependency preservation, not merely more tables. Use normalization from 1NF to BCNF for the formal tests.

7. How GATE and interviews test functional dependencies

IIT Guwahati's official GATE 2026 CS syllabus lists relational model, integrity constraints and normal forms under Databases. Official CS2 Question 42 tests a Union derivation: augment X -> Y by X for X -> XY; augment X -> Z by Y for XY -> YZ; transitivity gives X -> YZ. The rules are augmentation and transitivity. Together, the syllabus and question show that definitions alone are insufficient; you must reproduce the derivation.

For this relation, the following statements hold:

• Does CourseID -> Room follow? Yes, by transitivity.

• Is {StudentID, CourseID} a candidate key? Yes, its closure is complete and both proper-subset closures fail.

• Does CourseID -> InstructorID survive the hypothetical C201, I99 row? No.

• Does CourseID -> Room stay in the minimal cover? No, it is redundant.

Practise with solved DBMS normalization MCQs. In interviews, reject sample uniqueness as proof, compute closure aloud, and connect the decomposition to all three anomalies. Placement-focused readers can revise with CS Fundamentals for Placements.

8. Common traps, the short version and the next step

Do not reverse CourseID -> InstructorID or infer an FD because C202 appears once. Not every superkey is a candidate key. Run closure to a fixed point. Remove an FD before testing its redundancy. Keep both grade determinants unless their subset closures prove otherwise.

Use this six-step method:

1. Write the schema.

2. Translate business rules into FDs.

3. Split right sides.

4. Compute closures.

5. Prove key minimality.

6. Remove extraneous parts and redundant FDs, then inspect anomalies.

The results are CourseID+ = {CourseID, InstructorID, Room}, {StudentID, CourseID}+ = all seven attributes, and minimal cover size 5. Rebuild both unaided, then use GATE Guidance by Sanchit Sir for a structured path.

Can you explain exactly why CourseID -> Room is true but absent from the minimal cover?