DBMS | L-8 | Finding Keys Using Functional Dependencies | Vishvadeep Gothi

Main ideas / lessons (DBMS: Functional Dependencies → Keys)

1. Recap of functional dependency concepts (from prior lecture)

   • Functional dependencies (FDs) explain which attributes can be derived from others.
   • Previously covered:
     • Properties of functional dependencies
     • Canonical cover (minimal/cleaned form of an FD set)
     • Which attributes can be derived from given attributes
     • How FD sets imply other FDs
     • Left/right reduction ideas (mentioned in the context of canonical cover wording)

2. Core problem addressed today: extracting keys from FDs

   • In a relational schema, a key is an attribute set that can uniquely identify a tuple/row.
   • Main guiding idea:
     • If a set of attributes determines all other attributes (via FDs), then that set is a key candidate.
   • Think in reverse: given the FDs, infer which attribute sets are necessary to derive everything.

3. Two-direction intuition: key ↔ functional dependencies

   • Direct direction (typical):
     • If K is a key, then K functionally determines all attributes.
   • Reverse direction (used for key extraction):
     • If the FDs allow you to derive all attributes from X, then X is (at least) a candidate key.
   • Practical method emphasized: use closures (written as X+) to test what a set determines.

4. Speaker distinguishes key types

   • Super key
     • Any attribute set whose closure includes all attributes.
   • Candidate key (primary focus)
     • A minimal super key.
     • Minimality matters: remove extraneous attributes.
   • Primary key
     • Chosen from candidate keys (not deeply computed here, but referenced).
   • Why candidate keys matter:
     • Candidate keys can generate super keys by adding attributes.

5. Methodology for finding keys (structured as instruction-like steps)

   • Step A: Compute closures
     • For a proposed set X, compute X+ (attributes derivable from X using the FDs).
   • Step B: Determine super keys
     • If X+ contains all attributes of the relation, then X is a super key.
   • Step C: Enforce minimality to get candidate keys
     • If X is a super key, check whether any proper subset Y ⊂ X is also a super key:
       • If yes, X is not minimal → not a candidate key.
       • If no, X is a candidate key.
   • Step D: Avoid incorrect combinations
     • Common mistake: combining attributes incorrectly can break minimality.
     • In that case the set becomes a super key, not a candidate key.
   • Step E: Use “attributes not appearing on RHS” as a strong clue
     • If an attribute never appears on the RHS of any FD, then it cannot be derived from other attributes.
     • Therefore it must be included in any candidate key.
     • If multiple such attributes exist:
       • include them all in the candidate-key attempt,
       • then verify using closure.
   • Step F: “Find which attributes are required to derive others”
     • Candidate-key computation must respect dependency structure.
     • If deriving an attribute requires multiple conditions (e.g., both C and D), include what’s necessary for that derivation path.
   • Step G: “Reverse closure / remove extra FDs” concept later
     • Near the end, the instructor transitions from forward reasoning to reverse reasoning:
       • earlier: remove extra FDs using implication via closure,
       • now: reverse the process to remove redundant dependencies (toward minimum cover / minimum equivalent set).

6. Examples used to illustrate extraction of keys

   • Multiple FD-set examples using attribute letters (A, B, C, D, E, F, G, …).
   • Observed patterns:
     • Some single attributes determine many others → likely a key.
     • Some closures cover only part of the schema → not a key.
     • Candidate keys may be multiple; they are tested via:
       • single-attribute closures like A+, C+, D+
       • combinations like A+B, C+D, etc.
       • minimality checks

7. Final conceptual takeaway before next topic

   • Candidate key extraction requires:
     1. Coverage: closure gives all attributes
     2. Minimality: no attribute can be removed while preserving coverage
   • Next topic introduced:
     • Working backward on FD redundancy / minimum cover
     • “Remove all extra FDs” / find a minimum equivalent set by removing transitive or redundant dependencies.

---

Method / instruction list

A) Extract candidate keys from a given FD set

1. Identify the attribute universe

   • Let the relation schema be over attributes {A, B, C, …}.

2. Use closure to test determination

   • For any attribute set X, compute X+ using the FDs repeatedly until no more attributes can be added.

3. Candidate-key requirement #1: closure must be full

   • If X+ = all attributes, then X is at least a super key.

4. Candidate-key requirement #2: minimality

   • For each proper subset Y ⊂ X, compute Y+.
   • If any Y has Y+ = all attributes, then X is not a candidate key.
   • If no proper subset works, X is a candidate key.

5. Strong heuristic to reduce search

   • If an attribute never appears on the RHS of any FD:
     • it must be included in every candidate key (it can’t be derived).
   • If multiple such attributes exist:
     • include them together and test closure/minimality.

6. Avoid a common mistake

   • Don’t assume super key ⇒ candidate key.
   • Candidate keys must be minimal.

7. Handle “forced combinations”

   • If derivation requires multiple attributes together (based on FD patterns), candidate keys must include what’s necessary for that derivation path.

8. Use different starting points intelligently

   • Start from:
     • single attributes whose closures look promising,
     • required RHS-missing attributes,
     • combinations suggested by FD structure,
   • then use minimality checks to confirm candidate keys.

---

B) Next-step topic introduced: remove extra/redundant FDs (reverse reasoning toward a minimum set)

• Given a relation R with attributes A…G and a set of FDs:
  • Goal: remove “extra” FDs so the remaining set is minimal but equivalent.
• Instruction concept shown
  • Earlier approach: if an FD is implied by others, it is redundant (via closure).
  • Now: apply systematic redundancy removal:
    • test whether an FD is derivable from the remaining set,
    • remove it if it is not needed.
• Transitive dependency considerations
  • The instructor references removing FDs involved in transitive implications when they are redundant.

---

Speakers / sources featured

• Vishvadeep Gothi (main speaker/instructor; “Vishvadeep” appears as a recurring name)
• Academy Computer Science channel (referenced by the speaker)
• Jana Reddy platform / subscription offerings (promoted service; not an academic source)
• Reddy / Apna/Redmi platform mentions (promotional content within the lecture video)
• GATE exam (referenced as an external target; not quoted formally as a source)