The Transitive Rule

The Transitive Rule

The transitive rule lets us cascade two FD's.

●  If  A1A2 . . . An → B1B2 . . . Bm and B1B2 . . . Bm → C1C2 . . . Ck hold in relation R, then A1A2 . . . An → C1C2 . . . Ck also holds in R.

If some of the C's are among the A's, we may remove them from the right side by the trivial-dependencies rule.

To see why the transitive rule holds, apply the test of "Computing the Closure of Attributes". To test whether A1A2 . . . An → C1C2 . . . Ck holds, we need to compute the closure {A1, A2, . . . ,An}+ with respect to the two given FD's.

The FD A1A2 . . . An → B1B2 . . . Bm tells us that all of B1, B2, . . . ,Bm are in {A1, A2, . . . ,An}+. Then, we can use the FD B1B2 . . . Bm → C1C2 . . . Ck to add C1, C2, . . . ,Ck to {A1,  A2 , . . . , An}+. Since all the C's are in

{A1, A2, . . . ,An}+
we conclude that A1A2 . . . An → C1C2 . . . Ck holds for any relation that satisfies both A1A2 . . . An → B1B2 . . . Bm and B1B2 . . . Bm  → C1C2 . . . Ck.

Closures and Keys

Example : Let us begin with the relation Movies of Figure (a) of "Combining Relations" that was constructed in Example (a) (of the same article) to represent the four attributes of entity set Movies, plus its relationship Owns with Studios. The relation and some sample data is

Suppose we decided to represent some data about the owning studio in this same relation. For simplicity, we shall add only a city for the studio, representing its address. The relation might then look like

Two of the FD's that we might sensibly claim to hold are:

title year  studioName

The first is justified because the Owns relationship is many-one. The second is justified because the address is an attribute of Studios, and the name of the studio is the key of Studios.

The transitive rule allows us to combine the two FD's above to get a new FD:

title year studioAddr

This FD says that a title and year (i.e., a movie) determines an address - the address of the studio owning the movie.