Functional Dependencies

The single most important concept in relational schema designtheory is that of a functional dependency.

Definition of Functional Dependency
A functional dependency is a constraint between two sets of attributes from the database. Suppose that our relational database schema has n attributes A1, A2, ..., An.
If we think of the whole database as being described by a single universal relation schema R = {A1, A2, ... , An}.
A functional dependency, denoted by X ??Y, between two sets of attributes X and Y that are subsets of R, such that any two tuples t1 and t2 in r that have t1[X] = t2[X], they must also have t1[Y] = t2[Y].

This means that the values of the Y component of a tuple in r depend on, or are determined by, the values of the X component; We say that the values of the X component of a tuple uniquely (or functionally) determine the values of the Y component.
We say that there is a functional dependency from X to Y, or that
Y is functionally dependent on X.
Functional dependency is represented as FD or f.d. The set of attributes X is called the left-hand side of the FD, and Y is called the right-hand side.

X functionally determines Y in a relation schema R if, and only if, whenever two tuples of r(R) agree on their X-value, they must necessarily agree on their Y-value.
If a constraint on R states that there cannot be more than one tuple with a given X-value in any relation instance r(R)—that is, X
is a candidate key of R— this implies that X ?Y for any subset of attributes Y of R.
If X is a candidate key of R, then X?R.
If X?Y in R, this does not imply that Y?X in R.

A functional dependency is a property of the semantics or meaning of the attributes.
Whenever the semantics of two sets of attributes in R indicate that a functional dependency should hold, we specify the dependency as a constraint.

Legal Relation States:
Relation extensions r(R) that satisfy the functional dependency constraints are called legal relation states (or legal extensions) of R.
Functional dependencies are used to describe further a relation schema R by specifying constraints on its attributes that must hold at all times.

Certain FDs can be specified without referring to a specific relation, but as a property of those attributes given their commonly understood meaning.
For example, {State, Driver_license_number} ??Ssn should hold for any adult in the United States and hence should hold whenever these attributes appear in a relation.
Consider the relation schema EMP_PROJ from the semantics of the attributes and the relation; we know that the following functional dependencies should hold:

a. Ssn?Ename
b. Pnumber ?{Pname, Plocation}
c. {Ssn, Pnumber}?Hours
A functional dependency is a property of the relation schema R, not of a particular legal relation state r of R. Therefore, an FD cannot be inferred automatically from a given relation extension r but must be defined explicitly by someone who knows the semantics of the attributes of R.

Teacher Course Text
Smith Data Structures Bartram
Smith Data Management Martin
Hall Compilers Hoffman
Brown Data Structures Horowitz

?
Example:

A B C D
a1 b1 c1 d1
a1 b2 c2 d2
a2 b2 c2 d3
a3 b3 c4 d3

The following FDs may hold because the four tuples in the current extension have no violation of these constraints:
B ??C; C ??B; {A, B} ??C; {A, B} ??D; and {C, D} ??B

However, the following do not hold because we already have violations of them in the given extension:
A ??B (tuples 1 and 2 violate this constraint); B ??A (tuples 2 and 3 violate this constraint); D?C (tuples 3 and 4 violate it). Diagrammatic notation for displaying FDs:
Each FD is displayed as a horizontal line. The left-hand-side attributes of the FD are connected by vertical lines to the line representing the FD, while the right-hand-side attributes are connected by the lines with arrows pointing toward the attributes.