This paper investigates design issues associated with representing relations in binary networks augmented with hidden variables. The trade-off between the number of variables required and the size of their domains is discussed. We show that if the number of values available to each variable is just two, then hidden variables cannot improve the expressional power of the network, regardless of their number. However, for k greater than or equal to 3, we can always find a layered network using k-valued hidden variables that represent an arbitrary relation. We then provide a scheme for decomposing an arbitrary relation, p, using |p|-2/k-2 hidden variables, each having k values (k >2).