Functional dependency

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 VIN → EngineCapacity 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.) On the other hand, EngineCapacity → VIN is incorrect 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 VIN → VehicleModel and VehicleModel → EngineCapacity then that would not result in a normalized relation.

This example illustrates the concept of functional dependency. The situation modelled is that of college students visiting one or more lectures in each of which they are assigned a teaching assistant (TA). Let's further assume that every student is in some semester and is identified by a unique integer ID.

We notice that whenever two rows in this table feature the same StudentID, they also necessarily have the same Semester values. This basic fact can be expressed by a functional dependency:

• StudentID → Semester.

Note that if a row was added where the student had a different value of semester that the functional dependency, FD, would no longer exist. This means that the FD is implied by the data as it is possible to have values that would invalidate the FD.

Other nontrivial functional dependencies can be identified, for example:

• {StudentID, Lecture} → TA
• {StudentID, Lecture} → {TA, Semester}

The latter expresses the fact that the set {StudentID, Lecture} is a superkey of the relation.

A classic example of functional dependency is the employee department model.

This case represents an example where multiple functional dependencies are embedded in a single representation of data. Note that because an employee can only be a member of one department, the unique ID of that employee determines the department.

• Employee ID → Employee Name
• Employee ID → Department ID

In addition to this relationship, the table also has a functional dependency through a non-key attribute

• Department ID → Department Name

This example demonstrates that even though there exists a FD Employee ID → Department ID - the employee ID would not be a logical key for determination of the department ID. The process of normalization of the data would recognize all FDs and allow the designer to construct tables and relationships that are more logical based on the data.

Closure of a set of attributes X with respect to ${\displaystyle F}$ is the set X⁺ of all attributes that are functionally determined by X using ${\displaystyle F}$⁺.

Imagine the following list of FDs. We are going to calculate a closure for A from this relationship.

1. A → B
2. B → C
3. AB → D

The closure would be as follows:

a) A → A (by Armstrong's reflexivity)
b) A → AB (by 1. and (a))
c) A → ABD (by (b), 3, and Armstrong's transitivity)
d) A → ABCD (by (c), and 2)

The closure is therefore A → ABCD. By calculating the closure of A, we have validated that A is also a good candidate key as its closure is every single data value in the relationship.

Definition: ${\displaystyle F}$ covers ${\displaystyle G}$ if every FD in ${\displaystyle G}$ can be inferred from ${\displaystyle F}$. ${\displaystyle F}$ covers ${\displaystyle G}$ if ${\displaystyle G}$⁺ ⊆ ${\displaystyle F}$⁺
Every set of functional dependencies has a canonical cover.

Two sets of FDs ${\displaystyle F}$ and ${\displaystyle G}$ over schema ${\displaystyle R}$ are equivalent, written ${\displaystyle F}$ ≡ ${\displaystyle G}$, if ${\displaystyle F}$⁺ = ${\displaystyle G}$⁺. If ${\displaystyle F}$ ≡ ${\displaystyle G}$, then ${\displaystyle F}$ is a cover for ${\displaystyle G}$ and vice versa. In other words, equivalent sets of functional dependencies are called covers of each other.

A set ${\displaystyle F}$ of FDs is nonredundant if there is no proper subset ${\displaystyle F'}$ of ${\displaystyle F}$ with ${\displaystyle F'}$ ≡ ${\displaystyle F}$. If such an ${\displaystyle F'}$ exists, ${\displaystyle F}$ is redundant. ${\displaystyle F}$ is a nonredundant cover for ${\displaystyle G}$ if ${\displaystyle F}$ is a cover for ${\displaystyle G}$ and ${\displaystyle F}$ is nonredundant.
An alternative characterization of nonredundancy is that ${\displaystyle F}$ is nonredundant if there is no FD X → Y in ${\displaystyle F}$ such that ${\displaystyle F}$ - {X → Y} ${\displaystyle \models }$ X → Y. Call an FD X → Y in ${\displaystyle F}$ redundant in ${\displaystyle F}$ if ${\displaystyle F}$ - {X → Y} ${\displaystyle \models }$ X → Y.

An important property (yielding an immediate application) of functional dependencies is that if R is a relation with columns named from some set of attributes U and R satisfies some functional dependency X → Y then ${\displaystyle R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$ where Z = U − XY. Intuitively, if a functional dependency X → Y holds in R, then the relation can be safely split in two relations alongside the column X (which is a key for ${\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)}$) ensuring that when the two parts are joined back no data is lost, i.e. a functional dependency provides a simple way to construct a lossless join decomposition of R in two smaller relations. This fact is sometimes called Heaths theorem; it is one of the early results in database theory.[8]

Heath's theorem effectively says we can pull out the values of Y from the big relation R and store them into one, ${\displaystyle \Pi _{XY}(R)}$, which has no value repetitions in the row for X and is effectively a lookup table for Y keyed by X and consequently has only one place to update the Y corresponding to each X unlike the "big" relation R where there are potentially many copies of each X, each one with its copy of Y which need to be kept synchronized on updates. (This elimination of redundancy is an advantage in OLTP contexts, where many changes are expected, but not so much in OLAP contexts, which involve mostly queries.) Heath's decomposition leaves only X to act as a foreign key in the remainder of the big table ${\displaystyle \Pi _{XZ}(R)}$.

Functional dependencies however should not be confused with inclusion dependencies, which are the formalism for foreign keys; even though they are used for normalization, functional dependencies express constraints over one relation (schema), whereas inclusion dependencies express constraints between relation schemas in a database schema. Furthermore, the two notions do not even intersect in the classification of dependencies: functional dependencies are equality-generating dependencies whereas inclusion dependencies are tuple-generating dependencies. Enforcing referential constraints after relation schema decomposition (normalization) requires a new formalism, i.e. inclusion dependencies. In the decomposition resulting from Heath's theorem, there is nothing preventing the insertion of tuples in ${\displaystyle \Pi _{XZ}(R)}$ having some value of X not found in ${\displaystyle \Pi _{XY}(R)}$.

Normal forms are database normalization levels which determine the "goodness" of a table. Generally, the third normal form is considered to be a "good" standard for a relational database.

Normalization aims to free the database from update, insertion and deletion anomalies. It also ensures that when a new value is introduced into the relation, it has minimal effect on the database, and thus minimal effect on the applications using the database.