Collection-Intersect Join Algorithms for Parallel Object-Oriented Database Systems

Abstract. One of the differences between relational and object-oriented databases (OODB) is that attributes in OODB can of a collection type (e.g. sets, lists, arrays, bags) as well as a simple type (e.g. integer, string). Consequently, explicit join queries in OODB may be based on collection attributes. One form of collection join queries in OODB is collection-intersect join queries, where the joins are based on collection attributes and the queries check for whether there is an intersection between the two join collection attributes We propose two algorithms for parallel pro-cessing of collection-intersect join queries. The first one is based on sort-merge, and the second is based on hash. We also present two data par-titioning methods (i.e. simple replication and ”divide and partial broad-cast”) used in conjunction with the parallel collection-intersect join al-gorithms. The parallel sort-merge algorithm can only make use of the divide and partial broadcast data partitioning, whereas the parallel hash algorithm may have a choice which of the two data partitioning to use.