Search code examples
databaserelational-databasefunctional-dependencies

Armstrongs Axioms Proof

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!

Solution

  • 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