Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Lossless decomposition vs Dependency Preservation

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?

like image 706
Aditya Naidu Avatar asked Sep 13 '16 07:09

Aditya Naidu


People also ask

What is lossless decomposition and dependency preservation?

Relation R is decomposed into two or more relations if decomposition is lossless join as well as dependency preserving. Lossless Join Decomposition. If we decompose a relation R into relations R1 and R2, Decomposition is lossy if R1 ⋈ R2 ⊃ R. Decomposition is lossless if R1 ⋈ R2 = R.

What is dependency preserving decomposition?

Dependency Preserving In the dependency preservation, at least one decomposed table must satisfy every dependency. If a relation R is decomposed into relation R1 and R2, then the dependencies of R either must be a part of R1 or R2 or must be derivable from the combination of functional dependencies of R1 and R2.

Is it possible that a lossless decomposition does not exhibit dependency preservation?

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.

What is meant by lossless decomposition?

In database design, a lossless join decomposition is a decomposition of a relation into relations. such that a natural join of the two smaller relations yields back the original relation. This is central in removing redundancy safely from databases while preserving the original data.

Is the decomposition lossless or dependency preserving?

Hence the decomposition is not lossless. For dependency preserving decomposition, A->B can be ensured in R1 (AB) and C->D can be ensured in R2 (CD). Hence it is dependency preserving decomposition. So, the correct option is C. This article is contributed by Sonal Tuteja.

What is the difference between dependency preserving and lossless join?

Regarding dependency preserving, a decomposition of relation R is dependency preserving if the Functional dependency of R can be obtained by taking the union of the functional dependency of all the decomposed relation. Show activity on this post. Lossless Join doesn't mean that any of the tuples are lost, or cannot be recovered after a join.

What is Lossless Join Decomposition?

Lossless Join Decomposition: The lossless join property is a feature of decomposition supported by normalization. It is the ability to ensure that any instance of the original relation can be identified from corresponding instances in the smaller relations.

What is the point of dependency preservation?

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?


1 Answers

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.

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.

like image 178
Renzo Avatar answered Oct 22 '22 10:10

Renzo