Functional Dependencies in DBMS: Use of FD in Table Design

A Functional dependency is used to describe the relationship between attributes of a relation. In other words, it explains how one or more columns of a database table determine other columns. In this article, we will discuss, the use of functional dependencies in table design and uses of functional dependencies.

Let \Large X be a set of attributes, and \Large Y be another set of attributes.

If two rows of a relation have the same values for the attributes in \Large X, then they must have the same values for the attributes in \Large Y. This is known as the uniqueness property, and every functional dependency satisfies this property.

A functional dependency between \Large X and \Large Y is denoted as \Large X \rightarrow Y where \Large X is called the determinant and \Large Y is the dependent attribute set.

Example of Functional Dependency (FD)

Consider the following database table.

For each StudentID, there is only one StudentName. If two rows have same StudentID, then their StudentName must be same.

Similarly, for each StudentID there is exactly one Department. If two rows have same StudentID, then the deparment must contain same value.

This satisfies the uniqueness property of functional dependency.

Functional Dependencies in the Student Table

\Large StudentID \rightarrow StudentName\\StudentID \rightarrow Department

StudentName and Department are functionally dependent on StudentID. The StudentID is the determinant.

What Happens When There is no Functional Dependency

Consider another table with attributes – StudentID and CourseID.

The table shows that some students are associated with more than one CourseID.
Therefore, StudentID does not uniquely determine CourseID, and the uniqueness property is not satisfied for this relationship.

This means the functional dependency

\Large StudentID \rightarrow CourseID

does not hold.

1. StudentID does not uniquely determines CourseID.
2. Student can be associated with many Courses.

A functional dependency exists only when the left-hand side attributes (determinants) uniquely determine the right-hand side attributes (dependent).

If one value of set \Large X, is mapped to multiple values of \Large Y, then \Large X \rightarrow Y is not functional dependency.

In the real world, a student can enroll in multiple courses. Although there is a meaningful relationship between students and courses, it is not a functional dependency.

While designing a database, the learner must carefully distinguish between:

• Meaningful relationships, and
• Functional dependencies, which require uniqueness.

Only relationships that satisfy the uniqueness property can be modeled as functional dependencies.

Composite Functional Dependency

Consider the following Grade Table.

Step 1: Check for Individual Attributes

The StudentID alone cannot uniquely identify a student’s Grade. Students may obtain same grade for different courses.
Similarly, the CourseID alone cannot uniquely identify the grade of a student. Different student may get same grade for same course. There is no uniqueness.

Step 2: Check for Combination of Attributes

Consider the following combination:

\Large \{StudentID, CourseID\}

Now we can uniquely identify a grade. Therefore, the functional dependency

\Large \{StudentID, CourseID\} \to Grade

holds.

This is called a composite functional dependency because the determinant consists of more than one attribute. In such a dependency, the left-hand side of the functional dependency is called a composite determinant.

Why Functional Dependencies Matter Before Normalization

Normalization is a formal process that restructures tables based on functional dependencies (FDs). Forms such as 2NF, 3NF, and BCNF are defined entirely in terms of FDs.
Therefore, normalization cannot begin until functional dependencies are identified and analyzed.

Role of Functional Dependencies (FDs)

Before normalization, functional dependencies are used to:

• Identify candidate keys
• Detect redundancy
• Explain insertion, update, and deletion anomalies

Each of these tasks relies on formal dependency rules, not intuition

Identifying Keys

Functional dependencies are used to find the candidate keys of a table. A candidate key is a set of attributes \Large K that determines all other attributes of the table, and no proper subset of \Large K can do the same.

To find candidate keys, we use a procedure called attribute closure.

The closure of attribute set \Large K written as \Large K^+

• is the set of all attributes
• that can be functionally determined from \Large K
• using the given functional dependencies.

The attribute closure of a set of attributes finds all attributes that are functionally determined by that set using the given functional dependencies. If the closure of a set K contains all attributes of the table and no proper subset of $K$ has this property, then $K$ is a candidate key.

Formally, if

• \Large K^+ contains all attributes of the relation.
• No other proper subset can this property,

\Large K is the candidate key.

Example – Find the Candidate key for Student Table.

Consider a Student table with four attributes: StudentID, CourseID, StudentName, and Grade.

We usually begin by computing the closure of single attributes.

The attribute itself is always included in its closure.

Using the functional dependency StudentID → StudentName, we add StudentName to the closure.

StudentName is part of closure

There is no functional dependency StudentID → Grade, so Grade cannot be added to the closure.

Let us check closure for CourseID.

Initial value added to closure.

The above is not a dependency.

is not candidate set of keys.

Check closure of all attributes.

Initial value added to closure.

This is the candidate key which functionally determine all attributes in the table.

Can we minimize it ?

Yes, the Grade can be determined by \Large \{StudentID, CourseID\}, but \Large StudentID or \Large CourseID cannot be determined alone.

Conclusion

The candidate key for the student table is the set \Large {StudentID, CourseID} because it determine all the attributes in the table.

\Large \{StudentID, CourseID\} \to Grade.

\Large\{StudentID, CourseID\} \to StudentID.

\Large \{StudentID, CourseID\} \to CourseID.

Another use of FD is to find the redundancy.

FD and Redundancy

From the above discussion, it clear that a functional dependency is either determinant or dependent in an optimized table. Any table attribute that it dependent on non-key attribute is likely to have duplicate values.

Therefore, functional dependencies reveal such attributes that are dependent on non-key attributes.

Consider the Student table with three attributes – StudentID, DepartmentID, and DeptName.

The functional dependencies are:

\Large StudentID \to DepartmentID \\
DepartmentID \to DeptName

DeptName is not functionally dependent on StudentID.

The nature of functional dependency is Transitive.

\Large StudentID \to DepartmentID \to DeptName

We always want to remove the Transitive dependencies.

In these case, each student will not have exactly one value for Department name, but contains multiple redundant values.

Describe The Insert, Update and Deletion Anomalies

Here is a list of problems due to redundancies.

Insert anomalies – Unless student exists department id cannot be assigned , so a new department is not created if we don’t have a student. This is Insert anomalies.

Update anomalies – The table shows two students from same department – Physics. If we want to rename the Physics to something else, say Quantum Physics. We must change all the records where department name is Physics. This is update anomalies.

Deletion anomalies – If we delete the record for Student with id 20, then the department cease to exist. This is deletion anomalies.

Let us take another example.

The following Student table have four attributes – StudentID, CourseID, StudentName, and Grade.

Let us identify the functional dependencies from the table.

\Large StudentID \to StudentName\\
\{StudentID, CourseID\} \to Grade

Clearly, the primary key is \Large \{StudentID, CourseID\}.

However, StudentName is only dependent on StudentID. This is Partial Dependency.

Conclusion

The solution to example 1 and example are same:

Example 1 – In case of transitive dependency, split the table into two.

The Student table has multiple same values, this is not redundancy. The StudentID is unique key and it identity the row in Student table uniquely.

The department table is totally unique because each department id has exactly one department.

Example 2 – In the case of partial dependency, you have to split the table again.

In the second example, StudentID or CourseID, alone cannot determine the Grade. Here are the functional dependencies from both tables.

Student Table

\Large StudentID \to StudentName

Grade Table

\Large \{StudentID, CourseID\} \to Grade

The separate tables ensure that each row is unique and do not have redundant data.

You have seen two different types of functional dependencies. In the next section, we shall explore all types of functional dependencies.

Types of Functional Dependencies (Using Tables)

The functional dependencies are classified based on attribute dependencies. Its the relationship between determinant attributes and dependent attributes.

Trivial Functional Dependency

A functional dependency \Large X \to Y from a set of attributes \Large X to a set of dependent attributes \Large Y is trivial if \Large Yis a subset of \Large X.

In other words, all the attributes of \Large Y are already in \Large X.

\Large X \to Y, is \hspace{4px} trivial \hspace{4px} if \hspace{4px} Y \subseteq X

Example – Trivial Dependency

Observe that the key is \{StudentID, CourseID\} because StudentID or CourseID alone cannot be key.

Given the key, the following functional dependencies are Trivial.

\Large \{StudentID, CourseID\} \to StudentID\\
\{StudentID, CourseID\} \to CourseID

Axiom Used in Trivial Dependency

The Armstrong’s axiom used in trivial functional dependency is called the Reflexivity rule.

\Large FD: A \to A, \hspace{5px} because \hspace{5px} A \subseteq A

Non-Trivial Functional Dependency

A functional dependency \Large X \to Yfrom a set of attributes \Large X to a set of dependent attribute \Large Y is Non-Trivial if \Large Y is non a subset of \Large X.

\Large X \to Y \hspace{4px} is \hspace{4px} Non-Trivial \hspace{5px} if \hspace{4px}Y \nsubseteq X

Example – Non Trivial Dependency

The StudentID is the key and StudentName is dependent attribute. Also,

\Large StudentID \to StudentName,\\
\{StudentName\} \nsubseteq \{StudentID\}

The StudentName is not a subset or equal to set StudentID.

Axioms User in Non-Trivial Dependency

The non-trivial dependency is derived from other Armstrong’s axioms.

Suppose we have a functional dependency, \Large A \to \{B, C\} is called a Union Rule. The functional dependency can be decomposed into:

\Large FD: A \to \{B, C\} = \{A \to B\} \hspace{4px} and \hspace{5px} \{A \to C\}

Completely Non-Trivial Functional Dependency

A functional dependency \Large ( X \to Y ) is a completely non-trivial dependency for two sets of attributes \Large X and \Large Y if:

\Large X \cap Y = \empty 

In a completely non-trivial dependency, the sets \Large X and \Large Y are disjoint, and their intersection is a null or empty set.

Example – Completely Non-Trivial Dependency

Notes that \Large StudentID \cup DeptName are disjoint sets.

However, the functional dependency holds.

\Large StudentID \to DeptName

The functional dependency is correct, but each student can have more than one department. The student with ID 21 has two separate departments. This will cause redundancy in the table. You must normalize the table in such cases.

Full Functional Dependency

A dependency from \Large X \to Y is Full dependency if:

1. \Large Y is dependent on all attributes of \Large X.
2. No proper subset of \Large Xcan determine \Large Y.

Symbolically,

\Large \begin{aligned}
&X \to Y \hspace{5px} is  \hspace{5px} a \hspace{5px} Full \hspace{5px}Functional \hspace{5px} Dependency \hspace{5px} if:\\
&1. \hspace{3px}Y \not \subset X\\
&2. \hspace{3px} X' \not \to Y, \hspace{5px} where \hspace{5px} X' \subset X
\end{aligned}

Example – Full Functional Dependency

In this example, consider Student table with StudentID, CourseID and Grade.

This is a full functional dependency where Grade is dependent on key \Large \{StudentID, CourseID\}.

\Large \{StudentID, CourseID\} \to Grade

Now to validate, that this is full functional dependecy, we must check the conditions.

1. \Large Y is not a subset of \Large X.

\Large \{StudentID, CourseID\} \nsubseteq Grade

2. \Large X' cannot determine \Large Y, where \Large X' is proper subsets of \Large X.

\Large StudentID \not \to Grade\\
CourseID \not \to Grade

Hence, it is proved that the functional dependency is a full functional dependency.

Partial Functional Dependency

A functional dependency \Large X \to Y is a Partial functional dependency if:

1. \Large X is composite. In other words, \Large X has more than one attributes.
2. \Large Y depends only on part of \Large X.

Example – Partial Functional Dependency

Consider the student table.

We have two functional dependencies in the above table.

\Large \{StudentID, CourseID\} \to StudentName\\
StudentID \to StudentName

Let us check the conditions for partial dependency.

1. \Large X is composite. This condition is true because \Large \{StudentID, CourseID\} uniquely determine all the attributes in the student table.
2. \Large Y depends on part of \Large X. This is also true, because StudentName is dependent only on StudentID, and not on CourseID of composite key \Large \{StudentID, CourseID\}.

The partial dependency causes redundancy and violates the second normal form \Large (2NF). You will learn \Large (2NF) in future posts.

Transitive Functional Dependency

A functional dependency \Large X \to Y is Transitive if there exists another dependency \Large Y \to Z such that \Large X \to Z also exists. The \Large X \to Z is also a function dependency.

\Large \to Y \hspace{5px} is \hspace{5px} Transitive \hspace{5px} if:\\

X \to Y \hspace{5px} and \hspace{5px} Y \to Z \hspace{5px} implies \hspace{5px} X \to Z

Example – Transitive Functional Dependency

Consider the following Employee table.

We see two functional dependencies in the Employee table.

\Large EmployeeID \to DeptID\\
DeptID \to DeptAddress

Since, EmployeeID determines DeptID and DeptID determines DeptAddress.

A transitive functional dependency. exists between ExployeeID and DeptAddress.

\Large ExployeeID \to DeptAddress

A transitive dependency contains redundant data.

If you look at the Employee table, the department address Mumbai is repeated every time when an employee has department ID of D14. In these cases, splitting the table is the best solution.

Now, you know everything about Functional dependencies, let us summarize what you learned.

Summary

These are important points to remember for exams.

Uses Of Functional Dependencies (Concept Overview for Revision)

Types of Functional Dependencies