Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts

Partial Functional Dependency - Definition


Partial Functional Dependency - Definition / What is Partial dependency? / Example for partial key dependency / Partial key functional dependency - an overview

Partial Dependency


Partial Dependency is a form of Functional dependency that holds on a set of attributes. It is about the complete dependency of a right hand side attribute on one of the left hand side attributes. In a functional dependency XY Z, if Z (RHS attribute) can be uniquely identified by one of the LHS attributes, then the functional dependency is partial dependency.

Example:
Let us assume a relation R with attributes A, B, C, and D. Also, assume that the set of functional dependencies F that hold on R as follows;
F = {A B, D C}.
From set of attributes F, we can derive the primary key. For R, the key can be (A,D), a composite primary key. That means, AD BC, AD can uniquely identify B and C. But, for this case A and D is not required to identify B or C uniquely. To identify B, attribute A is enough. Likewise, to identify C, attribute D is enough. The functional dependencies AD B or AD C are called as Partial functional dependencies.


Go to Normalization - Solved Exercises page

Find minimal cover of set of functional dependencies Exercise

Find minimal cover of set of functional dependencies example, Solved exercise - how to find minimal cover of F? Easy steps to find minimal cover of FDs, What is minimal cover?

Question:
6. Find the minimal cover of the set of functional dependencies given; {A → C, AB → C, C → DI, CD → I, EC → AB, EI → C}

Solution:
Minimal cover:
Definition 1:
A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. There can be many such minimal covers for a set of functional dependencies F.
Definition 2:
A set of FDs F is minimum if F has as few FDs as any equivalent set of FDs.


Simple properties/steps of minimal cover:
1. Right Hand Side (RHS) of all FDs should be single attribute.
2. Remove extraneous attributes. [What is extraneous attribute? Refer here].
3. Eliminate redundant functional dependencies.

Let us apply these properties to F = {A → C, AB → C, C → DI, CD → I, EC → AB, EI → C}

1. Right Hand Side (RHS) of all FDs should be single attribute. So we write F as F1, as follows;
F1 = {A → C, AB → C, C → D, C → I, CD → I, EC → A, EC → B, EI → C}

2. Remove extraneous attributes.
Extraneous attribute is a redundant attribute on the LHS of the functional dependency. In the set of FDs, AB → C, CD → I, EC → A, EC → B, and EI → C have more than one attribute in the LHS. Hence, we check one of these LHS attributes are extraneous or not.
To check, we need to find the closure of each attribute on the LHS; [apply the closure finding algorithm – refer here]
(i) A+ = ACDI
(ii) B+ = B
(iii) C+ = CDI
(iv) D+ = D
(v) E+ = E
(vi) I+ = I
From (i), the closure of A included the attribute C. So, B is extraneous in AB → C, and B can be removed.
From (iii), the closure of C included the attribute I. So, D is extraneous in CD → I, and D can be removed.
No more extraneous attributes are found. Hence, we write F1 as F2 after removing extraneous attributes from F1 as follows;
F2 = {A → C, C → D, C → I, EC → A, EC → B, EI → C}

3. Eliminate redundant functional dependency.
None of the FDs in F2 is redundant. Hence, F2 is minimal cover.

Hence, set of functional dependencies F2 is the minimal cover for the set 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?




Go back to Question/QUIZ page














Find minimal cover of set of functional dependencies

Find minimal cover of set of functional dependencies example, Solved exercise - how to find minimal cover of F? Easy steps to find minimal cover of FDs, What is minimal cover?


Question:

5. Find the minimal cover of the set of functional dependencies given; {A → BC, B → C, AB → D}


Solution:
Minimal cover:
Definition 1:
A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. There can be many such minimal covers for a set of functional dependencies F.
Definition 2:
A set of FDs F is minimum if F has as few FDs as any equivalent set of FDs.


Simple properties/steps of minimal cover:
1. Right Hand Side (RHS) of all FDs should be single attribute.
2. Remove extraneous attributes. [What is extraneous attribute? Refer here].
3. Eliminate redundant functional dependencies.

Let us apply these properties to F = {A → BC, B → C, AB → D}
1. Right Hand Side (RHS) of all FDs should be single attribute. So we write F as F1, as follows;
F1 = {A → B, A → C, B → C, AB → D}
2. Remove extraneous attributes.
Extraneous attribute is a redundant attribute on the LHS of the functional dependency. In the set of FDs, on AB → D has more than one attribute in the LHS. Hence, we check one of A and B is extraneous or not.
First we check whether A is extraneous or not. To do that, we need to find the closure of the remaining attribute B with respect to F1.
B+ = BC.
This does not include D, so A is not extraneous.
Now we check whether B is extraneous or not. To do that, we need to find the closure of the remaining attribute A with respect to F1.
A+ = ABCD.
This includes D, so B is extraneous, ie., we can identify D without B on the LHS.
Now, we can write the new set of FDs, F2 as follows;
F2 = {A → B, A → C, B → C, A → D}
3. Eliminate redundant functional dependency.
If A → B, and B → C, then A → C is true (according to transitive rule). Hence, the FD A → C is redundant. We can eliminate this and we get final set of FDs F3 as follows;
F3 = {A → B, B → C, A → D}

The set of FDs F3 is the minimal cover of 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?




Go back to Question/QUIZ page











Equivalent sets of Functional dependencies

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


Question:
4. Let F1 = {A C, AC D, E AD} and F2 = {A CD, E AH}. Are F1 and F2 are equivalent?

Solution:
Equivalent sets of functional dependencies:
Two sets of FDs F and G over schema R are equivalent, if F+ = G+. That is, if every functional dependency of F is in G+ and every functional dependency of G is in F+, then we would say that the sets of functional dependencies F and G are equivalent. (here, F+ and G+ means the closure of sets of functional dependencies) - Further, refer here.

We first check if F1 F2+:
If we are able to find the closure for all the determinants of functional dependencies of F2, and if the derived closures are able to show the functional dependencies of F1, then we say that F1 F2+.
A+F2 = ACD.
That is, if you know A then you know ACD according to the FDs of F2. Hence, the functional dependency A C of F1 is in F2.
AC+F2 = ACD.
That is, if you know AC then you know ACD according to the FDs of F2. Hence, the functional dependency AC D of F1 is in F2.
E+F2 = ACDEH. (from E AH, A CD)
That is, if you know E then you know ACDEH according to the FDs of F2. Hence, the functional dependency E AD of F1 is in F2.
From this, we are able to derive all the FDs of F1 from F2+. Hence, F1 F2+ is TRUE.

We first check if F2 F1+:
We need to follow the above steps for this too;
A+F1 = ACD.
So, A CD of F2 is in F1.
E+F1 = ACDE.
So, E AH of F2 is not in F1.
We are not able to derive all the FDs of F2 from F. Hence, F2 F1+ is FALSE.

From the above, it is proved that F1 and F2 are not equivalent.


********************

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?




Go back to Question/QUIZ page








Wikipedia

Search results

Followers