Inference Rules for Functional Dependencies

Inference rules, also called Armstrong's Axioms, are the three primitive rules from which every functional dependency that logically follows from a given set can be derived. The three axioms are Reflexivity, Augmentation, and Transitivity. Everything else (union, decomposition, pseudo-transitivity) is provable from these three, which is why they are called sound (they never derive a false FD) and complete (they can derive every true one).

The value of this page is that each rule is checked against the same sample rows, not just stated. A functional dependency X → Y means: any two rows that agree on every attribute in X must also agree on every attribute in Y. So to verify a rule on data we look for rows that share the left side and confirm they also share the right side. To pick the running table well, we deliberately include a column whose value repeats across rows — that repetition is what makes a genuine row-by-row trace possible.

The running table

We use one Enrollment table for all three rules. It records, per student, their name, the department they belong to, and the department's name and building. Notice the column choices: Student_ID is unique per row (it is the key), but Dept_ID deliberately repeats — rows 101 and 103 both sit in department D01. That repetition is the lever for tracing transitivity on actual rows.

Two functional dependencies hold on this data, and we can see the determinant repeat for one of them:

• Student_ID → {Name, Dept_ID, Dept_Name, Building}. Student_ID is the key, so it determines every other attribute. Because every Student_ID is distinct, no two rows share the left side — this FD is satisfied vacuously on the data (there is simply no counterexample). We will rely on its meaning, not a row-pair, when we need it.
• Dept_ID → {Dept_Name, Building}. This is the FD whose determinant actually repeats: rows 101 and 103 both have Dept_ID = D01. We can therefore check it directly — and that is exactly what transitivity will need.

1. Reflexivity

Rule. If Y ⊆ X, then X → Y. A set of attributes always determines any subset of itself. This is a logical truth, independent of the data: if two rows agree on all of X, they trivially agree on the part of X that is Y.

Traced on the table. Take X = {Student_ID, Dept_ID} and Y = {Dept_ID}. Rows 101 and 103 do not agree on X (their Student_IDs differ, 101 vs 103), so they impose no requirement — no two rows here share both Student_ID and Dept_ID, so the FD holds with nothing to check. More illustratively, take X = {Dept_ID} and Y = {Dept_ID}: rows 101 and 103 agree on X (both D01), and they trivially agree on Y (both D01). The inclusion {Dept_ID} ⊆ {Dept_ID} guarantees this can never fail. So {Student_ID, Dept_ID} → Dept_ID and {Dept_Name, Building} → Building both hold by reflexivity. Dependencies derivable by reflexivity are called trivial FDs.

2. Augmentation

Rule. If X → Y, then XZ → YZ for any attribute set Z. Adding the same attribute(s) to both sides preserves a dependency.

Why it must hold (structural argument). Suppose two rows agree on XZ. Then in particular they agree on X, so by the assumed FD X → Y they agree on Y; and since they also agree on Z, they agree on YZ. The conclusion is forced by the premise — no data can break it.

Traced on the table. Start from Dept_ID → Dept_Name, which we verified above (rows 101 and 103 share D01 and share Science). Augment both sides with Building to get {Dept_ID, Building} → {Dept_Name, Building}. Check it on the only candidate pair, rows 101 and 103: they agree on the augmented left side (D01, Newton Hall), and they agree on the augmented right side (Science, Newton Hall). The dependency survives the augmentation, exactly as the rule promises.

3. Transitivity

Rule. If X → Y and Y → Z, then X → Z. Dependencies chain.

This is the rule that the data must actually exercise, and our repeated Dept_ID makes that possible. We chain through the department, not the student, because that is where rows genuinely share a left side. Take the two real FDs that hold on the table:

• Dept_ID → Building (the X → Y link)
• Building → Dept_Name (the Y → Z link) — in this data each building houses exactly one department, so the building name pins down the department name.

Step-by-step row trace.

1. Verify Dept_ID → Building. The only two rows that agree on Dept_ID are 101 and 103 (both D01). Do they agree on Building? Yes — both Newton Hall. (Rows 102 and 104 have unique Dept_IDs, so they place no further constraint.) The first link holds.
2. Verify Building → Dept_Name. The only two rows that agree on Building are again 101 and 103 (both Newton Hall). Do they agree on Dept_Name? Yes — both Science. The second link holds.
3. Derive Dept_ID → Dept_Name. Now check the conclusion directly on the data: rows 101 and 103 agree on Dept_ID (D01); do they agree on Dept_Name? Yes — both Science. The chain delivered a true dependency, and we confirmed it on the very rows that share the determinant.

Walking the same pair (101, 103) through both links and then through the conclusion is the whole point: D01 → Newton Hall → Science, therefore D01 → Science. Because departments repeat across students, this transitive dependency means storing Dept_Name alongside every student row duplicates the same fact (D01 is Science) on rows 101 and 103 — precisely the redundancy that normalization removes by splitting the department attributes into their own table.

Summary of the three axioms

Three derived rules follow from these axioms and are worth memorizing: Union (if X → Y and X → Z then X → YZ), Decomposition (if X → YZ then X → Y and X → Z), and Pseudo-transitivity (if X → Y and WY → Z then WX → Z). Each can be proved using only Reflexivity, Augmentation, and Transitivity, which is the precise sense in which Armstrong's three axioms are complete.

Sources

• Silberschatz, Korth & Sudarshan, Database System Concepts, 7th ed., ch. 7 (Armstrong's axioms, soundness and completeness, closure of FD sets).
• Elmasri & Navathe, Fundamentals of Database Systems, 7th ed., ch. 15 (inference rules IR1–IR3 and the derived union, decomposition, and pseudo-transitivity rules).
• Ramakrishnan & Gehrke, Database Management Systems, 3rd ed., ch. 19 (functional dependencies and reasoning about them).

🎯 STRICT STANDOUT: Why / worked / when-not / failure / drills — Inference Rules for Functional Dependencies

Why this concept exists (judgment chain)

Armstrong's axioms (reflexivity, augmentation, transitivity) are sound and complete: every true FD follows from them and they never invent false ones. You need them to compute attribute closure, candidate keys, and to justify 3NF/BCNF decompositions — not as trivia. Tracing on repeating Dept_ID shows why transitivity creates real redundancy.

Worked example with numbers or traced steps

Enrollment rows 101 & 103 both Dept_ID=D01, Building=Newton Hall, Dept_Name=Science.
Reflexivity: {Dept_ID} → {Dept_ID} (trivial).
Augmentation: Dept_ID → Dept_Name ⇒ {Dept_ID, Building} → {Dept_Name, Building}; pair 101/103 agrees.
Transitivity: Dept_ID → Building and Building → Dept_Name ⇒ Dept_ID → Dept_Name.
Redundancy: D01→Science stored on every student in D01 — normalize to Department table.

When NOT to use / named alternative

Do not memorize only derived rules (union/decomposition) without proving them from the three axioms when asked. Do not use a table where every determinant is unique — you cannot row-trace non-trivial FDs. Attribute closure algorithm is preferred over pure axiom chase for large FD sets.

Failure / ops fingerprint

Normalization bug: split tables without checking if original FDs are preserved (dependency preservation). Interview fail: cannot show a counterexample pair for a claimed FD. Ops schema smell: repeating Dept_Name with Dept_ID across millions of fact rows → update anomalies when Science renames.

Hostile-panel Q&As (model answers)

Q1. Prove soundness of transitivity in one sentence.
Model answer: If two tuples agree on X they agree on Y, and if they agree on Y they agree on Z; hence they agree on Z.

Q2. Why does Student_ID → * not need a repeating left side to hold?
Model answer: Unique keys satisfy FDs vacuously — no two rows share the left side, so no counterexample exists.

Q3. Name a derived rule and how it follows.
Model answer: Decomposition: from X→YZ, reflexivity gives YZ→Y; transitivity yields X→Y (similarly X→Z).