2 votes 2 votes Databases gateforum-test-series databases lossless-join bcnf-decomposition + – Mk Utkarsh asked Jan 12, 2018 Mk Utkarsh 1.5k views answer comment Share Follow See all 34 Comments See all 34 34 Comments reply joshi_nitish commented Jan 12, 2018 reply Follow Share option A) is correct both of the decomposition {(BD),(ABC)} and {(BD),(ADC)} are lossless and dependency preserving. 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share c is given as solution 0 votes 0 votes G.K.T commented Jan 12, 2018 reply Follow Share how {(BD) , (ADC)} is dependency preserving ? 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share AB and AD are candidate keys so yeah :| i missed that 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share G.K.T not preserved 0 votes 0 votes G.K.T commented Jan 12, 2018 reply Follow Share so it should be a option right ? 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share check options once again 0 votes 0 votes joshi_nitish commented Jan 12, 2018 reply Follow Share dependencies in {(BD) , (ADC)} are $B->D,D->B,AD->C$............(i) now, you think how $AB->C$ is preserved, it is actually preserved but not directly. take closer of $AB$ using dependencies of (i). $AB^+->ABDC$, now see, $AB->C$ is covered and hence preserved 1 votes 1 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share still unclear, dependencies in {(BD) , (ADC)} are B−>D, D−>B, AD−>C how AB---->C is preserved is this what you are saying that D-->B so AB+---->ABCD? 0 votes 0 votes joshi_nitish commented Jan 12, 2018 reply Follow Share yes, exactly. 1 votes 1 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share ok thank you :) 0 votes 0 votes Higgs commented Jan 12, 2018 reply Follow Share AB->C is not preserved because B is not part of the R2(ADC). Only after we join R1(BD), r2(ADC) ,we get AB->C 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share i always end up marking wrong answer in these questions where there is indirect dependency 0 votes 0 votes vishal chugh commented Jan 12, 2018 reply Follow Share So what is the ans then? Is it 'a' or 'c'? According to joshi_nitish is should be 'a' I suppose and that given in solution is 'c' 0 votes 0 votes Higgs commented Jan 12, 2018 reply Follow Share Given FD's: B->D D->B AB->C Decomposition: {R1(B,D) , R2(A,D,C)} What fd's will hold on R2?? A -> something D -> something C -> something AD -> something AC -> something DC -> something ADC -> something Now let's replace "something" by proper values that we get from fd's. A -> A D -> DB C -> C AD -> ADBC AC -> AC DC -> DBC ADC -> ADCB Now filter out fd's that include only those attributes that are present in our decomposed relation R2(A,D,C) A -> A D -> D C -> C AD -> ADC AC -> AC DC -> DC ADC -> ADC Excluding trivial fd's we get: AD -> C Now we have found fd's that hold on R2. Can we deduce AB - > C from these fd's?? (NO!). Likewise deduce fd's for R1. Can we deduce AB - > C from these fd's that hold on R1?? (NO!). 1 votes 1 votes joshi_nitish commented Jan 12, 2018 reply Follow Share @Higgs what you finally wants to say, is {R1(B,D) , R2(A,D,C)} is dependency preserving or not? 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share he wants to say it is not dependency preserving 0 votes 0 votes joshi_nitish commented Jan 12, 2018 reply Follow Share then he is wrong. 0 votes 0 votes Higgs commented Jan 12, 2018 reply Follow Share Please elaborate your veiwpoint. 0 votes 0 votes joshi_nitish commented Jan 12, 2018 reply Follow Share @Higgs @Mk Utkarsh tell me about dependency preserving decomposition 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share I'm already very confused but according to my understanding after decomposition we should somehow deduce the dependencies mentioned before decomposition 0 votes 0 votes vishal chugh commented Jan 12, 2018 reply Follow Share Ya I have the same understanding. So according to me also 'C' should be the ans. But joshi_nitish's explanation has created doubts in my understanding of the concept :P 1 votes 1 votes joshi_nitish commented Jan 12, 2018 reply Follow Share see, let you decompose original relation R(FD's set as F) into R1(FD's set as F1) and R2(FD's set as F2), now, the decomposition is dependency preserving, iff $F1^+\cup F2^+=F^+$ 2 votes 2 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share now that after his explanation i think both have preserved dependencies after decomposition because i just checked another question of the same type 0 votes 0 votes Ashwin Kulkarni commented Jan 12, 2018 reply Follow Share Both are FD preserving ! 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share wait i am posting another question based on this concept 0 votes 0 votes Higgs commented Jan 12, 2018 reply Follow Share Please refer the fd's that I have found, aren't they equivalent to $F_{2}^{^{+}}$ ?? i.e. R2(A,D,C) A -> A D -> D C -> C AD -> ADC AC -> AC DC -> DC ADC -> ADC 0 votes 0 votes Higgs commented Jan 12, 2018 reply Follow Share Why isn't anyone replying?? A healthy discussion is going on and it can help in clearing doubt of the future readers as well. 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share If we decompose a relation R into relations R1 and R2, All dependencies of R either must be a part of R1 or R2 or must be derivable from combination of FD’s of R1 and R2. by combination of R1 and R2 we can derive AB----->C 0 votes 0 votes Hemant Parihar commented Jan 12, 2018 reply Follow Share @Higgs see the definition of FD preservation. First, we take the union of F1 and F2 then keen closure. See this pdf for detail. http://old.sztaki.hu/~fodroczi/dbs/dep-pres-own.pdf 1 votes 1 votes Higgs commented Jan 12, 2018 reply Follow Share Let me present my case from another viewpoint: Suppose we have R(ABCD) and fd AB->C on this table. Each time tuples are inserted in R, it is checked whether this fd is satisfied or not. If yes, then tuple is inserted. Now suppose we decompose this R(ABCD) into two relations: R1(BD), R2(ADC) (Now also AB->C must hold.) After decomposition, how can we check AB->C holds or not?? --- We need to join these two relations and then check. (Can you devise any other method??) This is the whole point of dependency preservation that after decomposition, whether you can verfiy that the fd's are satisfied or not without performing join on the decomposed tables. 0 votes 0 votes Mk Utkarsh commented Jan 12, 2018 reply Follow Share i don't think we have to use JOIN specifically just need to do union of FD's. like from SQL viewpoint we can use AB and uniquely identify C right? it doesn't matter if tables are different because B-->D and D--->B 0 votes 0 votes Higgs commented Jan 12, 2018 reply Follow Share I think I need to revisit my concepts. Thanks everyone. Future comments are welcome. 1 votes 1 votes Higgs commented Jan 19, 2018 reply Follow Share Update: If you are reading this discussion then please note that what others have pointed out is absolutely correct. i.e. dependencies are preserved in both decompositions. Actually, I was simply checking whether $F_{1}^+ \ U\ F_{2}^+ = F^{+}\ or\ not.$ But the correct approach is $(F_{1}^+ \ U\ F_{2}^+) ^{+}= F^{+}$ i.e. We take the union of F1 and F2 and then keen closure. Thankyou @joshi_nitish, @Hemant, @Mk. 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes Answer must be 'A'.... As in option B dependency is preserved.... Achal Gupta 1 answered Jan 12, 2018 Achal Gupta 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply Nishtha3121996 commented Jan 12, 2018 reply Follow Share How is dependency preserved in second option can you please explain as from ADC decomposition AB -) C can't be derived 0 votes 0 votes Achal Gupta 1 commented Jun 26, 2018 reply Follow Share In this we have to check whether the dependency is preserved or not for decomposition ADC..... So take the dependency AB - >C and check using polynomial time algorithm ( it is an algo used to find out whether dependency is preserved or not...)..... Then u will get your answer 0 votes 0 votes Please log in or register to add a comment.