Functional dependency: Difference between revisions

Revision as of 16:21, 6 January 2023

Revision as of 11:35, 21 March 2023

Line 6:

In other words, a dependency FD: ''X'' → ''Y'' means that the values of ''Y'' are determined by the values of ''X''. Two tuples sharing the same values of ''X'' will necessarily have the same values of ''Y''.

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|lossless-join decomposition]] property, namely into <math>\Pi_{XY}(R)\bowtie\Pi_{XZ}(R) = R</math> where ''Z'' = ''U'' − ''XY'' are the rest of the attributes. ([[set union|Union]]s of attribute sets are customarily denoted by merethere 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 ___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.

A notion of [[logical implication]] is defined for functional dependencies in the following way: a set of functional dependencies <math>\Sigma</math> logically implies another set of dependencies <math>\Gamma</math>, if any relation ''R'' satisfying all dependencies from <math>\Sigma</math> also satisfies all dependencies from <math>\Gamma</math>; this is usually written <math>\Sigma \models \Gamma</math>. The notion of logical implication for functional dependencies admits a [[soundness|sound]] and [[completeness (logic)|complete]] finite [[axiomatization]], known as ''Armstrong's axioms''.