Parallel collection-equi join algorithms for object-oriented databases

One of the differences between relational and object-oriented databases (OODB) is that attributes in OODB can be 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-equi join queries”, where the joins are based on collection attributes and the queries check for an equality of both collection operands. Our previous work (1997) describes “Parallel Double Sort-Merge” algorithm for collection-equi join queries, Since the publication, we realize that we have overlooked the complexity of collection merging in the algorithm. In this paper, we not only present alternative solutions relating to the collection merging problem, but also introduce a new algorithm called “Parallel Sort-Hash” algorithm. The two algorithms play an important role in parallel object-oriented query processing, due to their superiority over the conventional join methods through relational division and intersection operators