Functional dependency

functional dependenciesfunctionally dependentinspired from relational database theory
In relational database theory, a functional dependency is a constraint between two set of attributes in a relation from a database.wikipedia
55 Related Articles

Candidate key

candidatekey candidateskeys
(Unions of attribute sets are customarily denoted by mere 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.
e.g. from the set of functional dependencies.

Database normalization

normalizationnormalizednormal form
The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization.
Genre ID and Genre Name both depend upon the primary key {Title}, but they are not independent of one another.

Armstrong's axioms

axiom of transitivityArmstrong rulesinference
One uses Armstrong's axioms to provide a proof - i.e. reflexivity, augmentation, transitivity.
Armstrong's axioms are a set of axioms (or, more precisely, inference rules) used to infer all the functional dependencies on a relational database.

Superkey

The latter expresses the fact that the set {StudentID, Lecture} is a superkey of the relation.
It can be defined as a set of attributes of a relation schema upon which all attributes of the schema are functionally dependent.

Relational model

relationalrelational data modelrelationships
The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization.

Lossless-Join Decomposition

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 property, namely into where Z = U − XY are the rest of the attributes.
Let F be a set of functional dependencies on R.

Canonical cover

Every set of functional dependencies has a canonical cover.
A canonical cover F_c for F (a set of functional dependencies on a relation scheme) is a set of dependencies such that F logically implies all dependencies in F_c, and F_c logically implies all dependencies in F.

Referential integrity

Declarative Referential Integrityreferential integrity constraintforeign-key candidates
Functional dependencies however should not be confused with inclusion dependencies, which are the formalism for foreign keys; even though they are used for normalization, functional dependencies express constraints over one relation (schema), whereas inclusion dependencies express constraints between relation schemas in a database schema.
However, logical implication between dependencies that can be inclusion dependencies or functional dependencies is undecidable by reduction from the word problem for monoids.

Third normal form

3NF3NF databasesthird
Generally, the third normal form is considered to be a "good" standard for a relational database.
A non-prime attribute of R is an attribute that does not belong to any candidate key of R. A transitive dependency is a functional dependency in which X → Z (X determines Z) indirectly, by virtue of X → Y and Y → Z (where it is not the case that Y → X).

Multivalued dependency

multivalued dependenciesembedded multi-valued dependencies (EMVD s)
In contrast to the functional dependency, the multivalued dependency requires that certain tuples be present in a relation.

Chase (algorithm)

the chasechase
In its simplest application the chase is used for testing whether the projection of a relation schema constrained by some functional dependencies onto a given decomposition can be recovered by rejoining the projections.

Join dependency

lossless-join decompositionrecovered by rejoining the projections
Intuitively, if a functional dependency X → Y holds in R, then the relation can be safely split in two relations alongside the column X (which is a key for ) ensuring that when the two parts are joined back no data is lost, i.e. a functional dependency provides a simple way to construct a lossless-join decomposition of R in two smaller relations.
Unlike in the case of functional dependencies, there is no sound and complete axiomatization for join dependencies, though axiomatization exist for more expressive dependency languages such as full typed dependencies.

Equality-generating dependency

equality-generating dependencies
Furthermore, the two notions do not even intersect in the classification of dependencies: functional dependencies are equality-generating dependencies whereas inclusion dependencies are tuple-generating dependencies.
An important subclass of equality-generating dependencies are functional dependencies.

Relational database

relational database management systemRDBMSrelational databases
In relational database theory, a functional dependency is a constraint between two set of attributes in a relation from a database.

Relation (database)

relationrelation schemarelations
In relational database theory, a functional dependency is a constraint between two set of attributes in a relation from a database.

Projection (relational algebra)

projectionprojectionsproject
Equivalently, the projection \Pi_{X,Y}R is a function, i.e. Y is a function of X.

Function (mathematics)

functionfunctionsmathematical function
Equivalently, the projection \Pi_{X,Y}R is a function, i.e. Y is a function of X.

Tuple

tuplesn-tuple5-tuple
In simple words, if the values for the X attributes are known (say they are x), then the values for the Y attributes corresponding to x can be determined by looking them up in any tuple of R containing x.

Subset

supersetproper subsetsubsets
A functional dependency FD: X → Y is called trivial if Y is a subset of X.

Denormalization

denormalizeddatabase denormalization
The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization.

Union (set theory)

unionset unionunions
(Unions of attribute sets are customarily denoted by mere 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.

Attribute domain

The functional dependencies, along with the attribute domains, are selected so as to generate constraints that would exclude as much data inappropriate to the user domain from the system as possible.

Logical consequence

entailmententailsfollows from
A notion of logical implication is defined for functional dependencies in the following way: a set of functional dependencies \Sigma logically implies another set of dependencies \Gamma, if any relation R satisfying all dependencies from \Sigma also satisfies all dependencies from \Gamma; this is usually written.

Soundness

soundunsoundSoundness theorem
The notion of logical implication for functional dependencies admits a sound and complete finite axiomatization, known as Armstrong's axioms.

Completeness (logic)

completecompletenessincompleteness
The notion of logical implication for functional dependencies admits a sound and complete finite axiomatization, known as Armstrong's axioms.