Functional Dependencies

Syllabus tag: Paper-II, Section-B, Topic IV.6 (part 1) — Functional Dependencies. Normal forms themselves are on Functional Dependencies and Normalization; this page is the deep dive on FD theory and numericals.

Definition

A functional dependency (FD) X → Y on a relation R means: whenever two tuples agree on the values of X, they must also agree on the values of Y. X is the determinant (left-hand side, LHS); Y is the dependent (right-hand side, RHS). Read it as "X functionally determines Y" or "Y is functionally dependent on X".

• Formally: for all tuples t1, t2 in R, if t1[X] = t2[X] then t1[Y] = t2[Y].
• FDs come from the meaning of the data (business rules), not from whatever rows happen to be in the table today.
• FDs are the tool used to define keys and to decide normal forms.

Everyday Examples

• Does NOT hold: City → PostalCode (Lahore has many postal codes); Name → CNIC (two people can share a name); CourseCode → Grade (different students get different grades).

Numerical 1 — Which FDs Hold in This Table Instance?

Method: group rows by the LHS value; the FD fails if any group shows two different RHS values.

⚠️

Key exam point: a table instance can disprove an FD (one counter-example is enough) but can never prove it — the next inserted row might break it. FDs are declared from business rules.

Types of Functional Dependency

• Prime attribute: belongs to at least one candidate key. Non-prime: belongs to none. Normal-form rules are stated in these terms.

Armstrong's Axioms (sound and complete)

1. Reflexivity: if Y ⊆ X, then X → Y (produces trivial FDs).
2. Augmentation: if X → Y, then XZ → YZ.
3. Transitivity: if X → Y and Y → Z, then X → Z.

• Sound: they never derive an FD that does not actually hold. Complete: repeated use derives every FD that holds (all of F⁺).

Derived Rules with Proofs (proofs are asked!)

• Union: X → Y and X → Z ⟹ X → YZ.

  Proof: augment X → Y with X to get X → XY; augment X → Z with Y to get XY → YZ; transitivity gives X → YZ.

• Decomposition: X → YZ ⟹ X → Y and X → Z.

  Proof: YZ → Y by reflexivity; transitivity with X → YZ gives X → Y (same for Z).

• Pseudotransitivity: X → Y and WY → Z ⟹ WX → Z.

  Proof: augment X → Y with W to get WX → WY; transitivity with WY → Z gives WX → Z.

• Composition: X → Y and A → B ⟹ XA → YB.

Closure of an Attribute Set (X⁺) — the Most Important Algorithm

X⁺ = the set of all attributes functionally determined by X.

result := X
repeat
    for each FD  A → B  in F:
        if A ⊆ result then result := result ∪ B
until result does not change
return result

Uses of X⁺: (1) test whether X → Y holds (is Y ⊆ X⁺?); (2) test whether X is a super key (is X⁺ = all attributes?); (3) find candidate keys; (4) compute minimal covers and test equivalence.

Numerical 2 — Attribute Closure (Silberschatz example)

R(A, B, C, G, H, I), F = { A → B, A → C, CG → H, CG → I, B → H }. Compute (AG)⁺.

• (AG)⁺ = R → AG is a super key. Check minimality: A⁺ = {A, B, C, H} and G⁺ = {G}, neither is all of R → AG is a candidate key.
• Same result with axioms (derive AG → I): A → C (given) → augment with G: AG → CG → transitivity with CG → I: AG → I.

Numerical 3 — Finding All Candidate Keys

Procedure: (1) attributes that never appear on any RHS must be in every key; (2) attributes that appear only on the RHS are never in a key; (3) start with the must-have set, compute its closure, and add other attributes one at a time until the closure is R; (4) keep only minimal sets.

Example A: R(A, B, C, D), F = { A → B, B → C, C → A }

• D is on no RHS → D is in every key. D⁺ = {D} → not enough.
• (AD)⁺ = {A, D, B, C} ✅ · (BD)⁺ = {B, D, C, A} ✅ · (CD)⁺ = {C, D, A, B} ✅
• Candidate keys: AD, BD, CD. Prime attributes: all four.

Example B: R(A, B, C, D, E), F = { A → B, BC → E, ED → A }

• RHS attributes = {B, E, A} → C and D never appear on the RHS → CD is in every key. (CD)⁺ = {C, D} → not enough.
• (ACD)⁺: A → B → {A, B, C, D}; BC → E → all ✅
• (BCD)⁺: BC → E → {B, C, D, E}; ED → A → all ✅
• (CDE)⁺: ED → A → {A, C, D, E}; A → B → all ✅
• Candidate keys: ACD, BCD, CDE (each is minimal because CD alone fails).
• Normal form check: every attribute is prime → 3NF; but A → B has a non-key determinant → not BCNF.

Closure of an FD Set (F⁺)

• F⁺ = every FD that can be inferred from F using Armstrong's axioms (including trivial ones). It can be exponentially large, which is why in practice we compute attribute closures instead of F⁺.
• To test whether X → Y ∈ F⁺: compute X⁺ under F and check Y ⊆ X⁺.
• Example: F = { A → B, B → C }. Is A → C in F⁺? A⁺ = {A, B, C} ✅ Yes. Is C → A? C⁺ = {C} ❌ No.

Numerical 4 — Equivalence of Two FD Sets (Elmasri example)

F = { A → C, AC → D, E → AD, E → H } and G = { A → CD, E → AH }. Are they equivalent?

Rule: F ≡ G if every FD of G follows from F and every FD of F follows from G.

• F covers G? Under F: A⁺ = {A, C, D} ⊇ CD ✅; E⁺ = {E, A, D, H, C} ⊇ AH ✅
• G covers F? Under G: A⁺ = {A, C, D} ⊇ C ✅; (AC)⁺ = {A, C, D} ⊇ D ✅; E⁺ = {E, A, H, C, D} ⊇ AD ✅ and ⊇ H ✅
• F and G are equivalent.

Numerical 5 — Minimal (Canonical) Cover (Elmasri example)

F = { B → A, D → A, AB → D }

A minimal cover must satisfy: single attribute on every RHS; no extraneous attribute on any LHS; no redundant FD.

1. Single RHS: already true.
2. Extraneous LHS in AB → D: compute B⁺ under F: B → A gives {A, B}; AB → D gives {A, B, D}. B⁺ contains D, so A is extraneous → replace AB → D with B → D. Now F = { B → A, D → A, B → D }.
3. Redundant FDs: B → A follows from B → D and D → A → remove it.

• Minimal cover = { B → D, D → A }
• Note: a set can have more than one minimal cover; the result depends on the order in which you check FDs — always show your steps.

How FDs Drive Normalization

Worked Mini-Example

EmployeeProject(EmpID, ProjID, EmpName, ProjName, Hours, DeptID, DeptHead) with FDs: (1) EmpID → EmpName, DeptID; (2) ProjID → ProjName; (3) (EmpID, ProjID) → Hours; (4) DeptID → DeptHead. Key = (EmpID, ProjID).

• Partial: EmpID → EmpName, DeptID and ProjID → ProjName → violates 2NF.
• Transitive: EmpID → DeptID → DeptHead → violates 3NF.
• Final 3NF/BCNF schema: Employee(EmpID, EmpName, DeptID) · Department(DeptID, DeptHead) · Project(ProjID, ProjName) · WorksOn(EmpID, ProjID, Hours).

MCQ Trap

• The FD is a constraint on all legal instances, not a pattern in current data — a table can disprove an FD but not prove it.
• X → Y does not imply Y → X (RollNo → Name, but not Name → RollNo).
• XY → Z does not imply X → Z or Y → Z (that would be decomposition of the LHS, which is not a valid rule).
• Decomposition works only on the RHS: X → YZ ⟹ X → Y is valid.
• If X is a super key, then X → every attribute; a candidate key is a minimal such X.
• Armstrong's axioms are 3 (Reflexivity, Augmentation, Transitivity); Union, Decomposition and Pseudotransitivity are derived rules.

CSS Exam Angle

• FPSC 2016 and 2023 asked directly about full, partial and transitive dependency; 2025 had BCNF/normalization MCQs — all are FD questions at heart.
• Expect: define FD with an example; distinguish FD types; compute a closure and find keys; apply axioms to derive an FD; identify the normal form of a relation from its FDs.
• Always show the closure table step by step — marks are for the working.

Likely Questions

1. Define functional dependency with examples. Why are FDs important in database design?
2. Differentiate trivial, non-trivial, full, partial and transitive dependencies with examples.
3. State Armstrong's axioms and prove the union and pseudotransitivity rules.
4. Given R and F, compute the closure of an attribute set and find all candidate keys.
5. Given a table instance, determine which of the stated FDs are violated.
6. Find the minimal cover of a given set of FDs.

---

✍️ Model Answers — Likely Questions

Q1. Define FD with examples. Why are FDs important?

Definition: X → Y holds in R if any two tuples that agree on X also agree on Y; X is the determinant.

Examples: CNIC → Name; (RollNo, CourseCode) → Grade; PostalCode → City.

Importance:

1. Keys: a candidate key is a minimal X with X⁺ = all attributes.
2. Normalization: partial and transitive FDs identify 2NF/3NF violations; non-key determinants identify BCNF violations.
3. Anomaly prevention: redundancy exists exactly where a non-key determines other attributes.
4. Decomposition quality: FDs are used to test lossless join and dependency preservation.
5. Integrity: FDs are business rules the DBMS enforces through keys and UNIQUE constraints.

Conclusion: FDs are the formal bridge between real-world rules and a good relational schema.

Q2. Differentiate trivial, non-trivial, full, partial and transitive dependencies.

Use the Types of Functional Dependency table above, one line and one example each, then show them together on one relation:

Result(RollNo, CourseCode, StudentName, Grade, Dept, DeptHead), key (RollNo, CourseCode):

• Trivial: (RollNo, CourseCode) → RollNo
• Full: (RollNo, CourseCode) → Grade
• Partial: RollNo → StudentName (part of key) → 2NF problem
• Transitive: RollNo → Dept → DeptHead → 3NF problem

Conclude: removing partial dependencies gives 2NF; removing transitive ones gives 3NF.

Q3. State Armstrong's axioms and prove union and pseudotransitivity.

Axioms: Reflexivity (Y ⊆ X ⟹ X → Y), Augmentation (X → Y ⟹ XZ → YZ), Transitivity (X → Y, Y → Z ⟹ X → Z). They are sound and complete.

Union proof: X → Y, augment by X ⟹ X → XY. X → Z, augment by Y ⟹ XY → YZ. Transitivity ⟹ X → YZ. ∎

Pseudotransitivity proof: X → Y, augment by W ⟹ WX → WY. With WY → Z, transitivity ⟹ WX → Z. ∎

Finish with the AG → I derivation from Numerical 2 as an applied example.

Q4. Compute a closure and find all candidate keys.

Write the closure algorithm, then solve Example B of Numerical 3 in full: identify C and D as never on an RHS, show (CD)⁺ fails, compute (ACD)⁺, (BCD)⁺, (CDE)⁺ step by step, confirm minimality, and state keys ACD, BCD, CDE. Add the prime/non-prime classification and the normal-form conclusion (3NF but not BCNF) for bonus marks.

Q5. Given a table instance, determine which FDs are violated.

Method: for each FD, group tuples by LHS values; if any group has two different RHS values, the FD is violated; otherwise it is not contradicted. Present the check table from Numerical 1 (A → B and C → A violated; A → C, B → D, D → B, AB → D not contradicted), and state the key caveat: the instance can only disprove FDs, never prove them.

Q6. Find the minimal cover of a set of FDs.

State the three conditions, then solve Numerical 5 step by step: single RHS → remove extraneous A from AB → D using B⁺ = {A, B, D} → remove redundant B → A → { B → D, D → A }. Mention that minimal covers are the first step of 3NF synthesis and are not always unique.

---

⚡ 60-Second Revision

• X → Y: same X ⟹ same Y. Determined by business rules, not data.
• Types: trivial, non-trivial, full, partial (→ 2NF), transitive (→ 3NF), multivalued (→ 4NF).
• Axioms: Reflexivity, Augmentation, Transitivity (sound + complete). Derived: Union, Decomposition, Pseudotransitivity.
• X⁺ algorithm answers: does X → Y hold? is X a key?
• Attribute on no RHS ⟹ in every key.
• Minimal cover: single RHS → no extraneous LHS → no redundant FD.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2016 · Paper-II · Q6(b) · 6 marks

Q. Distinguish among functional dependency, fully functional dependency and transitive dependency.

Ans.

• Functional dependency (X → Y): the value of X uniquely determines the value of Y. Example: RegNo → Name.
• Fully functional dependency: Y depends on the whole of a composite key X and on no proper subset of it. Example: with key (StudentID, CourseID), Grade depends on both, so (StudentID, CourseID) → Grade is full. If StudentID alone determined Name, that would be a partial dependency, which violates 2NF.
• Transitive dependency: X → Y and Y → Z (with Y not a key) mean X → Z indirectly. Example: EmpID → DeptID and DeptID → DeptName, so EmpID → DeptName is transitive. It violates 3NF.

2023 · Paper-II · Q6(c) · 4 marks

Q. Explain transitive dependency using an example.

Ans.

• In Employee(EmpID, Name, DeptID, DeptName), EmpID → DeptID and DeptID → DeptName. DeptName depends on EmpID only through DeptID, so it is a transitive dependency.
• Problems: department names are repeated for every employee (redundancy), and updating or deleting causes anomalies.
• Fix (3NF): split into Employee(EmpID, Name, DeptID) and Department(DeptID, DeptName).