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?

Covers for functional dependencies - what is cover set

Cover set for functional dependencies - What is cover set? - What are the steps to find a cover set? - How would we say that a set of functional dependencies covers another set of functional dependencies? - Given 2 sets of functional dependencies F1 and F2, how to find F1 covers F2 or F2 covers F1? - Finding cover set of a functional dependency set

Covers for functional dependencies

Cover set

Given 2 sets of functional dependencies F and G, the set of functional dependencies F is the cover of the set of functional dependencies G if every functional dependency in the set G can be inferred (derived) from the functional dependencies in the set F.

Example 1:

Let R (A, B, C, D, E, F) is a relation with set of functional dependencies F = { A → BC, D → DF } and G = { A → B }.

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 → B of G can be inferred from the FD A → BC of F.

No more functional dependencies are there in G. 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.

No functional dependencies of F can be inferred from the FD A → B of G.

Hence, G does not cover F.

Example 2:

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 }.

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.

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?

 

Full partial transitive and multivalued function dependencies

Set of keywords about functional dependencies used in Normalization process / Set of functional dependencies that you need to know in Normalization process / Full functional dependency / Partial functional dependency/ Transitive Dependency / Multi-valued dependency / Functional dependencies in Normalization process / Define Full, partial, transitive, and multi-valued function dependencies

Various Types of Functional Dependencies used in Normalization Process 

Full Functional Dependency – Click here to read more… Definition 1: If X is a set of attributes and Y is another set of attributes, then any functional dependency such that X → Y is said to be a full functional dependency if and only if all the attributes of Y is functionally dependent on complete X. In other words, X → Y becomes invalid if we remove any attribute from X. Definition 2: A functional dependency X → Y is a full functional dependency if removal of any attribute from A results in the dependency no longer existing

Functional Dependency – Click to read more… Functional dependency is a constraint (condition) that describes the relationship between two sets of attributes. It is written as X → Y. it can be read as, the values of X determine the values of Y uniquely, or the values of Y are uniquely determined by the values of X, or Y is functionally dependent on X. Here, X is determinant, and Y is dependent.

Multi-valued Dependency– Click to read more…

Partial Dependency – Click to read more… It is a type of functional dependency where a non-key (non-prime) attribute is functionally dependent on a subset of the primary key (or candidate key) attribute. For example, we would say that a functional dependency XY → A as a partial functional dependency, if there exists other FDs like X → A or Y → A. In other words, removal of Y from X → A or removal of X from Y → A still holds the dependency.

Transitive Dependency – Click to read more… Dependency of a non-key attribute (or set of non-key attributes) on another non-key attribute (or set of non-key attributes) is called transitive dependency. For example, if X → Y and  Y → Z holds in a relation R(X, Y, Z), then these FDs imply X → Z (through transitivity axiom). Then X → Z is called transitive dependency.

Trivial Functional Dependency – Click to read more… The dependency of an attribute (or set of attributes) on a set of attributes is called trivial functional dependency if the set of attributes on the Left Hand Side (LHS) of the functional dependency contains RHS attributes. In other words, a functional dependency A → B is said to be trivial if B is subset or equal to A. Other examples are X → X, Y → Y, AB → AB etc.

Go back to NORMALIZATION keywords page