2

Given a relation, a set of functional dependencies, and it's decomposition into multiple relations (> 2) , is there some method with which to check if this decomposition is lossless or lossy?

For decomposing R into two relations R1 and R2, we check if the intersection of R1 and R2 forms the primary key of either R1 or R2. If it does, then the decomposition is lossless.

Consider the question below, where a relation R,it's FD set and decomposition are given.

enter image description here

Now, I think this decomposition is lossy...but it's more of an intuition. If I am asked to prove this, I might not be able to. My intuition is based on the fact that the relation pairs R2-R3 , R1-R2 , R1-R4 don't have a common attribute between them, which is prime in either relation of the pair. So a natural join operation across R1, R2, R3 and R4 will produce some rows which were not in the original relation.

But I myself am not sure if this decomposition is lossy or not.. Can someone please help me understand this?

Thanks!

sanjeev mk
  • 4,276
  • 6
  • 44
  • 69
  • 1
    What does the end of the book says about it? This question feels like it is straight out of textbook. I have been in the industry for almost 10 years and I never heard anyone refer to these terms. Most DBA don't even talk about 3NF or 2NF they might mention that they need to normalize or denormalize the data but that is the extend of it. –  Feb 04 '14 at 21:01
  • 1
    For me it is over 20 years ago reading these constructs. To be honest, even when graduating from university few people could read such a question. I would really have to go back to old books to understand your question. Can you rephrase in more commonworld terms? – Guido Leenders Feb 04 '14 at 21:29
  • 1
    Please pose your question using text whenever possible. Use images only to augment or when necessary. We can't search on or cut & paste an image. – philipxy Apr 17 '17 at 21:34

2 Answers2

2

A binary decomposition is lossless when the common columns are a superkey of one component, ie include a CK (candidate key) of one component. (Not a "prime attribute", ie one that is a member of a CK.) So the following are lossless:

       join        FDs                        CKs
R1 R3  ABCDH       A->B, A->C, D->H, AH->D    AD, AH
R2 R4  CDEH        E->C, D->EH                D
R4 R3  ADEH        D->EH, AH->D               AD, AH

We can now join ABCDH & ADEH losslessly based on either CK of either relation, then join the result with CDEH losslessly based on CK D.

So the decomposition is lossless.

Alternatively we can try decomposing. Try R = R1 JOIN ADEH. We find ADEH's FDs & CKs (which happen to be in the table above). We continue, to see whether we can keep losslessly decompose to get R2, R3 & R4.

For a general algorithm see the Chase.

philipxy
  • 14,867
  • 6
  • 39
  • 83
0

According to me the decomposition is lossless. If you go with the tables, R1 intersection R3 and R2 intersection R4, it is lossless & it involves all the decomposed tables also. If you go for natural join between R1 & R3 and R2 & R4, you will get back the table R. thanks..

Guest
  • 1