Chapter 18 of 41

Functional Dependencies

So far we have learned how to model data (ER model), turn it into tables (relational model), protect it (keys and integrity constraints) and query it (relational algebra and calculus). But one big question is still open: how do we know whether a table is designed well?

Look at this table of exam results:

exam_result
+---------+-------+-----------+-------------+-------+
| roll_no | name  | course_id | course_name | marks |
+---------+-------+-----------+-------------+-------+
|     101 | Rahul | CS201     | DBMS        |    78 |
|     101 | Rahul | CS202     | OS          |    85 |
|     102 | Sana  | CS201     | DBMS        |    91 |
|     103 | Rahul | CS202     | OS          |    85 |
|     103 | Rahul | CS203     | CN          |    64 |
|     104 | Tara  | CS203     | CN          |    78 |
+---------+-------+-----------+-------------+-------+

Something feels wrong. Roll number 101's name is stored twice. The course name "DBMS" is stored next to CS201 every time anyone takes that course. If CS201 is renamed, we must update many rows, and if we miss one, the data contradicts itself.

Why does this happen? Because some columns are completely decided by other columns. Once you know the roll number, the student's name is fixed. Once you know the course id, the course name is fixed. These "is decided by" rules are called functional dependencies, and they are the foundation of normalization, which starts in the Normalization & Anomalies chapter.


What Is a Functional Dependency?

A functional dependency X → Y holds on a relation schema R if, in every legal instance of R, any two tuples that agree on all attributes of X also agree on all attributes of Y.

Here X and Y are sets of attributes of R. We read X → Y as "X functionally determines Y" or "Y is functionally dependent on X".

  • X is called the determinant (left-hand side, LHS).

  • Y is called the dependent (right-hand side, RHS).

In symbols:

X → Y holds  ⇔  for all tuples t1, t2 :  t1[X] = t2[X]  ⇒  t1[Y] = t2[Y]

The name comes from mathematics. A function gives exactly one output for each input. If X → Y, then there is a function from X-values to Y-values: one X value can never be paired with two different Y values.

FDs in the Exam Table

From the meaning of the data (not just from the six rows), these FDs hold:

roll_no             → name          a roll number belongs to one student
course_id           → course_name   a course id names one course
roll_no, course_id  → marks         a student gets one mark per course

And these do not hold:

name     → roll_no     two different students are called Rahul (101 and 103)
roll_no  → marks       101 has 78 in one course and 85 in another
marks    → course_id   78 appears for CS201 and for CS203

The third FD in the first list shows that the LHS can contain more than one attribute. Neither roll_no alone nor course_id alone decides the marks, but the pair does.


How to Check an FD Against Data

To test whether X → Y is violated in a table, group the rows by X and look for any group that has more than one distinct Y value. In SQL:

-- Is name → roll_no violated?
SELECT name, COUNT(DISTINCT roll_no) AS roll_nos
FROM exam_result
GROUP BY name
HAVING COUNT(DISTINCT roll_no) > 1;
+-------+----------+
| name  | roll_nos |
+-------+----------+
| Rahul |        2 |
+-------+----------+

One violating group is enough: name → roll_no does not hold. Running the same pattern for marks → course_id returns 78 with 2 courses, so that FD fails too. For roll_no → name the query returns no rows, which means this instance does not violate it.

The Important Catch: Data Can Only Disprove an FD

Now try name, course_id → marks. The query returns no rows here, because both Rahuls happen to have 85 in CS202. Does that mean "name and course id determine marks"? No. Tomorrow a third Rahul could score 40 in CS202. The FD held in this snapshot by coincidence.

A functional dependency is a statement about the meaning of the data, so it belongs to the schema, not to one instance. Looking at an instance can prove that an FD does NOT hold, but it can never prove that an FD DOES hold.

In practice, FDs come from business rules: "each employee works in exactly one department", "each PIN code belongs to one city", "each order has one customer". The database designer collects them while modelling, just like keys.

Practice: Which FDs Hold in This Instance?

+---+---+---+
| A | B | C |
+---+---+---+
| 1 | p | x |
| 1 | p | y |
| 2 | q | x |
| 3 | q | y |
+---+---+---+
Show answer

Checking every FD with a single attribute on the right (verified with a small script):

  • A → B is satisfied (1 always goes with p).

  • A → C fails (1 goes with x and y). B → A fails (q goes with 2 and 3). B → C, C → A and C → B also fail.

  • AB → C fails: rows 1 and 2 agree on (1, p) but differ on C.

  • AC → B is satisfied (it follows from A → B anyway), and BC → A is satisfied: every (B, C) pair appears once.

Remember: "satisfied by this instance" is all we can say. Only the real-world rules can tell us whether these FDs hold on the schema.


FDs and Keys

You already know keys from the Keys in DBMS chapter. FDs give a precise definition of them:

  • K is a superkey of R if and only if K → R (K determines every attribute).

  • K is a candidate key if K → R and no proper subset of K also determines R.

In exam_result, {roll_no, course_id} is a candidate key: from roll_no we get name, from course_id we get course_name, and from both we get marks. So keys are just a special case of FDs. The next chapter shows how to find all candidate keys systematically from a set of FDs.


Types of Functional Dependencies

1. Trivial FD

X → Y is trivial if Y ⊆ X. It holds in every relation, because if two tuples agree on X they obviously agree on any part of X.

roll_no, name → name          trivial
roll_no → roll_no             trivial

2. Non-Trivial FD

X → Y is non-trivial if Y is not a subset of X, i.e. at least one attribute of Y is outside X.

roll_no → name                non-trivial
roll_no → roll_no, name       non-trivial (name is new information)

3. Completely Non-Trivial FD

X → Y is completely non-trivial if X ∩ Y = ∅: no attribute is shared. roll_no → name is completely non-trivial; roll_no → roll_no, name is non-trivial but not completely non-trivial.

4. Full and Partial FD

X → Y is a full functional dependency if removing any attribute from X breaks it; otherwise it is partial.

roll_no, course_id → marks        full: neither attribute alone determines marks
roll_no, course_id → name         partial: roll_no alone already determines name

Partial dependencies on a key are exactly what Second Normal Form removes (see the 1NF, 2NF & 3NF chapter).

5. Transitive FD

If X → Y and Y → Z (and Y does not determine X), then Z depends on X through Y, and X → Z is called transitive.

emp_id → dept_id,  dept_id → dept_location   ⇒   emp_id → dept_location (transitive)

Transitive dependencies of non-key attributes on a key are what Third Normal Form removes.

6. Multivalued Dependency (preview)

A multivalued dependency X →→ Y says that X determines a set of Y values, independently of the other attributes. It is a different kind of constraint, used for Fourth Normal Form in the 4NF & 5NF chapter. Every FD is also an MVD, but not the other way round.

Type

Condition

Example

Trivial

Y ⊆ X

AB → A

Non-trivial

Y ⊄ X

AB → BC

Completely non-trivial

X ∩ Y = ∅

AB → C

Partial

A proper subset of X also determines Y

AB → C when A → C

Full

No proper subset of X determines Y

AB → C, but neither A → C nor B → C

Transitive

X → Y → Z

A → B, B → C gives A → C

A quick counting fact that sometimes appears in exams: on a relation with n attributes, the number of trivial FDs X → Y with X and Y both non-empty is 3n − 2n. For n = 3 that is 27 − 8 = 19 (each attribute is either outside X, in X but not in Y, or in both; subtract the cases with Y empty).


Inferring New FDs: Armstrong's Axioms

A designer usually lists a few FDs, but many more follow from them logically. If roll_no → name holds, then roll_no, course_id → name must also hold. We need rules to derive such FDs safely.

In 1974 W. W. Armstrong gave three rules, now called Armstrong's axioms. Let X, Y, Z be sets of attributes (XY means X ∪ Y):

Rule

Statement

Intuition

Reflexivity

If Y ⊆ X, then X → Y

Trivial FDs always hold

Augmentation

If X → Y, then XZ → YZ

Adding the same attributes to both sides keeps it true

Transitivity

If X → Y and Y → Z, then X → Z

Dependencies chain

These axioms are:

  • Sound: they never produce an FD that does not actually follow. You cannot derive anything false.

  • Complete: every FD that logically follows from a set F can be derived using only these three rules.

Derived Rules

Using the axioms we can prove some handy extra rules. You will use these constantly.

Union: if X → Y and X → Z, then X → YZ.

1. X → Y           given
2. X → XY          augment (1) with X        (XX = X)
3. X → Z           given
4. XY → YZ         augment (3) with Y
5. X → YZ          transitivity on (2) and (4)

Decomposition: if X → YZ, then X → Y and X → Z.

1. X → YZ          given
2. YZ → Y          reflexivity
3. X → Y           transitivity on (1) and (2)     (same for Z)

Pseudotransitivity: if X → Y and WY → Z, then WX → Z.

1. X → Y           given
2. WX → WY         augment (1) with W
3. WY → Z          given
4. WX → Z          transitivity on (2) and (3)

Composition: if X → Y and Z → W, then XZ → YW. (Augment the first with Z, the second with Y, then chain them.)

Decomposition works on the RHS only. From AB → C you can NOT conclude A → C or B → C. In exam_result, (roll_no, course_id) → marks holds, but roll_no → marks does not.

Worked Derivation

Given F = { A → B, B → C, CD → E } on R(A, B, C, D, E), prove that AD → E.

1. A → B           given
2. B → C           given
3. A → C           transitivity (1), (2)
4. AD → CD         augmentation of (3) with D
5. CD → E          given
6. AD → E          transitivity (4), (5)                  ∎

Proofs like this are fine for small cases, but they need a bit of creativity. The next chapter gives a mechanical method (attribute closure) that answers "does X → Y follow from F?" every time without guessing.


Closure of a Set of FDs (F+)

The closure of F, written F+, is the set of all FDs that are logically implied by F, that is, all FDs that can be derived from F using Armstrong's axioms.

F+ includes every trivial FD and every derived FD, so it is huge. Even on 3 attributes there are already 19 trivial FDs alone, and the count grows exponentially with the number of attributes. Nobody computes F+ fully in practice. Instead we ask targeted questions:

  • Does a particular FD X → Y belong to F+?

  • Is X a superkey?

  • Are two FD sets equivalent?

All three are answered with attribute closure, the subject of the next chapter, Attribute Closure & Candidate Keys. Equivalence of FD sets and removing redundant FDs are covered in the Canonical Cover chapter.


Why FDs Matter

  • They expose redundancy. In exam_result, name is repeated because it depends on only part of the key.

  • They define keys precisely.

  • They drive normalization. Every normal form from 2NF to BCNF is defined in terms of FDs.

  • They guide decomposition. Lossless-join and dependency-preserving decompositions are both tested using FDs.


Common Mistakes

  • Deciding an FD holds from sample data. Data can only disprove an FD.

  • Reversing an FD. roll_no → name does not mean name → roll_no.

  • Splitting the LHS. AB → C does not give A → C. Only the RHS can be split.

  • Calling every FD with a key on the left "trivial". Trivial means Y ⊆ X, nothing else.

  • Confusing "X → Y" with "Y depends on every attribute of X". That is the definition of a full dependency, which is stronger.


Interview and Exam Questions

Q1. Define functional dependency.

X → Y holds on R if any two tuples that have the same values for X must have the same values for Y, in every legal instance of R.

Q2. Can you determine the FDs of a table by looking at its data?

No. Data can only show that an FD is violated. Whether an FD holds depends on the real-world rules the schema must obey.

Q3. What are Armstrong's axioms? Why are they important?

Reflexivity, augmentation and transitivity. They are sound (derive only valid FDs) and complete (derive every implied FD), so they fully characterise FD reasoning.

Q4. If AB → C, does A → C hold?

Not necessarily. Decomposition applies only to the right-hand side.

Q5. What is the difference between a trivial and a non-trivial FD?

X → Y is trivial if Y ⊆ X, so it holds in every relation. It is non-trivial if Y contains at least one attribute not in X.

Q6. How are FDs related to superkeys?

K is a superkey of R exactly when K → R, i.e. K determines all attributes.

Q7. What is F+?

The set of all FDs logically implied by F, including trivial ones.


Summary

  • X → Y means equal X values force equal Y values, in every legal instance.

  • FDs come from real-world rules; data can disprove an FD but never prove it.

  • A superkey K is exactly a set with K → R.

  • Types: trivial, non-trivial, completely non-trivial, full, partial, transitive (and multivalued as a separate concept).

  • Armstrong's axioms (reflexivity, augmentation, transitivity) are sound and complete; union, decomposition, pseudotransitivity and composition follow from them.

  • F+ is the set of all implied FDs; we query it efficiently using attribute closure, coming up next.