What is a Functional Dependency (FD)?

In relational database design, a functional dependency (FD) is a constraint between two sets of attributes from the database.

Definition:
Let X and Y be sets of attributes in a relation R.
Y is functionally dependent on X (written as X → Y) if for any two tuples t1 and t2 in R:

If t1[X] = t2[X], then t1[Y] = t2[Y]

This means: X uniquely determines Y.

---

Minimal Cover (Canonical Cover)

A minimal cover is an equivalent set of functional dependencies that is:

1. Equivalent to the original set (same closure).
2. Right-reduced: Each FD has only one attribute on the right-hand side.
3. Left-reduced: No attribute in the left-hand side is redundant.
4. Minimal: No FD is redundant.

---

Steps to Find Minimal Cover

Given:
F = {B → A, D → A, AB → D}

Step 1: Ensure Right Side is Singleton

Each FD must have a single attribute on the right.
All FDs in F are already single attribute on RHS.

F = {B → A, D → A, AB → D}

---

Step 2: Remove Redundant Attributes from LHS

Check for unnecessary attributes in LHS of each FD.

Check AB → D

Is A necessary? Try removing it:
Check if B → D is implied by F:

• From B → A, and AB → D,
  Compute closure of B: B⁺ = {B} B → A → B⁺ = {B, A} AB → D → (B, A) → D → B⁺ = {B, A, D} So, B⁺ includes D ⇒ B → D holds

⇒ So A is not required in AB → D.
Replace AB → D with B → D

Now:

F = {B → A, D → A, B → D}

---

Step 3: Remove Redundant FDs

Check if any FD is redundant.

Check if D → A is redundant:

From other FDs: B → D, B → A

Check if D → A is implied by the others.

Start with:

• B → D
• B → A

Then:

• From B → D and B → A, but D → A cannot be derived directly.

So, D → A is not redundant.

---

Minimal Cover Result:

G = {B → A, D → A, B → D}

This is the minimal cover for F.

---

Inference Rules (Armstrong’s Axioms)

These are sound and complete rules to infer all FDs from a given set.

1. Reflexivity

If Y ⊆ X, then X → Y
Proof: If X contains Y, then clearly X determines Y.

---

2. Augmentation

If X → Y, then XZ → YZ for any Z
Proof: If knowing X gives Y, then knowing X and something else still gives Y (just more info).

---

3. Transitivity

If X → Y and Y → Z, then X → Z
Proof: If X gives Y and Y gives Z, then X must give Z.

---

Derived Rules

Using the above 3, we can derive:

4. Union

If X → Y and X → Z ⇒ X → YZ

5. Decomposition

If X → YZ ⇒ X → Y and X → Z

6. Pseudotransitivity

If X → Y and WY → Z ⇒ WX → Z

All these rules are used in normalization and in computing closures and minimal covers.