Cartesian factorization of a finite set of n-tuples

Question

(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

Answer 1

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 X⊆A₁×…×A_n 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 A_i for i∈I and some set of (n−|I|)-tuples (where indices are permuted appropriately).

You consider two formulations of the meaning of “best”: (1) the product ∏_i∈I |A_i| 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.