笛卡尔积的实现算法

1、简单算法

   计算笛卡尔积的最简单算法是嵌套循环算法

   For R中每个元组r Do

       For S中每个元组s Do

           产生元组(rs),存入结果关系;

       endFor

    endFor

注意，R和S在算法中的位置可以调换，但是把小关系放在外层循环可以节省时间

2、主存算法

   如果M》Bs+Br，可以首先把R和S读入主存，然后在主存中产生R*S。

   读入R和S;

   For 主存中R的每个元组r Do

       For 主存中S的每个元组s Do

           产生元组(rs)，存入结果关系

       endFor

   endFor

显然，这个算法需要Br+Bs+Br*s块磁盘存取。

3、半主存算法

   如果Br》Bs，Bs

   设SB是存储S的主存区，RB是R的缓冲区，半主存算法的形式定义如下：

   读入S到SB;

   WHILE R中仍有元组待处理 Do

         读R的元组到RB; 

         For RB中每个R元组r Do

             For SB中每个S元组s Do

                 产生元组(rs)，存入结果关系;

             endFor

          endFor

    endWhile

类似于主存算法，这个算法需要Br+Bs+Rr*s块磁盘存取

4、大关系算法

   如果M《Br，M《Bs，则R和S都不能一次读入主存。设Bs《Br。我们把关系S划分为Bs/(M-1)个子集合，每个子集合具有M-1块。令SB是容量为M-1块的S的主存缓冲区，RB是容量为一块的R的主存缓冲区。大关系算法的形式定义如下：

   For i=1 to Bs/(M-1) Do

       读S的第i个子集合到SB;

       For j=1 to Br Do

           读R的第j块到RB;

           For RB中每个R元组r Do

              For SB中每个S元组s Do

                  产生元组(rs),存入结果关系;

              endFor

           endFor

        endFor

    endFor

这个算法需要Br/(Bs/(M-1))+Bs+Br*s块磁盘存取