在时态数据库中时态数据的JOIN操作是一种能起到关键作用的操作,一方面是由于该操作本身代价比较高。设想两个大小为n的表进行JOIN操作,如果采用最简单的嵌套循环方式,这个代价是非常高的,特别是对于数据量迅速增长的今天,这个n将十分庞大,n2更是我们无法想象的。另一方面高效实现该操作有助于解决其他一些问题,对于提高查询优化器的效率至关重要。如今解决该问题的算法主要有四类:基于嵌套循环、基于排序合并、基于划分和基于索引。基于嵌套循环的算法简单且易于实现,但时间复杂度太高,对于实际问题往往不能胜任。基于排序合并的算法需要在JOIN属性上进行排序,然而时态数据的JOIN属性是二维的,因此很难找到一个线性顺序,这就导致进行JOIN的关系要被多次读取,进而造成性能下降。虽然也有其他的一些算法在JOIN属性上添加限制,但这样的算法就丧失了一般性。基于划分和基于索引的算法确实出现了一些不错的算法,如文献[1]中提出的重叠区间划分算法,但该算法不是一个精确算法,产生的连接结果会多于实际的连接结果。针对现如今这些算法的缺陷,本文提出了基于对称索引的增量式重叠区间JOIN算法SISJoin。首先该算法是一个精确算法,其次该算法简单且易于实现,最后通过理论分和实验验证该算法非常高效。该算法是直接针对JOIN条件构建索引结构,且索引结构非常简单构建也非常高效。在JOIN算法中又利用JOIN必要条件提前过滤掉不可能产生JOIN结果的数据,这样就减少了参与JOIN的数据规模,然后还采用增量策略又极大的减少了比较操作的次数。最后我们还进行了4组实验,实验结果表明采用增量策略JOIN时间会降低数十倍,在真实数据集上SISJoin算法优势显著,SISJoin算法也基本不受Long Lived Tuple影响,在大数据量的分布式环境下,SISJoin算法也表现出较好的扩展性。