- Functional Dependency
A tuple is an unordered set of triplets (also called components) consisting of attribute names, types, and values . It loosely corresponds to the concept of a “row” in SQL. A tuple is also a functional mapping from attributes to their respective values.
Given a tuple :
- Attribute names are unique:
- The values of each triplet are of the right type:
A pair is an attribute of a tuple if the tuple has a matching triplet: . The set of all attributes of a tuple is the heading of .
The type of a tuple of determined by its heading. Two tuples and are of the same type iff .
Every subset of a tuple is also a valid tuple, including the empty set (the zero-tuple).
Degree (or Arity)
The arity or degree of a tuple is its set cardinality, which corresponds to the number of triplets it contains.
Notice that the degree of a tuple is also equal to the set cardinality of its heading: .
Two tuples and are considered equal if they share the same heading and attribute values:
The unique tuple with arity zero is called the nullary or zero tuple. Its heading is the empty set: .
An attribute is a pair where is the attribute name and corresponds to its type.
Given a relation and a set of attributes , the closure of under a set of functional dependencies is the family union of all the attributes that are dependent of in : .
If then is a super key for .
A heading is a set of attributes . The heading of a tuple determines the type of the tuple and its equal to its set of attributes: .
Given a heading :
- Attribute names are unique:
- All subsets of a heading are also valid headings
A relation is an object containing a heading and a body where the body is an unordered set of tuples (which means no duplicates), and where and . The type of a relation is determined by the type of its heading.
Given a relation :
- Each tuple’s heading matches the relation heading:
- Every subset of is also a valid body
Given a relation , a set of attributes is a super key for if all the attributes of are funtionally dependent on . More formally: .
In terms of candidate keys, super keys are sets of attributes that contain some candidate key as a subset.
A candidate key is an irreducible super key. Given a relation , a set of attributes is a candidate key for it is the minimal such that .
The cardinality of a relation is equal to the cardinality of its body: .
Degree (or Arity)
The arity or degree of a relation is equal to the arity of its heading: .
Given relation and tuple , we may use the set membership operator to express that a relation contains a tuple in its body: .
Two relations and are considered equal if they have the same heading (i.e. they are of the same type) and the same body: .
A relation is a subset of another relation if they have the same type (i.e. they share the same heading) and the body of is a subset of the body of : .
The special relation contains an empty heading and an empty body:
The special relation contains an empty heading and a body containing the empty tuple, which matches the type of the empty heading:
The relation can only have at most the empty tuple as an element.
Given a relation and two sets of attributes and , the functional dependency means that in the values of are determined by the values of . The set of attributes at the left hand side of the arrow () is called the determinant, and the other set of attributes () is called the dependent.
A functional dependency is trivial if its dependent is a subset of its determinant: . For example: .
Armstrong’s Axioms (Inference Rules)
Also called inference rules, are a set of primary rules to infer new functional dependencies from an existing set of functional dependencies. Given relation and :
- Reflexivity: If , then
- Augmentation: If , then
- Transitivity: If and , then
The following additional inference rules are derived from the primary rules:
- Decomposition: If , then and
- Union: If and , then
- Composition: If and , then
General Unification Theorem
The theorem states that if and , then .
The closure of functional dependency of a set of functional dependencies is denoted , and it corresponds to the union of and the functional dependencies that are derived from .
Given two sets of functional dependencies and for a given relation, is a cover for if .
Given two sets of functional dependencies and for a given relation, is equivalent to if , which means that is a cover for and is a cover for .
A set of functional dependencies is irreducible (also called minimal) if and only if:
- The dependent of every functional dependency in involves only one attribute (has cardinality 1)
- Removing any functional dependency from affects
- All the functional dependencies are left irreducible, which means that removing any attributes from their determinant affects
Every set of functional dependencies has at least one equivalent set that is irreducible. These sets are called irreducible equivalents.