Functional Dependencies in DBMS

Definition of Functional Dependency

A functional dependency (FD) is a constraint between two sets of attributes in a relation. It describes a relationship where a particular attribute (or a set of attributes) uniquely determines another attribute.

Notation: If A → B, it means that if two tuples have the same value for A, they must have the same value for B.

Types of Functional Dependencies

1. Trivial Functional Dependency

A functional dependency is **trivial** if the right-hand side is a subset of the left-hand side.

Example: {A, B} → A (Here, A is already part of {A, B}, making it trivial).

2. Non-Trivial Functional Dependency

If the right-hand side is not a subset of the left-hand side, the FD is **non-trivial**.

Example: A → B (Here, B is not part of A).

3. Completely Non-Trivial Functional Dependency

An FD is **completely non-trivial** if the left and right sides have no attributes in common.

Example: A → B, where A and B are distinct attributes.

Closure of Attributes

The **closure of a set of attributes** (denoted as A+) is the set of all attributes that can be functionally determined by A.

Steps to Find Closure:

  1. Start with A+ = A.
  2. Apply the given functional dependencies iteratively.
  3. Stop when no more attributes can be added.

Finding Candidate Keys

A **candidate key** is the minimal set of attributes that uniquely identify a tuple in a relation.

Steps to Find Candidate Keys:

Concept Description
Trivial FD Right-hand side is a subset of the left-hand side (A, B → A).
Non-Trivial FD Right-hand side is not a subset of the left-hand side (A → B).
Completely Non-Trivial FD Left and right sides have no common attributes (A → B, A ≠ B).
Closure of Attributes Set of attributes functionally determined by a given attribute.
Candidate Key Minimal set of attributes that uniquely identify a row.

Closure of a Set in DBMS

Closure of a Set in DBMS

In Database Management Systems (DBMS), the closure of a set of attributes is the set of all attributes that can be functionally determined from that set using the given functional dependencies.

Definition

The closure of an attribute set X, denoted as X⁺, is the set of all attributes that can be derived from X using the functional dependencies (FDs) of a relation.

How to Compute Attribute Closure?

  1. Start with X⁺ = X (initially include all attributes in X).
  2. Iterate over the given set of FDs:
  3. Repeat until no more attributes can be added.

Why is Attribute Closure Required?

Purpose Explanation
To Check Superkey A set of attributes X is a superkey if its closure X⁺ contains all attributes of the relation.
To Find Candidate Keys Candidate keys are minimal superkeys. Compute X⁺ for different attribute sets to determine the smallest set that can determine all attributes.
To Verify Functional Dependencies If X⁺ contains Y, then X → Y is a valid functional dependency.
To Determine Closure of Functional Dependencies Used to check if a given set of FDs covers all possible dependencies.

Example

Given Relation: R(A, B, C, D, E)

Functional Dependencies:

Find Closure of {A}:

Since A⁺ contains all attributes of R, A is a superkey.

Conclusion