8

Suppose the relation R( K, L, M, N, P), and the functional dependencies that hold on R are:

 - L  -> P
 - MP -> K
 - KM -> P
 - LM -> N

Suppose we decompose it into 3 relations as follows: 

 - R1(K, L, M)
 - R2(L, M, N)
 - R3(K, M, P)

How can we tell whether this decomposition is lossless? I used this example

R1 ∩ R2 = {L, M}, R2 ∩ R3 = {M}, R1 ∩ R3 = {K,M} we use functional dependencies, and this is not lossless in my opinion, but a little bit confused.

philipxy
  • 14,867
  • 6
  • 39
  • 83
DjMix
  • 105
  • 1
  • 1
  • 7
  • Those are not the only FDs that hold, since there are trivial FDs & FDs that must hold when those do, per Armstrong's axioms. So you were probably told that that is a *cover*. If you don't know it's a cover, you can't answer the question. – philipxy Apr 16 '19 at 22:00

3 Answers3

21

It helps if we demystify the concept of lossless decomposition a bit: it really just means that joining R1, R2 and R3 should yield the original R.

Do you know the chase test a.k.a "the tableau method"? It's a cool algorithm to test for losslessness. It's easy to program, and it's actually used in the industry when reasoning about data consistency.

We start with the so-called "tableau of the decomposition", an n*m matrix where n is the number of relations and m is the number of attributes. For every field, if the relation n contains attribute m we write the attribute name; otherwise we write the attribute name subscripted with the number of the relation.

   |  K   L   M   N   P
 -----------------------
 1 |  K   L   M   n1  p1
 2 |  k2  L   M   N   p2
 3 |  K   l3  M   n3  P

Now the tableau will be "chased" (hence the name of the algorithm). We notice that the first and second rows agree on their L and M values. The dependency LM->N implies that their N values should agree too. Let's change the first row's n1 into the second row's N:

   |  K   L   M   N   P
 -----------------------
 1 |  K   L   M   N   p1
 2 |  k2  L   M   N   p2
 3 |  K   l3  M   n3  P

Now the first and third rows agree on their K and M values. We have a KM->P dependency, so they should agree on their P value also.

   |  K   L   M   N   P
 -----------------------
 1 |  K   L   M   N   P
 2 |  k2  L   M   N   p2
 3 |  K   l3  M   n3  P

And we're done! As soon as any of the rows has all of the proper attributes (as the first row does), the algorithm terminates and proves the decomposition was indeed lossless.

Note how the repeated applications of the dependencies represent joining the relations on the keys they share. So what we did was joining R1 and R2 on L and M (netting us (K, L M, N)), then joining the result with R3 on K and M (that yields R).

SáT
  • 3,633
  • 2
  • 33
  • 51
  • 1
    oh, thanks, i completely forget and stop waiting help :) clean answer. – DjMix May 21 '14 at 18:22
  • To consider above calculations true, R1 should be considered as (K,L,P) instead of (K,L,M) in example – SRK Jun 22 '17 at 10:00
  • @SRK Yes. I keep meaning to get back to this and correct the answer, but never seem to find the time or the mindset. Would you care to edit? :) – SáT Jun 22 '17 at 10:44
  • @SaT: Editing done but pending for peer review. So DjMix has to approve it. – SRK Jun 22 '17 at 11:04
  • @SRK Actually, the mistake is in my answer, not in the question. The answer posted by Vivek Pandya does the calculation correctly. – SáT Jun 22 '17 at 11:09
  • @SáT but your answer is very well formatted and also you explained it step by step. So I thought to make changes in question itself... ;p – SRK Jun 22 '17 at 11:17
  • @SRK OH COME ON :D. Never mind, I'm editing the question right now. (I have NO idea how I formatted the tables this nicely. By hand...?) – SáT Jun 22 '17 at 11:32
0

The algorithm mentioned above is correct but calculation is wrong
as R1 contains K, L, M not K , L , P
so here in 2nd step LM --> N will be used
and it will make N1 to N in R1
and then MP --> K will be used and R1 will contain all attributes of R
so algorithm will terminate.

Vivek Pandya
  • 1
  • 4
0

The tableau method is not that cool and not a promising one when you have a lot of attributes. Rather I claim this method,

In general, if R is decomposed into R1 and R2, either R1 Intersect R2 ->R1 Or R1 Intersect R2 ->R2 should be true.

So, when it is R1, R2, R3 .. Rn, first check the same for any two of them and reduce it to R with the help of given Functional Dependencies. check if (Rn U Rn-1) has a lossless decomposition into Rn-1 and Rn, If yes replace Rn-1 by (Rn U Rn-1), discard Rn and continue checking till you complete the joining.

If no, return False.

  • 1
    That test only holds for binary decompositions. But some decompositions have more than 2 components where pairwise joins to reconstruct are individually lossy but the final result is not. – philipxy Apr 16 '19 at 21:59