Appendix 2. Size of search

Number of partitions of size p1,..., p_q

Let N_q,m denote the number of normal disjunctive regular partitions of size p₁,...,p_q from an attribute set of m attributes (or, in the terminology of the lock and key algorithm in Appendix 1, N_q,m is the number of ways of selecting q groups of objects from a pool of m objects, with no embedding).

Consider first, the special case p₁ = p₂ = ... = p_q = p. Then, with c = ^mC_p, N_q,m = ^cC_q since there are c possible groups and N_q,m ways of picking q of them.

When the p_i's are not all equal then there is no simple general formula for N_q,m. Consider first q = 2 and suppose p₁ ≥ p₂. Let c_i = ^mC_pi for i = 1,2 and c₁₂ = p₁Cp₂. Then it can be shown that

N_2,m = (c₁c₂-c₁c₁₂)/e!

where e is the number of times a p_i is repeated, that is, either 1 or 2. e = 2 when p₁ = p₂ and the formula coincides with that given by N_q,m above.

For the case q = 3 define, as above, c_jk = ^p_jC_pk and, additionally, c'_jk = ^m-p_kC_pj-pk, then it can be shown that

N_3,m = (c₁c₂c₃-c₁c₃c₁₂-c₁c₂c₁₃-c₁c₂c₂₃+c₁c₁₂c₁₃+c₃c'₁₃c'₂₃)/e!

where e is the number of times a p_i is repeated, either 1,2 or 3. The following table gives values of N_q,m by these formulae:

Table of N_q,m

I have been unable to derive a general formula for q ≥ 4 when the p_i's are possibly unequal. The best that I have achieved is an upper bound. Suppose the unique elements of p₁,..., p_q are denoted u₁,...,u_r where r ≤ q and that u_i is repeated q_i times. Then with d_i = ^mC_qi and M_i = ^diC_ui

This upper bound may be pessimistic and may not give a good indication of the search size. However, in practice, searches with q ≥ 4 will be prohibitive anyway.

The actual number of partitions is 2 ×Nq,m if the disjunctive and conjunctive forms are both evaluated. The above formulæ are those used to produce the #( Class) values in the Search Extent Box (see below) .

When Up to p_1..p_q is checked in the Extent dialog, all partitions up to the specified size are generated, as discussed in section 14.2. Some of these may automatically be skipped to avoid duplication. Also if Conjunctive and disjunctive is checked, the search is effectively doubled, as discussed in section 14.3. In this case the overall search sizes are in the following table:

If the search entails sub-searching over cuts with full fine tuning (see 16.1) , and each variable in the attribute set has precisely l levels, then the scale of every sub-search is exactly S = l^vwhere v = p₁+p₂+...+p_q and the full extent of a search is N_q,m×S.

16.1

Sub-searches will differ in their extent if variables have an unequal number of cuts and the full extent of the search is the sum of the sub-search sizes of each of the N_q,m regular partitions. This is not known in advance of actually doing the search. However, an estimate of the full extent of a search can be obtained from N_q,m×E(S) where E(S) is the expected size of each sub-search and which is calculated from

where l_i is the number of cuts for variable x_i and the summation is over all ways of choosing vintegers, j₁,...,j_v, from 1,...,m, and ∑1 is the number of terms in the same summation. With limited fine tuning (see 16.1) N_q,m×E(S) provides an upper bounds which may be in excess of the actual search size. The formulæ for S or E(S) provide the #( SubSch) numbers in the Search Extent Box.

Search Extent Box

One feature of the output log that is given when a search is done is the Search Extent Box:

It gives a breakdown of the expected and actual extent of a search. The ANTICIPATED columns refer to numbers calculated before the search is carried out. The ACTUAL columns give the results of what actually occurred in the search.

The "#( Class)" column gives the computed anticipated extent of the p₁,...,p_q class, that is,N_q,m (see Appendix A2.1) . This number may be exact or an approximation. Approximations are tagged with a ~ symbol.

Appendix A2.1

The "#( Excl)" column gives the number of partitions that are expected to be excluded, usually 0 but in iterative mode partitions not containing the attribute of the previous iteration will be skipped. (see Appendix 6).

The "#( SubSch)" gives the anticipated number of sub- searches required if cuts are floating. This value is 1 for fixed cuts. For floating cuts the number is an estimate of the expected number of sub-searches for each partition. The number is exact if every variable in the attribute set has the same number of cuts (see Appendix A2.2)

The #( Search) gives the anticipated total size of the search and is calculated from :

#( Search) = { #( Class)- #( Excl)} * #( SubSch)

The #( Done) column gives the actual number of partitions generated and #( Skipped) the number skipped.

Skipped partitions

Partitions may be skipped for a number of reasons. Primarily, they are skipped in iterative mode if the partition does not include the attribute found on the previous iteration, for they must then have been covered on previous iterations. Sometimes an entire class may be skipped and shown with the message All skipped; subset of ... This will arise when searching up to a given p1,...,pq when an entire class is theoretically determined as a sub-class of some other. A full discussion of why partitions may be skipped is given in Appendix 6.

[Back to table of contents]