Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 79 ยท Database Design Theory

Functional Dependencies

Learn functional dependencies: trivial and non-trivial FDs, Armstrong's axioms, derived rules, and how to test an FD on real data in Python and SQL.

Redundancy and Update Anomalies showed that some tables repeat facts and then go wrong when one copy changes. This lesson gives you the vocabulary to say exactly what is wrong. The tool is the functional dependency, or FD: a precise statement that one set of columns determines another. Every normal form in the rest of this chapter is defined in terms of FDs, so this is the foundation of design theory.

An FD is a rule about the meaning of the data, not about one particular snapshot. "A student ID determines the student's name" is true because of how the real world works, and the schema must respect it no matter which rows happen to exist today.

Definition

Let R be a relation schema and let X and Y be sets of attributes of R. The functional dependency

TEXT
X -> Y

(read "X determines Y") holds in R when, in every legal instance of R, any two tuples that agree on all attributes of X also agree on all attributes of Y. Put differently: for each value of X there is at most one value of Y.

Reading X -> Y

Determinant X, the left side. Give me X.
Dependent Y, the right side. I can tell you Y.
Never two answers One X value never maps to two Y values.

A key is just a determinant of every attribute.

1 / 2

Consider a table that records which student took which course, who taught it, and the grade.

student_id name course instructor grade
1 Ana DB Lee A
1 Ana OS Kim B
2 Bo DB Lee B
3 Cy OS Kim A
3 Cy DB Lee C

From the meaning of the data we can state three FDs:

  • student_id -> name: a student has one name.
  • course -> instructor: in this school each course has exactly one instructor.
  • student_id, course -> grade: a student gets one grade per course.

Notice what is not an FD: student_id -> grade fails (student 1 has an A and a B), and grade -> student_id fails too. We usually write attribute sets without braces or commas when each attribute is one letter (AB -> C), and we use commas when names are longer.

Trivial and non-trivial dependencies

An FD X -> Y is trivial when Y is a subset of X. It is true in every relation, because if two tuples agree on X they certainly agree on the part of X you are asking about. Examples: student_id, course -> course, and name -> name.

An FD is non-trivial when at least one attribute of Y is not in X, and completely non-trivial when X and Y share no attribute at all. Design theory cares about the non-trivial ones, because only they say something about the data. When a textbook lists "the FDs of a relation" it means the non-trivial ones.

Testing an FD against data

You cannot prove an FD from data. Five rows in which names happen to be unique do not mean name -> student_id is a rule of the business. But data can refute an FD: one pair of rows that agree on X and disagree on Y is a counterexample. Checking this is a handy sanity test for an existing table, and a good way to discover candidate FDs to ask the business about.

The test is a single pass: remember the Y value you saw for each X value, and complain when a different one shows up.

Python A Python FD checker

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line is the lesson inside the lesson: name -> student_id holds on these five rows, yet no sensible designer would declare it, because two different students can share a name. The checker answers "is this FD consistent with the current data?", never "is it a rule?".

SQL can run the same test. Group by the determinant and look for groups that contain more than one distinct dependent value; an empty result means the FD holds.

SQL Testing FDs with GROUP BY and HAVING

Press Run (or Ctrl + Enter) to see the result here.

The first query returns nothing (the FD holds); the second lists students 1 and 3, who each have two different grades. For a multi-column dependent, use COUNT(DISTINCT col1 || '|' || col2) or compare against a subquery. Also remember that COUNT(DISTINCT ...) ignores NULL, a trap discussed in Nulls and Three-Valued Logic.

Armstrong's axioms

Given a set F of FDs that we know hold, other FDs must hold too. For example, if A -> B and B -> C, then A -> C is forced. The set of all FDs implied by F is written F+, the closure of F. William Armstrong showed that three simple rules generate all of F+, and nothing outside it:

  1. Reflexivity. If Y is a subset of X, then X -> Y. (The trivial FDs.)
  2. Augmentation. If X -> Y, then XZ -> YZ for any set Z.
  3. Transitivity. If X -> Y and Y -> Z, then X -> Z.

The axioms are sound (they never derive a false FD) and complete (every implied FD can be derived). Soundness is easy to believe; completeness is the deep result.

Three more rules save time. They are derived: each follows from the three axioms.

  • Union. If X -> Y and X -> Z, then X -> YZ.
  • Decomposition. If X -> YZ, then X -> Y and X -> Z.
  • Pseudotransitivity. If X -> Y and WY -> Z, then WX -> Z.

Union and decomposition together let you treat X -> ABC as three separate FDs X -> A, X -> B, X -> C. That is why later algorithms start by splitting every right side into single attributes. A warning: decomposition works on the right side only. AB -> C does not give you A -> C.

Here is a short derivation of pseudotransitivity from the axioms. Suppose A -> B and BC -> D. Augment the first with C to get AC -> BC. Now AC -> BC and BC -> D give AC -> D by transitivity. Each step used one axiom, and the conclusion is exactly pseudotransitivity.

Checking whether an FD is implied

Deriving FDs by hand is slow. The practical test, covered fully in Attribute Closure, Keys and Minimal Cover, asks: starting from X, keep adding the right sides of any FD whose left side is already collected. If Y ends up inside the collected set, then X -> Y is implied. The next example uses a deliberately small version of that idea to confirm the three derived rules.

Python Confirming derived rules with a tiny closure function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

AC -> D is implied (that is pseudotransitivity at work), but B -> D and C -> D are not: D needs both B and C. The closure of AC is ABCDE, which means AC determines every attribute of this five-column schema, a first hint that AC could be a key.

Why FDs matter for design

A superkey is any set of attributes that determines all attributes of the relation, and a candidate key is a minimal superkey (Keys and Integrity Constraints). So keys are a special case of FDs. The anomalies from the previous lesson appear when a table contains an FD whose left side is not a key: course -> instructor in the table above is such an FD, and that is exactly why the instructor's name is repeated on every row for that course. Normalization, starting in 1NF, 2NF and 3NF, is the discipline of removing those dependencies.

An FD with a non-key left side is not always a bug. It becomes a problem when the schema stores that fact on many rows. If you store course -> instructor once in a courses table, the same FD is perfectly healthy.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement is true for the functional dependency X -> Y?

    An FD only says that agreeing on X forces agreement on Y. It is not symmetric, and X is not necessarily a key.
  2. 2. Which of these is a trivial dependency?

    An FD is trivial when the right side is a subset of the left side. Here course is already part of the left side.
  3. 3. A table has 10,000 rows and the query SELECT a FROM t GROUP BY a HAVING COUNT(DISTINCT b) > 1 returns no rows. What can you conclude?

    Data can refute an FD with one counterexample but never prove it. An empty result only means the current rows are consistent with A -> B.
  4. 4. Given AB -> C, which dependency can you conclude with the Armstrong axioms?

    Reflexivity gives AB -> AB, and union with AB -> C gives AB -> ABC. Decomposition only splits the right side, so A -> C does not follow.

Summary

  • A functional dependency X -> Y says that each value of X is paired with at most one value of Y; it is a statement about meaning, not about one snapshot.
  • Trivial FDs (Y inside X) always hold; design theory studies the non-trivial ones.
  • Data can refute an FD (one counterexample) but never prove it; test with a single pass in Python or GROUP BY ... HAVING COUNT(DISTINCT ...) > 1 in SQL.
  • Armstrong's axioms (reflexivity, augmentation, transitivity) are sound and complete for deriving F+; union, decomposition and pseudotransitivity are handy derived rules.
  • Decomposition applies to right sides only: AB -> C does not give A -> C.
  • Keys are FDs whose left side determines every attribute; anomalies come from FDs whose left side is not a key.

Next: Attribute Closure, Keys and Minimal Cover.