DBMS Menu

Functional Dependencies and its reasoning in DBMS



Functional dependencies play a vital role in the normalization process in relational database design. They help in defining the relationships between attributes in a relation and are used to formalize the properties of the relation and drive the process of decomposition.

Functional Dependencies (FD)

A functional dependency `\( X \rightarrow Y \)` between two sets of attributes X and Y in a relation R is defined as: if two tuples (rows) of R have the same value for attributes X, then they must also have the same values for attributes Y. In other words, the values of X determine the values of Y.

Consider a relation (table) Students:


| sid  | sname    | zipcode | cityname       | state          |
|------|----------|---------|----------------|----------------|
| S001 | Aarav    | 110001  | New Delhi      | Delhi          |
| S002 | Priyanka | 400001  | Mumbai         | Maharashtra    |
| S003 | Rohit    | 700001  | Kolkata        | West Bengal    |
| S004 | Ananya   | 560001  | Bengaluru      | Karnataka      |
| S005 | Kartik   | 600001  | Chennai        | Tamil Nadu     |
| S006 | Lakshmi  | 500001  | Hyderabad      | Telangana      |
| S007 | Aditya   | 160017  | Chandigarh     | Chandigarh     |
  1. sid functionally determines sname because for a given student ID, there's only one possible student name
  2. zipcode functionally determines cityname, a specific zip code should determine a unique cityname
  3. cityname functionally determines state, A city name could determine a state.

Mathematically, these functional dependencies can be represented as:

\( sid \rightarrow sname \)
\( zipcode \rightarrow cityname \)
\( cityname \rightarrow state \)


Reasoning About Functional Dependencies

1. Trivial Dependency

- If Y is a subset of X, then the dependency X -> Y is trivial.
- For example, in {A, B} -> {A}, the dependency is trivial because A is part of {A, B}.

Example: For attributes A,B,C:

  • \( A \rightarrow A \) is a trivial dependency because an attribute always determines itself.
  • \( AB \rightarrow A \) is a trivial dependency because the combined attributes A and B always determine A as it's a subset.
  • \( ABC \rightarrow AC \) is a trivial dependency for the same reason; the combined attributes A,B, and C always determine A and C.

2. Full Functional Dependency

- An attribute functionally depends on a set of attributes, X, and does not functionally depend on any proper subset of X.

Example: Consider a relation StudentCourses that has the following attributes:

  • StudentID (unique identifier for each student)
  • CourseID (unique identifier for each course)
  • Instructor (name of the instructor teaching the course)

The relation is used to keep track of which student is enrolled in which course and who the instructor for that course is.

Now, assume we have the following functional dependency:
(StudentID,CourseID) → Instructor

This means that a combination of a specific student and a specific course will determine who the instructor is.

Thus, Instructor is fully functionally dependent on the combined attributes StudentID and CourseID.

3. Transitive Dependency

- If A -> B and B -> C, then A has a transitive dependency on C through B.

Example: Consider a relation Employees with the following attributes:

  • EmployeeID (unique identifier for each employee)
  • EmployeeName
  • Department (department in which the employee works)
  • DepartmentLocation (location of the department)

Now, let's consider the following functional dependencies:

EmployeeID → Department
Department → DepartmentLocation

From the above functional dependencies:

An EmployeeID determines the Department an employee works in.
A Department determines its DepartmentLocation.

However, the DepartmentLocation is also dependent on the EmployeeID through Department. This means the DepartmentLocation has a transitive dependency on EmployeeID via Department.

This kind of transitive dependency can lead to redundancy.

4. Closure

- The closure of a set of attributes X with respect to a set of functional dependencies FD, denoted as X+, is the set of attributes that are functionally determined by X.
- For example, given FDs: {A -> B, B -> C}, the closure of {A}, denoted as A+, would be {A, B, C}.

Next Topic :Introduction to Normal Forms