Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts

## 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

 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:
S1 = {A → B, B → C, C → A}
A different set S2 of functional dependencies is equivalent to S1 if exactly the same FDs follow from S1 and S2. 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

 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)

 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?
R3(b); R1(b); W3(p); R2(b); R1(p); R1(c); W2(c); W1(c); R3(c); R2(c); W3(p);

d) Serializable

 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

 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:

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

## 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

 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

 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

 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 R1 = 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 R1 is in?
a) 1NF
b) 2NF
c) 3NF
d) BCNF

 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 R1 = ABCD is decomposed from R, which of the following decomposition of R1 satisfies BCNF?
a) R11(AB), R12(CD)
b) R11(ABC), R12(BD)
c) R11(AC), R12(BD)
d) R11(BCD), R12(AB)

 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:

# Sample quiz questions on normalization process of database management systems

## Finding candidate keys in a relational table - Solved exercise

Question:
Given the following relation R and the set of functional dependencies F that hold on R, find all candidate keys for R.
R (A, B, C, D, E, F)
F = {AB → C, AC → B, AD → E, BC → A, E → F}

Solution:
Let us follow the steps given in the box below to find all the candidate keys of R.
 Step 1: Let γ = set of attributes not present in the RHS of any FD. The set of attributes in γ must be a part of any candidate key of R. Step 2: Let β = set of attributes appear on RHS but not on LHS of any FD. The set of attributes in β cannot be a part of any candidate key of R. Step 3: Find closure γ+. if γ+ = R, then γ  is the only candidate key Step 4: If γ+ ≠ R, then for each attribute x in R- β, ·        Test whether γ U {x} is a candidate key. ·        If not, add another attribute from R- β to γ and test whether it is a candidate key ·        Repeat this step until all candidate keys found

Given,
R (A, B, C, D, E, F) and F = {AB → C, AC → B, AD → E, BC → A, E → F}
Step 1: Find the set γ of attributes that are not present in the RHS of any functional dependency.
D is the only attribute that is not present in RHS of any of the functional dependencies. Hence, the candidate key(s) must have the attribute D.
γ = {D}
Step 2: Find the attributes that appear on RHS but not on LHS of any FD.
F is the only attribute that appear on RHS but not on LHS. Hence, F cannot be part of any candidate keys of R.
β = {F}
Step 3: Find closure of γ, ie., γ+
γ+ = D+ =
γ+ ≠ R, hence we move on to step 4.
Step 4: Find R- β and combine each attribute from this set with D and find the closures.
R- β = {A, B, C, D, E, F} – {F} = { A, B, C, D, E}
Let’s combine D with each of the element from the above set to test for candidate keys. Keep in mind that our candidate keys must consist of D in it but not F. Let us do one by one as follows;
= ADEF from FD E → F
≠ R.
Hence, AD is not a candidate key. We try the others the same way.
(BD)+ = BD ≠ R.
(CD)+ = CD ≠ R.
(DE)+ = DEF ≠ R.
Now let us add one more attribute to check for candidate keys;
(ABD)+ = ABDCEF = R. Hence, (ABD) is a candidate key.
(ACD)+ = ACDBEF = R. Hence, (ACD) is a candidate key.
(AED)+ = AEDF ≠ R.
(BCD)+ = BCDAEF = R. Hence, (BCD) is a candidate key.
(BED)+ = BEDF ≠ R.
(CED)+ = CEDF ≠ R.
(ABCD)+ = ABCDEF = R. But (ABCD) is not a candidate key. It is a super key, because its subset consists of keys.
Result:
ABD, ACD, and BCD are the candidate keys of R.

**********

Go back to Normalization – solved exercises page.

Go to How to find closure page

Go to 2NF, 3NF and BCNF

# How to find candidate keys in a relational database for normalization

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

data recovery