0

In R(A,B,C, D), let the dependencies be

A->B 
B->C 
C->D 
D-> B

the decomposition of R into (A,B), (B,C) and (B,D) is lossless or dependency preserving?

My attempt : (A,B) and (B,C) can be combined lossless-ly because of B->C. However, for (A,B,C) and (B,D), B does not form a key for either. Hence the decomposition in lossy.

Also for dependency preserving, the relation (C-D) can't be gotten from any of the decomposed relations and hence the decomposition is not dependency preserving.

However the answer given is that the decomposition is both lossless and dependency preserving. So where am I wrong?

Also the key for relation R is only {A} isn't it?

philipxy
  • 14,867
  • 6
  • 39
  • 83
user2277550
  • 553
  • 7
  • 22
  • Your "I have these FDs" doesn't make sense. "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.](https://stackoverflow.com/a/53386492/3404097) Eg "B does not form a key for either"--false. – philipxy Jan 09 '21 at 02:34
  • Does this answer your question? [What is the minimal proof that a database relation is not in BCNF?](https://stackoverflow.com/questions/53386095/what-is-the-minimal-proof-that-a-database-relation-is-not-in-bcnf) – philipxy Jan 09 '21 at 02:45
  • Please ask 1 question. Give reasoning clearly--to have any chance at solving, to communicate & to justify that you put in reasonable research effort. Connect claims to definitions & theorems you give via small clearly justified steps. Eg "because of B->C" & "B does not form a key for either"--Why? "the relation (C-D) can't be gotten"--Unclear. Whatever you mean, how does that fit into determining losslessness? PS If the given FDs form a cover then {A} is the only CK. But if you're not sure then ask about it as the 1 question of a separate post with reasoning up to being stuck/unsure. – philipxy Jan 09 '21 at 03:13

1 Answers1

2
  1. You say:

However, for (A,B,C) and (B,D), B does not form a key for either. Hence the decomposition in lossy.

This is wrong, since B is a key for (B, D). We can see this by computing B+ from the original dependencies, assuming that they form a cover of the relation.

B+ = B
B+ = BC (for the dependency B->C)
B+ = BCD (for the dependency C->D)

so, since D is included in B+, we have that B->D can be derived from the original set of dependencies, and in the decomposition (B, D) B is a key (as it is D).

  1. To be dependency preserving we must check that the union of all the projected dependencies of the decomposition is a cover of the original set of dependencies. Since three covers of the decomposed relations are, respectively, {A->B}, {C->B, B->C} and {D->B, B->D}, by uniting those three sets you can easily derive also D->C as well as C->D, so the dependencies are preserved.

  2. Finally, yes {A} is the unique candidate key of the original relation.

Renzo
  • 26,848
  • 5
  • 49
  • 61