Functional Dependencies Explained

Concept

A functional dependency, written X -> Y, holds on relation R when:

  for ANY two tuples t1 and t2 of R,
      if  t1[X] = t2[X]
      then t1[Y] = t2[Y]

  Read aloud: "X determines Y", or "Y is functionally
  dependent on X".

  X is the DETERMINANT.  Y is the DEPENDENT.

The word functional is used in its mathematical sense: X behaves like the input of a function whose output is Y. Give the same X twice and you must get the same Y twice.

The most important point

A functional dependency is a constraint on every possible instance, not a pattern spotted in the current rows. You cannot prove a dependency by looking at data — you can only disprove one. Dependencies come from the meaning of the data, which means they come from the requirement, not from the table.

  roll_no | name  | dept
  --------+-------+-----
     21   | Meera | CS
     22   | Ravi  | CS
     23   | Anitha| EC

  Looking at THIS instance you might claim  name -> dept.
  Every name here has one department, after all.

  But the RULE is false: two students can share a name and
  sit in different departments. The next insert disproves it.

  Meanwhile  roll_no -> name  IS true, because the college
  guarantees roll numbers are unique. That guarantee comes
  from the requirement, not from the three rows above.

Reading a dependency correctly

Dependencies are directional. X -> Y says nothing at all about Y -> X.

Trivial and non trivial

  { roll_no, name } -> roll_no        TRIVIAL
     of course two tuples agreeing on both agree on one

  { roll_no, name } -> { roll_no, dept }   NON TRIVIAL
     dept is not inside the left hand side

  roll_no -> dept                     COMPLETELY NON TRIVIAL
     no shared attribute at all

Kinds of dependency you must recognise

Full functional dependency

Y depends on the whole of X and not on any proper subset. This is what 2NF requires.

Partial dependency

Y depends on only part of a composite determinant. This is what 2NF forbids.

  ENROLMENT ( roll_no, course_code, marks, student_name )
    key = { roll_no, course_code }

  { roll_no, course_code } -> marks          FULL
     marks needs BOTH - a mark exists for a pair

  roll_no -> student_name                    PARTIAL
     the name depends on the student ALONE, so it depends
     on only part of the key. The name is therefore
     repeated on every enrolment row of that student.
     That repetition is the anomaly 2NF removes.

Transitive dependency

X -> Y and Y -> Z, where Y is not a key, giving X -> Z indirectly. This is what 3NF forbids.

  STUDENT ( roll_no, name, dept_code, dept_head )
    key = roll_no

    roll_no   -> dept_code       direct
    dept_code -> dept_head       dept_code is NOT a key
    -----------------------------
    roll_no   -> dept_head       TRANSITIVE

  Consequence: the head of Computing is repeated on every
  Computing student row. Change the head and every one of
  those rows must change together, or the table contradicts
  itself. That is the anomaly 3NF removes.

Where dependencies come from

1. Read the requirement. "Each department has one head" is dept_code -> dept_head.
2. Ask about uniqueness. "Is a roll number ever reused?" No, so roll_no determines everything about the student.
3. Ask in both directions. A department has one head; does a person head only one department? Different question, different dependency.
4. Look for counterexamples. If you can imagine two legal tuples that agree on X and disagree on Y, the dependency is false.

Worked identification

  RESULT ( roll_no, course_code, semester, marks,
           student_name, course_title, credits )

  Stated rules:
    a roll number identifies one student
    a course code identifies one course
    a student may repeat a course in a later semester
    marks are recorded per attempt

  Dependencies:
    roll_no     -> student_name              from rule 1
    course_code -> course_title, credits     from rule 2
    { roll_no, course_code, semester } -> marks   from rules 3, 4

  Key: { roll_no, course_code, semester }
    because semester is needed to distinguish attempts

  Classification against that key:
    roll_no -> student_name       PARTIAL   (part of the key)
    course_code -> course_title   PARTIAL   (part of the key)
    key -> marks                  FULL

  Two partial dependencies means this relation is in 1NF but
  NOT 2NF. Phase 8 does the decomposition; this note only
  needs you to see them.

Common mistakes

• Inferring a dependency from sample data. Data can disprove, never prove.
• Reading the arrow backwards. X -> Y says nothing about Y -> X.
• Calling a dependency partial without a composite key. Partial dependency requires a composite determinant — with a single attribute key, no dependency can be partial.
• Missing that the middle attribute of a transitive dependency must not be a key. If it is a key, the dependency is not a 3NF violation.
• Ignoring trivial dependencies in proofs. They are always true and are used by the axioms.

Exam and interview questions

1. Define a functional dependency formally, using two tuples.
2. Why can a dependency not be proved from an instance?
3. Differentiate trivial, non trivial and completely non trivial dependencies.
4. Define full, partial and transitive dependencies with an example of each.
5. Which normal form removes each of partial and transitive dependencies?

Practice

1. For BOOK ( isbn, title, author_id, author_name, publisher, pub_city ) write every dependency you can justify from meaning.
2. Classify each as trivial, partial or transitive against the key.
3. Give a counterexample disproving author_name -> author_id.
4. State which requirement sentence would make publisher -> pub_city true.

Conclusion

A functional dependency is a rule over every legal instance, drawn from the meaning of the data. Learn to spot full, partial and transitive forms, because the next three phases — closure, keys and normalisation — are entirely built on them.