Sampling

F’ and G’ are samples from relations F and G, respectively. f'_i and g’_i be the frequency of the value i in F’ and G’, respectively. Size of join of the sample relations is:

Note: f ’_i and g’_i are random variables depending on the type of sampling and the sampling process parameters. Most characterization of sampling can be carried out without specifying the type of sampling.

1.Generic Sampling

The above mentioned estimator can be biased, but a constant corrections that scales for the difference in size between the samples and the original relations can be made to obtain unbiased estimator. The estimator is:

where C is the scaling factor.
There are two cases: 1) F and G are different and samples are obtained independently. 2) F and G are identical, compute size of self-join.

1.1 Proposition of size of join

Estimator:

Expectation:

Variance:

1.2 Proposition of size of self join

Estimator:

Expectation:

Variance:

2.Bernoulli Sampling

Each tuple in F and G is selected independently in the sample F’ and G’ with probability p or q, 0 <= p <= 1, 0 <= q <= 1.

Expectation:

Where f ’_i and g’_i are independent binomial random variables, f ’_i =Binomial(f ’_i, p) and g’_i = Binomial(g’_i, q) . In this case, the scaling factor is 1/pq

2.1 Proposition of size of join

Estimator:

Expectation:

Variance:

2.2 Proposition of size of self join

Estimator:

Expectation:

Variance: