patternMinor
Is the inverse of Armstrong's Axioms valid as well?
Viewed 0 times
armstrongtheinversevalidwellaxioms
Problem
I have been looking into Armstrong's axioms a little bit. In a homework[1] exercise I was asked to prove A→G is in F-closure. I managed to get it at this point:
Being at this point, can I simply say that A → G as it seems pretty straightforward or do I have to go through certain steps as well. As Armstrong's axiom states:
Would the inverse be true as well ?
[1] I don't think the content of the homework does relate in here.
AB → GBBeing at this point, can I simply say that A → G as it seems pretty straightforward or do I have to go through certain steps as well. As Armstrong's axiom states:
if X → Y then XZ → YZWould the inverse be true as well ?
if XZ → YZ then X → Y <-- ?[1] I don't think the content of the homework does relate in here.
Solution
No, that is not true.
Armstrong's axioms are a sound and complete axiomatization of the logical implication for functional dependencies.
Here is a relation, where the functional dependency
But the functional dependency
If this "inverse" law would hold, then we can show that
Armstrong's axioms are a sound and complete axiomatization of the logical implication for functional dependencies.
Here is a relation, where the functional dependency
XZ → YZ holds:X Y Z
--------
x1 y1 z1
x2 y1 z1
x1 y2 z2
x2 y2 z2But the functional dependency
X → Y does not hold, as the tuples x1 y1 z1 and x1 y2 z2 show. Because of the soundness of Armstrong's axioms, which means that only valid functional dependencies can be derived, the "inverse" is not true. So we have constructed a counterexample.If this "inverse" law would hold, then we can show that
X → Y for arbitrary attribute sets X and Y:Y → Y (reflexivity)
XY → XY (augmentation)
XY → Y (reflexivity)
XY → YY (idempodency of union-operator: Y=YY)
X → Y ("inverse")Code Snippets
X Y Z
--------
x1 y1 z1
x2 y1 z1
x1 y2 z2
x2 y2 z2Y → Y (reflexivity)
XY → XY (augmentation)
XY → Y (reflexivity)
XY → YY (idempodency of union-operator: Y=YY)
X → Y ("inverse")Context
StackExchange Database Administrators Q#203356, answer score: 4
Revisions (0)
No revisions yet.