The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+58 votes

R(A,B,C,D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF decomposition?

- $A \rightarrow B, B \rightarrow CD$
- $A \rightarrow B, B \rightarrow C, C \rightarrow D$
- $ AB \rightarrow C, C \rightarrow AD$
- $A \rightarrow BCD$

+64 votes

Best answer

taking up **option A** first :

We have, R(A, B, C, D) and the Functional Dependency set = {A→B, B→CD}.

Now we will try to decompose it such that the decomposition is a Lossless Join, Dependency Preserving and new relations thus formed are in BCNF.

We decomposed it to R_{1}(A, B) and R_{2}(B, C, D). This decomposition satisfies all three properties we mentioned prior.

taking up **option B** :

we have, R(A, B, C, D) and the Functional Dependency set = {A→B, B→C, C→D}.

we decomposed it as R_{1}(A, B), R_{2}(B, C) and R_{3}(C, D). This decomposition too satisfies all properties as decomposition in *option A**.*

taking up **option D** :

we have, R(A, B, C, D) and the Functional Dependency set = {A→BCD}.

This set of FDs is equivalent to set = {A→B, A→C, A→D} on applying decomposition rule which is derived from Armstrong's Axioms.

we decomposed it as R_{1}(A, B), R_{2}(A, C) and R_{3}(A, D). This decomposition also satisfies all properties as required.

taking up **option C** :

we have, R(A, B, C, D) and the Functional Dependency set = {AB→C, C→AD}.

we decompose it as R_{1}(A, B, C) and R_{2}(C, D). This preserves all dependencies and the join is lossless too, but the relation R_{1 }is not in BCNF. In R_{1} we keep ABC together otherwise preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R_{1}. {C→A} violates the condition for R_{1} to be in BCNF as C is not a superkey. Condition that all relations formed after decomposition should be in BCNF is not satisfied here.

We need to identify the INCORRECT, Hence mark **option C**.

0

Great explanation.

Just one thing:

Do we need to decompose in case of option D {A → BCD}?

It's already in BCNF, right?

Just one thing:

Do we need to decompose in case of option D {A → BCD}?

It's already in BCNF, right?

+3

I have also same question. Do we need to decompose option D? It is already in BCNF.

Also, can you post BCNF decomposition algorithm?

I am using algorithm 11.3 of Navathe book. But getting different decomposed relation in option C. Keys are AB and BC. So C -> AD not in BCNF. So, decomposition result as BC and CAD. So, decomposition result as BC and CAD. Please comment.

**Algorithm 11.3**: Relational Decomposition into BCNF with Nonadditive Join Property

Input: A universal relation Rand a set of functional dependencies F on the attributes of R.

1. Set D := {R};

2. While there is a relation schema Q in D that is not in BCNFdo

{

choose a relation schema Q in D that is not in BCNF;

find a functional dependency X ~ Y in Qthat violates BCNFj

replace Q in D by two relation schemas (Q - Y) and (X U Y);

};

+1

No, we don't need to decompose R(A, B, C, D) for option D.

And the algorithm you posted is the correct one, and your decomposition for option C is also correct, that follows lossless join property but doesn't preservere dependency.

And the algorithm you posted is the correct one, and your decomposition for option C is also correct, that follows lossless join property but doesn't preservere dependency.

+1

@Rajesh Raj , If we do so, then what should we take FDs for R1 ??

here Lossless is okay but dependecy(AB -> C) would not be preserved any more...

am I right ??

+2

yup thats why we could also choose the** option C **because the question is asking "Which of the following does not have a lossless join, dependency preserving BCNF decomposition? ". whats say ??

0

@vijay @Rajesh raj Although it's very appropriate explanation i understood it very well,i have a small query

what if i decompose (c) in the table like this

R1(ABC) R2(ACD)

AB->C C->AD // here also doesn't have lossless join dependency preserving decomposition

AC common part which doesn't imply any key of both tables

which leads to option (C)

m i correct ??

what if i decompose (c) in the table like this

R1(ABC) R2(ACD)

AB->C C->AD // here also doesn't have lossless join dependency preserving decomposition

AC common part which doesn't imply any key of both tables

which leads to option (C)

m i correct ??

0

*AC common part which doesn't imply any key of both tables.*

First of all, the common part should be key for any table ( R1 or R2 ).( Both not necessary)

And No, It is not so. If C is alone a key of R2(**C -> AD)**, then why not AC. ?

+29 votes

(C) is the answer. Because of AB -> C and C -> A, we cannot have A, B and C together in any BCNF relation- in relation ABC, C is not a super key and C->A exists violating BCNF condition. So, we cannot preserve AB -> C dependency in any decomposition of ABCD.

For (A) we can have AB, BCD, A and B the respective keys

For (B) we can have AB, BC, CD, A, B and C the respective keys

For (D) we can have ABCD, A is key

For (A) we can have AB, BCD, A and B the respective keys

For (B) we can have AB, BC, CD, A, B and C the respective keys

For (D) we can have ABCD, A is key

0

We are not given the candidate keys here so how can we determine that which decomposition is in BCNF....?Please explain....

0

@dhingrak candidate keys won't be given. We have to find them from the FDs.

@Tamojit-Chatterjee I have edited the answer. Is it clear now?

@Tamojit-Chatterjee I have edited the answer. Is it clear now?

+1

@Arjun Sir ..I have a doubt regarding dependency preserving- if all attributes of a particular Functional Dependency are not present in any decomposition then we apply the dependency preserving algorithm...

http://www.cs.uakron.edu/~chanc/cs475/Fall2000/ExampleDp%20decomposition.htm

But its application is too lengthy ....is there any other short method..?

0

The steps of that algorithm is lengthy. But if you correctly apply it, it is very easy. I mean for most of the questions, the algorithm stops very fast.

0

Yes. But it can be skipped if you are sure, we cannot check for any dependency without a join of the relations.

+2

Do we need to decompose option D? It is already in BCNF.

Also, can you post BCNF decomposition algorithm?

I am using algorithm 11.3 of Navathe book. But getting different decomposed relation in option C. Keys are AB and BC. So C -> AD not in BCNF. So, decomposition result as BC and CAD. Please comment.

**Algorithm 11.3**: Relational Decomposition into BCNF with Nonadditive Join Property

Input: A universal relation Rand a set of functional dependencies F on the attributes of R.

1. Set D := {R};

2. While there is a relation schema Q in D that is not in BCNFdo

{

choose a relation schema Q in D that is not in BCNF;

find a functional dependency X ~ Y in Qthat violates BCNFj

replace Q in D by two relation schemas (Q - Y) and (X U Y);

};

0

@Arjun sir can you give the intuition with this algorithm on the link. Will be helpful? not able to get it

0

@Arjun Sir, I think it is silly to ask but why can't we do like:

R(A,B,C,D)

{AB ->C , C-> AD}

R1(ABC) R2(CD)

AB->C, C->A //NOT IN BCNF C->D //IN BCNF

R11(ABC) R12(AC)

AB->C // IN BCNF C->A //IN BCNF

R(A,B,C,D)

{AB ->C , C-> AD}

R1(ABC) R2(CD)

AB->C, C->A //NOT IN BCNF C->D //IN BCNF

R11(ABC) R12(AC)

AB->C // IN BCNF C->A //IN BCNF

0

the decomposition you have ABC AC and CD lossless join and dependency preserving, but it is still not in BCNF. because in ABC $C\rightarrow A$ will still be implied.

0

@Arjun sir @Bikram sir pls look at this once. I have a doubt on c option $AB\rightarrow C, C\rightarrow AD$.

We have 2 algorithms for decomposition,

**1. BCNF decompositoin algorithm, **according to this we will get two relations R1(CAD) with $C\rightarrow AD$ and R2(BC) , where $AB\rightarrow C$ is not preserved. So its not possible this way.

But given Schema is also not in 3NF so we can try 3NF atleast.

**2. 3NF synthesis algorithm**, which makes a relation for each dependency in the minimal cover of given relation A. This guarantees lossless and dependency preserving decompositoin. If we use this in C option then we will get 2 relations R1(ABC) with FD $AB\rightarrow C$ and R2(CAD) with FD $C\rightarrow AD$. So this is in 3NF according to the algorithm, But this also happens to be **in BCNF. **

I use this because sometimes through 3NF decomposition we get a BCNF decomposition. Also for $AB\rightarrowC, C\rightarrowA$ the 3NF algorithm gives no decomposition as expected.

Since given that C is wrong, does it mean that we must use only BCNF decompostition algorithm in this case.

+7 votes

(A) A->B, B->CD

AB and BCD, B is the key of second and hence decomposition is lossless.

(B) A->B, B->C, C->D

AB, BC, CD B is the key of second and C is the key of third, hence lossless.

(C) AB->C, C->AD

ABC, CD. C is key of second, but C->A violates BCNF condition in ABC as C is not a key. We cannot decompose ABC further as AB->C dependency would be lost. Hence the ANSWER.

(D) A ->BCD

Already in BCNF.

AB and BCD, B is the key of second and hence decomposition is lossless.

(B) A->B, B->C, C->D

AB, BC, CD B is the key of second and C is the key of third, hence lossless.

(C) AB->C, C->AD

ABC, CD. C is key of second, but C->A violates BCNF condition in ABC as C is not a key. We cannot decompose ABC further as AB->C dependency would be lost. Hence the ANSWER.

(D) A ->BCD

Already in BCNF.

0

@ARJUN sir we have, R(A, B, C, D) and the Functional Dependency set = {AB→C, C→AD}.

we decompose it as R_{1}(A, B, C) and R_{2}(C, D). This preserves all dependencies and the join is lossless too, but the relation R_{1 }is not in BCNF. In R_{1} we keep ABC together otherwise preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R_{1}. {C→A} violates the condition for R_{1} to be in BCNF as C is not a superkey. Condition that all relations formed after decomposition should be in BCNF is not satisfied here..

why i can not do this R1(ABC) and R2(ACD) ??

–1 vote

0

if possible help me..

R(A,B,C,D)

OPTION A : A ->B, B->CD which can be further written in to B->C , C->D

clearly from here in right hand side we dont have A, so the p.k. will surely have A

so lets find (A)+ --> ABCD ... so we get A is the only primary key right?

and according to the rule B,C,D are non-prime attributes. but in relation's F.D. we have B->C & B-->D where a non prime determines a non prime attribute, which clearly says the relation is not in 3NF also. Then how the hell the relation can be in BCNF?

can you please explain....

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 411
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,786 questions

41,762 answers

118,950 comments

41,409 users