Armstrongs Axioms Proof

Question

I am having issues proving functional dependencies with Armstrong's Axioms. This one i'm struggling with. Let R(A,B,C,D,E) be a relation schema and F = {A→CD, C→E, B→D} 1. Prove: F: BC-> DE

What I have:

1 Given B->D 1. Augment C on 1, BC->DC

2. Decomposition on 2, BC->D BC->C

3. Transitivity on BC->C, BC->E

4. Union on BC ->D and and 4, BC->DE

Unsure if this is a proper solution.

Also Prove: AC-> BD I don't think this can be proven. Please Help!

Answer 1

your solutions are correct, apart from some apparent misspelling:

1. Given B->D, C->E
2. Augment C on 1: BC -> DC
3. Decomposition on 2: BC -> C (3.1), BC -> D (3.2)
4. Transitivity on 1, 3.1: BC -> C, C -> E: BC -> E
5. Union on 3.2 and 4: BC -> DE

alternatively:

1. B->D, C->E
2. augment(1.1, c): bc -> dc
3. augment(1.2, d): cd -> ed
4. trans(2, 3): bc -> de (note: bc -> dc <=> bc -> cd <=> cb -> cd <=> cb -> dc)

ac -> bd cannot be proven in general: inspecting the armstrong axioms you notice that for some X to appear on the rhs of a derived fd, it must occur on the rhs of one of the original fds, except for

1. X is a subset of some X' on the lhs of an original fd

   or

2. the fd is derived by augmentation with X

1.) constitutes a constraint never mentioned. if 2.) applies, X would appear on a lhs of the original fd too. the only way to eliminate X is by transitivity which requires X to appear on the rhs of one of the original fds.

take b as X to see that ac -> bd is unprovable.

Abbreviations:

Shorthand	Expansion
fd(s)	Functional dependency(/-cies)
lhs	Left-hand side (of an equation / a derivation )
rhs	Right-hand side