A mathematical study on statistical database designs (Q1174682)

Let be given a finite set \(U\) and non-negative integers \(f(x)\) for all \(x\in U\). Then, by taking the sum of products of them, we have an integer \[ \text{SP}_ f({\mathcal A})=\sum_{A\in{\mathcal A}} \prod_{x\in A}f(x) \leqno(1) \] for each subfamily \({\mathcal A}\subset2^ U-\{\emptyset\}\), especially, for any covering \({\mathcal A}\) of \(U\); and we can consider the following problem: For given \(U\), \(f\) as above and a covering \({\mathcal B}\) of \(U\), find effectively \({\mathcal A}\) in such coverings \({\mathcal A}'\) that \({\mathcal B}\) is a refinement of \({\mathcal A}'\) so that the function \(\text{SP}_ f\) in (1) takes the minimum value at \({\mathcal A}\) among such coverings \({\mathcal A}'\). We call \({\mathcal A}\) in this problem an MSPD for \(\langle U,{\mathcal B},f\rangle\) simply. Of course, an MSPD exists and any MSPD can be found by calculating \(\text{SP}_ f({\mathcal A}')\) for all finitely many such \({\mathcal A}'\); but the number of \({\mathcal A}'\) may increase rapidly as \(| U|\) increases. (\(| X|\) denotes the number of elements in a finite set \(X\).) We establish an effective method of finding an MSPD of special type, which is applicable even when \(| U|\) may be large. We give an algorithm to find an MSPD which is effective when \(| U|\leq20\) and \(|{\mathcal B}|\leq200\) and which is applicable for statistical database designs.