# 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

If I understand the question correctly, the problem is easy (once we understand the problem).

As I understand it, you are given a finite set XA1×…×An and want to find the “best” set I⊆{1,…,n} of indices that is feasible, where we say that a set I is feasible when X can be written as the direct product of the sets Ai for iI and some set of (n−|I|)-tuples (where indices are permuted appropriately).

You consider two formulations of the meaning of “best”: (1) the product ∏iI |Ai| is maximized, (2) the size |I| is maximized. However, it does not matter which criterion you use because both can be maximized at the same time.

For each i=1,…,n, test whether the singleton set {i} is feasible (this can be done efficiently). Let J be the set of indices i such that {i} is feasible. It is easy to see that J is also feasible, and moreover J is the maximum with respect to inclusion among the feasible sets of indices. Therefore, the index set J maximizes both criteria (1) and (2) stated above.

• Your solution looks right to me, thanks! I'd like to know what you had in mind for testing the feasibility of the singletons "efficiently". The only method I can think of is pretty much "brute force": classify the elements of X by their i-th coordinate; {i} is feasible only if all the partitions have the same cardinality; if this is the case, test for equality the set of all (n-1) tuples obtained from the elements of the first partition by discarding their i-th components against the corresponding sets of the remaining partitions. If all tests pass, {i} is feasible. Is that it? – kjo Jan 29 '11 at 23:47
• @kjo: Yes, that is what I had in mind. (I would first sort the elements of X with respect to the coordinates except for the i-th, which makes the rest of the test slightly easier, but that is a minor detail.) – Tsuyoshi Ito Jan 29 '11 at 23:51
• one more question: the math symbols in your reply don't look like the ones in my question; did you use mathjax? if not, what did you use? do you have a good collection of such symbols for cut-and-paste? thnx – kjo Jan 31 '11 at 13:05
• @kjo: No, I did not use MathJax in this answer. I usually avoid MathJax whenever possible because processing MathJax takes some time. I use Microsoft Office IME which allows me to enter Japanese text, and it has a secondary functionality to enter mathematical and other symbols. I also have an HTML file with many Unicode symbols. It was in my local hard drive, but I have put it on the web: iqc.ca/~tito/unicode-character-index. Please let me know if you find it useful. – Tsuyoshi Ito Feb 1 '11 at 18:32