Outer join operations using responsibility regions assigned to inner tables in a relational database

摘要

A computer database system utilizes a method for performing a right outer join of database tables without sorting the inner table (T2). The processing of each tuple in the outer table (T1) includes the preservation in the joint output of all tuples in T2 which are in its responsibility region. The initialization step of the process preserves in the join output all of the tuples in T2 which have column set values less than the lowest column set value in T1, i.e. the first tuple in T1, since T1 is sorted or accessed using a sorted index. The responsibility region for tuples in T1, other than the last tuple, is defined as those tuples which have column set values less than the column set value for the next tuple in T1 and greater than or equal to the column set value for the current T1 tuple. The last tuple in T1 must preserve all of the tuples in T2 which have not already been preserved in T2, i.e. all tuples greater than or equal to its column set value. If T1 has duplicate values for the column set value, only the last one preserves the associated T2 tuples. Additional methods for parallel execution of the outer join methods and methods for applying the outer join methods to subqueries (i.e., an All (or universal) Right Join (ARJOIN) and an Existential Right Join (ERJOIN)) are described.