Relational Theory – Closure of a Family of Functional Dependencies

dependenciesrelational-theory

I have some issues to determine what a closure F of a family of functional dependencies is.

I know its definition is

F⁺= {X → Y\F⊨X → Y}

One example

Let be the following relation

R(Student,Examination, Date) with the following set of functional dependencies:

F={D,St → Ex, Ex → D}

The relation is decomposed in R¹(St,Ex) R²(Ex,D)

Why is F¹= ∅ but F²={Ex → D}? I would have made: F²= ∅ from the definition of F⁺

I know from the community wiki that

Functional dependencies requires that they must hold for every
possible instance.

From an instance, you cannot find the functional dependencies that hold in a certain relation schema

Therefore I don't know how to know what is the closure of a family of functional dependencies.

Another example would have been:

Second example

R(Course,Student,Birthday,Grade)

with the following set of functional dependencies:

F={C,St → G, St → B}

And the following relations:

R¹(C,St,G) and R²(St,B)

F¹{C,St → G} and R²(St → B) I would have done, from the definition:

F¹=F²=∅

Best Answer

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

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

  2. The projection of the set of dependencies F, over the decomposition of R. By definition, this projection is, for each Ri, the set of all the dependencies of F+ that have all the attributes in Ri (and is represented as πRi(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 Ri, so we are sure that such dependency holds in Ri. 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 R2 = (Ex, D), we can see immediately that in the dependency Ex → D holds in R2, since all its attributes are contained in R2, while the first dependency cannot hold neither in R1 and R2, since it has three attributes. Actually, in relation R1, you have neither the first, nor the second dependency (only trivial dependencies from F+ are present in R1, 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 πRi(F), there is an efficient polynomial algorithm to see if a certain decomposition preserves the dependencies, in other words, if ∪πRi(F) is a cover of F+. You can see more details in this answer.

Related Question