DBMS Keys & FDs
Keys in DBMS
Super Key
Any attribute set that uniquely identifies a tuple. May contain extra attributes.
RollNo, (RollNo, Name), Email
Example: Student(RollNo, Email, Name)
Candidate Key
Minimal Super Key. No redundant attributes.
RollNo, Email
CK ⊆ SK Every CK is a SK, but not vice versa.
Primary Key
Selected Candidate Key. No NULL values.
RollNo (chosen)
Alternate / Composite
Alternate: Candidate keys not selected as PK.
Composite: Key with ≥2 attributes.
(StudentID, CourseID)
Foreign Key
Refers to PK of another table. Maintains Referential Integrity.
DeptID → references Dept(DeptID)
May contain NULL.
Primary Key ⊆ Candidate Key ⊆ Super Key
Functional Dependency (FD)
Definition
X → Y If two tuples have same X, they must have same Y.
RollNo → Name
Trivial FD
If Y ⊆ X, then X → Y is always true.
(A,B) → A
Non‑Trivial
If Y ⊄ X
RollNo → Name
Completely Non‑Trivial
If X ∩ Y = ∅
RollNo → Course
Armstrong's Axioms & Derived Rules
Reflexivity
If Y ⊆ X → X → Y
(A,B) → A
Augmentation
If X → Y → XZ → YZ
A → B ⇒ AC → BC
Transitivity
X → Y, Y → Z ⇒ X → Z
A→B, B→C ⇒ A→C
Union
X→Y, X→Z ⇒ X→YZ
Decomposition
X→YZ ⇒ X→Y, X→Z
Pseudotransitivity
X→Y, WY→Z ⇒ WX→Z
Attribute Closure X⁺
Algorithm
- Start with X
- Apply FDs repeatedly
- Stop when no new attributes
R(A,B,C,D) ; A→B, B→C, C→D → A⁺ = {A,B,C,D}
Candidate Key: A
Candidate Key Shortcut
- Closure contains all attributes
- No proper subset has same property
Minimal Cover & GATE Facts
Minimal Cover
- RHS has single attribute
- Remove redundant FDs
- Remove redundant attributes
GATE Quick Facts
- CK = Minimal Super Key
- Every PK is a CK
- Every CK is a SK
- FK may contain NULL
- Closure → find CK
- Armstrong's axioms → FD inference
- Minimal Cover → Normalization
Formula Sheet
| Trivial FD | Y ⊆ X |
| Non-Trivial FD | Y ⊄ X |
| Completely Non-Trivial | X ∩ Y = ∅ |
| Candidate Key | Minimal Super Key |
| Attribute Closure | X⁺ |
GATE MCQs (15)
Last‑Minute Revision
- Key → uniquely identifies tuple
- Super Key → may contain extra
- Candidate Key → minimal SK
- Primary Key → selected CK
- Foreign Key → referential integrity
- FD: X → Y
- Armstrong: Reflexivity, Augmentation, Transitivity
- Closure X⁺ → find CK
- Minimal Cover → remove redundant FDs
- Most important: Closure, CK, FD, Axioms, Minimal Cover
GATE CSE · RPSC · Rajasthan IA · JVVNL · NIELIT · ISRO · PSUs