{
  "id": "enwiki-001370885918",
  "slug": "functional-dependency",
  "title": "Functional dependency",
  "qid": "",
  "lead": "In relational database theory, a functional dependency (FD) is constraint between two attribute sets, whereby values in one set (the determinant set) determine the values of the other set (the dependent set). A functional dependency between a determinant set X and a dependent set Y can be described as follows: Given a relation R and attribute sets X,Y \\subseteq R, then X is said to functionally determine Y (written X → Y) if each X value is associated with precisely one Y value. R is then said to satisfy the functional dependency X → Y. Equivalently, the projection \\Pi_{X,Y}R is a function, that is, Y is a function of X. In other words: * when X attributes have known values (here, x), the values for their corresponding Y attributes can be determined by looking them up in any tuple of R containing x. * two tuples sharing the same values of X will necessarily have the same values of Y. A dependency FD: X → Y means that the values of Y are determined by the values of X. A functional dependency FD: X → Y is called trivial if Y is a subset of X. The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization.…",
  "body": "In relational database theory, a functional dependency (FD) is constraint between two attribute sets, whereby values in one set (the determinant set) determine the values of the other set (the dependent set). A functional dependency between a determinant set X and a dependent set Y can be described as follows: Given a relation R and attribute sets X,Y \\subseteq R, then X is said to functionally determine Y (written X → Y) if each X value is associated with precisely one Y value. R is then said to satisfy the functional dependency X → Y. Equivalently, the projection \\Pi_{X,Y}R is a function, that is, Y is a function of X. In other words: when X attributes have known values (here, x), the values for their corresponding Y attributes can be determined by looking them up in any tuple of R containing x. two tuples sharing the same values of X will necessarily have the same values of Y. A dependency FD: X → Y means that the values of Y are determined by the values of X. A functional dependency FD: X → Y is called trivial if Y is a subset of X. 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 property, namely into \\Pi_{XY}(R)\\bowtie\\Pi_{XZ}(R) = R where Z = U − XY are the rest of the attributes. (Unions of attribute sets are customarily denoted by their 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 domains, 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 \\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 \\Sigma \\models \\Gamma . The notion of logical implication for functional dependencies admits a sound and complete finite axiomatization, known as Armstrong's axioms. Therefore, A + = ABCD. Because A + includes every attribute in the relationship, it is a superkey. Two sets of FDs F and G over schema R are equivalent, written F &equiv; G , if F + = G + . If F &equiv; G , then F is a cover for G and vice versa. In other words, equivalent sets of functional dependencies are called covers of each other. An important property (yielding an immediate application) of functional dependencies is that if R is a relation with columns named from some set of attributes U and R satisfies some functional dependency X → Y then R=\\Pi_{XY}(R)\\bowtie\\Pi_{XZ}(R) where Z = U − XY. 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 \\Pi_{XY}(R)\\bowtie\\Pi_{XZ}(R) ) 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. This fact is sometimes called Heaths theorem; it is one of the early results in database theory. Heath's theorem effectively says we can pull out the values of Y from the big relation R and store them into one, \\Pi_{XY}(R) , which has no value repetitions in the row for X and is effectively a lookup table for Y keyed by X and consequently has only one place to update the Y corresponding to each X unlike the \"big\" relation R where there are potentially many copies of each X, each one with its copy of Y which need to be kept synchronized on updates. (This elimination of redundancy is an advantage in OLTP contexts, where many changes are expected, but not so much in OLAP contexts, which involve mostly queries.) Heath's decomposition leaves only X to act as a foreign key in the remainder of the big table \\Pi_{XZ}(R) . 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. 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. Enforcing referential constraints after relation schema decomposition (normalization) requires a new formalism, i.e. inclusion dependencies. In the decomposition resulting from Heath's theorem, there is nothing preventing the insertion of tuples in \\Pi_{XZ}(R) having some value of X not found in \\Pi_{XY}(R) .",
  "categories": [
    "20351041",
    "22929646",
    "22975041",
    "23118434",
    "23603337",
    "24043274",
    "24745122"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1370885918",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1787493575.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001370885918",
    "type": "webpage",
    "title": "Functional dependency",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/functional-dependency",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          22
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          22
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001370885918",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1370885918",
    "note": "Immutable snapshot enwiki-001370885918"
  }
}