# Equivalence of Functional Dependencies | DBMS

In this tutorial, we are going to learn about the **equivalence of functional dependencies in database management system**.

Submitted by Anushree Goswami, on September 01, 2019

**Equivalence of Functional dependencies** states that, if the relations of different Functional dependencies sets are given, then we have to find out whether one Functional dependency set is a subset of other given set or both the sets are equal.

To find out whether one Functional dependency set is a subset of other given set or both the sets are equal.

Suppose **R1** and **R2** are two Functional dependencies sets for a relation **R**.

- If all Functional dependencies of R1 can be derived from Functional dependencies present in
**R2**, we can say that**R2**is a subset of**R1 (R2 ⊃ R1)**. - If all Functional dependencies of R2 can be derived from Functional dependencies present in
**R1**, we can say that**R1**is a subset of**R2 (R1 ⊃ R2)**. - If
**1**and**2**both are satisfied, then**R1 = R2**.

### Case 1) Determining Whether R2 ⊃ R1 or not

Steps are followed to determine whether R2 is a subset of R1 (R2 ⊃ R1) or not,

**Step 1)**

- Take into consideration, the functional dependencies of set R1.
- For every functional dependency P→ Q, find by using the functional dependencies of set R1, the closure of P.

**Step 2)**

- Take into consideration, the functional dependencies of set R2.
- For every functional dependency P→ Q, find by using the functional dependencies of set R2, the closure of P.

**Step 3)**

- Compare the results of Step 1 and Step 2.
- If the functional dependency of set R2 has determined all those attributes that were determined by the functional dependencies of set R1, then it means R2 ⊃ R1.
- Thus, we conclude R2 is a subset of R1 (R2 ⊃ R1) otherwise not.

### Case 2) Determining Whether R1 ⊃ R2 or not

Steps are followed to determine whether R1 is a subset of R2 (R1 ⊃ R2),

**Step 1)**

- Take into consideration the functional dependencies of set R2.
- For every functional dependency P → Q, find by using the functional dependencies of set R2, the closure of P.

**Step 2)**

- Take into consideration the functional dependencies of set R1.
- For every functional dependency P → Q, find by using the functional dependencies of set R1, the closure of P.

**Step 3)**

- Compare the results of Step 1 and Step 2.
- If the functional dependency of set R1 has determined all those attributes that were determined by the functional dependencies of set R2, then it means R1 ⊃ R2.
- Thus, we conclude that R1 is a subset of R2 (R1 ⊃ R2) otherwise not.

### Case 3) Determining Whether Both R1 and R2 satisfy each other or not

- If R2 is a subset of R1 and R1 is a subset of R2, then both R1 and R2 satisfied each other.
- Thus, if both the above cases satisfied, we conclude that R1 = R2.

## Example based on Equivalence of Functional Dependencies

**Q)** A relation R (P, Q, U, S, and T) is having two functional dependencies sets R1 and R2, which is shown as

Set R1: Set R2: P → C P → QU PQ → U S → PT S → T

**Solution...**

**Case 1) Determining Whether R2 ⊃ R1 or not**

**Step 1)**

- (P)+ = {P, Q, U} // closure of left side of P → QU using set R1.
- (S)+ = {P, Q, U, S, T} // closure of left side of S → PT using set R1.

**Step 2)**

- (P)+ = {P, Q, U} // closure of left side of P → QU using set R2.
- (S)+ = {P, Q, U, S, T} // closure of left side of S → PT using set R2.

**Step 3)**

Comparing the results of Step 1 and Step 2, we find,

- Functional dependencies of set R2 can determine all the attributes which have been determined by the functional dependencies of set R1.
- Thus, we conclude R2 is a subset of R1 i.e. R2 ⊃ R1.

**Case 2) Determining Whether R1 ⊃ R2 or not**

**Step 1)**

- (P)
^{+}= {P, Q, U} // closure of left side of P→ Q using set R2. - (PQ)
^{+}= {P, Q, U} // closure of left side of PQ → U using set R2. - (S)
^{+}= {P, Q, U, S, T} // closure of left side of S → PU and S → T using set R2.

**Step 2)**

- (P)
^{+}= {P, Q, U} // closure of left side of P→ Q using set R1. - (PQ)
^{+}= {P, Q, U} // closure of left side of PQ → U using set R1. - (S)
^{+}= {P, Q, U, S, T} // closure of left side of S → PU and S → T using set R1.

**Step 3)**

Comparing the results of Step 1 and Step 2, we find,

- Functional dependencies of set R1 can determine all the attributes which have been determined by the functional dependencies of set R2.
- Thus, we conclude R1 is a subset of R2 i.e. R1 ⊃ R2.

**Case 3) Determining Whether Both R1 and R2 satisfy each other or not**

- From Step 1, we conclude R2 ⊃ R1.
- From Step 2, we conclude R1 ⊃ R2.
- Thus, we conclude that both R1 and R2 satisfied each other i.e. R1 = R2.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.