Articles / DBMS · Part 9

Functional Dependencies and Attribute Closure

Learn functional dependencies, determinants, Armstrong's axioms, and attribute closure with step-by-step examples in DBMS.

Functional Dependencies and Attribute Closure

1. Introduction

When designing a relational database, we need to understand how different attributes are related to one another.

For example, in a university database, a student’s ID may uniquely determine their name and department. Similarly, a department ID may determine the name of that department.

These relationships are known as Functional Dependencies. They help us identify keys, detect redundancy, and design well-structured databases.

Attribute Closure is a technique used to determine which attributes can be derived from a given set of attributes using functional dependencies.


2. Functional Dependency (FD)

A functional dependency is a relationship between attributes in a relation in which one attribute, or a set of attributes, determines the value of another attribute, or a set of attributes.

It is represented as:

\[
X \rightarrow Y
\]

Where:

  • (X) is called the determinant.
  • (Y) is the dependent attribute or set of dependent attributes.
  • The arrow means that (X) functionally determines (Y).

Formal Definition

A functional dependency \(X \rightarrow Y\) holds in a relation if, whenever two tuples have the same values for attributes (X), they must also have the same values for attributes (Y).

In simple words, if we know the value of (X), we can uniquely determine the value of (Y).

Example

Consider the following Student relation:

Student_ID Name Dept_ID
101 Aamir D01
102 Sara D02
103 Ali D01

Here, Student_ID uniquely identifies each student.

Therefore:

\[
Student_ID \rightarrow Name
\]

\[
Student_ID \rightarrow Dept_ID
\]

This means that knowing the Student_ID allows us to determine the student’s name and department.

However:

\[
Name \not\rightarrow Student_ID
\]

in general, because different students may have the same name.

Important: Functional dependencies are based on the meaning and rules of the data, not merely on the values currently appearing in a table.


3. Determinant and Dependent Attributes

In a functional dependency:

\[
X \rightarrow Y
\]

  • Determinant: The attribute or group of attributes on the left side, (X).
  • Dependent attributes: The attributes on the right side, (Y).

For example:

\[
Student_ID \rightarrow Name, Dept_ID
\]

Here, Student_ID is the determinant, while Name and Dept_ID are dependent attributes.

A determinant may contain a single attribute or multiple attributes.

For example:

\[
(Student_ID, Course_ID) \rightarrow Grade
\]

The combination of Student_ID and Course_ID determines the grade obtained by a student in a particular course.

Neither attribute alone may be sufficient to determine the grade.


4. Types of Functional Dependencies

A. Trivial Functional Dependency

A functional dependency is trivial if the attributes on the right side are already included in the attributes on the left side.

For example:

\[
(Student_ID, Name) \rightarrow Name
\]

This is trivial because Name is already part of the determinant.

More generally, (X \rightarrow Y) is trivial if:

\[
Y \subseteq X
\]

B. Non-Trivial Functional Dependency

A functional dependency is non-trivial if the right-side attributes are not a subset of the left-side attributes.

For example:

\[
Student_ID \rightarrow Name
\]

Here, Name is not included in Student_ID.

Therefore, it is a non-trivial functional dependency.

C. Completely Non-Trivial Functional Dependency

A functional dependency is completely non-trivial if the left and right sides have no attributes in common.

For example:

\[
Student_ID \rightarrow Department
\]

If Student_ID and Department are separate attributes, this is completely non-trivial.


5. Functional Dependency Rules

Functional dependencies follow certain rules that help us derive additional dependencies from existing ones.

These fundamental rules are called Armstrong’s Axioms.

1. Reflexivity

If (Y) is a subset of (X), then (X) determines (Y).

\[
Y \subseteq X \Rightarrow X \rightarrow Y
\]

Example:

\[
(Student_ID, Name) \rightarrow Student_ID
\]

2. Augmentation

If (X) determines (Y), adding the same attributes to both sides preserves the dependency.

If:

\[
X \rightarrow Y
\]

Then:

\[
XZ \rightarrow YZ
\]

Example:

If:

\[
Student_ID \rightarrow Name
\]

Then:

\[
(Student_ID, Dept_ID) \rightarrow (Name, Dept_ID)
\]

3. Transitivity

If (X) determines (Y), and (Y) determines (Z), then (X) also determines (Z).

If:

\[
X \rightarrow Y
\]

and:

\[
Y \rightarrow Z
\]

Then:

\[
X \rightarrow Z
\]

Example:

\[
Student_ID \rightarrow Dept_ID
\]

\[
Dept_ID \rightarrow Dept_Name
\]

Therefore:

\[
Student_ID \rightarrow Dept_Name
\]

This is called a transitive functional dependency.


6. Attribute Closure

Attribute Closure is the set of all attributes that can be functionally determined by a given set of attributes using the available functional dependencies.

It is represented as:

\[
X^+
\]

Where \(X^+\) means the closure of attribute set (X).

For example, if we have the functional dependencies:

\[
A \rightarrow B
\]

\[
B \rightarrow C
\]

Then:

\[
A^+ = {A,B,C}
\]

Because A determines B, and B determines C.

Why is Attribute Closure Important?

Attribute closure helps us:

  • Determine whether a set of attributes is a superkey.
  • Identify candidate keys.
  • Check whether a functional dependency is implied by a given set of dependencies.
  • Understand relationships between attributes.
  • Support database normalization.

7. How to Calculate Attribute Closure

To calculate the closure of an attribute set, follow these steps:

  1. Start with the given attribute set.
  2. Examine all functional dependencies.
  3. Whenever the attributes on the left side of a dependency are present in your closure, add the attributes on the right side.
  4. Repeat until no new attributes can be added.

Example

Consider the relation:

\[
R(Student_ID, Name, Dept_ID, Dept_Name)
\]

Given the following functional dependencies:

\[
F = \{
\begin{aligned}
Student\_ID &\rightarrow Name \\
Student\_ID &\rightarrow Dept\_ID \\
Dept\_ID &\rightarrow Dept\_Name
\end{aligned}
\}
\]

Find:

\[
Student\_ID^+
\]

Step 1: Start with the Given Attribute

\[
Student_ID^+ = {Student_ID}
\]

Step 2: Apply the Functional Dependencies

Since:

\[
Student_ID \rightarrow Name
\]

Add Name:

\[
Student_ID^+ =
{Student_ID, Name}
\]

Since:

\[
Student_ID \rightarrow Dept_ID
\]

Add Dept_ID:

\[
Student_ID^+ =
{Student_ID, Name, Dept_ID}
\]

Step 3: Apply the Dependencies Again

We now have Dept_ID in our closure.

Since:

\[
Dept_ID \rightarrow Dept_Name
\]

Add Dept_Name:

\[
Student_ID^+ =
{Student_ID, Name, Dept_ID, Dept_Name}
\]

Step 4: Stop

No further attributes can be added.

Therefore:

\[
\boxed{
Student_ID^+ =
{Student_ID, Name, Dept_ID, Dept_Name}
}
\]

The closure contains every attribute of relation R.

Hence, Student_ID is a superkey of this relation.


8. Finding the Closure of a Set of Attributes

Attribute closure can also be calculated for multiple attributes together.

Consider the functional dependencies:

\[
A \rightarrow C
\]

\[
B \rightarrow D
\]

\[
CD \rightarrow E
\]

Find:

\[
(AB)^+
\]

Step 1

Start with:

[
(AB)^+ = {A,B}
]

Step 2

Using \(A \rightarrow C\):

\[
(AB)^+ = {A,B,C}
\]

Step 3

Using \(B \rightarrow D\):

\[
(AB)^+ = {A,B,C,D}
\]

Step 4

Since C and D are both present, use:

\[
CD \rightarrow E
\]

Add E:

\[
(AB)^+ = {A,B,C,D,E}
\]

Therefore:

\[
\boxed{(AB)^+ = {A,B,C,D,E}}
\]

The combination AB determines all the attributes of this relation.


9. Using Closure to Test a Functional Dependency

Attribute closure can be used to determine whether a functional dependency is implied by a given set of dependencies.

Suppose we have:

\[
F = {A \rightarrow B,\ B \rightarrow C}
\]

We want to check whether:

\[
A \rightarrow C
\]

is implied by F.

First, calculate \(A^+\):

\[
A^+ = {A}
\]

Using \(A \rightarrow B\):

\[
A^+ = {A,B}
\]

Using \(B \rightarrow C\):

\[
A^+ = {A,B,C}
\]

Since C belongs to \(A^+\), the dependency \(A \rightarrow C\) is implied.

General Rule

A functional dependency (X \rightarrow Y) is implied by F if:

\[
Y \subseteq X^+
\]


10. Relationship Between Functional Dependencies, Closure and Keys

These three concepts are closely connected.

Concept Meaning
Functional Dependency Describes how attributes determine other attributes
Attribute Closure Finds all attributes determined by a given attribute set
Superkey An attribute set that determines every attribute in a relation
Candidate Key A minimal superkey

If the closure of an attribute set contains all attributes of a relation, that set is a superkey.

For example, if:

\[
R(A,B,C,D)
\]

and:

\[
A^+ = {A,B,C,D}
\]

then A is a superkey.

If no proper subset of A can determine all attributes, it is also a candidate key.

We will study the identification of candidate keys and superkeys in detail in the next article.


Article in a Nutshell

  • Functional dependency describes a relationship in which one attribute or a group of attributes determines another.
  • The left side of a dependency is the determinant.
  • Trivial dependencies have the right-side attributes contained in the left side.
  • Armstrong’s Axioms are Reflexivity, Augmentation and Transitivity.
  • Attribute Closure, \(X^+\), finds all attributes determined by X.
  • Closure can be used to test functional dependencies and identify superkeys.

Functional dependencies provide the foundation for identifying keys and understanding how relations should be structured. In the next article, we will use these concepts to study Candidate Keys, Superkeys and Key Identification.

Quick quiz

5 questions
What does the functional dependency \(A \rightarrow B\) mean?
Which of the following is a trivial functional dependency?
Given \(A \rightarrow B\) and \(B \rightarrow C\), which rule allows us to derive \(A \rightarrow C\)?
Given \(F = \{A \rightarrow B,\ B \rightarrow C\}\), what is \(A^+\)?
When can an attribute set X be considered a superkey of relation R?

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

Ask Farhan

Ask anything about Farhan