CODEWITHSUNDEEP
database-normalizationfunctional-dependenciesdatabase-relations
Naman Sood
Naman Sood

Reputation: 47

Proving Lossless or Lossy Decomposition

I was trying to solve a question regarding proving whether the given decomposition is lossy or lossless:

Verify which among the following decompositions of R(ABCDE) are lossless or lossy by applying the test for lossless join property. F = {AB→C, C→E, B→D, E→A} is the set of functional dependencies on R.

  1. R(ABCDE) is decomposed as R1(AB), R2(ADE) and R3(BCD)
  2. R(ABCDE) is decomposed as R1(BCD) , R2(ACE) and R3(BD)

My attempt at the solution:

A decomposition can only be lossless if there are common attributes between the given tables and the common attributes are candidate key/super key.

In the first part, we have no candidate key in R1 and none in R2 so can we call it as lossy decomposition ?

In the second part, C is the candidate key for R2 and B is the candidate key for R3, but R1 has no key and also R2 and R3 share no common attributes so its also not a lossless decomposition ?

Is my explanation valid or are there any more criteria ?

Upvotes: 0

Views: 1227

Answers (1)

philipxy
philipxy

Reputation: 15118

The instructions are clear: "by applying the test for lossless join property". Presumably that is the important theorem that says that a binary join/decomposition is lossless when/iff .... But you don't quote it. Look in your textbook. (Beware, the Wikipedia article has problems.) You do say "can only be lossless if" but that's just saying something is necessary, which is the "if" in one direction, whereas you haven't said what's also sufficient, which is the "if" in the other direction, which is the direction you need, so your reasoning is not sound--unless you are just using poor language and you mean "iff". But even using "iff" your definition is wrong. You need to say that "the common columns form a superkey" of at least one of the components. And "there are common attributes between" doesn't belong--there don't need to be common attributes whether or not a join is lossless. No common attributes means a common attribute set {} and a cross join; but if its subset {} is a CK of a component--that component has at most one row--the join is lossless.--But you don't need to know that, you just have to use the theorem. Also you need to be told F is a cover--then tell us--or CKs can't be found. Another problem is "we have no CK"--every schema has a CK, since the set of all columns forms a superkey--and there are always the trivial FDs.--But you don't need to know that, you just have to use the definitions, theorems & algorithms for finding CKs. Also you need to find all the FDs of the closure of the cover you were given & then calculate the new CKs for each component using the FDs that have all their attributes in it. There's another theorem that says that those FDs of the closure are exactly the FDs that hold in the components. There could be FDs that are implied by the given ones & have all their attributes in a component even though the given ones don't.--But you don't need to know that, you just need to justify you have the CKs by justifying you have the FDs by using definitions, theorems & algorithms. But also the "property" theorem involves binary decompositions--so have you been told to assume--but not told us--that R = R1 JOIN (R2 JOIN R3) in that order? This is all clear from the theorems & algorithms & definitions of FD, cover, closure & CK but you need to memorize definitions & theorems exactly & then apply them precisely & tediously. That's all I just did.

Why do you have doubts in your questions in the 2 parts? Why are you not applying the "property" theorem? Why are you not addressing the fact that it is about binary joins?

If you are ever unsure of how to do an exercise that you have seen in your textbook that you know doesn't require creativity then you literally don't know what you are doing so go back in your textbook & find out.

Usually when I see good ol' F or another set or list of FDs in a quoted database normalization assignment without explanation I try to work towards an answerable post by commenting a variant of this:

What does "I have these FDs" mean? "These are all the FDs that hold"?--Not possible. "These are all the non-trivial FDs that hold"?--Not possible. "These are some FDs that hold"?--Question can't be answered. Find out what a cover is & what the exact conditions are to apply a particular definition/rule/algorithm. To determine CKs & NFs we must be given FDs that form a cover. Sometimes a minimal/irreducible cover. And the set of all attributes must given. See this answer at What is the minimal proof that a database relation is not in BCNF?

Upvotes: 1

Related Questions