Functional Dependencies

Functional Dependencies (FDs)

A Functional Dependency (FD) is a relationship between two sets of attributes in a relational database. It is a key concept in database normalization and plays a crucial role in ensuring the consistency and integrity of the data. Functional dependencies define how the values of one set of attributes determine the values of another set of attributes.

---

1. Definition of Functional Dependency

A functional dependency between two sets of attributes is denoted as:

• X → Y

Where:

• X is a set of attributes (also known as the determinant).
• Y is a set of attributes (the dependent attributes).

This means that if two rows have the same value for the attributes in X, they must also have the same value for the attributes in Y. In other words, X functionally determines Y.

Example:

• EmployeeID → EmployeeName
  • This means that for each unique EmployeeID, there is exactly one corresponding EmployeeName. If two rows have the same EmployeeID, they must have the same EmployeeName.

---

2. Types of Functional Dependencies

a. Trivial Functional Dependency

• A functional dependency is called trivial if the dependent attributes are a subset of the determinant. In other words, X → Y is trivial if Y is a subset of X.

Example:

• EmployeeID, EmployeeName → EmployeeID
  • This is a trivial dependency because EmployeeID is already part of the left side, and the right side is a subset of it.

b. Non-Trivial Functional Dependency

• A functional dependency is non-trivial if Y is not a subset of X.

Example:

• EmployeeID → EmployeeName
  • This is a non-trivial dependency because EmployeeName is not a subset of EmployeeID.

c. Transitive Dependency

• A transitive dependency occurs when an attribute A determines attribute B, and attribute B determines attribute C, implying that A indirectly determines C through B.
• A → B and B → C lead to the transitive dependency A → C.

Example:

• If EmployeeID → DepartmentID and DepartmentID → DepartmentName, then we can infer that EmployeeID → DepartmentName through transitivity.

---

3. Importance of Functional Dependencies in Database Design

a. Normalization

Functional dependencies are essential for normalization, which is the process of organizing data to reduce redundancy and improve data integrity. Normalization is achieved through different normal forms (1NF, 2NF, 3NF, etc.), and functional dependencies help in defining the rules for achieving these forms.

• 1NF (First Normal Form) focuses on removing duplicate rows.
• 2NF (Second Normal Form) eliminates partial dependencies (dependencies that involve only part of a composite primary key).
• 3NF (Third Normal Form) removes transitive dependencies.
• BCNF (Boyce-Codd Normal Form) further refines the rules for functional dependencies.

b. Data Integrity

Functional dependencies help ensure that the data adheres to certain integrity rules. For example, if a StudentID uniquely determines the StudentName, then the StudentName cannot change independently of the StudentID.

c. Minimizing Redundancy

By enforcing functional dependencies, we can minimize redundancy in the database. For example, in a table where a CourseID determines the Instructor, there is no need to store the Instructor multiple times for each student taking the same course. This reduces the chances of anomalies (insertion, deletion, and update anomalies).

---

4. Examples of Functional Dependencies

Example 1: Simple Dependency

• In a Student table with columns: StudentID, Name, Course, Instructor.
• The functional dependency could be:
  • StudentID → Name (Each StudentID determines the Name of the student).
  • Course → Instructor (Each Course determines which Instructor teaches it).

Example 2: Composite Dependency

• In a table that stores data about a StudentCourse with columns: StudentID, CourseID, Instructor, Grade.
• A composite functional dependency might be:
  • (StudentID, CourseID) → Grade (The combination of StudentID and CourseID determines the Grade).

---

5. Finding Functional Dependencies

Functional dependencies can be inferred from the business rules and constraints of the application or system. To identify FDs, it is important to:

• Analyze the relationships between attributes in the real-world scenario the database is modeling.
• Look at the data and see if there is any pattern that indicates one attribute determines another.
• Identify candidate keys (attributes or sets of attributes that can uniquely identify a row) since any key in the table is a determinant for all other attributes.

---

6. Closure of Functional Dependencies

The closure of a set of functional dependencies refers to all the attributes that can be functionally determined by a given set of attributes.

• Closure of a set of attributes (denoted X+) is the set of all attributes that can be functionally determined by X using the given set of functional dependencies.

Example:

Consider the following set of attributes and functional dependencies:

• FD1: A → B
• FD2: B → C
• FD3: A → D

Now, to find the closure of A (denoted A+):

• A+ starts with A.
• From A → B, we can add B to A+.
• From B → C, we can now add C to A+.
• From A → D, we can add D to A+.

Thus, A+ = {A, B, C, D}.

---

7. Armstrong's Axioms

Armstrong's Axioms are a set of rules used to derive all the functional dependencies that can be inferred from a given set of functional dependencies. These axioms help in determining whether a functional dependency is valid or not.

The four basic Armstrong’s Axioms are:

1. Reflexivity: If Y is a subset of X, then X → Y.

   • Example: {A, B} → A is always true because A is a subset of {A, B}.

2. Augmentation: If X → Y, then XZ → YZ (where Z is any set of attributes).

   • Example: If A → B, then AC → BC.

3. Transitivity: If X → Y and Y → Z, then X → Z.

   • Example: If A → B and B → C, then A → C.

4. Union: If X → Y and X → Z, then X → YZ.

   • Example: If A → B and A → C, then A → BC.

---

8. Conclusion

Functional dependencies are a fundamental concept in relational database design, as they help define the relationships between attributes within a table. Understanding FDs is crucial for normalizing a database, ensuring data integrity, and minimizing redundancy. By using techniques such as Armstrong's Axioms and FD closure, we can derive all valid functional dependencies from a set of existing ones, which can guide us in achieving efficient and normalized database designs.