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

the answer can be found out by hit and trial method.

at first find whether the relation is in bcnf or not.

then, if it is not in bcnf you need to decompose it into bcnf by taking a violation,

 suppose X-> A is R.

then, R is splitted into R1 and R2

by R1(x+) and R2(R-x+ + x)

now the relation is in bcnf if not again do the splitting.

however if it becomes a bcnf, now check whether it is lossless or dependency preserving or not.

check it for other options.

a lengthy question.

---

hey aspirants. this question is a good one.

take option a, seperate into two groups, (ab) (bcd). here intersection is b which is a super key in R2. also both a->b and b->cd are in bcnf becuase lhs is super key in those relations. thus no problem here

take option b, seperate into 3 relations, (ab) (bc) (cd). its lossless because the intersection is always a superkey in one of the relations. Also, lhs of a->b b->c c->d is always super key. thus individual relations are already in bcnf.

take option d, a->bcd can be written as a->b, a->c a->d. this is amstrong's property as discussed by deepak poonia sir. now seperate into three groups (ab) (ac) (ad) all are in bcnf and common attribute is a which is a superkey in individual relations. thus no problem here too.

finally c option, ab->c c->ad. here find candidate key: b is not in the rhs of any fd's. so it'll be a part of every ck. check closure of ab. its {a,b,c,d} thus ab, bc are the candidate key. i dont think any other ck exists. the fd which is creating the trouble here is c->ad because c is not a super key. thus decompose this in the follwing way:
attribute closure of c in one side and others along with c in the other side. so (cad), (cb) is the decomposition. this is lossless because common attribute is c which is super key in (cb). lets check dependency preserving. no where we can find ab->c getting preserved. so this is not dependency preserving.

 

thus option C is the correct answer.

---

Option A

R(A,B,C,D)   FD(A--->B, B---->CD)

CK's = A,  So not in BCNF

Now Decompose into BCNF

R1(A,B)  R2(BCD)    AFER DECOMPOSITON BOTH RELATION ARE IN BCNF

NOW THIS OPTION IS LOSSLESS, DEPENDENCY PRESERVING AND BCNF

OPTION B

A→B,B→C,C→D

CANDIDATE KEYS  = A

THIS IS NOT IN BCNF

NOW DECOMPOSE INTO BCNF

TAKE B---->C VOILATION

R1(BCD)  R2(AB)   R1 IS NOT IN BCNF

NOW FURTHER DECOMPOSE

TAKE VOILATION C-->D

R1(CD) R2(BC) R3(AB)   

NOW THIS IS IN BCNF, DEPENDENCY PRESERVING AND LOSSLESS

OPTION 3

AB→C, C→AD

CANDIDATE KEYS = AB,BC

BCNF VOILATION BECZ C IS NOT SUPERKEYS

DECOMPOSE INTO BCNF

R1(ACD)  R2(BC)

NOW BOTH RELATION  IN BCNF  ALSO LOSSLESS BUT NOT DEPENDENCY

BECZ AB-->C IS LOST

 

OPTION D

Already in bcnf

 

finally Option C is correct

 

 

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

Detailed Video Solution with Complete Analysis: https://www.youtube.com/watch?v=Epy_Vw4gFpo&t=3541s

---

Similar Question in GATE 1994: https://www.youtube.com/watch?v=Epy_Vw4gFpo&t=3107s

Above video solution contains Another Relation for which there is No BCNF decomposition which preserves dependencies. 

---

Yes, but in R1(ABC) there will be AB → C and C → A which does not work as C → A violates conditions for BCNF. Also we need to have ABC relation so as to have AB → C to have the functional dependency condition fulfilled as aksed by the question. I may be wrong so suggestions are welcomed. Thank You. This is my first time writing a comment or any post on this platform.

---

@Deepak Poonia absolutely amazing explaination :-)

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

@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

R(ABCD)

a)      A --> B          B --> CD

Candidate key= A 

So,

A --> B              In BCNF   (Bec A is the superkey)

B --> CD           (Violation of BCNF)

Therefore not in BCNF. So Decompose into BCNF

B -->CD

Closure of B = BCD     

So R1 = BCD   (In BCNF)

      R2=  AB      (In BCNF)

Now Check lossless or Lossy join 

R1 ∩ R2 = B      (B is SK in R1) 

So lossless 

Now Check dependency preserving 

A --> B           Dependency preserved in  R2

B --> CD         Dependency preserved in  R1

So dependency preserved 

------------------------------------------------------

b)      A --> B     

        B --> C

        C --> D

CK= A

So, 

         A --> B       (In BCNF)   bec A is SK 

        B --> C       Not in BCNF

        C --> D       Not in BCNF 

So decompose into BCNF 

B --> C 

Closure of B = BCD

R1= BCD   ( Again not in BCNF)

R2= AB      (In BCNF)

Take violation and decompose into BCNF

R1= BCD 

B--->  C                 C---> D

CK= B 

So,

B --->  C   (In BCNF) 

C---> D    (Not in BCNF)

Take violation and decompose into BCNF

Closure of C = CD 

R1= CD  (In BCNF)

R2= BC   (In BCNF)

So  Decomposition BCNF

R1= (AB)     R2=(BC)      R3=(CD)

Now Check lossless or Lossy join 

R1 ∩ R2 = B      (B is SK in R1)        R2 ∩ R3 = C      (C is SK in R3) 

So lossless 

Now Check dependency preserving 

A --> B           Dependency preserved in  R1

B --> C         Dependency preserved in  R2

C --> D            Dependency preserved in  R3

So dependency preserved 

-----------------------------------------------------

d)  A-->  BCD

CK= A 

So,   A-->  BCD  (In BCNF)   A is the superkey 

Here no BCNF Decomposition Required 

so here it is already in BCNF, Lossless and dependency preserving.

-------------------------------------------------

c)  AB ---> C,   C---> AD

CK= AB, BC 

AB ---> C        (In BCNF )  (Bec AB is the superkey)

C---> AD        (Violation of BCNF)

Therefore not in BCNF. So Decompose into BCNF

Take a Violation 

C ---> AD

Closure of C= CAD

R1= CAD        (In BCNF)

R2= BC             (In BCNF)

Now Check lossless or Lossy join 

R1 ∩ R2 = C      (B is SK in R2) 

So lossless

Now Check dependency preserving 

AB --> C           Dependency Not preserved 

C --> AD         Dependency preserved in  R1

So dependency not  preserved 

 

so C is the Correct answer

------------------------------------------------------------

BCNF Decomposition Algo:

if R is not in BCNF:

Take a violation   X--->  A    (X is not SK)

Decompose R in R1, R2:

R1(Closure of X)     R2(R - (Closure of X )+ X)

Answer 5

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

Answer 6

Option C: R(A, B, C, D) and the Functional Dependency set = {AB→C, C→AD}

Candidate keys are AB, CB & C→ AD violates BCNF, so decompose it using BCNF decomposition algorithm (Source: Navathe). C+ = CAD. Decomposition is R1(BC) and R2(CAD).

C→AD is preserved but AB → C can’t be preserved. So decomposition is in BCNF but not dependency preserving hence option C is the right answer.