Absolute Bounds on Set Intersection and Union Sizes from Distribution Information.
A catalog of quick closed-form bounds on set intersection and union sizes is presented; they can be expressed as rules, and managed by a rule-based system architecture. These methods use a variety of statistics precomputed on the data, and exploit homomorphisms (onto mappings) of the data items onto distributions that can be more easily analyzed. The methods can be used anytime, but tend to work best when there are strong or complex correlations in the data. This circumstance is poorly handled by the standard independence-assumption and distributional-assumption estimates.
r
e
methods for data in a database, especially when joins are involved. Such estimation is necessary fo
stimates of paging or blocks required. But often absolute bounds on such sizes can serve the purpose
of estimates, for several reasons:
1. Absolute bounds are more often possible to compute than estimates. Estimates generally
d
a
require distributional assumptions about the data, assumptions that are sometimes difficult an
wkward to verify, particularly for data subsets not much studied. Bounds require no assumptions

. Bounds are often easier to compute than estimates, because the mathematics, as we shall see,
can be based on simple principles - rarely are integrals (possibly requiring numerical approxima-
ion) needed as with distributions. This has long been recognized in computer science, as in the
a
analysis of algorithms where worst-case (or bounds) analysis tends to be much easier than
verage-case.
3. Even when bounds tend to be weak, several different bounding methods may be tried and the
e
best bound used. This paper gives some quite different methods that can be used on the sam
roblems.
4. Bounds fill a gap in the applicability of set-size determination techniques. Good methods exist
e
when one can assume independence of the attributes of a database, and some statistical techniques
xist when one can assume strong but simple correlations between attributes. But until now there
ave been few techniques for situations with many and complicated correlations between attri-
butes, situations bounds can address. Such circumstances occur more with human-generated data
han natural data, so with increasing computerization of routine bureaucratic activity we may seemore of them.
. Since choices among database access methods are absolute (yes-or-no), good bounds on the
e
sizes of intersections can sometimes be just as helpful for making decisions as "reasonable-guess
stimates, when the bounds do not substantially overlap between alternatives.
6. Bounds in certain cases permit absolutely certain elimination (pruning) of possibilities, as i
ranch-and-bound algorithms and in compilation of database access paths. Bounds also help random
sampling obtain a sample of fixed size from an unindexed set whose size is not known, since
error retrieving too few items is much worse than an error retrieving too many.
a
s
7. Bounds also provide an idea of the variance possible in an estimate, often more easily than
tandard deviation. This is useful for evaluating retrieval methods, since a method with the sameestimated cost as another, but tighter bounds, is usually preferable.
. Sizes of set intersections are also valuable in their own right, particularly with "statistical data-
bases" [16], databases designed primarily to support statistical analysis. If the users are doing
exploratory data analysis" [18], the early stages of statistical study of a data set, quick estimates
s
are important and bounds may be sufficient. This was the basis of an entire statistical estimation
ystem using such "antisampling" methods [14].
9. Bounds (and especially bounds on counts) are essential for analysis of security of statistical
A
databases from indirect inferences [5].
s with estimates, precomputed information is necessary for bounds on set sizes. The more space
e
allocated to precomputed information, the better the bounds can be. Unlike most work with
stimates, however, we will exploit prior information besides set sizes, including extrema,
frequency statistics, and fits to other distributions. We will emphasize upper bounds on
ntersection sizes, but we will also give some lower bounds, and also some bounds on set unions
and complements.
ince set intersections must be defined within a ""universe"" U, and we are primarily interested in
s
database applications, we will take U to be a relation of a relational database. Note that imposin
elections or restrictions on a relation is equivalent to intersecting sets of tuples defining those
s
selections. Thus, our results equivalently bound the sizes of multiple relational-database selection
n the same relation.
Section 2 of this paper reviews previous research, and Section 3 summarizes our method of
c
obtaining bounds. Section 4 examines in detail the various frequency-distribution bounds
overing upper bounds on intersections (section 4.1), lower bounds on intersections (section 4.2),
c
bounds on unions (section 4.4), bounds on arbitrary Boolean expressions for sets (section 4.6), and
oncludes (section 4.7) with a summary of storage requirements for these methods. Section 5
a
evaluates these bounds both analytically and experimentally. Section 6 examines a different bu
nalogous class of bounds, range-analysis, first for univariate ranges (section 6.1), thenmultivariate (section 6.2).
. Previous work
Analysis of the sizes of intersections is one of several critical issues in optimizing database query
performance; it is also important in optimizing execution of logic-programming languages like Prolog
The emphasis in previous research on this subject has been almost entirely on developing estimates, no
ounds. Various independence and uniformity assumptions have been suggested (e.g., [4] and [11]).
These methods work well for data that has no or minor correlations between attributes and between sets
ntersected, and where bounds are not needed.
Christodoulakis [2] (work extending [9]) has estimated sizes of intersections and unions where
r
correlations are well modeled probabilistically. He uses a multivariate probability distribution to
epresent the space of possible combinations of the attributes, each dimension corresponding to a set
being intersected and the attribute defining it. The size of the intersection is then the number of points
n a hyperrectangular region of the distribution. This approach works well for data that has a few
s
a
simple but possibly strong correlations between attributes or between sets intersected, and where bound
re not needed. Its main disadvantages are (1) it requires extensive study of the data beforehand to
d
l
estimate parameters of the multivariable distributions (and the distributions can change with time an
ater become invalid), (2) it only exploits count statistics (what we call level 1 and level 5 information
in section 4), and (3) it only works for databases without too many correlations between entities.
imilar work is that of [7]. They model the data by coefficients equivalent to moments. They do not
O
use multivariate distributions explicitly, but use the independence assumption whenever they can
therwise they partition the database along various attribute ranges (into what they call "betas", what
a
[5] calls "1-sets", and what [12] calls "first-order sets") and model the univariate distributions on every
ttribute. This approach does allow modeling of arbitrary correlations in the data, both positive and
e
d
negative, but requires potentially enormous space in its reduction of everything to univariat
istributions. It can also be very wasteful of space, since it is hard to give different correlation
d
phenomena different granularities of description. Again, the method expoits only count statistics an
nly gives estimates, not bounds.
Some relevant work involving bounds on set sizes is that of [8], which springs from a quite different
c
motivation that ours (handling of incomplete information in a database system), and again only uses
ount statistics. [10] investigates bounds on the sizes of partitions of a single numeric attribute using
e
a
prior distribution information, but does not consider the much more important case of multipl
ttributes.
There has also been relevant work over the years on probabilistic inequalities [1]. We can divide
f
counts by the size of the database to turn them into probabilities on a finite universe, and apply some
hese mathematical results. However, the first and second objections of section 1 apply to this work: it
l
d
usually makes detailed distributional assumptions, and is mathematically complex. For practica
atabase situations we need something more general-purpose and simpler.
3. The general method
e present two main approaches to calculation of absolute bounds on intersection and union sizes in
this paper.
uppose we have a census database on which we have tabulated statistics of state, age, and income.
a
Suppose we wish an upper bound on the number of residents of Iowa that are between the ages of
nd 34 inclusive, when all we know are statistics on Iowa residents and statistics on people age 30-34
eseparately. One upper bound would be the frequency of the mode (most common) state for people ag
0-34. Another would be five times the frequency of the most common age for people living in Iowa
s
(since there are five ages in the range 30-34). These are examples of frequency-distribution bound
discussed in section 4), to which we devote primary attention in this paper.
e
Suppose we also have income information in our database, and suppose the question is to find th
umber of Iowans who earned over 100,000 dollars last year. Even though the question has nothing to
d
with ages, we may be able to use age data to answer this question. We obtain the maximum and
s
minimum statistics on the age attribute of the set of Americans who earned over 100,000 dollar
combining several subranges of earnings to get this if necessary), and then find out the number of
Americans that lie in that age range, and that is an upper bound. We can also use the methods of the
receding paragraph to find the number of Iowans lying in that age range. This is an example of
O
range-restriction bounds (discussed in section 6).
ur basic method for both kinds of bounds is quite simple. Before querying any set sizes, preprocess
the data:
Group the data items into categories. The categories may be arbitrary.
(2) Count the number of items in each category, and store statistics characterizing (in some way
these counts.
Now when bounds on a set intersection or union are needed:
(3) Look up the statistics relevant to all the sets mentioned in the query, to bound certain subse
counts.
(4) Find the minima (for intersections) or maxima (for unions) of the corresponding counts for each
subset.
Sum up the minima (or maxima) to get an overall bound on the intersection size.
All our rules for bounds on sizes of set intersections will be expressed as hierarchy of differen
"levels"" of statistics knowledge about the data. Lower levels mean less prior knowledge, but
generally poorer bounding performance.
he word ""value"" may be interpreted as any equivalence class of data attribute values. This
means that prior counts on different equivalence classes may be used to get different bounds on
he same intersection size, and the best one taken, though we do not include this explicitly in ourformulae.
. Frequency-distribution bounds
We now examine bounds derived from knowledge (partial or complete) of frequency distributions ofattributes.
.1. Upper frequency-distribution bounds
y
I
4.1.1. Level 1: set sizes of intersected sets onl
f we know the sizes of the sets being intersected, an upper bound ("sup") on the size of the intersection
is obviously
where n (i ) is the size of the ith set and s is the number of sets
s
4.1.2. Level 2a: mode frequencies and numbers of distinct value
uppose we know the mode (most common) frequency m (i , j ) and number of distinct values d (i , j ) for
some attribute j for each set i of s total. Then an upper bound on the size of the intersection is
ss
prove this: (1) an upper bound on the mode frequency of the intersection is the minimum of the
e
mode frequencies; (2) an upper bound on the number of distinct values of the intersection is th
inimum of the number for each set; (3) an upper bound on the size of a set is the product of its mode
e
frequency and number of distinct values; and (4) an upper bound on the product of two nonnegativ
ncertain quantities is the product of their upper bounds.
e
If we know information about more than one attribute of the data, we can take the minimum of th
pper bound computations on each attribute. Letting r be the number of attributes we know these
statistics about, the revised bound is:
min
ss
special case occurs when one set being intersected has only one possible value on a given attribute-
that is, the number of distinct values is 1. This condition can arise when a set is defined as a partition
f the values on that attribute, but also can occur accidentally, particularly when the set concerned is
small. Hence the bound is the first of the inner minima, or the minimum of the mode frequencies on
hat attribute. For example, an upper bound on the number of American tankers is the mode frequency
of tankers with respect to the nationality attribute.
he second special case is the other extreme, when one set being intersected has all different values forsome attribute, or a mode frequency of 1. This arises from what we call an "extensional key" ([12], ch
functions like a key to a relation but only in a particular database
r
e
state. Hence the first bound is the minimum of the number of distinct values on that attribute. Fo
xample, an upper bound on the number of American tankers in Naples, when we happen to know
r
Naples requires only one ship per nationality at a time, is the number of different nationalities fo
ankers at Naples.
4.1.3. Level 2b: a different bound with the same information
A different line of reasoning leads to a different bound utilizing mode frequency and number of distinc
alues, an "additive" bound instead of the "multiplicative" one above. Consider the mode on some
attribute as partitioning a set into two pieces, those items having the mode value of the attribute, and
hose not. Then a bound on the size of the intersection of r sets is
min
r
s
s
prove this, let R be the everything in set i except for its mode, and consider three cases. Case 1:
e
assume the set i that satisfies the first inner min above also satisfies the second inner min. Then the
xpression in brackets is just the size of this set. But if such a set has minimum mode frequency and
f
minimum-size R , it must be the smallest set. Therefore its size must be an upper bound on the size
the intersection.
ase 2: assume set i satisfies the first inner min, some other set j satisfies the second inner min, and sets
have the same mode (most common value). We need only consider these two sets, because an
pper bound on their intersection size is an upper bound on the intersection of any group of sets
c
ontaining them. Then the minimum of the two mode frequencies is an upper bound on the mode
r
frequency of the intersection, and the minima of the sizes of R and R is an upper bound on the R fo
the intersection. Thus the sum of two minima on s is a minimum on s.
ase 3: assume set i satisfies the first inner min, set j satisfies the second inner min, and i and j have
s
f
different modes. Let the mode frequency of i be a and that of j be d; suppose the mode of i ha
requency e in set j, and suppose the rest of j (besides the d+e) has total size f. Furthermore suppose
that the mode of j has frequency b in set i, and the rest of i (besides the a+b) has total count c. Then
he 2b bound above is a +e But in the actual intersection of the two sets, a would match with e, b
with d, and c with f, giving an upper bound of min(a ,e )+min(b ,d )+min(c , f ). But e -min(a ,e )
lastly a -min(b ,d ) because a -b . Hence our 2b bound is an upper bound on the
actual intersection size.
ut the above bound doesn't use the information about the number of distinct values. If the set i that
d
minimizes the last minima in the formula above contains more than the minimum of the number of
istinct values d(i,j) over all the sets, we must "subtract out" the excess, assuming conservatively that
the extra values occur only once in set i:
min
ss
t would seem that we could do better by subtracting out the minimum mode frequency the sets a
number of times corresponding to the minima of the number of distinct values over all the sets
owever, this reduces to the level 2a bound.
s
A
4.1.4. Level 2c: Diophantine inferences from sum
different kind of information about a distribution is sometimes useful when the attribute is numeric:
its sum and other moments on the attribute for the set. (Since the sum and standard deviation require
he same amount of storage as level 2a and 2b information, we call them another level 2 situation.)
a
This information is only useful when (a) we know the set of all possible values for the universal set
nd (b) there are few of these values relative to the size of the sets being intersected. Then we can
f
write a linear Diophantine (integer-solution) equation in unknowns representing the number
ccurrences of each particular numeric value in each of the sets being intersected, and each solution
s
represents a possible partition of counts on each value. An upper bound on the intersection size is thu
he sum over all values of the minimum over all sets of the maximum number of occurrences of a
s
particular value for a particular set. See [13] for a further discussion of Diophantine inferences abou
tatistics. A noteworthy feature of Diophantine equations is the unpredictability of their number ofsolutions.
.1.5. Level 3a: other piecemeal frequency distribution information
e
f
The level 2 approach will not work well for sets and attributes that have relatively large mod
requencies. We could get a better (i.e. lower) upper bound if we knew the frequencies of other values
than the mode. Letting m2(i,j) represent the frequency of the second most common value of the ith se
n the jth attribute, a bound is:
min
(min m2(i , j ))* ((min d (i , j ))-1)
ss
or this we can prove by contradiction that the frequency of the second most common value of the
s
intersection cannot occur more than the minimum of the frequencies of the second most common value
f those sets. Let M be the mode frequency of the intersection and let M2 be the frequency of the
s
econd most common value in the intersection. Assume M2 is more than the frequency of the second
most common value in some set i. Then M2 must correspond to the mode frequency of that set i. Bu
hen the mode frequency of the intersection must be less than or equal to the frequency of the second
F
most frequent value in set i, which is a contradiction.
or knowledge of the frequency of the median-frequency value (call it mf(i,j)), we can just divide the
e
outer minimum into two parts (assuming the median frequency for an odd number of frequencies is th
igher of the two frequencies it theoretically falls between):
min
r
s
s
s
s
ss
min
*min d (i , j )
/2The mean frequency is no use since this is always the set size divided by the number of distinct values
.1.6. Level 3b: a different bound using the same information
e
In the same way that level 2b complements level 2a, there is a 3b upper bound that complements th
receding 3a bound:
min
ss
Here we don't include the median frequency because an upper bound on this for an intersection is not
l
f
the minimum of the median frequencies of the sets intersected.) The formula can be improved stil
urther if we know the frequency of the least common value on set i, and it is greater than 1: justmultiply the maximum of (d(i,j)-d(k,j)) above by this least frequency for i before taking the minimum.
.1.7. Level 4a: full frequency distribution information
r
e
An obvious extension is to knowledge of the full frequency distribution (histogram) for an attribute fo
ach set, but not which value has which frequency. By similar reasoning to the last section the bound
is:
r
s
here freq(i,j,k) is the frequency of the kth most frequent value of the ith set on the jth attribute. This
s
follows from recursive application of the first formula for a level-2b bound. First we decompose the
ets into two subsets each, for the mode and non-mode items; then we demcompose the non-mode
d
subsets into two subsets each, for their mode and non-mode items; and so on until the frequency
istributions are exhausted.
We can still use this formula if all we know is an upper bound on the actual distribution-we just get a
a
c
weaker bound. Thus there are many gradations between level 3 and level 4a. This is useful because
lassical probability distribution (like a normal curve) that lies entirely above the actual frequency
A
distribution can be specified with just a few parameters and thus be stored in very little space.
s an example, suppose we have two sets characterized by two exponential distributions of numbers
between 0 and 2. Suppose we can upper-bound the first distribution by 100e and the second by
-x
00e , so there are about 86 of each set. Then the distribution of the set intersection is bounded
above by the minimum of those two distributions. So an upper bound on the size of the intersection is
x -22
A
4.1.8. Level 4b: Diophantine inferences about values
different kind of Diophantine inference than that discussed in 4.1.4 can arise when the data
distribution is known for some numeric attribute. We may be able to use the sum statistic for se
alues on that attribute, plus other moments, to infer a list of the only possible values for each set being
intersected; then the possible values for the intersection set must occur in every possibility list. We ca
se this to upper-bound size of the intersection as the product of an upper bound on the mode frequency
of the intersection and the number of possible values of the intersection. To make this solutio
ractical we require that (a) the number of distinct values in each set being intersected is small with
l
respect to the size of the set, and (b) the least common divisor of the possible values be not too smal
say less than .001) of the size of the largest possible value. Then we can write a linear Diophantine
e
equation in unknowns which this time are the possible values, and solve for all possibilities. Again, se
13] for further details.
4.1.9. Level 5: tagged frequency distributions
Finally, the best kind of frequency-distribution information we could have about sets would specify
exactly which values in each distribution have which frequencies. This gives an upper bound of:
r
s
here gfreq(i,j,k) is the frequency of globally-numbered value k of attribute j for set i, which is zero
when value k does not occur in set i, and where d(U,j) is the number of distinct values for attribute j i
he data universe U.
All that is necessary to identify values is a unique code, not necessarily the actual value. Bit strings
can be used together with an (unsorted) frequency distribution of the values that do occur at least once
otice that level 5 information is analogous to level 1 information, as it represents sizes of particular
subsets formed by intersecting each original set with the set of all items in the relation having a
articular value for a particular attribute. This is what [12] calls "second-order sets" and [5] "2-sets".Thus we have come full circle, and there can be no "higher" levels than 5.
.2. Lower bounds from frequency distributions
On occasion we can get nonzero lower bounds ("inf") on the size of a set intersection, when the size ofthe data universe U is known, and the sets being intersected are almost its size.
.2.1. Lower bounds: levels 1 and 5
A set intersection is the same as the complement (with respect the universe) of the set union of the
r
complements. An upper bound on the union of some sets is the sum of their set sizes. Hence a lowe
ound on the size of the intersection, when the universe U is size N, is
s
s
hich is the statistical form of the simplest case of the Bonferroni inequality. For most sets of interest
a database user this will be zero since the sum is at most sN. But with only two sets being
e
e
intersected, or sets corresponding to weak restrictions (that is, sets including almost all the univers
xcept for a few unusual items, sets intersected with others to get the effect of removing those items), a
F
nonzero lower bound may more often occur.
or level 5 information the bound is:
r
s
here gfreq(i,j,k) is as before the number of occurrences of the kth most common value of the jth
a
attribute for the ith set, U is the universe set, and d(U,j) is the number of distinct values for attribute
mong the items of U.I
4.2.2. Lower bounds: levels 2, 3, and
t is more difficult to obtain nonzero lower bounds when statistical information is not tagged to specific
e
f
sets, as for what we have called levels 2, 3, and 4. If we know the mode values as well as the mod
requencies, and the modes are all identical, we can bound the frequency of the mode in the intersection
s
by the analogous formula to level using the mode frequency of the universe (if the mode i
dentical) for N. Without mode values, we can infer that modes are identical for some large sets,
whenever for each
c
where m(i,j) is the mode frequency of set i on attribute j, m2(i,j) the frequency of the second mos
ommon value, n(i) the size of set i, and N the size of the data universe.
The problem for level 4 lower bounds is that we do not know which frequencies have which values
ut if we have some computer time to spend, we can exhaustively consider combinatorial possibilities,
excluding those impossible given the frequency distribution of the universe, and take as the lower
ound the lowest level-5 bound. For instance, with an implementation of this method in Prolog, we
e
considered a universe with four data values for some attribute, where the frequency distribution of th
niverse was (54, 53, 52, 51), and the frequency distributions of the two sets intersected were (40, 38,
22, 20) and (30, 23, 21, 16). The level 4a lower bound was 8, and occurred for several matchings
ncluding:
r
The level 1 lower bound is 210 - 120 - so the effort may be worth it. (The level 1 and 4 uppe
ounds are both But the number of combinations that must be considered for
distinct values in the universe is (k !) .A
4.2.3. Definitional sets
nother very different way of getting lower bounds is from knowledge of how the sets intersected were
defined. If we know that set i was defined as all items having particular values for an attribute j, then
n analyzing an intersection including set i, the "definitional" set i contributes no restrictions on
attributes other than j and can be ignored. This is redundant information with levels 1 and 5, but i
ay help with the other levels. For instance, for i1 definitional on attribute j, a lower bound on the
f
s
size of the intersection of sets i1 and i2 is the frequency of the least frequent value (the "antimode")
et i2 on j.
4.3. Better bounds from relaxation on sibling sets
oth upper and lower bounds can possibly be improved by relaxation among related sets in the manner
c
of [3], work aimed at protection of data from statistical disclosure. This requires a good deal more
omputation time than the closed-form formulae in this paper and requires sophisticated algorithms.Thus we do not discuss it here.
.4. Set unions
Rules analogous to those for intersection bounds can be obtained for union bounds. Most of these arelower bounds.
.4.1. Defining unions from intersections
Since
means the size of the union of set i and set j, and n (i j ) means the size of thei
ntersection, extending our previous notation for set size, it follows that
using the distribution of intersection over union, and
ss
s
s
s
Another approach to unions is to use complements of sets and DeMorgan's Law
A (i )
s
s
ss
A (i )
he problem with using this is the computing of statistics on the complement of a set, something
I
difficult for level 2, 3, and 4 information.
one important situation the calculation of union sizes is particularly easy: when the two sets unioned
s
are disjoint (that is, their intersection is empty). Then the size of the union is just the sum of the se
izes, by the first formula in this section. Disjointness can be known a priori, or we can infer it usingmethods in section 6.1.2.
.4.2. Level 1 information for unions
To obtain union bounds rules from intersection rules, we can do a "compilation" of the above formulae
(section 3.5.5 of [12] gives other examples of this process) by substituting rules for intersections in
hem, and simplifying the result. Substituting the level 1 intersection bounds in the above set-
complement formula:
A (i )
ss
sup(n
A (i )
s
s
s
ere we use the standard notation of "inf" for the lower bound and "sup" for the upper bound.
I
4.4.3. Level 2b unions
f we know the mode frequency m(i,j) and the number of distinct values d(i,j) on attribute j, then we
can use a formula analogous to the level 2b intersection upper bound, a lower bound on the union:
ss
4.4.4. Level 2a unions
he approach used in level 2a for intersections is difficult to use here. We cannot use the negation
s
formula to relate unions to intersections because there is no comparable multiplication of two quantitie
like mode frequency and number of distinct values) that gives a lower bound on something. However,
for two sets we can use the other (first) formula relating unions to intersections, to get a union lower
ound:
For three sets, it becomes
r
+min(m (i 2,j ),m (i 3,j ))* min(d (i 2,j ),d (i 3, j
rj =The formulae get messy for more sets
.4.5. Level 3b unions
Analogous to level 2b, we have the lower bound
ss
here m2(i,j) is the frequency of the second most common value of set i on attribute j. And if we
a
know the frequency of the least common value in set i, we multiply the maximum of (d(k,j)-d(i,j)
bove by it before taking the maximum.
A
4.4.6. Level 3a unions
nalogous to level 2a, and to level 3a intersections, we have for the union of two sets a lower bound
of:
f
where m2 is the frequency of the second most common value, and mf the frequency of the median
requency value.
s
4.4.7. Level 4 union
he analysis of level 4 is analogous to that of section 4.1.7, giving a lower bound of
r
s
here freq(i,j,k) is the frequency of the kth most frequent value of the ith set unioned on the jthattribute.
.4.8. Level 5 unions
Level 5 is analogous to level 1
r
s
s
up: min
4.5. Complements
our coverage of set algebra we need set complements. The size of a complement is just
the difference of the size N of the universe U (something that is often important, so we ought to know
t) and the size of the set. An upper bound on a complement is N minus a lower bound on the size ofthe set; a lower bound on a complement is N minus an upper bound on the size of the set.
.6. Embedded set expressions
So far we have only considered intersections, unions, and complements of simple sets about which we
e
know exact statistics. But if the set-description language permits arbitrary embedding of query
xpressions, new complexities arise.
One problem is that the formulae of sections 4.1-4.4 require exact values values for statistics, and such
statistics are usually impossible for an embedded expression. But we can substitute upper bounds
he embedded-expression statistics in upper-bound formulae (or lower bounds when preceded in the
f
formula by a minus sign). Similarly, we can substitute lower bounds on the statistics in lower-bound
ormulae (or upper bounds when preceded in the formula by a minus sign). This works for statistics on
counts, mode frequency, frequency of the second-most common value, and number of distinct items-
ut not the median frequency.
s
A
4.6.1. Summary of equivalence
nother problem is that there can be many equivalent forms of a Boolean-algebra expression, and we
A
have to be careful which equivalent form we choose because different forms give different bounds
ppendix A surveys the effect of various equivalences of Boolean algebra on bounds using level 1
information. Commutativity and associativity do not affect bounds, but factoring out of common sets i
conjuncts or disjuncts with distributive laws is important since it usually gives better bounds and canno
orsen them. Factoring out enables other simplification laws which usually give better bounds too.
e
The formal summary of Appendix A is in Figure 1 ("yes" means better in all but trivial cases).
hese transformations are sufficient to derive set expression equivalent to another a set expression, the
a
information in the table is sufficient to determine whenever one expression is always better than
nother.
4.6.2. The best form of a given set expression, for level 1 information
e
So the best form for the best level 1 bounds is a highly factored form, quite different from a disjunctiv
ormal form or a conjunctive normal form. The number of Boolean operators doesn't matter, more the
l
number of sets they operate on, so we don't want the "minimum-gate" form important in classica
oolean optimization techniques like Karnaugh maps. So minimum-term form [6] seems to be closest
to what we want; note that all the useful transformations in the above table reduce the number of terms
n an expression. Minimum-term form makes sense because multiple occurrences of the same term
f
should be expected to cause suboptimal bounds arising from failure to exploit the perfect correlation
tems in the occurrences. Unfortunately, the algorithms in [6] for transforming a Boolean expression to
this form are considerably more complicated than the one to a minimum-gate form.
inimum-term form is not unique. Consider these three equivalent expressions:
e
l
These cannot be ranked in a fixed order, though they are all preferable (by their use of a distributiv
aw) to the unfactored equivalent
we may need to compute bounds on each of several minimum-term forms, and take the best bounds.
This situation should not arise very often, because users will query sets with few repeated mentions of
he same set-parity queries are rarely needed.
Another problem with the minimum-term form is that it does not always give optimal bounds. For
r
instance, let set A in the above be the union of two new sets D and E. Let the sizes of B, C, D, and E
espectively be 10, 7, 7, and 8. Then the three factored forms give upper bounds respectively of
min(15,17)+min(10,7)=22, min(10,22)+min(15,7)=17, and min(7,25)+min(15,10)=17. But the first form
s the minimum-term form, with 6 terms instead of 7. However, this situation only arises when there
are different ways to factor, and can be forestalled by calculating a bound separately for the minimum
erm form corresponding to every different way of factoring.
4.6.3. Embedded expression forms with other levels of informatio
evel 5 is analogous to level 1-it just represents a partition of all the sets being intersected into subsets
r
of a particular range of values on a particular attribute, with bounds being summed up on all such
anges of values of the attribute. Thus the above "best" forms will be equally good for level 5
e
information. Analysis is considerably more complicated for levels 2, 3, and 4 since we do not hav
oth upper and lower bounds in those cases. But the best forms for level 1 can be used heuristically
then.
4.7. Analysis of storage requirements
.7.1. Some formulae
Assume a universe of r attributes on N items, each attribute value requiring an average of w bits of
storage. The database thus requires rNw bits of storage. Assume we only tabulate statistics on "1-sets"
5] or "first-order sets" [12] or universe partitions by the values of single attributes. Assume there are
s
f
approximately even partitions on each attribute. Then the space required for storage of statistics is a
ollows:
Level 1: there are mr sets with just a set size tabulated for each. Each set size should average
e
about N /m , and should require about log (N /m ) bits, so a total of mr* log (N /m ) bits ar
required. This will tend to be considerably less than rNw, the size of the database, because
ill likely be on the same order as log (N /m ), and m is considerably less than N.
Level 2: for each of the mr sets we have 2r statistics (the mode frequency and number of distinct
values for each attribute). (This assumes we do not have any criteria to claim certain attributes as
eing useless, as when their values exhibit no significantly different distributions for different
sets-if not, we replace r by the number of useful attributes.) Hence we need 2mr log (N /m ) bits.2
e
Level 3: we need twice as much space as level 2 to include the second highest frequency and th
edian frequency statistics too, hence 4mr log (N /m ) bits.
evel 4: we can describe a distribution either implicitly (by a mathematical formula
a
d
approximating it) or explicitly (by listing of values). For implicit storage, we need to specify
istribution function and absolute deviations above and below it (since the original distribution is
s
f
discrete, it is usually easier to use the corresponding cumulative distributions). We can use code
or common distributions (like the uniform distribution, the exponential, and the Poisson), and we
f
need a few distribution parameters of w bits, plus the positive and negative deviation extrema
bits each too. So space will be similar to level 3 information.
e
d
If a distribution is not similar to any known distribution, we must represent it explicitly. Assum
ata items are aggregated into approximately equal-size groups of values; the m-fold partitioning
r
that defined the original sets is probably good (else we would not have chosen it for the othe
urpose originally), so let us assume it. Then we have a total of m r log (N /m ) bits. If some of
the groups of values (bins) on a set are zero, we can of course omit them and save space
evel 5: this information is similar to level 4 except that values are associated with points of the
distribution. Implicit representation by good-fit curves requires just as much space as level-4
mplicit representation-we just impose a fixed ordering of values along the horizontal axis instead
of sorting by frequency. Explicit representation also takes the level 4 of m r log (N /m ), but a
alternative is to give pairs of values and their associated frequencies, something good when dat
alues are few in number.
We also need storage for access structures. If users query only a few named sets, we can just
a
store the names in a separate lexicon table mapping names to unique integer identifiers, requiring
total of m*r* (l +log mr ) bits for the table, where l is the average length of a name, assuming all
statistics on the same set are stored together.
But if users want to query arbitrary value partitions of attributes, rather than about named sets,
a
we must also store definitions of the sets about which we have tabulated statistics. For sets that
re partitions of numeric attributes, the upper and lower limits of the subrange are sufficient, for
2mw bits each. But nonnumeric attributes are more trouble, because we usually have no
alternative than to list the set to which each attribute value belongs. We can do this with a has
able on value, for 2V log m bits assuming a 50% hash table occupancy. Thus total storage is
A
variety of compression techniques can be applied to storage of statistics, extending standard
d
compression techniques for databases [15]. Thus the storage calculations above can be considere
pper bounds.
These storage requirements are not necessarily bad, not even the level 4 and 5 explicit
distributions. In many databases, storage is cheap. If a set intersection is often used, or a bound
s needed to determine how to perform a large join when a wrong choice may mean hours or days
r
more time, quick reasoning with a few page fetches of precomputed statistics (it's easy to group
elated precomputed statistics on the same page) will usually be much faster than computing the
s
actual statistic or estimating it by unbiased sampling. That is because the number of page fetche
s by far the major determinant of execution time for this kind of simple processing. Computing
s
the actual statistic would require looking at every page containing items of the set; random
ampling will require examining nearly as many pages, even if the sampling ratio is small, because
r
d
except in the rare event in which the placement of records on pages is random (generally a poo
atabase design strategy), records selected will tend to be the only records used on a page, andthus most of the page-fetch effort is ""wasted."" Reference [14] discusses these issues further.
. Evaluation of the frequency-distribution bounds
5.1. Comparing bounds
e can prove some relationships between frequency-distribution bounds on intersections (see Figure 2):
1. Level 2b upper bounds are better than level 1 since
ss
s
s
s
-min n (i
. Level 3a upper bounds are better than level 2a because you get the latter if you substitutem(i,j) for m2(i,j) and mf(i,j) in the former, and m2(i , j )-m (i
. Level 3b upper bounds are better than level 2b because
s
s
s
ss
+min
d
4. Level 4a upper bounds are better than level 3a because the mode frequency is an upper boun
n the frequency of the half of the most frequent values, and the median frequency is an upper
s
bound on the frequency of the other half. Hence writing the level 3a expression in brackets as a
ummation of d(U,j) terms comparable to that in the level 4a summation, each level-3a term is an
upper bound on a corresponding level-4 term.
5. Level 4a upper bounds are better than level 2b since they represent repeated application oflevel-2b bounds to subsets of the sets intersected.
. Level 5 upper bounds are better than level 4a by the proof in Appendix B.
l7. Level 5 lower bounds are better than level 1 lower bounds because level 5 partitions the leve
sets into many subsets and computes lower bounds separately on each subset instead of all at
A
once.
nalogous arguments hold for bounds on unions since rules for unions were created from rulesfor intersections.
.2. Experiments
There are two rough guidelines for bounds on set intersection and union sizes to be more useful than
estimates of those same things:
1. Some of the sets being intersected or unioned are significantly nonindependent (that is, not
drawn randomly from some much larger population). Hence the usual estimates of their
ntersection size obtained from level 1 (size of the intersected sets) information will be poor.
f
2. At least one set being intersected or unioned has a significantly different frequency distributio
rom the others on at least one attribute. This requires that at least one set has values on an
attribute that are not randomly drawn.
hese criteria can be justified by the general homomorphism idea behind our approach (see
d
section 3): good bounds result whenever values in the range of the homomorphism get very
ifferent counts mapped onto them for each set considered. These criteria can be used to decidewhich sets on a database it might be useful to store statistics for computing bounds.
.2.1. Experiments: nonrandom sets
As a simple illustration, consider the experiments summarized in the tables of Figures 3 and 4. We
r
created a synthetic database of 300 tuples of four attributes whose values were evenly distributed
andom digits 0-9. We wrote a routine (MIX) to generate random subsets of the data set satisfying theabove two criteria, finding groups of subsets that had unusually many common values. We conducted
experiments each on random subsets of sizes 270, 180, 120, and 30. There were four parts to the
e
s
experiment, each summarized in a separate table. In the top tables in Figures 3 and 4, we estimated th
ize of the intersection of two sets; in the lower tables, we estimated the size of the intersection of four
sets. In Figure 3 the chosen sets had 95% of the same values; in Figure 4, 67%.
he entries in the tables represent means and standard deviations in 10 experiments of the ratios of
r
d
bounds or estimates to the actual intersection size. There are four pairs of columns for the fou
ifferent set sizes investigated. The rows correspond to the various frequency-distribution levels
discussed: the five levels of upper bounds first, then two estimate methods, then the two lower bound
ethods. (Since level 5 information is just level 1 information at a finer level of detail, it is easier to
e
generalize the level 1 estimate formula to a level 5 estimate formula.) Only level 2a and 3a rules wer
sed, not 2b and 3b.
The advantage of bounds shows in both Figure 3 and Figure 4, but more dramatically in Figure 3 where
c
sets have the 95% overlap. Unsurprisingly, lower bounds are most helpful for the large set sizes (lef
olumns), whereas upper bounds are most helpful for the small set sizes (right columns). However, the
e
lower bounds are not as useful because when they are close to the true set size (i.e. the ratio is near 1)
stimates are also close. But when upper bounds are close to the true set size for small sets, both
estimates and lower bounds can be far away.
.2.2. Experiments: real data
The above experiments were with synthetic data, but we found similar phenomena with real-world data.
A variety of experiments, summarized in [17], were done with data extracted from a database of
edical (rheumatology) patient records. Performance of estimate methods vs. our bounding methods
f
s
was studied for different attributes, different levels of information, and different granularities
tatistical summarization. Results were consistent with the preceding ones for a variety of set types.
d
This should not be surprising since our two criteria given previously are often fulfilled with medical
ata, where different measures (tests, observations, etc.) of the sickness of a patient often tend tocorrelate.
. Bounds from range analysis
Frequency-distribution bounds are only one example of a class of bounding methods involving
e
a
mappings (homomorphisms) of a set of data items onto a distribution. Another very important exampl
re bounds obtained from analysis on the range of values for some attribute, call it j, of the data items
c
for each set intersected. These methods essentially create new sets, defined as partitions on j, which
ontain the intersection or union being studied. These new sets can therefore can be included in the list
of sets being intersected or unioned without affecting the result, and this can lead to tighter (better)
ounds on the size of the result. Many formulas analogous to those of section 4 can be derived.6.1. Intersections on univariate ranges
.1.1. Statistics on partitions of an attribute
All the methods we will discuss require partition counts on some attribute j. That is, the number of
data items lying in mutually exclusive and exhaustive ranges of possible values for j. For instance, we
ay know the number of people ages 0-9, 10-19, 20-29, etc.; or the number of people with incomes 0-
r
9999, 10000-19999, 20000-29999, etc. We require that the attribute be sortable by something othe
han item frequency in order for this partioning to make sense and be different from the frequency-
distribution analysis just discussed; this means that most suitable attributes are numeric.
his should not be interpreted, however, as requiring anticipation of every partition of an attribute
f
that a user might mention in a query, just a covering set. To get counts on arbitrary subsets
he ranges, inequalities of the Chebyshev type may be used when moments are known, as for
instance Cantelli's inequalities:
[probability that x -l]-s /(s +l )
f
[probability that x -l]-l /(s +l
or - the mean and s the standard deviation of the attribute. Otherwise the count of a containingrange partition may be used as an upper bound on the subset count.
.1.2. Upper bounds from set ranges and bin counts on the universe (level 1)
Suppose we know partition (bin) counts on some numeric attribute j for the universe U. (We mus
now them for at least one set to apply these methods, so it might as well be the universe.) Suppose
we know the maximum h(i,j) and minimum l(i,j) on attribute j for each set i being intersected. Then an
upper bound on the maximum of the intersection H(j), and a lower bound on the minimum of th
ntersection are
ss
ote if H (j )<L ( j ) we can immediately say the intersection is the empty set. Similarly, for the union
of sets
ss
an intersection or union must be a subset of U that has values bounded by L(j) and H(j) on attribute
e
j, for any numeric attribute j. So an upper bound on the size of an intersection or union is th
inimum-size such range-partition set over all attributes j in Q, or
min
r
where s sets are intersected; where there are r numeric attributes; where B(x,j) denotes the number of
the bin into which value x falls on attribute j; and where binfreq(U,j,k) is the number of items in
artition (bin) k on attribute j for the universe U.
Absolute bounds on correlations between attributes may also be exploited. If two numeric attributes
r
have a strong relationship to each other, we can formally characterize a mapping from one to the othe
ith three items of information: the algebraic formula, an upper deviation from the fit to that formula
c
a
for the universe U, and a lower deviation. We can calculate these three things for pairs of numeri
ttributes on U, and store only the information for pairs with strong correlations. To use correlations in
y
s
finding upper bounds, for every attribute j we find L(j) and H(j) by the old method. Then, for ever
tored correlation from an arbitrary attribute j1 to an arbitrary attribute j2, we calculate the projection of
l
r
the range of j1 (from L(j1) to H(j1)) by the formula onto j2. The overlap of this range on the origina
ange of j2 (from L(j2) to H(j2)) is then the new range on j2, and L(j2) and H(j2) are updated if
r
necessary. Applying these correlations requires iterative relaxation methods since narrowing of the
ange of one attribute may allow new and tighter narrowings of ranges of attributes to which thatattribute correlates, and so on.
.1.3. Upper bounds from mode frequencies on bin counts for intersected sets (level 2)
e
At the next level of information, analogous to level 2 for frequency-distribution bounds, we can hav
nformation about distributions of values for particular sets. Suppose this includes an upper bound
e
f
m(i,j) on the number of things in set i in a bin of some attribute j. (This m(i,j) is like the mod
requency in section 4, except the equivalence classes here are all items in a certain range on a certain
r
attribute.) Assume as before we know what bins a given range of an attribute covers. Then an uppe
ound on the size of the set intersection is
min
sr
here H(j) and L(j) are as before. Similarly, an upper bound on the size of a set union is
min
6.1.4. Upper bounds from bin counts for intersected sets (level 5
inally, if we know the actual distribution of bin counts for each set i being intersected, we can modify
the intersection formula of level 1 as follows:
min
r
s
where s sets are intersected; where there are r numeric attributes; where B(x,j) is the number of the bi
nto which value x falls on attribute j; and where binfreq(i,j,k) is the number of items in partition (bin)
k on attribute j for set i. Similarly, the union upper bound is:
min
r
s
e
As with frequency-distribution level 4a and level 5 bounds, we can also use this formula when all w
now is an upper bound on the bin counts, perhaps from a distribution fit.
A
6.2. Multidimensional intersection range analysis
nalogous to range analysis, we may be able to obtain a multivariate distribution that is an upper
bound on the distribution of the data universe U over some set S of interest (as discussed in [9] and
2]). We determine ranges on each attribute of S by finding the overlap of the ranges for each set being
r
intersected as before. This defines a hyperrectangular region in hyperspace, and the universe uppe
ound also bounds the number of items inside it. We can also use various multivariate generalizations
s
of Chebyshev's inequality [1] to bound the number of items in the region from knowledge of moment
f any set containing the intersection set (including the universe). As with univariate range analysis, we
r
can exploit known correlations to further truncate the ranges on each attribute of S, obtaining a smalle
yperrectangular region.
Another class of correlation we can use is specific to multivariate ranges: those between attributes in the
l
set S itself. For instance, a tight linear correlation between two numeric attributes j1 and j2, strongly
imits the number of items within rectangles the regression line does not pass through. If we know
a
s
absolute bounds on the regression fit we can infer zero items within whole subregions. If we know
tandard error on the regression fit we can use Chebyshev's inequality and its relatives to bound how
many items can lie certain distances from the regression line.
ust as for univariate range analysis, we can exploit more detailed information about the distributions of
any attribute (not necessarily the ones in S). If we know an upper bound on bin size, for some
artitioning into subregions or "bins", or if we know the exact distribution of bin sizes, we may be ableto improve on the level 1 bounds.
.3. Lower bounds from range analysis
Lower bounds can be obtained from substituting the above upper bounds in the first three formulae
U
relating intersections and unions in section 4.4.1, either substituting for the intersection or for the union
nfortunately the resulting formulae are complicated, so we won't give them here.
6.4. Embedded set expressions for range analysis
et us consider the effect of Boolean equivalences on embedded set descriptions for the above range-
analysis bounds, for level 1 information. First, range-analysis bounds cannot be provided for expressions
f
with set complements in them, because there is no good way to determine a maximum or minimum
he complement of a set other than the maximum or minimum of the universe. So none of the
equivalences involving complements apply.
he only set-dependent information in the level-1 calculation are the extrema of the range, H and L.
Equivalence of set expressions under commutativity or associativity of terms in intersections or unions
hen follows from the commutativity of the maxima and minima of operations, as does distributivity of
a
intersections over unions and vice versa. Equivalence under reflexivity follows because max(a ,a )=a
nd min(a ,a )=a . Introduction of terms for the universe and the null set are useless, because the
e
max(a ,0)=a for a -0, and min(a ,N )=a . So expression rearrangements do not affect the bounds, so w
ight as well not bother; that seems a useful heuristic for level 2 and 5 information too.
6.5. Storage requirements for range analysis
pace requirements for these range analysis bounds can be computed in the same way as for the
e
frequency-distribution bounds. Assume that the number of bins on each attribute is m, the averag
umber of attributes is r, the number of bits required for each attribute value is w, and the number of
items in the database is N. Then the space requirements for univariate range bounds are:
level 1: mr log (N /m )+2mr w22
l
level 2: mr log (N /m )+2mr
evel 5: m r log (N /m )+2mr w
A
gain, these are pessimistic estimates since they assume that all attributes can be helpful for rangeanalysis.
.6. Evaluation of the range-analysis bounds
Level 2 upper bounds are definitely better than level 1 because the binfreq(U,j,k) is an upper bound on
e
a
level 5 is better than level 2 because mf(i,j) is an upper bound on binfreq(i,j,k). But th
verage-case performance of the range-analysis bounds is harder to predict than that of the frequency-
distribution bounds, since the former depends on widely-different data distributions, while the latter's
istributions tend to be more similar. Furthermore, maxima and minima statistics have high variance
r
for randomly distributed data, so it is hard to create an average-case situation for them; strong range
estriction effects do occur with real databases, but mostly with human-artifact data that does not fit
a
well to classical distributions. Thus no useful average-case generalizations are possible about range-
nalysis bounds.
6.7. Cascading range-analysis and frequency-distribution methods
e
The above determination of the maximum and minimum of an intersection set on an attribute can b
sed to find better frequency-distribution bounds too, since it effectively adds new sets to the list of sets
being intersected, sets defined as partitions of the values of particular attributes. These new sets may
ave unusual distributions on further attributes that can lead to tight frequency-distribution bounds.
7. Conclusion
e have provided a library of formulae for bounds on the sizes of intersections, unions, and
d
complements of sets. We have emphasized intersections (because of their greater importance) an
ntersection upper bounds (because they are easier to obtain). Our methods exploit simple precomputed
s
tatistics (counts, frequencies, maxima and minima, and distribution fits) on sets. The more we
a
precompute, the better our bounds can be. We illustrated by analysis and experiments the time-space
ccuracy tradeoffs involved between different bounds. Our bounds tend to be most useful when there
e
are strong or complex correlations between sets in an intersection or union, a situation in which
stimation methods for set size tend to do poorly. This work thus nicely complements those methods.
A



--R

Neil C.
cknowledgements: The work reported herein was partially supported by the Foundation l R Research Program of the Naval Postgraduate School with funds provided by the Chief of Nava esearch.
""
""
""
""
""
""
""
""
""
""
""
""
""
""
""
""


ince sup(n






""
he lower bounds on Q3 and Q4 are: inf(n (Q 3))


""

irst we prove this for a two-row matrix
he result for a two-row matrix easily extends to matrices with more rows
igure 4: experiments measuring average ratio of bounds and estimates to actual intersection size
Figure 5: table of cases for Appendix
upper a upper 2b upper r 3a upper 3b uppe 4a upper a 5 upper ctual intersection size
lower lower
level 1 upper bound 1.05 0.0 1.05 level 2a upper bound 1.28 0.01 1.31
level 3a upper bound 1.11 0.01 1.12 level 4a upper bound 1.02 0.0 1.02
level 1 estimate 0.94 0.0 0.63
level 5 lower bound 0.93 0.0 0.42


--TR
Antisampling for estimation: an overview
On semantic issues connected with incomplete information databases
An Approach to Multilevel Boolean Minimization
Evaluation of the size of a query expressed in relational algebra
Accurate estimation of the number of tuples satisfying a condition
Statistical Databases
An Analytic Approach to Statistical Databases
Rule-based statistical calculations on a database abstract

--CTR
Francesco M. Malvestuto, A universal-scheme approach to statistical databases containing homogeneous summary tables, ACM Transactions on Database Systems (TODS), v.18 n.4, p.678-708, Dec. 1993
distribution information;closed-form bounds;database theory;statistical analysis;set theory;union sizes;file organisation;set intersection;boolean algebra;database access;rule-based system architecture