Editing Functional dependency (section)

== Properties  and axiomatization of functional dependencies ==
{{Main article|Armstrong's axioms}}
Given that ''X'', ''Y'', and ''Z'' are sets of attributes in a relation ''R'', one can derive several properties of functional dependencies.  Among the most important are the following, usually called [[Armstrong's axioms]]:<ref name="SilberschatzKorth2010a">{{cite book|author1-link=Abraham Silberschatz|author2-link=Henry F. Korth|author1=Abraham Silberschatz|author2=Henry Korth|author3=S. Sudarshan|title=Database System Concepts|year=2010|publisher=McGraw-Hill|isbn=978-0-07-352332-3|edition=6th|page=339}}</ref>
* '''Reflexivity''': If ''Y'' is a subset of ''X'', then ''X'' → ''Y'' 
* '''Augmentation''': If ''X'' → ''Y'', then ''XZ'' → ''YZ''
* '''Transitivity''': If ''X'' → ''Y'' and ''Y'' → ''Z'', then ''X'' → ''Z''

"Reflexivity" can be weakened to just <math>X \rightarrow \varnothing</math>, i.e. it is an actual [[axiom]], where the other two are proper [[inference rules]], more precisely giving rise to the following rules of syntactic consequence:<ref name="Vardi">M. Y. Vardi. [http://www.cs.rice.edu/~vardi/papers/ttcs87.pdf Fundamentals of dependency theory]. In E. Borger, editor, Trends in Theoretical
Computer Science, pages 171–224. Computer Science Press, Rockville, MD, 1987. {{ISBN|0881750840}}</ref>

<math>\vdash X \rightarrow \varnothing</math><br/>
<math>X \rightarrow Y \vdash XZ \rightarrow YZ</math><br/>
<math>X \rightarrow Y, Y \rightarrow Z \vdash X \rightarrow Z</math>.

These three rules are a [[Soundness|sound]] and [[Completeness (logic)|complete]] axiomatization of functional dependencies. This axiomatization is sometimes described as finite because the number of inference rules is finite,<ref name="alice">{{Citation
|last1=Abiteboul
|first1=Serge
|author-link=Serge Abiteboul
|last2=Hull
|first2=Richard B.
|author2-link=Richard B. Hull
|last3=Vianu
|first3=Victor
|author3-link=Victor Vianu
|title=Foundations of Databases
|publisher=Addison-Wesley
|year=1995
|isbn=0-201-53771-0
|url=https://archive.org/details/foundationsofdat0000abit/page/164
|pages=[https://archive.org/details/foundationsofdat0000abit/page/164 164–168]
}}</ref> with the caveat that the axiom and rules of inference are all [[Schema (logic)|schemata]], meaning that the ''X'', ''Y'' and ''Z'' range over all ground terms (attribute sets).<ref name="Vardi"/>

By applying augmentation and transitivity, one can derive two additional rules:
* '''Pseudotransitivity''': If ''X'' → ''Y'' and ''YW'' → ''Z'', then ''XW'' → ''Z''<ref name="SilberschatzKorth2010a"/>
* '''Composition''': If ''X'' → ''Y'' and ''Z'' → ''W'', then ''XZ'' → ''YW''<ref name="Singh2009">{{cite book|author=S. K. Singh|title=Database Systems: Concepts, Design & Applications|url=https://books.google.com/books?id=8PNCKe2SpRwC&pg=PA323|year=2009|orig-year=2006|publisher=Pearson Education India|isbn=978-81-7758-567-4|page=323}}</ref>

One can also derive the [[Armstrong's axioms#Additional rules (Secondary Rules)|'''union''' and '''decomposition''']] rules from Armstrong's axioms:<ref name="SilberschatzKorth2010a"/><ref name="Garcia-MolinaUllman2009">{{cite book|author1=Hector Garcia-Molina|author2=Jeffrey D. Ullman|author3=Jennifer Widom|title=Database systems: the complete book|year=2009|publisher=Pearson Prentice Hall|isbn=978-0-13-187325-4|edition=2nd|page=73}} This is sometimes called the splitting/combining rule.</ref>
:''X'' → ''Y'' and ''X'' → ''Z'' [[if and only if]] ''X'' → ''YZ''