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

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.

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.

REFERENCE:
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.

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.

Cheers,