Inference Rules for Functional Dependencies

📌 Basic Idea

• Let F be a set of functional dependencies (FDs) defined on a relation schema.
• Many additional FDs are not explicitly given, but can be derived (inferred) from F.

👉 These are called:

• Inferred / Implied Functional Dependencies

---

Key Definitions

🔹 Implied Functional Dependency

An FD X → Y is implied by F if:

It holds in every valid relation that satisfies all dependencies in F.

---

🔹 Closure of F (F⁺)

• F⁺ (F plus) = set of:
  • All given FDs in F
  • All FDs that can be inferred from F

👉 Important:

• We don’t list all FDs explicitly
• Instead, we use rules to derive them

---

📌 Example 

Given:

Dept_no → Mgr_ssn
Mgr_ssn → Mgr_phone

👉 We can infer:

Dept_no → Mgr_phone

✔ This is an implied FD

---

⚙️ Armstrong’s Inference Rules

These are basic rules used to derive new FDs from existing ones.

---

🔹 IR1: Reflexivity Rule

📌 Rule:

If Y ⊆ X, then:

X → Y

💡 Meaning:

• A set of attributes always determines its subset

✔ Example:

{A, B} → A

---

🔹 IR2: Augmentation Rule

📌 Rule:

If:

X → Y

Then:

XZ → YZ

💡 Meaning:

• Adding the same attribute(s) to both sides keeps the dependency valid

✔ Example:

A → B  
Then AC → BC

---

🔹 IR3: Transitivity Rule

📌 Rule:

If:

X → Y  
Y → Z

Then:

X → Z

💡 Meaning:

• Dependencies can be chained

✔ Example:

Dept_no → Mgr_ssn  
Mgr_ssn → Mgr_phone  
⇒ Dept_no → Mgr_phone

---

🧩 Additional Derived Examples

From:

Ssn → Dnumber  
Dnumber → Dname

👉 We can infer:

Ssn → Dname   (using transitivity)

---

Notation

• Writing:

F ⊨ X → Y

means:

X → Y is logically implied by F

---

🎯 Why Inference Rules Matter

• Help find hidden dependencies
• Used in:
  • Database design
  • Normalization
  • Checking redundancy

---

 Summary

“Inference rules  are used to derive new functional dependencies from a given set, helping us understand all constraints (closure F⁺) that hold in a database schema.”