In relational database theory, a functional dependency (FD) is constraint between two attribute sets, whereby values in one set (the determinant set) determine the values of the other set (the dependent set). A functional dependency between a determinant set X and a dependent set Y can be described as follows: Given a relation R and attribute sets X,Y ⊆ {\displaystyle \subseteq } R, then X is said to functionally determine Y (written X → Y) if each X value is associated with precisely one Y value. R is then said to satisfy the functional dependency X → Y. Equivalently, the projection Π X , Y R {\displaystyle \Pi _{X,Y}R} is a function, that is, Y is a function of X. In other words:
when X attributes have known values (here, x), the values for their corresponding Y attributes can be determined by looking them up in any tuple of R containing x. two tuples sharing the same values of X will necessarily have the same values of Y. A dependency FD: X → Y means that the values of Y are determined by the values of X. A functional dependency FD: X → Y 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. A simple application of functional dependencies is Heath's theorem; it says that a relation R over an attribute set U and satisfying a functional dependency X → Y can be safely split in two relations having the lossless-join decomposition property, namely into Π X Y ( R ) ⋈ Π X Z ( R ) = R {\displaystyle \Pi _{XY}(R)\bowtie \Pi _{XZ}(R)=R} where Z = U − XY are the rest of the attributes. (Unions of attribute sets are customarily denoted by their juxtapositions in database theory.) An important notion in this context is a candidate key, defined as a minimal set of attributes that functionally determine all of the attributes in a relation. 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. A notion of logical implication is defined for functional dependencies in the following way: a set of functional dependencies Σ {\displaystyle \Sigma } logically implies another set of dependencies Γ {\displaystyle \Gamma } , if any relation R satisfying all dependencies from Σ {\displaystyle \Sigma } also satisfies all dependencies from Γ {\displaystyle \Gamma } ; this is usually written Σ ⊨ Γ {\displaystyle \Sigma \models \Gamma } . The notion of logical implication for functional dependencies admits a sound and complete finite axiomatization, known as Armstrong's axioms.
Examples
Cars 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.
Lectures 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. If a row was added where the student had a different value of semester, then 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.
Employee department 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 Name. 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.
Properties and axiomatization 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 the following, usually called Armstrong's axioms:
… excerpt ends here. Continue reading the full article.
