Content deleted Content added
Huggums537 (talk | contribs) m Clean up/copyedit |
Citation bot (talk | contribs) Add: pages, issue, volume, chapter-url, s2cid, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 644/2500 |
||
Line 91:
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
|
|
|author-link=Serge Abiteboul
|last2=Hull
Line 159:
=== 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 | s2cid = 22069259 }} 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]|chapter-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}}
</ref>
Line 180:
# Reducing any functional dependency will change the content of S.
Sets of functional dependencies with these properties are also called ''canonical'' or ''minimal''. Finding such a set S of functional dependencies which is equivalent to some input set S' provided as input is called finding a ''minimal cover'' of S': this problem can be solved in polynomial time.<ref>{{Cite journal|last1=Meier|first1=Daniel|title=Minimum covers in the relational database model|year=1980|journal=[[Journal of the ACM]]|volume=27 |issue=4 |pages=664–674 |doi=10.1145/322217.322223|s2cid=15789293 }}{{Closed access}}</ref>
== See also ==
| |||