Functional dependency: Difference between revisions

Revision as of 13:17, 22 June 2020

Revision as of 00:08, 17 December 2020

Line 115:

''X'' → ''YZ'', holds [[iff]] ''X'' → ''Y'' and ''X'' → ''Z''. This is sometimes called the splitting/combining rule.<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}}</ref>

Another rule that is sometimes handy is:<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|origyearorig-year=2006|publisher=Pearson Education India|isbn=978-81-7758-567-4|page=323}}</ref>

* '''Composition''': If ''X'' → ''Y'' and ''Z'' → ''W'', then ''XZ'' → ''YW''

Line 162:

=== Heath's theorem ===

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 <math>R=\Pi_{XY}(R)\bowtie\Pi_{XZ}(R)</math> 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 <math>\Pi_{XY}(R)\bowtie\Pi_{XZ}(R)</math>) 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.<ref>{{Cite book | last1 = Heath | first1 = I. J. | chapter = Unacceptable file operations in a relational data base | doi = 10.1145/1734714.1734717 | title = Proceedings of the 1971 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '71 | pages = 19–33 | year = 1971 | pmid = | pmc = }} cited in:

* {{cite book|editor=Michael Anshel and William Gewirtz|title=Mathematics of Information Processing: [short Course Held in Louisville, Kentucky, January 23-24, 1984]|url=https://archive.org/details/mathematicsofinf0034unse/page/23|year=1986|publisher=American Mathematical Soc.|isbn=978-0-8218-0086-7|author=Ronald Fagin and Moshe Y. Vardi|chapter=The Theory of Data Dependencies - A Survey|page=[https://archive.org/details/mathematicsofinf0034unse/page/23 23]}}

*{{cite book|author=C. Date|title=Database in Depth: Relational Theory for Practitioners|url=https://books.google.com/books?id=TR8f5dtnC9IC&pg=PT162|year=2005|publisher=O'Reilly Media, Inc.|isbn=978-0-596-10012-4|page=142}}