tag:blogger.com,1999:blog-10552251.post2288409751216876824..comments2021-01-08T06:41:18.450-05:00Comments on Mark's Musings: General Unification Theorem Proof Concerning Functional Dependencies in Relational DatabasesMarkhttp://www.blogger.com/profile/16102801024300792473noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-10552251.post-81328227122259580122013-02-26T21:48:55.194-05:002013-02-26T21:48:55.194-05:00Thanks for the proof Adam. It is correct. However,...Thanks for the proof Adam. It is correct. However, you did not supply any members in the sets. <br /><br />I would site that in order to provide sets A, B, C, and D with members, and for them to fulfill the theorem, they become "convenient sets." <br /><br />That is the nature of functional dependencies in the use of relational databases. Hopefully, in the normalization process they become even more convenient. :-)Markhttps://www.blogger.com/profile/16102801024300792473noreply@blogger.comtag:blogger.com,1999:blog-10552251.post-35527241673496311722013-02-26T18:32:59.239-05:002013-02-26T18:32:59.239-05:00Heh, I didn't expect a reply so quickly (or at...Heh, I didn't expect a reply so quickly (or at all). :)<br />Here's my proof. I use Armstrong's axioms, some of their close derivatives, and a little bit of set-theoretical reasoning.<br /><br />REFERENCE:<br />A, B, C, and D are subsets of attributes of a relation.<br />Reflexivity: If B is a subset of A, then A→B (i.e. A determines B)<br />Transitivity: If A→B and B→C then A→C<br />Composition: If A→B and C→D then AC→BD<br />General Unification Theorem: If A→B and C→D then A∪(C-B)→DB<br /><br />I use (parentheses) liberally because this isn't typeset. [Bracketed] text denotes explanation of that step of the proof.<br /><br />PROOF:<br />01) A→B [given]<br />02) C→D [given]<br />03) (B∩C)⊆B [property of intersection]<br />04) B→(B∩C) [reflexivity, 3]<br />05) (C-B)→(C-B) [self determination]<br />06) A→B∩C [transitivity, 1, 4]<br />07) A∪(C-B)→(B∩C)∪(C-B) [composition 4, 5]<br />08) (A∪(C-B))→C [properties of intersection and difference operators]<br />09) (A∪(C-B))→D [transitivity, 2, 8]<br />10) (A∪A∪(C-B))→(D∪B) [composition, 1, 9)<br />11) A∪(C-B)→DB [simplification]<br /><br />I turned in a similar proof in an undergrad database theory course, and have replied under an identifiable name (as opposed to 'Horse') should anyone at the university need to prove that this is my own work.<br /><br />Cheers,<br /><br />AdamFAWBDnoreply@blogger.comtag:blogger.com,1999:blog-10552251.post-43487420530383076632013-02-25T03:27:53.394-05:002013-02-25T03:27:53.394-05:00Horse, then, just as you stated all the sets do no...Horse, then, just as you stated all the sets do not have functional dependencies.<br /><br />Show me your "proof." :-)Markhttps://www.blogger.com/profile/16102801024300792473noreply@blogger.comtag:blogger.com,1999:blog-10552251.post-69467532680813173352013-02-25T01:44:43.644-05:002013-02-25T01:44:43.644-05:00How does this constitute a proof? It's just an...How does this constitute a proof? It's just an example applied on convenient sets. To "prove" something in this manner one would need to apply the theorem to all possible sets A, B, C, and D, which is not feasible. Horsenoreply@blogger.com