Functional dependency
Functional dependencies ( FA; functional dependency English, FD ) are a concept of the relational design theory and form the basis for the normalization of relation schemas.
A relation is defined by attributes. Determining some of these attributes clearly the values of other attributes, then one speaks of a functional dependency. So you could imagine about a customer database in which the address and telephone number of a customer are uniquely determined by their name along with his date of birth. So here would work address or telephone number functionally dependent on name and date of birth.
With the help of functional dependencies can also define the term key:
Determining some of the attributes of a relation clearly the values of all attributes of the relation, it is called a super key, that is, each tuple of this relation is uniquely determined by the values of these attributes. For example, one could introduce a customer number that identifies each customer. A candidate key is a minimal super key, that is, no proper subset of the attributes of this key completely determines the values of all other attributes of the relation. Among all the candidate keys of a relation known as a primary key is selected.
Example:
In this example, C is functionally dependent on A and B, written A, B → C. The arrow can thus be read as " uniquely determined ": The first two attributes together uniquely determine the value attribute C has. In other words: If it is known which values the first two attributes, therefore the value of the last attribute is determined. But C is not functionally dependent on A alone. There are also functional dependencies "A is functionally dependent on C", " A is functionally dependent on B " and "C is functionally dependent on B".
Formal definition
Let r (R ) is a relation with the relation schema R and let α and β subsets of attributes of R. Let t ∈ r is a tuple of r. Then t [ α ] is the restriction of t to the attributes of α. The functional dependency α → β ( β is functionally dependent on α ) holds on R if for any valid relation r (R):
That is, for all tuples t1, t2 ∈ r with the same α - attributes ( t1 [ α ] = t2 [ α ] ) is also true that their β - attributes are the same ( t1 [ β ] = t2 [ β ] ). The values of the attributes from the attribute set α so uniquely determine the values of the attributes from the attribute set β; α is referred to in the literature as a determinant of β. By the way: For attribute sets one usually writes short αβ instead of α ⋃ β.
β is called fully functionally dependent on α, α if for no attribute can be removed, so that the condition still applies.
In the above example makes the attribute "A" for the determination of 'C' does not matter:
From the functional dependency AB → C, the full functional dependency B → C can win.
Axioms of Armstrong
Using the axioms of Armstrong (also Armstrong axioms ) can be derived from a set of functional dependencies that apply to a relation, derive more functional dependencies. The following three rules are sufficient to derive all functional dependencies:
1 a set of attributes is uniquely determined, the values of a subset of these attributes ( trivial dependence), ie. ( Reflexivity )
2 Applies so also applies to any set of attributes of the relation. ( Expansion rule, gain)
3 Applies and so also applies. ( Transitivity )
In order to make easier derivations, the following additional ( secondary ) rules can be used:
4 Apply and so also applies. (Association rule)
5 Applies, as well as apply and. ( Dekompositions-/Zerlegungsregel )
6 Applies and so also applies. ( Pseudotransitivitätsregel )
Normalization with functional dependencies
With the help of functional dependencies to relation schemas can normalize. A relation schema R is, for example, in Boyce - Codd Normal Form if for all functional dependencies α → β, which apply to R, the following applies: The functional dependency is trivial or α is a super key of R. The third normal form is weakened somewhat. For them, any of the above conditions must apply or that all attributes from β - α are contained in at least one of the candidate keys of R.
There are algorithms that decompose a relation schema based on functional dependencies in normalized schemas. The aim of such decomposition is losslessness loyalty and dependence (including dependence preservation ) of the decomposition. Dependence loyalty means that all functional dependencies that apply to the original relation, are also on the decomposition yet. One such algorithm, which transferred to the third normal form, the synthesis algorithm. The losslessness a decomposition into two relations can be detected with the help of the set of Delobel.
Attribute Case
The attributes cover a specific attribute is a list of all attributes that are dependent on functional. In the smallest case, the attribute shell is only the attribute itself, since no other attributes depend on him. If one wishes to determine the attribute of a shell for a given number of attribute functional dependencies F, one can use a simple algorithm, which is determined by the repeated application of the set of dependent attributes transitivity. The algorithm is defined as follows:
Input:
- A lot of functional dependencies
- A set of attributes
Issue:
- The complete set of attributes that can be derived from the dependencies. It is true.
Envelope while ( change ) do foreach ( dependence) do if ( ) then
When applied to a specific amount of functional dependencies F:
- F has the dependencies:
1
2 passing through the functional dependencies from top to bottom:
- Is not a subset of
- Is not a subset of
- Is a subset of
Completed cover
Intuitively, is the closure of a set of functional dependencies, the set of attributes, which is determined by the " left side " of the dependencies.
If F = { α1 → β1, ..., →? N? N } be a set of functional dependencies, the closed hull or shell attribute is the amount
And is designated by. For the envelope, the following applies:
Advanced Concepts
- Multivalued dependencies form an extension of functional dependencies, which make it possible to detect additional abnormalities in a relational schema.
- Conditional dependencies (English Conditional Functional Dependencies ) form an extension of functional dependencies to concrete values tables. A dependency such as ZIP → City will be extended by an additional table with specific values, such as 80001 → Munich. The zip code 80001 is the place Munich is allocated directly. Using these conditional dependencies, the quality of data measured, or it can be derived measures to improve the data quality.