Inference Rules for Functional Dependencies

Inference rules, also known as Armstrong’s Axioms, are foundational rules used to derive all possible functional dependencies from a given set of dependencies in a relational database. These rules—Reflexivity, Augmentation, and Transitivity—are essential for understanding and organizing functional dependencies effectively, which aids in database normalization and minimizes redundancy.

Let’s go through these three main rules with examples and tables based on a Student database.

1. Reflexivity Rule

The Reflexivity Rule states that if a set of attributes Y is a subset of a set of attributes X, then X → Y holds. This means an attribute or a combination of attributes always determines itself or any subset of itself.

• Notation: If Y ⊆ X, then X → Y.

• Example: Consider the following Student table with attributes {Student_ID, Name, Course}.

In this table:

• {Student_ID, Name} → Student_ID is a valid dependency because Student_ID is a subset of {Student_ID, Name}.
• {Student_ID, Course} → Course also holds by reflexivity, as Course is a subset of {Student_ID, Course}.

The reflexivity rule emphasizes that any attribute set inherently determines itself and any subset of its components.

2. Augmentation Rule

The Augmentation Rule states that if X → Y holds, then adding an attribute Z to both sides of the dependency will still result in a valid dependency. This rule allows attributes to be added to a dependency without altering its validity.

• Notation: If X → Y, then XZ → YZ (where XZ is the union of X and Z).

• Example: Using the same Student table above, suppose we know that Student_ID → Name holds true, meaning that each Student_ID uniquely identifies a Name.

Now, let’s add Course to both sides:

• {Student_ID, Course} → {Name, Course} also holds by the augmentation rule. If we know that Student_ID determines Name, then {Student_ID, Course} will still uniquely determine both Name and Course.

This rule is especially useful when constructing complex dependencies that involve multiple attributes while ensuring no loss of information.

3. Transitivity Rule

The Transitivity Rule is similar to the transitive property in mathematics. It states that if X → Y and Y → Z hold, then X → Z is also a valid dependency. Transitivity is crucial for identifying indirect dependencies that can contribute to redundancy if not properly managed.

• Notation: If X → Y and Y → Z, then X → Z.

• Example: Consider an expanded Student_Department table with the following attributes:

In this table, suppose the following dependencies hold:

• Student_ID → Department_ID: Each student is assigned a unique department.
• Department_ID → Department_Name: Each department ID uniquely identifies a department name.

By the transitivity rule:

• Student_ID → Department_Name can be inferred, meaning Student_ID indirectly determines Department_Name through Department_ID.

This transitive dependency highlights the need to normalize data to reduce redundancy, as it indicates that storing Department_Name with Student_ID could result in unnecessary data duplication.

Summary Table of Inference Rules