Rules About Functional Dependencies

Rules About Functional Dependencies

In this section, we shall learn how to reason about FD's. That is, suppose we are told of a set of FDs that a relation satisfies. Sometimes, we can deduce that the relation must satisfy certain other FD's. This ability to find out additional FD's is important when we discuss the design of good relation schemas in "Design of Relational Database Schemas".

Example : If we are told that a relation R with attributes A, B, and C, satisfies the FD's A → B and B → C, then we can deduce that R also satisfies the FD A → C.  How does that reasoning go? To prove that A → C, we must take into account two tuples of R that agree on A and prove they also agree on C.

Let the tuples agreeing on attribute A be (a, b1,c1) and (a, b2,c2). We assume the order of attributes in tuples is A, B, C. Since R satisfies A → B, and these tuples agree on A, they must also agree on B. That is, b1 = b2, and the tuples are really (a, b, c1) and (a, b, c2), where b is both b1 and b2. Likewise, since R satisfies B → C, and the tuples agree on B, they agree on C. In this way, c1 = c2; i.e., the tuples do agree on C. We have proved that any two tuples of R that agree on A also agree on C, and that is the FD A  → C.

FD's often can be presented in various different ways, without changing the set of legal instances of the relation. We say:

●  Two sets of FD's S and T are equivalent if  the set of relation instances satisfying S is exactly the same as the set of relation instances satisfying T.

●  More generally, a set of FD's S follows from a set of FDs T if every relation instance that satisfies all the FD's in T also satisfies all the FD's in S

Note then that two sets of FD's S and T are equivalent if and only if S follows from T, and T follows from S.

In this section we shall see various useful rules about FD's. Generally, these rules let us replace one set of FD's by an equivalent set, or to add to a set of FD's others that follow from the original set. An example is the transitive rule that lets us follow chains of FD's, as in above example. We shall also give an algorithm for answering the general question of whether one FD follows from one or more other FD's.



Tags