Inference Rules for Functional Dependencies

Relational Database Design and Modeling for Software Engineers

Ask Author

Back to course home

0% completed

Vote For New Content

Inference Rules for Functional Dependencies

Table of Contents

Contents are not accessible

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}.

Student_ID	Name	Course
101	Alice Smith	Math
102	Bob Johnson	Science
103	Carol White	History

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:

Student_ID	Department_ID	Department_Name
101	D01	Science
102	D02	Arts
103	D03	Commerce

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

Rule	Definition	Example
Reflexivity	If Y is a subset of X, then X → Y	{Student_ID, Name} → Student_ID
Augmentation	If X → Y, then XZ → YZ	If Student_ID → Name, then {Student_ID, Course} → {Name, Course}
Transitivity	If X → Y and Y → Z, then X → Z	If Student_ID → Department_ID and Department_ID → Department_Name, then Student_ID → Department_Name

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible