Thursday, December 27, 2007

General Unification Theorem Proof Concerning Functional Dependencies in Relational Databases

For a problem that was to be solved in my database systems graduate class this last semester, we were asked to prove a theorem by Hugh Darwen that is known as the General Unification Theorem concerning Functional Dependencies within Relational Databases.

Click here to see the proof.


Horse said...

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.

Mark said...

Horse, then, just as you stated all the sets do not have functional dependencies.

Show me your "proof." :-)

FAWBD said...

Heh, I didn't expect a reply so quickly (or at all). :)
Here's my proof. I use Armstrong's axioms, some of their close derivatives, and a little bit of set-theoretical reasoning.

A, B, C, and D are subsets of attributes of a relation.
Reflexivity: If B is a subset of A, then A→B (i.e. A determines B)
Transitivity: If A→B and B→C then A→C
Composition: If A→B and C→D then AC→BD
General Unification Theorem: If A→B and C→D then A∪(C-B)→DB

I use (parentheses) liberally because this isn't typeset. [Bracketed] text denotes explanation of that step of the proof.

01) A→B [given]
02) C→D [given]
03) (B∩C)⊆B [property of intersection]
04) B→(B∩C) [reflexivity, 3]
05) (C-B)→(C-B) [self determination]
06) A→B∩C [transitivity, 1, 4]
07) A∪(C-B)→(B∩C)∪(C-B) [composition 4, 5]
08) (A∪(C-B))→C [properties of intersection and difference operators]
09) (A∪(C-B))→D [transitivity, 2, 8]
10) (A∪A∪(C-B))→(D∪B) [composition, 1, 9)
11) A∪(C-B)→DB [simplification]

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.



Mark said...

Thanks for the proof Adam. It is correct. However, you did not supply any members in the sets.

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."

That is the nature of functional dependencies in the use of relational databases. Hopefully, in the normalization process they become even more convenient. :-)