The Gateway to Computer Science Excellence

+98 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**.

+2

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?

+10

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);

};

+5

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.

+3

@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 ??

+3

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

+4

@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. ?

+1

@vijay i was meant "ANY" of table

yeah AC would be super key bcoz union with candidate key would give super key

yeah AC would be super key bcoz union with candidate key would give super key

0

anyone please explain this

In R1 we keep ABC together otherwise preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R1. {C→A} violates the condition for R1 to be in BCNF as C is not a superkey.

0

Why can't we decompose like R1 like (A,B,C) and R2 like (A,C,D)? Then both tables will be BCNF right?

0

Because for lossless decomposition common attribute has to be work as a key for any of the decomposed relation.

+1

If we decompose as R1(ABC) and R2(CAD),then C is the common attribute and is key for R2. Why are we decomposing as R1(ABC),R2(CD)?

+9

@amitqy

Both will give the same result.

Since given, AB$\rightarrow$C and C$\rightarrow$AD

So rewriting them, AB$\rightarrow$C, C$\rightarrow$A, C$\rightarrow$D

Though R2(CAD) is in BCNF as C$\rightarrow$AD is the only FD present but

R1(ABC) will have FDs AB$\rightarrow$C and C$\rightarrow$A

C$\rightarrow$A violates the BCNF property

Both will give the same result.

Since given, AB$\rightarrow$C and C$\rightarrow$AD

So rewriting them, AB$\rightarrow$C, C$\rightarrow$A, C$\rightarrow$D

Though R2(CAD) is in BCNF as C$\rightarrow$AD is the only FD present but

R1(ABC) will have FDs AB$\rightarrow$C and C$\rightarrow$A

C$\rightarrow$A violates the BCNF property

0

There is one more decomposition possible for option B i.e R1(A,B), R2(A,D) , R3(B,C) which is also lossless but not dependency preserving .Now, which one to choose between option B and option C and why?

0

@amitqy If we decompose as R1(ABC) and R2(CAD),then AC is the common attribute and AC is not a key in any of the two decomposed relations as the FD for R1 is AB->C and for R2 C->AD.

We can't have AC as a key to get lossless decomposition.

+1

@Arjun @vijaycs @amarVashishth

If a given relation is decomposed in more than 2 relations then how we can conclude that it is loseless join decomposition.??????

(How to identify and tackle such problem like option (B) in the above question)

0

To get lossless decomposition, one of the common attribute must be candidate key in any one table. So i think, arguing "*AC is common and AC is not a candidate key in any relation so decomposition does not have lossless join* " is not correct.

We can take C as common attribute and C is candidate key in the relation $R_{2}$ (CAD) and it is enough to say that decompostion to $R_{1}$ (ABC) and $R_{2}$ (CAD) is lossless. But $R_{1}$ (ABC) is not in BCNF, refer Minipanda's explanation.

+33 votes

(C) is the answer. Because of AB $\to$ C and C $\to$ A, we cannot have A, B and C together in any BCNF relation- in relation ABC, C is not a super key and C$\to$ A exists violating BCNF condition. So, we cannot preserve AB $\to$ 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.

+11 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) ??

–2 votes

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.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,243 answers

198,012 comments

104,604 users