FUNCTIONAL DEPENDENCY (FD) INTRODUCTION Database Management System

FUNCTIONAL DEPENDENCY (FD) INTRODUCTION

FUNCTIONAL DEPENDENCY (FD) INTRODUCTION Database Management System : Functional Dependencies plays an important role in database design process. They are core to any RDBMS design. Normalization is totally based on FD.

Definition: A functional dependency is a constraint between two sets of attributes from the database. A functional dependency occurs when one attribute in a relation uniquely determines another attribute. This can be written A-B which would be the same as stating “B is functionally dependent upon A.”

Example: in a table listing employee characteristics including Employee Number (EN) and name, it can be said that “Name is functionally dependent upon EN” (or EN à name) because an employee’s name Can be uniquely determined from their EN. However, the reverse statement (name – EN) is not true because more than one employee can have the same name but different EN’s.

EN – NAME

1 – Amit

2 – Rohit

3 – Amit

 

Another Definition: Given a set of attributes R, and subsets X, Y of R, XàY is a functional dependency (read “X functionally determines Y” or “X determines Y”) if for any instance r of R, and tuples t1, t2, in r, whenever t1 [X] = t2 [X] then t1 [Y] = t2 [Y].

(We use t[X] to mean the “projection” of the tuple t on attributes X) A superkey (a superset of a key) is simply a set X such that XàR A key can now be defined, somewhat perversely, as a minimimal Superkey.

Formally, 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 Ano more than one value of Bis 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 Athen 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 Balthough 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.

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 Dis 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, thens 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) -> (mar, 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 atmost 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.