Definition and Types of Temporal Joins

    A join condition  is said to be temporal if it enforces a certain relationship between the timestamps  of the participating tuples.  Hence, temporal joins  combine two (or more) temporal relations using a temporal join condition. In terms of interval timestamps , this means that the intervals are related to each other. In chapter 2, we have already seen a typical example of such a temporal join condition, namely the intersection of two intervals as described by equation (2.3).

There are many possible relationships between two intervals: one interval can lie completely before the other, both intervals can start and/or end at the same time, they can overlap each other etc. Temporal joins can be classified according to the type of relationship on which its join condition is based. Table 4.1 shows a set of join conditions. We treat them as elementary for the following three reasons:

• they translate into simple expressions that describe the relationships between intervals' start- and endpoints,
• they, nevertheless, have reasonable semantics, that can be related to natural language expressions of everyday use,
• they can be used to compose more complex types, such as those in table 4.2.

 

Table: Elementary temporal joins and respective conditions for joining tuples with .

Relationship	Join Name & Symbol	Condition	Informal Description
start	start join:	r.ts = q.ts	same timestamp startpoints
finish	finish join:	r.te = q.te	same timestamp endpoints
meet	meet join:	r.te = q.ts	timestamp of r ends where timestamp of q starts, i.e. they meet.
before	before join:	r.te < q.ts	timestamp of r comes before q's timestamp
left-overlap	left-overlap join:		startpoint of r's timestamp lies within q's timestamp
right-overlap	right-overlap join:		endpoint of r's timestamp lies within q's timestamp

Additional constraints are:

 

Table: Examples of temporal join types that can be derived from the elementary ones.

Join Name	3c|Composition	Informal Description
equal join		=		same timestamps
after join		=		timestamp of is required to lie entirely after the timestamp of a
overlap join		=		timestamps overlap but do not start or finish at the same point
contain join		=		timestamp of an
				contains the entire
				timestamp of a
during join		=		timestamp of an is required to lie entirely within the timestamp of a
intersection join		=		timestamps intersect

The literature has mainly concentrated on the intersection of intervals in the join predicate join. The reason behind this is that it requires the timestamps of the participating tuples to share at least one chronon. This is a minimum constraint that can be found in most other temporal join conditions (see tables 4.1 and 4.2).

Leung and Muntz referred to this minimum constraint as the `TSJ1 query property' [Leung and Muntz, 1992]. Thus intersection join queries are identical with the TSJ1 queries discussed by Leung and Muntz. They show what optimisations (with respect to reducing tuple replication in the case of partitioning over the interval timestamps) can be drawn from specialising the general intersection condition to, for example, a contain or during condition. In these cases, tuple replication can be restricted to some of the participating relations, e.g. to R in a contain join . However, replication is necessary for at least one of the participating relations in most temporal join conditions if the join is to be processed by partitioning over the interval timestamp attribute . To summarise: whereas Leung and Muntz identify the situations in which tuple replication can be restricted, we will concentrate on how the impact of replication can be reduced when replication is necessary. The latter applies to a wide set of intersection based join conditions. Therefore we will focus on the temporal intersection join as the most general of these joins. However, we stress again that replication is not only relevant for the pure intersection join but it is equally important for many other temporal joins, such as the during, contain, left-overlap, right-overlap and overlap joins. The results that are obtained for the case of the intersection join are therefore easily transferable to these joins.

Usually the tuples that satisfy the join condition are concatenated. In the case of temporal joins this concatenation is not trivial as the value of the timestamp  for the resulting tuple has to be defined. This definition depends on the type of the temporal join; assuming temporal intersection the resulting timestamp is defined to be the intersection of the individual timestamps of the participating tuples. For example in the case of the two tuples r and q the resulting timestamp is  

(10)