Advanced Database Management System - Tutorials and Notes: How to prove that two sets of functional dependencies are equal or not

Saturday, 13 February 2016

How to prove that two sets of functional dependencies are equal or not

How to prove that two sets of functional dependencies are equal or not - Proving equality of two sets of functional dependencies - How to find whether two sets of functional dependencies are equal or not? - Equivalent sets of functional dependencies



How to find whether two sets of functional dependencies are equal or not?


Let F and G be two different sets of functional dependencies holding on a relation R. These two functional dependencies are called equivalent if F+ = G+, i.e., if closure of the set F is equal to the closure of set G.

In other words,
Two sets of functional dependencies F and G are said to be equal if;

  • Every FD in G can be inferred (derived) from the functional dependencies in F, and
  • Every FD in F can be inferred (derived) from the functional dependencies in G.

Alternative definition;
Two sets of functional dependencies F and G are said to be equal if;

  • F can cover G, and
  • G can cover F.

Example:

Let R (A, B, C, D, E) be a relation with set of functional dependencies F = { A BC, A D, CD E } and G = { A BCE, A ABD, CD E }. Is F = G?

Does F cover G?
If set of FDs of G can be inferred from F, then we would say that F covers G.
The FD A BCE of G can be inferred from the FDs A BC, A D, and CD E of F. [here, A gives BCD. If you know C and D then E can be derived]
The FD A ABD of G can be inferred from the FDs A BC, and A D of F.
The FD CD E of G can be inferred from the FD CD E of F.
All the three FDs of G can be inferred from FDs of F. Hence, F covers G.

Does G cover F?
If set of FDs of F can be inferred from G, then we would say that G covers F.
The FD A BC of F can be inferred from the FD A BCE of G.
The FD A D of F can be inferred from the FD A ABD of G.
The FD CD E of F can be inferred from the FD CD E of G.
All the three FDs of F can be inferred from FDs of G. Hence, G covers F.
Hence, we would say F is equivalent to G.


Similar topics

How to find closure of set of functional dependencies?

How to find closure of attributes?

How to find canonical cover for a set of functional dependencies?

How to find extraneous attribute?





No comments:

Post a comment

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents