5

Does anyone of them implies the other?

My logic is that if all dependencies are preserved, then there is no loss of information and similarly, if decomposition is lossless then no functional dependency must have been violated.

So essentially, dependency preservation is a way to ensure that your decomposition is lossless.

I am having a hard time accepting/denying it. So do both of these guarantee one another or are there cases where one can be achieved without the other?

Aditya Naidu
  • 697
  • 2
  • 7
  • 18
  • Your words & arguments too vague to follow or critique. There are neither clear claims with correct use of appropriate technical terms nor clear connection between claims justifying that they follow from definitions & earlier claims. – philipxy Oct 17 '22 at 21:44

1 Answers1

7

In general these are two independent things: you can have a lossless decomposition without dependency preservation, as well as a decomposition that preserves the dependencies but that is not lossless.

Here an example of this fact.

Given the relation:

R (A B C D)

with a cover of the functional dependencies:

F = {A B → C, C → B, D → C}

The decomposition:

R1 = (A B C)
R2 = (C D)

preserves the functional dependences but is not a lossless decomposition (if you join R1 and R2 you obtain more tuples that the original relation).

On the other hand, the decomposition:

R1 (A C D)
R2 (B C D)

is lossless but does not preserve the functional dependencies (in this case A B → C is not preserved).

So, the answer to your first question is no, none of them implies the other.

However, these two properties can be “connected” by the following basic result, that gives a sufficient (even if not necessary) condition to establish if a dependency preserving decomposition is also lossless:

Let ρ = {R(Ti,Fi)} a decomposition of a relation schema R(T,F) that preserves the dependencies. If, for some j, Tj is a superkey of R(T,F), then the decomposition ρ is lossless.

Actually, this property is applied in the last step of the “synthesis” algorithm that decompose a relation in 3NF: if no schema obtained in the previous steps contains a superkey of the original relation, then add a new schema with any candidate key of the original relation.

This guarantees that the algorithm produces a decomposition which is both lossless and preserves the dependencies, while, on the other hand, it is known that the “analysis” algorithm to decompose a relation in BCNF can produce, in some cases, the loss of functional dependencies.

So the following decomposition in 3NF of the previous relation is both lossless and preserves the dependencies (notes R3 containing the only candidate key of R):

R1 (A B C)
R2 (C D)
R3 (A D)

but the relation R1 is not in BCNF because of the dependency C → B (while the only candidate key of R1 is {A B}.

Renzo
  • 26,848
  • 5
  • 49
  • 61
  • For anybody else that almost understands the yellow part (like me), I believe http://stackoverflow.com/a/26816032/2550406 says the same thing in the grey block. Helped me to understand this a lot better – lucidbrot Mar 30 '17 at 09:33
  • 1
    @lucidbrot, the two things are different. The gray part in the linked answer gives a condition to be satisfied if the decomposition must be lossless. In the yellow part of the above answer, instead, I cite a theorem that says the condition that must hold for lossless decomposition, **when a decomposition already preserves the dependencies**. And in fact the question was exactly about this subject, “Lossless decomposition vs Dependency Preservation”, while in the aswer that you linked the two properties are not related. So you can see that the two answers concerns different facts. – Renzo Mar 31 '17 at 14:13
  • "The gray part in the linked answer gives a condition to be satisfied if the decomposition must be lossless." Reversed. It gives a condition that implies the decomposition must be lossless. (It's not necessary, it's sufficent.) (We can sometimes losslessly decompose when the common columns are {} & it isn't a CK of either component.) – philipxy Feb 01 '23 at 12:16
  • (Maybe it's (sufficient &) necessary when the only JDs in the join are (binary &) implied by the FDs? Maybe that's demonstrated by the BCNF algorithm that extracts FDs?) – philipxy Feb 01 '23 at 12:33