Functional Dependencies
Below you can find some of the best tutorials or videos on Functional Dependencies. Also find below few examples on Functional Dependencies.
1. Lecture on Functional Dependencies and Normal Form.
2. An assignment about Functional Dependencies is being discussed by Philippe Bonnet(Highly Recommended).
3. Use Functional Dependencies to determine keys, good examples on prime, non-prime, closure etc.
4. Excellent document explaining Functional Dependency.
5. Functional Dependency problems & examples.
6. This PPT has a good closure example.
7. Good examples for closure computation.
8. Normalisation & Functional Dependency.
9. Functional Dependencies & problems.
10. This PDF includes Questions and Answers related to Functional Dependency & Normalization.
Example 1 of Functional Dependency
Consider a relation with schema R(A,B,C,D) and FDs
AC → B,
B → A,
BD → C and
D → A
a)Describe the concept of Functional Dependency and Dependency-preserving decomposition.
ANSWER:
Functional dependency can be thought of as a generalization of the idea of a key for a relation. It states that if 2 tuples of a relation agrees on the attributes A1A2…An, then they must also agree on attributes B1B2…Bn, written A1A2…An -> B1B2…Bn. Simply put, it means attributes A1A2…An functionally determines attributes B1B2…Bn.
Dependency-preserving decomposition is a decomposition of a relation R into R1, R2…,Rn according to some FD where all FDs that hold on R also hold on all "sub-relations" R1, R2…,Rn.
b) Find the closures for subsets A, BD and BC respectively.
ANSWER:
{A}+ = {A}
{BD}+ = {ABCD}
{BC}+ = {ABC}
c) List all nontrivial FDʻs that follow from the given FDʻs.
ANS: BD -> A, CD -> A, CD -> B, CD -> AB, ABD -> C, BCD -> A, ACD -> B,BC -> A, BD -> AC
d) Find all the candidate keys for this relation (you donʻt need to list superkeys that are not keys). Explain your answer.
ANSWER: BD, CD since {B,D} and {C,D} are both minimal set of attributes
whose closure contains all attributes {A,B,C,D,E}. [Via]
Example 2 of Functional Dependency
Consider a relation with schema R(A,B,C,D) and FD's
A -> C;
BC -> D,
D -> C and
AD -> B.
1. Find the closure of the following:
(A)
(A,D)
(B,C)
2. List all nontrivial FD's that follow from the given FD's. (As an example, if we had the relation S(X, Y, Z) and FD's X -> Y, Y -> Z then a nontrivial FD that would follow is (X -> Y, Y -> Z) => X -> Z where => means "implies". List only the implied FD's with a single attribute on the right side and the minimal set of attributes on the left side. In our toy example, XY -> Z is therefore not a correct answer, as the left hand side does not have a minimal number of attributes)
3. What are all the (minimal) keys? Explain your answer.
4. What are all the superkeys of R that are not (minimal) keys?
Solution
1. Closures:
A: (A,C)
AD: (A,D,B,C)
BC: (B,C,D)
2. (A->C, BC->D) => AB->D
3. Closure of AD is ADBC, A is not a key, and D is not a key, therefore AD is a key. Also, closure of AB is ABCD, and B is not a key, so AB is also a key.
4. Superkeys which are not minimal keys: ADB, ADC, ABC, ADBC.[Via]
Example 3 of Functional Dependency
Suppose that we decompose the schema R = (A, B, C, D, E) into
(A, B, C)
(A, D, E)
Show that this decomposition is a lossless-join decomposition if the following set F of functional dependencies holds:
A → BC
CD → E
B → D
E → A
Answer: A decomposition {R1, R2} is a lossless-join decomposition if
R1 ∩ R2 → R1 or R1 ∩ R2 → R2.
Let R1 = (A, B, C), R2 = (A, D, E),
R1 ∩ R2 = A.
Since A is a candidate key (see below) , Therefore R1 ∩ R2 → R1.
Starting with A → BC, we can conclude: A → B and A → C.
Since A → B and B → D, A → D (decomposition, transitive)
Since A → CD and CD → E, A → E (union, decomposition, transitive)
Since A → A, (reflexive)
A → ABCDE from the above steps (union)
Example 4 of Functional Dependency
List all functional dependencies satisfied by the below relation.
Answer: The nontrivial functional dependencies are: A → B and C → B, and a dependency they logically imply: AC → B. There are other trivial FDs such as AB → B etc.
Example 5 of Functional Dependency
Compute the closure of the following set F of functional dependencies for relation schema R = (A, B, C, D, E).
A →BC
CD →E
B → D
E → A
List the candidate keys for R.
Answer: Starting with A → BC, we can conclude: A → B and A → C.
Since A → B and B → D, A → D (decomposition, transitive)
Since A → CD and CD → E, A → E (union, decomposition, transitive)
Since A → A, we have (reflexive)
A → ABCDE from the above steps (union)
Since E → A, E → ABCDE (transitive)
Since CD → E, CD → ABCDE (transitive)
Since B → D and BC → CD, BC → ABCDE (augmentative, transitive)
Also, C → C, D → D, BD → D, etc.
The candidate keys are therefore A, BC, CD, and E.
Therefore, any functional dependency with A, E, BC, or CD on the left hand side of the arrow is in F+, no matter which other attributes appear in the FD.
Allow * to represent any set of attributes in R, then F+ is BD → B, BD → D, C → C, D → D, BD → BD, B → D, B → B, B → BD, and all FDs of the form A∗ → α, BC ∗ → α, CD∗ → α, E∗ → α where α is any subset of {A, B, C, D, E}.
[Via]
Below you can find some of the best tutorials or videos on Functional Dependencies. Also find below few examples on Functional Dependencies.
1. Lecture on Functional Dependencies and Normal Form.
2. An assignment about Functional Dependencies is being discussed by Philippe Bonnet(Highly Recommended).
3. Use Functional Dependencies to determine keys, good examples on prime, non-prime, closure etc.
4. Excellent document explaining Functional Dependency.
5. Functional Dependency problems & examples.
6. This PPT has a good closure example.
7. Good examples for closure computation.
8. Normalisation & Functional Dependency.
9. Functional Dependencies & problems.
10. This PDF includes Questions and Answers related to Functional Dependency & Normalization.
Example 1 of Functional Dependency
Consider a relation with schema R(A,B,C,D) and FDs
AC → B,
B → A,
BD → C and
D → A
a)Describe the concept of Functional Dependency and Dependency-preserving decomposition.
ANSWER:
Functional dependency can be thought of as a generalization of the idea of a key for a relation. It states that if 2 tuples of a relation agrees on the attributes A1A2…An, then they must also agree on attributes B1B2…Bn, written A1A2…An -> B1B2…Bn. Simply put, it means attributes A1A2…An functionally determines attributes B1B2…Bn.
Dependency-preserving decomposition is a decomposition of a relation R into R1, R2…,Rn according to some FD where all FDs that hold on R also hold on all "sub-relations" R1, R2…,Rn.
b) Find the closures for subsets A, BD and BC respectively.
ANSWER:
{A}+ = {A}
{BD}+ = {ABCD}
{BC}+ = {ABC}
c) List all nontrivial FDʻs that follow from the given FDʻs.
ANS: BD -> A, CD -> A, CD -> B, CD -> AB, ABD -> C, BCD -> A, ACD -> B,BC -> A, BD -> AC
d) Find all the candidate keys for this relation (you donʻt need to list superkeys that are not keys). Explain your answer.
ANSWER: BD, CD since {B,D} and {C,D} are both minimal set of attributes
whose closure contains all attributes {A,B,C,D,E}. [Via]
Example 2 of Functional Dependency
Consider a relation with schema R(A,B,C,D) and FD's
A -> C;
BC -> D,
D -> C and
AD -> B.
1. Find the closure of the following:
(A)
(A,D)
(B,C)
2. List all nontrivial FD's that follow from the given FD's. (As an example, if we had the relation S(X, Y, Z) and FD's X -> Y, Y -> Z then a nontrivial FD that would follow is (X -> Y, Y -> Z) => X -> Z where => means "implies". List only the implied FD's with a single attribute on the right side and the minimal set of attributes on the left side. In our toy example, XY -> Z is therefore not a correct answer, as the left hand side does not have a minimal number of attributes)
3. What are all the (minimal) keys? Explain your answer.
4. What are all the superkeys of R that are not (minimal) keys?
Solution
1. Closures:
A: (A,C)
AD: (A,D,B,C)
BC: (B,C,D)
2. (A->C, BC->D) => AB->D
3. Closure of AD is ADBC, A is not a key, and D is not a key, therefore AD is a key. Also, closure of AB is ABCD, and B is not a key, so AB is also a key.
4. Superkeys which are not minimal keys: ADB, ADC, ABC, ADBC.[Via]
Example 3 of Functional Dependency
Suppose that we decompose the schema R = (A, B, C, D, E) into
(A, B, C)
(A, D, E)
Show that this decomposition is a lossless-join decomposition if the following set F of functional dependencies holds:
A → BC
CD → E
B → D
E → A
Answer: A decomposition {R1, R2} is a lossless-join decomposition if
R1 ∩ R2 → R1 or R1 ∩ R2 → R2.
Let R1 = (A, B, C), R2 = (A, D, E),
R1 ∩ R2 = A.
Since A is a candidate key (see below) , Therefore R1 ∩ R2 → R1.
Starting with A → BC, we can conclude: A → B and A → C.
Since A → B and B → D, A → D (decomposition, transitive)
Since A → CD and CD → E, A → E (union, decomposition, transitive)
Since A → A, (reflexive)
A → ABCDE from the above steps (union)
Example 4 of Functional Dependency
List all functional dependencies satisfied by the below relation.
| A | B | C |
|---|---|---|
| a1 | b1 | c1 |
| a1 | b1 | c2 |
| a2 | b1 | c1 |
| a2 | b1 | c3 |
Answer: The nontrivial functional dependencies are: A → B and C → B, and a dependency they logically imply: AC → B. There are other trivial FDs such as AB → B etc.
Example 5 of Functional Dependency
Compute the closure of the following set F of functional dependencies for relation schema R = (A, B, C, D, E).
A →BC
CD →E
B → D
E → A
List the candidate keys for R.
Answer: Starting with A → BC, we can conclude: A → B and A → C.
Since A → B and B → D, A → D (decomposition, transitive)
Since A → CD and CD → E, A → E (union, decomposition, transitive)
Since A → A, we have (reflexive)
A → ABCDE from the above steps (union)
Since E → A, E → ABCDE (transitive)
Since CD → E, CD → ABCDE (transitive)
Since B → D and BC → CD, BC → ABCDE (augmentative, transitive)
Also, C → C, D → D, BD → D, etc.
The candidate keys are therefore A, BC, CD, and E.
Therefore, any functional dependency with A, E, BC, or CD on the left hand side of the arrow is in F+, no matter which other attributes appear in the FD.
Allow * to represent any set of attributes in R, then F+ is BD → B, BD → D, C → C, D → D, BD → BD, B → D, B → B, B → BD, and all FDs of the form A∗ → α, BC ∗ → α, CD∗ → α, E∗ → α where α is any subset of {A, B, C, D, E}.
No comments:
Post a Comment