Functional dependency

A functional dependency is a constraint between two sets of attributes in a relation from a database.

An attribute or set of attributes X is said to functionally determine another attribute Y (written <math>X\to Y<math>) if and only if each X value is associated with at most one Y value. Customarily we call X determinant set and Y a dependent set.

So if we are given the value of X we can determine the value of Y.

(Note: the "function" being discussed in "functional dependency" is the function of identification.)

A functional dependency FD:<math>X\to Y<math> is called trivial if Y is a subset of X.

The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization. The functional dependencies, along with the attribute domains, are selected so as to generate constraints that would exclude as much data inappropriate to the user domain from the system as possible.

For example, suppose one is designing a system to track vehicles and the capacity of their engines. Each vehicle has a unique vehicle identification number (VIN). One would write:

<math>\mbox{VIN}\,\to\,\mbox{EngineCapacity}<math>

because it would be inappropriate for a vehicle's engine to have more than one capacity. (Assuming, in this case, that vehicles only have one engine.) However,

<math>\mbox{EngineCapacity}\,\not \to\,\mbox{VIN}<math>

because there could be many vehicles with the same engine capacity.

This functional dependency may suggest that the attribute EngineCapacity be placed in a relation with candidate key VIN. However, that may not always be appropriate. For example, if that functional dependency occurs as a result of the transitive functional dependencies

<math>\mbox{VIN}\,\to\,\mbox{VehicleModel}, \mbox{VehicleModel}\,\to\,\mbox{EngineCapacity},<math>

then that would not result in a normalized relation.

Irreducible function depending set

A functional depending set S is irreducible if the set has three following properties:

I. Each right set of a functional dependency of S contains only one attribute.

II. Each left set of a functional dependency of S is irreducible. It means that reducing any one attribute from left set won't change the content of S(S will lose some information).

III. Reducing any functional dependency will change the content of S.

Functional dependency inference rules

Reflexivity:

If B is a subset of A then A functionally determines B

For example:

{name, location} -> {name}

Augmentation:

If B is a subset of A and C functionally determines D then A and C functionally determine B and D

For example:

{name, location} and {birthdate, time} -> {name} and {age}

(as {name} is a subset of {name, location} and {birthdate, time} functionally determines {age})

Transitivity:

If A functionally determines B and B functionally determines C then A functionally determines C

For example:

{name, location} -> {initials}

(as {name, location} functionally determines {name} and {name} functionally determines {initials})

Pseudo transitivity:

If A functionally determines B and B and C functionally determine D then A and C functionally determine D

Union:

If A functionally determines B and A functionally determines C then A functionally determines B and C

For example:

{name, location, birthdate, time} -> {initials, age}

(as {name, location, birthdate, time} -> {intials} and {name, location, birthdate, time} -> {age})

Decomposition:

If A functionally determines B and C then A functionally determines B and A functionally determines C

For example:

{name, location, birthdate, time} -> {initals, age} implies that {name, location, birthdate, time} -> {initials} and {name, location, birthdate, time} -> {age}