Set of FDs are equivalent or not Exercise 11

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

Exercise:

Let F = {A → C, AC → D, E → AD}, and let G = {A → CD, E → AHE}. Are they equivalent?

Solution:

To check whether two sets of functional dependency are equivalent, we have to verify every functional dependency (FD) of F is in G⁺ and every FD of G is in F⁺.

Theorem: If F ⊆ G⁺ and G ⊆ F⁺, then F and G are equivalent.

To check for F ⊆ G⁺

Let us take the first FD of F, A → C and find the closure using FDs from G as follows;

• A⁺ = ACD through the FD A → CD of G. The result includes the RHS attribute of FD A → C. Hence, A → C is in G⁺.

Let us do the same for other FDs of F;

• AC⁺ = ACD through the FD A → CD of G. The result includes the RHS attribute of FD AC → D. Hence, AC → D is in G⁺.

• E⁺ = AHECD through the FDs E → AHE and A → CD of G. The result includes the RHS attribute of FD E → AD. Hence, E → AD is in G⁺.

As all the FDs of F can be derived using G, F ⊆ G⁺ is true.

To check for G ⊆ F⁺

• A⁺ = ACD through the FDs A → C and AC → D of F. The result includes the RHS attribute of FD A → CD. Hence, A → CD is in F⁺.

• E⁺ = ACDE through the FDs E → AD, A → C and AC → D of F. The result does not include the RHS attribute of FD E → AHE. Hence, E → AHE is in F⁺.

As all the FDs of G cannot be derived using F, G ⊆ F⁺ is false.

Result:

We found that F ⊆ G⁺ is true but not G ⊆ F⁺. Hence, the given set of functional dependencies F and G are not equivalent (F ≠ G).  

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

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

Go back to Online Quizzes home page

Functional dependencies and normalization solved multiple choice questions

Functional dependencies and normalization solved multiple choice questions

Functional Dependencies and Normalization MCQ with Answers

1. Consider relation R(A,B,C,D,E) with functional dependencies:

AB → C, C → D, BD → E

Which of the following attribute sets does not functionally determine E ?

a) AB

b) AC

c) BC

d) ABC

View Answer

Answer: (b) (AB)+ = ABCDE (BC)+ = BCDE (ABC)+ = ABCDE (AC)+ = AC Only the closure of AC does not include E in the result.

2. Let relation R(A,B,C,D) satisfy the following set of functional dependencies:

S₁ = {A → B, B → C, C → A}

A different set S₂ of functional dependencies is equivalent to S₁ if exactly the same FDs follow from S₁ and S₂. Which of the following sets of functional dependencies is equivalent to the set above? [Refer here: How to find whether two sets of FDs are equivalent to each other or not]

a) B → AC, C → AB

b) A → B, B → A, C → A

c) A → BC, C → AB

d) A → BC, B → AC, C → AB

View Answer

Answer: (d) Two sets of FDs are said to be equal if every FD of one of them can be inferred from the FDs of the other and vice versa. If the set of FDs of S2 can be inferred from FDs of S1, then we would say that S1 covers S2. We check this for the answer (d). The FD A → BC of S2 can be inferred from the FDs A → B and B → C of S1. The FD B → AC of S2 can be inferred from the FDs B → C and C → A of S1. The FD C → AB of S2 can be inferred from the FDs C → A and A → B of S1. If the set of FDs of S1 can be inferred from FDs of S2, then we would say that S2 covers S1. We check this for the answer (d). The FD A → B of S1 can be inferred from the FDs A → BC of S2. The FD B → C of S1 can be inferred from the FDs B → AC of S2. The FD C → A of S1 can be inferred from the FDs C → AB of S2. S1 covers S2 and S2 covers S1. Hence, we would say that S1 covers S2 and so they are equivalent.

3. Suppose relation R(A,B,C) has tuples (0,0,0) and (1,2,0) , and it satisfies the functional dependencies A → B and B → C . Which of the following tuples may be inserted into R legally?

a) (0,0,1)

b) (1,2,1)

c) (0,1,1)

d) (0,0,2)

View Answer

Answer: None are correct None of the options are correct. If the record (0,0,1) will be inserted, it will violate the FD B → C. because, alredy there exists a record with B value 0 and C value 0. Now we try to insert B value 0 and C value 1. Likewise, record (b) and (d) both will violate this FD. If the record (0,1,1) will be inserted, it will violate both FDs A → B and B → C.

4. Under what isolation level is the following schedule allowed?

R₃(b); R₁(b); W₃(p); R₂(b); R₁(p); R₁(c); W₂(c); W₁(c); R₃(c); R2(c); W₃(p); 

[Refer here: Transaction isolation level READ UNCOMMITTED]

a) Read uncommitted

b) Read committed

c) Repeatable read

d) Serializable

View Answer

Answer: (a) Given schedule; R3(b); R1(b); W3(p); R2(b); R1(p); R1(c); W2(c); W1(c); R3(c); R2(c); W3(p); In this schedule, transaction 1 reads a value (R1(p)) which was written by transaction 3 (W3(p)) before T3 commits. Hence, the read was a dirty read. The transaction isolation level that permits this type of read is READ UNCOMMITTED. [Other violating instructions also highlighted].  [Refer here: Transaction isolation level READ UNCOMMITTED]

5. Consider the following relational schema and set F of functional dependencies;

R(A,B,C,D,E,F,G), F = {E → C, G → AD, B → E, C → BF}. Which of the following is E⁺?

a) EC

b) ECG

c) BCEF

d) ABCEF

View Answer

Answer: (c) E+ is the closure of E. This can be calculated using the given FD.             E+       = EC from FD E → C                         = ECBF from FD C → BF                         = ECBF from FD B → E (no change) No more FDs with any of the attributes or combination of E, C, B, and F. Hence, closure finding algorithm stops here. [Refer here: How to find closure of a set of attributes here]

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

Related posts:

• Go to Multiple Choice Questions in DBMS home

• Go to Normalization - MCQs page

• Go to General Mixed Quiz in all topics of DBMS page

• Go to Advanced DBMS Concepts page

Quiz questions with answers on DBMS normalization

Solved quiz questions on functional dependencies and normalization process of database management systems

MCQ with answers on normalization process of DBMS

Normalization solved exercises in MCQs.

Normalization process multiple choice questions with answers

MCQ on Database Management Systems Normalization process, Normalization quiz on 1NF, 2NF, 3NF and BCNF

Normalization Quiz Questions with Answers

Consider the attribute set R = ABCDEGH and the FD set F = {AB → C, AC → B, AD → E, B → D, BC → A, E → G} to answer the following questions.

Q1. Which of the following relations if decomposed from R satisfies BCNF?

a) ABC

b) ABCD

c) ABCEG

d) None of the above

View Answer

Answer: (a) Let us say R1 = ABC. If decomposed from R, R1 will have the following set of functional dependencies F1; F1 = {AB → C, AC → B, BC → A} The candidate keys for R1 are AB, AC, and BC. As per rules governing BCNF, LHS of all the functional dependencies must be the candidate key which is true for R1. Hence, R1 in BCNF.

Q2. Which of the following relations if decomposed from R satisfies BCNF?

a) ABCD

b) ABCEG

c) AECH

d) None of the above

View Answer

Answer: (c) Let us say R1 = AECH. If decomposed from R, R1 will have no functional dependencies. Hence, the key for R1 is AECH itself. So, R1 is in BCNF.

Q3. Which of the following relations if decomposed from R does not satisfy 2NF?

a) ABC

b) AB

c) ABCEG

d) All of the above

View Answer

Answer: (c) Let us say R1 = ABCEG. If decomposed from R, R1 will have the following set of functional dependencies F1; F1 = { AB → C, AC → B, BC → A, E → G} Candidate keys;             (AB)+ = ABC ≠ R1             (AC)+ = ACB ≠ R1             (BC)+ = BCA ≠ R1             (ABE)+ = ABCEG = R1. Likewise, (ACE)+ = (BCE)+ = R. Hence, candidate keys are ABE, ACE, and BCE. As per the rules of 2NF, there shouldn’t be any partial key dependencies. But, in R1, the FD E → G is a partial key dependency. That is, E is not a candidate key but a key attribute. And E alone determines another non-key attribute G uniquely (the FD E → G). Hence, R1(ABCEG) is not in 2NF.

Q4. Let us suppose that R₁ = DCEGH is a relation which is decomposed from R satisfies the set F of functional dependencies F= {E → G}. What is the strongest normal form currently R₁ is in?

a) 1NF

b) 2NF

c) 3NF

d) BCNF

View Answer

Answer: (a) The key is DCEH. R1 is not in BCNF because E on the LHS of FD E → G is not a candidate key. R1 is not in 3NF and not even in 2NF because the FD E → G is a partial key dependency. Hence, R1 is in 1NF.

Q5. If R₁ = ABCD is decomposed from R, which of the following decomposition of R₁ satisfies BCNF?

a) R₁₁(AB), R₁₂(CD)

b) R₁₁(ABC), R₁₂(BD)

c) R₁₁(AC), R₁₂(BD)

d) R₁₁(BCD), R₁₂(AB)

View Answer

Answer: (b) If R1(ABCD) is decomposed from R, then the set of functional dependencies holds by R1 is as follows; F1 = { AB → C, AC → B, B → D, BC → A } We can take, for instance, the first FD AB → C to find the closure. The closure of AB = ABC. So, we can create a separate table R11(ABC) with the first FD. The remaining is the FD B → D, and B+ is BD. This can go as R12(BD). Hence, the decomposition results in R11(ABC), R12(BD)

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

Related posts:

• Go to Multiple Choice Questions in DBMS home

• Go to Normalization - MCQs page

• Go to General Mixed Quiz in all topics of DBMS page

• Go to Advanced DBMS Concepts page

Quiz questions with answers on DBMS normalization

Sample quiz questions on normalization process of database management systems

MCQ with answers on normalization process of DBMS

Normalization solved exercises in MCQs.