Show that functional dependency pseudotransivity holds using closure test

dependenciesrelational-theory

I'm currently studying a basic database course with the course literature Database Systems – The Complete Book¹.

In one of the book's exercises you are asked to

Show that the following rules hold, by using the closure test.

This is the closure test described in the book:

And the question I'm having trouble with is as follows:

How can I show that the rules hold? Can I do it by computing the closures of the relevant attributes somehow prove that?

Thank you in advance!

^{¹ Garcia-Molina, H. & Ullman, J. D. & Widom, J. (2009). Database Systems – The Complete Book, Second Edition. Pearson Education Inc., Upper Saddle River, NJ, USA.}

Best Answer

The definition of Pseudotransitivity given above is equivalent to say the following.

From:

(1) A1 A2 ... An -> B1 B2 ... Bm
(2) B1 B2 ... Bm E1 E2 ... Ej -> D

we can derive:

(3) A1 A2 ... An E1 E2 ... Ej -> D

Here is a possible simple proof.

Let’s try to compute the closure of {A1 A2 ... An E1 E2 ... Ej} from the first two functional dependencies. If this closure contains D then we have proved the hypothesis.

{A1 A2 ... An E1 E2 ... Ej}+ = A1 A2 ... An E1 E2 ... Ej    (starting point)
{A1 A2 ... An E1 E2 ... Ej}+ = A1 A2 ... An B1 B2 ... Bm E1 E2 ... Ej (by using 1)
{A1 A2 ... An E1 E2 ... Ej}+ = A1 A2 ... An B1 B2 ... Bm D E1 E2 ... Ej (by using 2)
No other derivation is possible.

So, since D is included in the closure of {A1 A2 ... An E1 E2 ... Ej}, we have shown that A1 A2 ... An E1 E2 ... Ej -> D.

Related Solutions

Database functional dependency candidate keys

If you're talking about identifying candidate keys for relational synthesis you need to know the dependencies. If you have the functional dependencies you can use the relational synthesis algorithm; a synopsis of which can be found here.

Note, if this is a homework question please mark it as such in the tags.

Relational Theory – Closure of a Family of Functional Dependencies

When you have a relation R with a set of functional dependencies F and a decomposition of R in R₁...R_n, you must consider two different concepts:

The closure of the set of functional dependencies F. This closure, called F⁺, is the set of all the dependencies derived from F, by applying, until possible, a set of rules called “Armstrong’s axioms”. This set can be very lange, (exponential with the number of dependencies of F), so in general it is not calculated. What can be calculated, instead, is a cover of it, which is a small number of dependencies from which F⁺ can be derived (and so which is equivalent to F⁺). This computation is useful, for instance, when you normalize a relation.
The projection of the set of dependencies F, over the decomposition of R. By definition, this projection is, for each R_i, the set of all the dependencies of F⁺ that have all the attributes in R_i (and is represented as π_{R_i}(F)). But, since we do not calculate F⁺, as said above, we cannot calculate such projection. What can be done in practice, in simple cases, is to see if there is some dependency in F that has all its attributes contained in R_i, so we are sure that such dependency holds in R_i. However, if in this way you don’t find a dependency in one of the decomposed relation, this is not a guarantee that such dependency is lost, since it could hold as consequence of other dependencies.

In your first example, you have two dependencies in F for the relation R(S, Ex, D):

D, St → Ex
Ex → D

So, consider R₂ = (Ex, D), we can see immediately that in the dependency Ex → D holds in R₂, since all its attributes are contained in R₂, while the first dependency cannot hold neither in R₁ and R₂, since it has three attributes. Actually, in relation R₁, you have neither the first, nor the second dependency (only trivial dependencies from F⁺ are present in R₁, like St → St).

In your second example, instead, the decomposed relations are such that in the first there are all the attributes of the first dependency, so it hold trivially in it, while in the second there are all the attributes of second dependency, and again you can be sure that this second dependency holds in the second relation.

Finally, note that, while it is no computationally feasible to calculate π_{R_i}(F), there is an efficient polynomial algorithm to see if a certain decomposition preserves the dependencies, in other words, if ∪π_{R_i}(F) is a cover of F⁺. You can see more details in this answer.

Best Answer

Related Solutions

Database functional dependency candidate keys

Relational Theory – Closure of a Family of Functional Dependencies

Related Question