0

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.)

philipxy
  • 14,867
  • 6
  • 39
  • 83
gbgult
  • 3
  • 3
  • You don't seem to understand that when some FDs hold, all the ones derivable by Armstrong's axioms hold, and for a decomposition to be preserving it has to preserve all of those, not just the ones you started with. Also you need to know *all* FDs that hold in order to say whether they are all preserved, so it's not enough to just know that given FDs hold, they have to form a cover. Etc. PS What is your textbook name & edition? We don't know "where you are going wrong" unless you tell us your entire process, so please give it, don't ask us to rewrite a textbook. – philipxy Jan 06 '19 at 22:31

1 Answers1

0

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.

Community
  • 1
  • 1
Renzo
  • 26,848
  • 5
  • 49
  • 61
  • is it true to state that if there is a key of the original relation inside one of the sub relations, the decomposition must be dependency preserving, because that key covers all dependencies? – DsCpp Jan 24 '19 at 11:26
  • @DsCpp, no, it is not correct, since there could be other dependencies on attributes different from the key. – Renzo Jan 24 '19 at 13:41