Consider a relation R that has two attributes A and B. The attribute B of the relation is functionally dependent on the attribute A if and only if for each value of A no more than one value of B is associated. In other words, the value of attribute A uniquely determines the value of B and if there were several tuples that had the same value of A then all these tuples will have an identical value of attribute B. That is, if t1 and t2 are two tuples in the relation R and
t1(A) = t2(A) then we must have t1(B) = t2(B).

A and B need not be single attributes. They could be any subsets of the attributes of a relation R (possibly single attributes). We may then write

R.A -> R.B

if B is functionally dependent on A (or A functionally determines B). Note that functional dependency does not imply a one-to-one relationship between A and B although a one-to-one relationship may exist between A and B.

A simple example of the above functional dependency is when A is a primary key of an entity (e.g. student number) and A is some single-valued property or attribute of the entity (e.g. date of birth). A -> B then must always hold. (why?)

Functional dependencies also arise in relationships. Let C be the primary key of an entity and D be the primary key of another entity. Let the two entities have a relationship. If the relationship is one-to-one, we must have C -> D and D -> C. If the relationship is many-to-one, we would have C -> D but not D -> C. For many-to-many relationships, no functional dependencies hold. For example, if C is student number and D is subject number, there is no functional dependency between them. If however, we were storing marks and grades in the database as well, we would have

(student_number, subject_number) -> marks

and we might have

marks -> grades

The second functional dependency above assumes that the grades are dependent only on the marks. This may sometime not be true since the instructor may decide to take other considerations into account in assigning grades, for example, the class average mark.

For example, in the student database that we have discussed earlier, we have the following functional dependencies:

sno -> sname
sno -> address
cno -> cname
cno -> instructor
instructor -> office

These functional dependencies imply that there can be only one name for each sno, only one address for each student and only one subject name for each cno. It is of course possible that several students may have the same name and several students may live at the same address. If we consider cno -> instructor, the dependency implies that no subject can have more than one instructor (perhaps this is not a very realistic assumption). Functional dependencies therefore place constraints on what information the database may store. In the above example, one may be wondering if the following FDs hold

sname -> sno
cname -> cno

Certainly there is nothing in the instance of the example database presented above that contradicts the above functional dependencies. However, whether above FDs hold or not would depend on whether the university or college whose database we are considering allows duplicate student names and subject names. If it was the enterprise policy to have unique subject names than cname -> cno holds. If duplicate student names are possible, and one would think there always is the possibility of two students having exactly the same name, then sname -> sno does not hold.

Functional dependencies arise from the nature of the real world that the database models. Often A and B are facts about an entity where A might be some identifier for the entity and B some characteristic. Functional dependencies cannot be automatically determined by studying one or more instances of a database. They can be determined only by a careful study of the real world and a clear understanding of what each attribute means.

We have noted above that the definition of functional dependency does not require that A and B be single attributes. In fact, A and B may be collections of attributes. For example

(sno, cno) -> (mark, date)

When dealing with a collection of attributes, the concept of full functional dependence is an important one. Let A and B be distinct collections of attributes from a relation R end let R.A -> R.B. B is then fully functionally dependent on A if B is not functionally dependent on any subset of A. The above example of students and subjects would show full functional dependence if mark and date are not functionally dependent on either student number ( sno) or subject number ( cno) alone. The implies that we are assuming that a student may have more than one subjects and a subject would be taken by many different students. Furthermore, it has been assumed that there is at most one enrolment of each student in the same subject.

The above example illustrates full functional dependence. However the following dependence

(sno, cno) -> instructor

is not full functional dependence because cno -> instructor
holds.

As noted earlier, the concept of functional dependency is related to the concept of candidate key of a relation since a candidate key of a relation is an identifier which uniquely identifies a tuple and therefore determines the values of all other attributes in the relation. Therefore any subset X of the attributes of a relation R that satisfies the property that all remaining attributes of the relation are functionally dependent on it (that is, on X), then X is candidate key as long as no attribute can be removed from X and still satisfy the property of functional dependence. In the example above, the attributes (sno, cno) form a candidate key (and the only one) since they functionally determine all the remaining attributes.

Functional dependence is an important concept and a large body of formal theory has been developed about it. We discuss the concept of closure that helps us derive all functional dependencies that are implied by a given set of dependencies. Once a complete set of functional dependencies has been obtained, we will study how these may be used to build normalised relations.

Copyright © 1996 Gopal Gupta. All rights reserved.

Back Contents Next