Lossless Join and Decomposition From Functional Dependencies

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.