# Cartesian factorization of a finite set of n-tuples

(NB: I asked this question in Math Overflow, and based on the one reply [a comment, actually] that it received so far, I realized that this may be a more appropriate forum for it. I've added a few comments to this post, connecting the problem to the theory of databases.)

I'm interested in factoring a finite set of $n$-tuples as the Cartesian product of two "factor sets", of which the first factor is itself the Cartesian product of some of the set's projection images, and the second factor is an unfactorizable "remainder".

To describe the problem more precisely, let $X$ be a non-empty, finite set of $n$-tuples, and let $A_1,...,A_n$ be the images of $X$ upon projection onto its various coordinates. Hence, $X \subset \prod_{i=1}^{n} A_i$. Furthermore, assume that this inclusion is strict; that is, $X \neq \prod_{i=1}^{n} A_i$. (From this it follows that $n > 1$.) If $\sigma$ is some permutation of $\{1,...,n\}$, let $X_\sigma$ denote the set of $n$-tuples derived from $X$ by permuting the coordinates of its elements according to $\sigma$: $X_\sigma = \{(x_{\sigma(1)},...,x_{\sigma(n)})|(x_1,...,x_n)\in X \}$. (See the end of this post for a restatement of the problem using OLAP terminology.)

For any $n$-permutation $\sigma$, I'm interested in factorizations of $X_\sigma$ having the form $X_\sigma = (\prod_{i=1}^{k} A_{\sigma(i)}) \times Z$, where $0 \leq k \lt n$ and $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$. This factorization means that every $n$-tuple in $X_\sigma$ can be written (obviously uniquely) as the concatenation of one $k$-tuple from $\prod_{i=1}^{k} A_{\sigma(i)}$ and one $(n-k)$-tuple from $Z \subsetneq \prod_{i=k+1}^{n} A_{\sigma(i)}$, and, conversely, every concatenation of such tuples represents some element of $X_\sigma$. (If $k = 0$, then $Z = X_\sigma$; i.e. the factorization is a trivial one.)

I am primarily interested in factorizations for which the factor $\prod_{i=1}^{k} A_{\sigma(i)}$ has maximal cardinality, over all possible choices of $\sigma$ and $k$. I am also interested in factorizations for which $k$ is maximal, over all possible choices of $\sigma$. [Edit: both criteria actually lead to the same result; see Tsuyoshi Ito's answer.]

[(This bracketed paragraph is intended by way of background; it is tangential to the questions of this post. Please disregard it if it is not useful or clear.) One area where this problem arises is in the theory of databases and OLAP: given a facts table $X$ with $n$ dimension (aka "metadata") columns, how can it be "most efficiently" converted to a collection of perfectly dense (i.e. no empty cells) multidimensional data "(hyper)cubes" having identical domains. (These domains correspond to the sets $A_{\sigma(1)},...,A_{\sigma(k)}$ above.) This formulation leaves the optimization criterion fuzzy. I use the term "efficient" here to describe solutions that pack "as much information as possible" in the regular hypercubes, but even with this clarification the criterion is ill-defined, because "most information" could be defined as "the greatest number of cells" or "the greatest number of dimensions" (i.e. potential explanatory factors) for the regular hypercubes. These correspond to the two classes of factorizations I described in the previous paragraph.]

I'm looking for keywords I may use to search for algorithms to compute such maximal factorizations, given some concrete set of $n$-tuples $X$. Do such factorizations, or the problem of computing them, have a name? Are their complexity classes known? Any pointers to the relevant literature would be appreciated!

~kj

• Crosspost in MO. – Hsien-Chih Chang 張顯之 Jan 29 '11 at 18:28
• The definition of ≅ looks exactly identical to the definition of = to me. Can you clarify the difference between ≅ and =? – Tsuyoshi Ito Jan 29 '11 at 20:54
• My use of ≅ was left over from an earlier version of the write-up, in which the LHS of the factorization expression was just X, and the ≅ was meant to denote that a reordering of dimensions may be necessary. I've fixed it now. Sorry for the confusion. – kjo Jan 29 '11 at 23:31