Search code examples
databasefunctional-dependencies

Is this decomposition dependency preserving?

I'm trying to figure out how to see if a decomposition is dependency preserving or not. The relation is: R(ABCDEF)and have the following FD's. AB -> CE,C -> EB,E -> D,C -> D. We then split the relation into: R1(BF), R2(ACB) and R3(CDE). Is this dependency preserving?

I was under the impression that to calculate this, you do a closure on all of the left sides of the FD's. This gives:

AB+ = ABCEBD which includes AB -> CE
C+ = CEBD which includes the FD's
E+ = ED which include E->D

So in my world, this is dependency preserving. However, according to the markings the answer is that it isn't. What am I doing wrong and/or misunderstanding about the concept?

I do understand that some of the dependencies don't hold in each decomposed relation. For example AB -> E since we can't find a relation which includes these three together. However, I though that since the closure of AB still includes E it would be dependency preserving anyway. Is this where I go wrong? What is an explanation of the concept? (My textbook is VERY brief.)

Solution

  • In brief: you are correct, the dependencies are preserved.

    Long explanation.

    To define the concept of dependencies preservation first we need to define the concept of projection of a set of functional dependencies:

    Given a schema R(T) with a set of dependencies F, and given a subset Ti of T, the projection of F on Ti is defined as:

    πTi = { X → Y ∈ F+ | X, Y ⊆ Ti}

    Note that we need to consider the dependencies of F+ (the closure of the dependency of F), not only those on F.

    We can now define the property of dependencies preservation for a decomposition:

    A decomposition ρ = {R1(T1), ..., Rn(Tn)} of R(T) with dependencies F preserves the dependencies if and only if ∪ πTi(F) ≡ F.

    This can be formally verified by applying an algorithm, described in books at least from 1983 (see for instance: Ullman, J. (1983). Principles of Database Systems. Computer Science Press, Rockville, Maryland), that computes in a polynomial time the closure of a set of attributes with respect to a projection of dependencies.

    In practice, in order to check that the dependencies are preserved in your example there is no need to apply that algorithm, but it is sufficient to compute a canonical cover of the dependencies:

    A B → C
C → B
C → E
E → D

    From it we can see that each dependency is contained in a decomposed relation, so we can conclude that the dependencies are preserved.

    Note that, when reasoning on a set of dependencies, it is always convenient to reason on a canonical cover of them.