Thursday, August 15, 2013

Functional data dependencies

Given an N-ary relation on slots 0,1,2,3,4,... we can consider the potential existence of a function that goes from one slot to another. The identity function maps any slot back to itself and if there is a function mapping one slot to another and another function mapping that other slot to yet another slot those two functions can be composed to get a function between the first and the last one so this relation is also transitive.

The combination of transitivity and reflexivity means that this functional dependency relation forms a preorder which is of course particularly nice for us as we can use all the tools of order theory to reason about these dependencies.

No comments:

Post a Comment