HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is the inverse of Armstrong's Axioms valid as well?

Submitted by: @import:stackexchange-dba··
0
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:

AB → GB


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:

if X → Y then XZ → YZ


Would 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 XZ → YZ holds:

X  Y  Z
--------
x1 y1 z1
x2 y1 z1
x1 y2 z2
x2 y2 z2


But 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 z2
Y → 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.