next up previous contents index
Next: Composite Joins Up: Size and Selectivity Calculations Previous: Size and Selectivity Calculations

Elementary Joins

    

We now show how the result size - and therefore also the selectivity factor according to (11.1) - of the elementary temporal joins of table 11.1 can be calculated. For notational purposes, we assume that the selectivity factor / result size of some join $R
\Join_{\scriptscriptstyle C}Q$ is to be derived. The set comprises the interval start- and endpoints of all the rows in both of the relations that participate in the join, i.e. R and Q.

In the case of a start join  we are looking for combinations $r \circ q$ of tuples $r \in R$ and $q \in Q$whose timestamps  start at the same time. There are $s_{\scriptscriptstyle R}(t)$ tuples in R and tuples in Q that start at a timepoint t. As for all we can concentrate on the tj for .Considering that any timestamp has exactly one startpoint, we know that there are no redundant counts, therefore the result size can be computed by summing up the numbers. Thus the result size of a start join is

Similarly, one can compute the result sizes for finish  and meet joins :

A before join  requires a timestamp  of a tuple r to end before the timestamp of q starts if they are to be combined and put into the join result. Thus those tuples in R that end at timepoint t combine with all those tuples in Q that start after t, i.e.

tuple combinations arise from that. Alternatively, one could consider those tuples in Q that start at t. They join with all tuples in R that have ended before t, i.e.

tuple combinations arise from that. As above and for the same reasons we can concentrate on those t that are start- and endpoints. Thus the result size of a before join is

As the after join  is an inverted before join, its result size is derived similarly as

Finally, a left-overlap join  requires an r's timestamp's  startpoint to lie inside the timestamp of a q if they are to qualify for the result. At a timepoint t these are tuples. Similarly, a right-overlap join  requires an r's timestamp's endpoint to lie inside the timestamp of a q if they are to qualify for the result. At a timepoint t these are tuples. Again, we can concentrate on the tj and calculate the result sizes of left-overlap- and right-overlap joins as
next up previous contents index
Next: Composite Joins Up: Size and Selectivity Calculations Previous: Size and Selectivity Calculations

Thomas Zurek