Answered here: https://cstheory.stackexchange.com/questions/4631/cartesian-factorization-of-a-finite-set-of-n-tuples#4633