Content deleted Content added
make formula more clear relative to the following text. |
Turtlecrown (talk | contribs) fix typo Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 2:
{{about|a concept in relational database theory|function dependencies in the Haskell programming language|type class}}
{{refimprove|date=October 2012}}
In [[relational database]] theory, a '''functional dependency''' ('''FD''') is [[Relational database#Constraints|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 described as follows:
In [[relational database]] theory, a '''functional dependency''' is the following [[Relational database#Constraints|constraint]] between two attribute sets in a [[Relation (database)|relation]]: Given a relation ''R'' and attribute sets ''X'',''Y'' <math>\subseteq</math> ''R'', ''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 (relational algebra)|projection]] <math>\Pi_{X,Y}R</math> is a [[Function (mathematics)|function]], that is, ''Y'' is a function of ''X''.<ref name="HalpinMorgan2008">{{cite book |author1=Terry Halpin |title=Information Modeling and Relational Databases |url=https://books.google.com/books?id=puO_VlbR_x4C&pg=PA140 |year=2008 |publisher=Morgan Kaufmann |isbn=978-0-12-373568-3 |page=140 |edition=2nd}}</ref><ref name="Date2012">{{cite book |author=Chris Date |title=Database Design and Relational Theory: Normal Forms and All That Jazz |url=https://books.google.com/books?id=8jAGhpMSjAcC&pg=PA21 |year=2012 |publisher=O'Reilly Media, Inc. |isbn=978-1-4493-2801-6 |page=21}}</ref> 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#Relational model|tuple]] of ''R'' containing ''x''. Customarily ''X'' is called the ''determinant'' set and ''Y'' the ''dependent'' set. A functional dependency FD: ''X'' → ''Y'' is called ''trivial'' if ''Y'' is a [[subset]] of ''X''.▼
▲
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''.▼
In other words:
* when ''X'' attributes have known values (here, ''x''), the values for their corresponding ''Y'' attibutes can be determined by looking them up in ''any'' [[Tuple#Relational model|tuple]] of ''R'' containing ''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 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 ___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.
Line 121 ⟶ 127:
Given <math>R</math> and <math>F</math> a set of FDs that holds in <math>R</math>:
The closure of <math>F</math> in <math>R</math> (denoted <math>F</math><sup>+</sup>) is the set of all FDs that are logically implied by <math>F</math>.<ref>{{Cite journal|last=Saiedian|first=H.|date=1996-02-01|title=An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema|url=https://academic.oup.com/comjnl/article-lookup/doi/10.1093/comjnl/39.2.124|journal=The Computer Journal|language=en|volume=39|issue=2|pages=124–132|doi=10.1093/comjnl/39.2.124|issn=0010-4620|url-access=subscription}}</ref>
=== Closure of a set of attributes ===
| |||