The Size of an IP-Table

In this section, we look at the realistic size of an IP-table and how it compares to sizes of data samples that are used in a typical data sampling approach. The ratio of the sizes of an IP-table I(R) and its corresponding temporal relation R can be calculated by  

(25)

with   being the size of an entry in the IP-table and   referring to the size of a tuple of R.

The ratio (7.3) has to be compared to ratios achieved when sampling data. To that end, we want to look at one such example, i.e. the approach taken in [Soo et al., 1994]. It uses the Kolmogorov test statistic [Conover, 1980] which is frequently employed in data sampling approaches for query optimisation, e.g. in [DeWitt et al., 1991]. The Kolmogorov test  is non-parametric which means that it does not make any assumptions about the underlying distributions of the tuples. Soo et al. conclude that one has to draw a sample whose size is determined by  

(26)

with errorsize being the number of buffer pages that are provided for keeping an overflow of tuples in the buffer. This overflow can be caused by the error difference between the data characteristics of the sample and that of the entire data. Therefore one has to provide a certain buffer space to cope with such an overflow situation. Soo et al. optimise errorsize in order to minimise the accumulated costs of sampling and joining the two relations. However, the algorithm determinePartIntervals provided for that in [Soo et al., 1994] is erroneous as it always reaches the extreme case of drawing the entire relation as a sample. For that reason and in order to get an idea of an actual sample size, we assume the ratio

• 10:1, which leads to a data sample size of 266 pages according to (7.4), i.e. 3.2% of the original relation which they assume to have 8192 pages, or
• 20:1, which leads to a data sample size of 1063 pages, i.e. 13% of the original relation, or
• 30:1, which leads to a data sample size of 2392 pages, i.e. 29% of the original relation.

• a timepoint t_j, which might be represented as 6 bytes, and
• the two integers, and , which are usually represented as 4 bytes each.

The ratio |V(R)|:|R| shows how many new elements are contributed to V(R) on average by a tuple r's interval. A ratio of 0.5 indicates that two intervals contribute one new timepoint to V(R), in the case of 1.0 it is one interval adding one timepoint on average and the worst case is 2.0 with each interval introducing two new timepoints (its start- and endpoint) to the plot. Therefore |V(R)|:|R| is an indicator for observing whether there are many tuples in R that share interval start- and endpoints - in this case the ratio is low - or whether most intervals have start- and endpoints that do not appear in other intervals within R - in this case the ratio is high, reaching 2.0 in the worst case when each interval has a start- and an endpoint that does not appear either as a start- or an endpoint in any other interval. Some applications will impose a low ratio, e.g. in the case of a temporal relation holding air pollution figures that are obtained through periodic measurements. Here, many intervals share the timepoints of the measurements as their start- or endpoints. In other situations, such as a temporal relation storing start- and endtimes of telephone calls or computer accesses, we can expect the start- and endpoints of tuple intervals to be arbitrarily distributed over the timeline, therefore possibly causing a higher ratio than in periodic or other regular applications. In section 7.3.2, examples of various real-world temporal relations are analysed and the respective values of the |V(R)|:|R| ratio are given.

Table 7.1 shows typical values for (7.3) depending on the and the ratio |V(R)|:|R|. For most combinations we get values that are at least as good as those achieved by data samples. But recall that an IP-table provides precise information whereas the data sample approach achieves these figures only at the expense of introducing error margins which vary immensely with the sample size.