Closing Sets of Functional Dependencies

Closing Sets of Functional Dependencies

As we have seen, given a set of FD's, we can sometimes infer some other FD's, including both trivial and nontrivial FD's. We shall, in later sections, want to differentiate between given FD's that are stated initially for a relation and derived FD's that are inferred using one of the rules of this section or by using the algorithm for closing a set of attributes. 

Furthermore, we often have a choice of which FD's we use to represent the full set of FD's for a relation. Any set of given FD's from which we can infer all the FD's for a relation will be called a basis for that relation. If no proper subset of the FD's in a basis can also derive the complete set of FD's, then we say the basis is minimal.

Example : Think about a relation R(A, B, C) such that each attribute functionally determines the other two attributes. The full set of derived FD's thus includes six FD's with one attribute on the left and one on the right; A → B, A → C, B → A, B → C, C → A, and C → B. It also contains the three nontrivial FD's with two attributes on the left: AB → C,  AC → B, and BC → A. There are also the shorthands for pairs of FD's such as A → BC, and we might also contain the trivial FD's such as A → A or FD's like AB → BC that are not completely nontrivial (although in our strict definition of what is a FD we are not required to list trivial or partially trivial FD's, or dependencies that have various attributes on the right.

This relation and its FD's have various minimal bases. One is

{A → B, B → A, B → C, C → B}

Another is

{A → B, B → C, C → A}

There are many other bases, even minimal bases, for this example relation, and we leave their discovery as an exercise.



Tags