Functional Dependencies

Functional Dependencies

"From E/R Diagrams to Relational Designs" and "Converting Subclass Structures to Relations" showed us how to convert E/R designs into relational schemas. It is also possible for database designers to produce relational schemas directly from application requirements, although doing so can be difficult. Apart from how relational designs are produced, we shall see that often it is possible to improve designs systematically based on certain types of constraints. The most important type of constraint we use for relational schema design is a unique-value constraint called a "functional dependency" (often abbreviated FD). Knowledge of this type of constraint is very important for the redesign of database schemas to remove redundancy, as we shall see in "Design of Relational Database Schemas". There are also some other types of constraints that help us design good databases schemas. For example, multivalued dependencies are covered in "Multivalued Dependencies", and referential-integrity constraints are mentioned in "Constraints on Relations".

Definition of Functional Dependency

A functional dependency (FD) on a relation R is a statement of the form "if two tuples of R agree on attributes A1, A2,. .  .,An (i.e., the tuples have the same values in their respective components for each of these attributes), then they must also agree on another attribute, B". We write this FD formally as A1A2 . . . An → B and say that "A1, A2, . . . , An, functionally determine B".

If a set of attributes A1, A2, . . . , An, functionally determines more than one attribute, say

     A1A2An → B1
     A1A2An → B2
     A1A2An → Bm

then we can, as a shorthand, write this set of FD's as

     A1A2...An → B1B2...Bm

Figure 1 suggests what this FD tells us about any two tuples t and u in the relation R.

The effect of a functional dependency on two tuples.

Example : Let us consider the relation

Movies(title, year, length, filmType, studioName, starName)

from figure (b) of "Combining Relations", an instance of which we reproduce here as figure 2. There are various FDs that we can reasonably assert about the Movies relation. For example, we can assert the three FDs:

     title year → length
     title year → filmType
     title year → studioName

An instance of the relation Movies(title, year, length, filmType, studioName, starName)

Since the three FDs each have the same left side, title and year, we can summarize them in one line by the shorthand

title year → length filmType studioName

Informally, this set of FD's says that if two tuples have the same value in their title components, and they also have the  same value in their year components, then these two tuples must have the same values in their length components, the same values in their filmType components, and the same values in their studioName components. This assertion makes sense if we remember the original design from which this relation schema was developed. Attributes title and year form a key for the Movies entity set. Therefore, we expect that given a title and year, there is a unique movie. Therefore, there is a unique length for the movie and a unique film type. Further, there is a many-one relationship from Movies to Studios. Thus, we expect that given a movie there is only one owning studio.

On the other hand, we observe that the statement

title year → starName

is false; it is not a functional dependency. Given a movie, it is entirely possible that there is more than one star for the movie listed in our database.