GATE CSE 2001 | Question: 2.23

Question

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

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

Comments

Option D

---

Fine i agree with that . explain rest .

---

c is correct {ACD ,BC} is BCNF decomposition lossless but not dependency preserving

Answer 1

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₁(A, B) and R₂(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₁(A, B), R₂(B, C) and R₃(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₁(A, B), R₂(A, C) and R₃(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₁(A, B, C) and R₂(C, D). This preserves all dependencies and the join is lossless too, but the relation R₁ is not in BCNF. In R₁ we keep ABC together otherwise preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R₁. {C→A} violates the condition for R₁ 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.

Comments

MRINMOY_HALDER

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.

---

We can break C->AD as C->A and C->D, here only C-> D will get break in the process because it is not in 2NF and we will get decomposition as 1.(ABC) and 2.(CD). Please correct me if I am wrong.

---

@Prateek kumar 

for lossless:

                        1. R1 U R2 = all attribute

               and  2. R1 ∩ R2 = super key of R1 or R2

Answer 2

(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

Comments

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

---

explanation is not clear.

---

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

---

hmmm thanx

---

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

---

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.

---

That means we need to apply this algo everytime we need to check for functional dependency?

---

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

---

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

---

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

---

@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

---

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.

---

@Shivansh Gupta thanks!!

---

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

---

Sir means it is possible that relation can never be in BCNF?

Answer 3

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

Comments

here AC is common and it is not the key any of the R1 and R2 that's why it is not lossless.

---

Sir,can you share link for how to convert dependency to any normal form ??

---

R1(ABC) and R2(ACD) is also dependency preserving because AC is common and c is candidate key for R2

Answer 4

Initially FD X-> Y is in BCNF if

X is superkey

A) A is candidate key but B->CD voilates since B is not super key (not BCNF)

B)A is candidate key but B->C,C->D voilates since B,C are not super key (not BCNF)

C)AB , CB are candidate keys but C->D voilates since C alone is not SuperKey  (not BCNF)

D) A is candidate Key and satisfies BCNF

Therefore Option D is BCNF

A,B,C are not BCNF

Comments

bdw answer would be a b c not d Read question !

---

i didn't get you

---

yeap sorry which is not BCNF i will edit