Functional Dependencies

Functional Dependencies in Database Design

Functional Dependency (FD) is a fundamental concept in database design and normalization. It describes a relationship between two sets of attributes in a relational database. A functional dependency ensures that the value of one attribute (or set of attributes) uniquely determines the value of another attribute (or set of attributes). Functional dependencies are used to enforce data integrity and to guide the normalization process, helping to eliminate redundancies and dependencies that could lead to data anomalies.

Definition of Functional Dependency

A functional dependency exists between two attributes (or sets of attributes) if, for every valid instance of the relation, the value of one attribute (or set of attributes) uniquely determines the value of another attribute.

Formally, if X and Y are two sets of attributes, we say that there is a functional dependency from X to Y (denoted as X → Y) if, whenever two rows of a relation agree on all attributes in X, they must also agree on all attributes in Y.

• Notation: X → Y means that attribute(s) X functionally determines attribute(s) Y.
• Explanation: If two tuples (rows) have the same value for X, they must have the same value for Y.

Example:

Consider a relation Employee with the following attributes:

• EmployeeID
• EmployeeName
• DeptID
• DeptName

If the value of EmployeeID determines the value of EmployeeName (i.e., for each unique EmployeeID, there is exactly one EmployeeName), we can represent this functional dependency as:

EmployeeID → EmployeeName

This means that knowing the EmployeeID is sufficient to determine the corresponding EmployeeName.

Similarly, if DeptID determines DeptName, we have:

DeptID → DeptName

This means that if two employees share the same DeptID, they must be in the same department (DeptName).

Types of Functional Dependencies

There are different types of functional dependencies used to express relationships between attributes in a relation:

1. Trivial Functional Dependency
2. Non-Trivial Functional Dependency
3. Transitive Functional Dependency
4. Full Functional Dependency
5. Partial Functional Dependency

---

1. Trivial Functional Dependency

A trivial functional dependency is one where the set of attributes on the right-hand side is a subset of the attributes on the left-hand side. Essentially, this is a dependency that is always true and doesn't provide any useful information.

• Notation: X → X
• Example: EmployeeID, DeptID → EmployeeID or EmployeeID → EmployeeID
• Explanation: This dependency is trivial because an attribute (or set of attributes) trivially determines itself.

---

2. Non-Trivial Functional Dependency

A non-trivial functional dependency is one where the left-hand side is not a subset of the right-hand side, and the dependency is not obvious or trivial.

• Notation: X → Y, where X and Y are sets of attributes and Y is not a subset of X.
• Example: EmployeeID → EmployeeName
• Explanation: Here, EmployeeID determines EmployeeName, but EmployeeID is not a subset of EmployeeName.

---

3. Transitive Functional Dependency

A transitive functional dependency occurs when an attribute depends on another attribute through a third attribute. This happens when there is an indirect relationship between attributes.

• Notation: X → Y and Y → Z imply X → Z.
• Example: If StudentID → Department and Department → Instructor, then we have the transitive dependency StudentID → Instructor.
• Explanation: If knowing StudentID gives us Department, and knowing Department gives us Instructor, then StudentID indirectly determines Instructor.

In normalization, transitive dependencies are removed in higher normal forms (like 3NF) to ensure that non-key attributes depend directly on the primary key.

---

4. Full Functional Dependency

A full functional dependency is a type of functional dependency where a non-key attribute is fully dependent on the entire primary key. This is important in the context of composite keys.

• Notation: X → Y, where X is a set of attributes that includes the entire primary key, and Y is a non-key attribute that is fully dependent on all of X.
• Example: In a table with composite primary key (StudentID, CourseID), if Grade depends on the entire composite key, we have a full functional dependency: (StudentID, CourseID) → Grade.
• Explanation: Here, knowing both StudentID and CourseID is required to uniquely determine Grade. If only part of the primary key were to determine Grade, this would be a partial dependency, which is not allowed in 2NF.

---

5. Partial Functional Dependency

A partial functional dependency occurs when a non-key attribute depends on only part of a composite primary key. This kind of dependency violates the rules of 2NF (Second Normal Form), which requires that every non-key attribute be fully dependent on the entire primary key.

• Notation: If X → Y and X is only part of the primary key, then X → Y is a partial dependency.
• Example: Consider a table with a composite primary key (StudentID, CourseID), and suppose Instructor only depends on CourseID, not on the entire composite key.
  • The functional dependency CourseID → Instructor is a partial dependency.
• Explanation: This dependency violates 2NF because Instructor is dependent on only part of the composite primary key.

---

Importance of Functional Dependencies in Normalization

Functional dependencies play a critical role in database normalization because they help to identify and eliminate redundancy in data by guiding the decomposition of relations into smaller, well-structured relations.

Functional Dependency and Normal Forms

• 1NF: There should be no repeating groups or arrays, and all attributes should be atomic.
• 2NF: A relation is in 2NF if it is in 1NF and there are no partial dependencies (i.e., every non-key attribute depends on the full primary key).
• 3NF: A relation is in 3NF if it is in 2NF and there are no transitive dependencies between non-key attributes.
• BCNF: A relation is in BCNF if every non-trivial functional dependency has a superkey on the left side.

---

Closure of a Set of Functional Dependencies

The closure of a set of functional dependencies is the set of all functional dependencies that can be inferred from a given set of functional dependencies. It is useful for determining all possible relationships in a relation and for checking if a particular functional dependency is valid or implied.

• Notation: If we have a set of functional dependencies F, the closure of F is denoted as F+.
• Example: If we know the dependencies A → B and B → C, the closure of {A} would be {A → B, A → C}, because from A → B and B → C, we can infer that A → C.

---

Summary of Functional Dependencies:

• A Functional Dependency expresses a relationship where one set of attributes determines another.
• Trivial Functional Dependency: A dependency where the right-hand side is a subset of the left-hand side (e.g., X → X).
• Non-Trivial Functional Dependency: A dependency where the left-hand side is not a subset of the right-hand side.
• Transitive Dependency: When one attribute determines another indirectly.
• Full Functional Dependency: A non-key attribute is fully dependent on the entire primary key.
• Partial Dependency: A non-key attribute is dependent on only part of a composite primary key.
• Functional dependencies help guide the process of normalization to reduce redundancy and dependency in relational databases.