Functional dependency
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. In simple words, if X value is known, Y value is certainly known. 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.
|identification]].)
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
. The functional dependencies, along with the attribute domain
s, 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 VIN → VehicleModel and VehicleModel → EngineCapacity then that would not result in a normalized relation.
Sets of Functional Dependencies(FD) with these properties are also called canonical or minimal.
, which are used in database normalization:
From these rules, we can derive these secondary rules:
Equivalent sets of functional dependencies are called covers
of each other. Every set of functional dependencies has a canonical cover.
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:
Other nontrivial functional dependencies can be identified, for example:
The latter expresses the fact that the set {StudentID, Lecture} is a superkey
of the relation.
Dependency theory (database theory)
Dependency theory is a subfield of database theory which studies implication and optimization problems related to logical constraints, commonly called dependencies, on databases....
(FD) is a constraint between two sets of attributes in a relation
Relational model
The relational model for database management is a database model based on first-order predicate logic, first formulated and proposed in 1969 by Edgar F...
from a database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
.
Given a relation R, a set of attributes
Attribute (computing)
In computing, an attribute is a specification that defines a property of an object, element, or file. It may also refer to or set the specific value for a given instance of such....
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
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
and the values of the attributes in X, one can determine the corresponding value of the Y attribute. In simple words, if X value is known, Y value is certainly known. 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
Candidate key
In the relational model of databases, a candidate key of a relation is a minimal superkey for that relation; that is, a set of attributes such that# the relation does not have two distinct tuples In the relational model of databases, a candidate key of a relation is a minimal superkey for that...
is a minimal set of attributes that functionally determine all of the attributes in a relation.
|identification]].)
A functional dependency FD: X → Y is called trivial if Y is a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of X.
The determination of functional dependencies is an important part of designing databases in the relational model
Relational model
The relational model for database management is a database model based on first-order predicate logic, first formulated and proposed in 1969 by Edgar F...
, and in database normalization
Database normalization
In the design of a relational database management system , the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce smaller, well-structured relations...
and denormalization
Denormalization
In computing, denormalization is the process of attempting to optimise the read performance of a database by adding redundant data or by grouping data. In some cases, denormalisation helps cover up the inefficiencies inherent in relational database software...
. The functional dependencies, along with the attribute domain
Attribute domain
In computing, the attribute domain is the set of values allowed in an attribute.For example: Rooms in hotel Age Married Nationality...
s, 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
Vehicle identification number
A Vehicle Identification Number, commonly abbreviated to VIN, is a unique serial number used by the automotive industry to identify individual motor vehicles. VINs were first used in 1954...
(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
Candidate key
In the relational model of databases, a candidate key of a relation is a minimal superkey for that relation; that is, a set of attributes such that# the relation does not have two distinct tuples In the relational model of databases, a candidate key of a relation is a minimal superkey for that...
VIN. However, that may not always be appropriate. For example, if that functional dependency occurs as a result of the transitive
Transitivity (mathematics)
-In grammar:* Intransitive verb* Transitive verb, when a verb takes an object* Transitivity -In logic and mathematics:* Arc-transitive graph* Edge-transitive graph* Ergodic theory, a group action that is metrically transitive* Vertex-transitive graph...
functional dependencies VIN → VehicleModel and VehicleModel → EngineCapacity then that would not result in a normalized relation.
Irreducible function depending set
A functional depending set S is irreducible if the set has following three properties:- Each right set of a functional dependency of S contains only one attribute.
- 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).
- Reducing any functional dependency will change the content of S.
Sets of Functional Dependencies(FD) with these properties are also called canonical or minimal.
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 axiomsArmstrong's axioms
Armstrong's axioms are a set of axioms used to infer all the functional dependencies on a relational database. They were developed by William W. Armstrong on his paper. The axioms are sound in that they generate only functional dependencies in the closure of a set of functional dependencies when...
, 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 WY → Z, then WX → Z
Equivalent sets of functional dependencies are called covers
Cover (topology)
In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset. Formally, ifC = \lbrace U_\alpha: \alpha \in A\rbrace...
of each other. Every set of functional dependencies has a canonical cover.
Example
This example illustrates the concept of functional dependency. The situation modeledis 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.
| StudentID | Semester | Lecture | TA |
|---|---|---|---|
| 1234 | 6 | Numerical Methods | John |
| 2380 | 4 | Numerical Methods | Peter |
| 1234 | 6 | Visual Computing | Amina |
| 1201 | 4 | Numerical Methods | Peter |
| 1201 | 4 | Physics II | Simone |
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.
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
Superkey
A superkey is defined in the relational model of database organization as a set of attributes of a relation variable for which it holds that in all relations assigned to that variable, there are no two distinct tuples that have the same values for the attributes in this set...
of the relation.
See also
- Multivalued dependencyMultivalued dependencyIn database theory, multivalued dependency is a full constraint between two sets of attributes in a relation.In contrast to the functional dependency, the multivalued dependency requires that certain tuples be present in a relation. Therefore, a multivalued dependency is a special case of...
(MVD) - Database normalizationDatabase normalizationIn the design of a relational database management system , the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce smaller, well-structured relations...
- First normal formFirst normal formFirst normal form is a normal form used in database normalization. A relational database table that adheres to 1NF is one that meets a certain minimum set of criteria...