Reflexivity in functional dependencies

Question

I'm taking a class on databases and I'm doing an assignment on functional dependencies. As an example of taking given dependencies and deriving other non-trivial dependencies using Armstrong's Axioms, the TA wrote this and I can't wrap my head around it.

Considering the relation R(c,p,h,s,e,n) and F the set of functional dependencies {1. c->p, 2. hs->c, 3. hp->s, 4. ce->n, 5. he->s}:

Iteration 1:

From F, we can build F1

6. hs->p (transitivity: 1+2)
7. hc->s (pseudo-transitive. 1+3)
8. hp->c
  1. hp->hs (reflexivity 3)
  2. hp->c (transitivity: 8.1+2)
9. he->c
  1. he->hs (reflexivity: 4)
  2. he->c (transitivity: 9.1+2)

I understand most of it fine except the cases where 'reflexivity' is used (using quotes because that's pretty far from the definition of reflexivity in my textbook). Can anyone tell me how that's reflexivity? Also, how do I know when an iteration is over? Couldn't you find an infinity of ways to rewrite functional dependencies?

Answer 1

These are the classical Armstrong’s Axioms (see for instance wikipedia):

Reflexivity: If Y ⊆ X then X → Y
Augmentation: If X → Y then XZ → YZ for any Z
Transitivity: If X → Y and Y → Z, then X → Z

So in your example, to derive hp → c you can procede in the following way:

1. hp → s (given)
2. hp → hs (by augmentation of 1 adding h)
3. hs → c (given)
4. hp → c (by transitivity of 2 + 3)

Note that to produce hp → hs from hp → s the axiom to use is Augmentation, in which the role of Z is taken by h, and not Reflexivity, and this is the axiom to use also to derive he → c (by Reflexivity you can only derive, for instance, hp → hp, hp → p, hp → h).

You are also asking:

How do I know when an iteration is over? Couldn't you find an infinity of ways to rewrite functional dependencies?

The Armstrong’s Axioms can be applied to a set of functional dependencies only a finite number of times to produce new functional dependencies. This is simple to show since the number of attributes is finite, and, given n attributes you can have at most 2ⁿ * 2ⁿ different functional dependencies (since you can have any subset of the attributes both on the left and the right part, of course including the trivial dependencies).