Equivalence of Functional Dependencies

# Equivalence of Functional Dependencies Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)

## Document Description: Equivalence of Functional Dependencies for Computer Science Engineering (CSE) 2022 is part of Database Design (Integrity Constraints, Normalization) for Database Management System (DBMS) preparation. The notes and questions for Equivalence of Functional Dependencies have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Equivalence of Functional Dependencies covers topics like Introduction and Equivalence of Functional Dependencies Example, for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Equivalence of Functional Dependencies.

Introduction of Equivalence of Functional Dependencies in English is available as part of our Database Management System (DBMS) for Computer Science Engineering (CSE) & Equivalence of Functional Dependencies in Hindi for Database Management System (DBMS) course. Download more important topics related with Database Design (Integrity Constraints, Normalization), notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Equivalence of Functional Dependencies Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE)
 1 Crore+ students have signed up on EduRev. Have you?

Introduction

Given a Relation with different FD sets for that relation, we have to find out whether one FD set is subset of other or both are equal.

How to find relationship between two FD sets?

Let FD1 and FD2 are two FD sets for a relation R.

1. If all FDs of FD1 can be derived from FDs present in FD2, we can say that FD2 ⊃ FD1.
2. If all FDs of FD2 can be derived from FDs present in FD1, we can say that FD1 ⊃ FD2.
3. If 1 and 2 both are true, FD1 = FD2.

All these three cases can be shown using Venn diagram as: Q. Let us take an example to show the relationship between two FD sets. A relation R(A, B, C, D) having two FD sets FD1 = {A -> B, B -> C, AB -> D} and FD2 = {A -> B, B -> C, A -> C, A -> D}
Step 1: Checking whether all FDs of FD1 are present in FD2

• A -> B in set FD1 is present in set FD2.
• B -> C in set FD1 is also present in set FD2.
• AB -> D in present in set FD1 but not directly in FD2 but we will check whether we can derive it or not. For set FD2, (AB)+ = {A, B, C, D}. It means that AB can functionally determine A, B, C and D. So AB -> D will also hold in set FD2.

As all FDs in set FD1 also hold in set FD2, FD2 ⊃ FD1 is true.

Step 2: Checking whether all FDs of FD2 are present in FD1

• A -> B in set FD2 is present in set FD1.
• B -> C in set FD2 is also present in set FD1.
• A -> C is present in FD2 but not directly in FD1 but we will check whether we can derive it or not. For set FD1, (A)+ = {A,B,C,D}. It means that A can functionally determine A, B, C and D. SO A -> C will also hold in set FD1.
• A -> D is present in FD2 but not directly in FD1 but we will check whether we can derive it or not. For set FD1, (A)+ = {A, B, C, D}. It means that A can functionally determine A, B, C and D. SO A -> D will also hold in set FD1.

As all FDs in set FD2 also hold in set FD1, FD1 ⊃ FD2 is true.
Step 3: As FD2 ⊃ FD1 and FD1 ⊃ FD2 both are true FD2 = FD1 is true. These two FD sets are semantically equivalent.

Q. Let us take another example to show the relationship between two FD sets. A relation R2(A, B, C, D) having two FD sets FD1 = {A -> B, B -> C,A -> C} and FD2 = {A -> B, B -> C, A -> D}

Step 1: Checking whether all FDs of FD1 are present in FD2

• A -> B in set FD1 is present in set FD2.
• B -> C in set FD1 is also present in set FD2.
• A -> C is present in FD1 but not directly in FD2 but we will check whether we can derive it or not. For set FD2, (A)+ = {A, B, C, D}. It means that A can functionally determine A, B, C and D. SO A -> C will also hold in set FD2.

As all FDs in set FD1 also hold in set FD2, FD2 ⊃ FD1 is true.

Step 2: Checking whether all FDs of FD2 are present in FD1

• A -> B in set FD2 is present in set FD1.
• B -> C in set FD2 is also present in set FD1.
• A -> D is present in FD2 but not directly in FD1 but we will check whether we can derive it or not. For set FD1, (A)+ = {A, B, C}. It means that A can’t functionally determine D. SO A -> D will not hold in FD1.

As all FDs in set FD2 do not hold in set FD1, FD2 ⊄ FD1.

Step 3: In this case, FD2 ⊃ FD1 and FD2 ⊄ FD1, these two FD sets are not semantically equivalent.

Armstrong’s Axioms in Functional Dependency in DBMS

The term Armstrong axioms refer to the sound and complete set of inference rules or axioms, introduced by William W. Armstrong, that is used to test the logical implication of functional dependencies. If F is a set of functional dependencies then the closure of F, denoted as F^+, is the set of all functional dependencies logically implied by F. Armstrong’s Axioms are a set of rules, that when applied repeatedly, generates a closure of functional dependencies.

Axioms
1. Axiom of reflexivity: If A is a set of attributes and B is subset of C, then C holds B. If B ⊆ A then A → B  This property is trivial property.
2. Axiom of augmentation: If A → B holds and Y is attribute set, then AY → BY also holds. That is adding attributes in dependencies, does not change the basic dependencies. If A → B, then AC → BC for any C.
3. Axiom of transitivity: Same as the transitive rule in algebra, if A → B holds and → C holds, then A → C also holds. A → B is called as A functionally that determines B. If  → Y and Y → Z, then → Z.
Secondary Rules

These rules can be derived from the above axioms.

1. Union: If A → B holds and A → C holds, then A → BC holds. If X → Y and → Z then → YZ
2. Composition: If → B and → Y holds, then A→ BY holds.
3. Decomposition: If → BC holds then → B and → C hold. If → YZ then → Y and → Z
4. Pseudo Transitivity: If A → B holds and BC → D holds, then AC → D holds. If → Y and YZ → W then XZ → W.

Why armstrong axioms refer to the Sound and Complete?
By sound, we mean that given a set of functional dependencies F specified on a relation schema R, any dependency that we can infer from F by using the primry rules of amrmstrong axioms holds in every relation state r of R that satisfies the dependencies in F.
By complete, we mean that using primary rules of amrstrong axioms repeatedly to infer dependencies until no more dependencies can be inferred results in the complete set of all possible dependencies that can be inferred from F.

The document Equivalence of Functional Dependencies Notes | Study Database Management System (DBMS) - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Database Management System (DBMS).
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

## Database Management System (DBMS)

1 videos|49 docs|15 tests
 Use Code STAYHOME200 and get INR 200 additional OFF

## Database Management System (DBMS)

1 videos|49 docs|15 tests

Track your progress, build streaks, highlight & save important lessons and more!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;