Two (or more) IP-tables of two (or more) temporal relations can be merged into one IP-table that describes the timestamp characteristics of the union of these relations. This is very useful as we can precompute the IP-tables for individual relations and merge them when optimising a temporal join between those relations. This is only relevant for join algorithms that require two or more input relations to be partitioned along certain constraints. Partitioning then needs information on all these relations, i.e. we need the IP-table of the union of the relations. This leads to the layout of the data-analysis stage within the optimisation process that is shown in figure 7.16.
However, merging is not only relevant in the context of optimisation although the latter is the main purpose for which we will use it. It can also be considered as a general technique for updating individual IP-tables: assume a data warehouse that is updated over night by inserting a batch of new data that has been accumulated during the day. One could then simply create a temporary IP-table for this batch and merge it with the existing IP-table in order to get an updated IP-table.
The different types of IP-tables require slightly different algorithms for merging them. Condensed and endpoint IP-tables can be treated equally due to the analogy in collapsing timepoints. This led to analogous definitions of the and functions. To stress this analogy, we will refer to condensed and endpoint IP-tables as incomplete IP-tables in the remainder of this section.
In the following, we give the algorithms for the case that two IP-tables are to be merged. A three- or more-way merge can easily be derived from that, similarly to the numerous algorithms that are based on merging several streams of data, such as sort-merge joins (see chapters 3 and 4 for example) or the mergesort algorithm [Knuth, 1973]. For the two-way merge we have to consider three cases: