Superkey A superkey is a set of column headers for which the values of those columns concatenated are unique across all rows. Formally: A superkey is written as a finite set of attribute names. A superkey holds in a relation if: and there exist no two distinct tuples such that . A superkey holds in a relation universe if it holds in all relations in . Theorem: A superkey holds in a relation universe over if and only if and holds in . Candidate key A candidate key is a superkey that cannot be further subdivided to form another superkey. A superkey holds as a candidate key for a relation universe if it holds as a superkey for and there is no proper subset of that also holds as a superkey for . Functional dependency Functional dependency is the property that a value in a tuple may be derived from another value in that tuple. A functional dependency (FD for short) is written as for finite sets of attribute names. A functional dependency holds in a relation if: and tuples , A functional dependency holds in a relation universe if it holds in all relations in . Trivial functional dependency A functional dependency is trivial under a header if it holds in all relation universes over . Theorem: An FD is trivial under a header if and only if . Closure Armstrong's axioms: The closure of a set of FDs under a header , written as , is the smallest superset of such that: (reflexivity) (transitivity) and (augmentation) Theorem: Armstrong's axioms are sound and complete; given a header and a set of FDs that only contain subsets of , if and only if holds in all relation universes over in which all FDs in hold. Completion The completion of a finite set of attributes under a finite set of FDs , written as , is the smallest superset of such that: The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs. Theorem: Given a set of FDs, if and only if . Irreducible cover An irreducible cover of a set of FDs is a set of FDs such that: there exists no such that is a singleton set and .
Superkey A superkey is a set of column headers for which the values of those columns concatenated are unique across all rows. Formally: A superkey is written as a finite set of attribute names. A superkey holds in a relation if: and there exist no two distinct tuples such that . A superkey holds in a relation universe if it holds in all relations in . Theorem: A superkey holds in a relation universe over if and only if and holds in . Candidate key A candidate key is a superkey that cannot be further subdivided to form another superkey. A superkey holds as a candidate key for a relation universe if it holds as a superkey for and there is no proper subset of that also holds as a superkey for . Functional dependency Functional dependency is the property that a value in a tuple may be derived from another value in that tuple. A functional dependency (FD for short) is written as for finite sets of attribute names. A functional dependency holds in a relation if: and tuples , A functional dependency holds in a relation universe if it holds in all relations in . Trivial functional dependency A functional dependency is trivial under a header if it holds in all relation universes over . Theorem: An FD is trivial under a header if and only if . Closure Armstrong's axioms: The closure of a set of FDs under a header , written as , is the smallest superset of such that: (reflexivity) (transitivity) and (augmentation) Theorem: Armstrong's axioms are sound and complete; given a header and a set of FDs that only contain subsets of , if and only if holds in all relation universes over in which all FDs in hold. Completion The completion of a finite set of attributes under a finite set of FDs , written as , is the smallest superset of such that: The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs. Theorem: Given a set of FDs, if and only if . Irreducible cover An irreducible cover of a set of FDs is a set of FDs such that: there exists no such that is a singleton set and .