Functional dependency

From Wikipedia, the free encyclopedia

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

Given a relation R, a set of attributes X in R is said to functionally determine another attribute Y, also in R, (written X → Y) if and only if each X value is associated with precisely one Y value. Customarily we call X the determinant set and Y the dependent attribute. Thus, given a tuple and the values of the attributes in X, one can determine the corresponding value of the Y attribute. For the purposes of simplicity, given that X and Y are sets of attributes in R, X → Y denotes that X functionally determines each of the members of Y - in this case Y is known as the dependent set. Thus, a candidate key is a minimal set of attributes that functionally determine all of the attributes in a relation.

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

A functional dependency FD: 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 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.) However, 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

then that would not result in a normalized relation.

[edit] Irreducible function depending set

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

1. Each right set of a functional dependency of S contains only one attribute.
2. Each left set of a functional dependency of S is irreducible. It means that reducing any one attribute from left set will change the content of S (S will lose some information).
3. Reducing any functional dependency will change the content of S.

Sets of functional dependencies with these properties are also called canonical or minimal.

[edit] Properties of functional dependencies

Given that X, Y, and Z are sets of attributes in a relation R, one can derive several properties of functional dependencies. Among the most important are Armstrong's axioms, which are used in database normalization:

• Subset Property (Axiom of Reflexivity): If Y is a subset of X, then X → Y
• Augmentation (Axiom of Augmentation): If X → Y, then XZ → YZ
• Transitivity (Axiom of Transitivity): If X → Y and Y → Z, then X → Z

From these rules, we can derive these secondary rules:

• Union: If X → Y and X → Z, then X → YZ
• Decomposition: If X → YZ, then X → Y and X → Z
• Pseudotransitivity: If X → Y and YZ → W, then XZ → W
• Accumulation: If X → YZ and Z → V, then X → YZV
• Extension: If X → Y and W → Z, then WX → YZ

Equivalent sets of functional dependencies are called covers of each other. Every set of functional dependencies has a canonical cover.

[edit] See also

• Multivalued dependency (MVD)