Composition of Database Relations

The composition operation has been implemented in most of the current database systems as two separate steps: a step in which projection is performed at the same time as the join, followed by a second step of duplicate elimination. When a hash-based or sort-merge algorithm is used for the join operation and the size of the result is large, duplicate elimination cannot be performed at the same time a join is being performed. In this paper, we argue for implementing composition as a primitive operation in the database systems, and present a single-sided composition algorithm that combines the three operations, join, projection, and duplicate elimination in one single step. We also present experimental results that show that there are operating regions of considerable interest where the single-sided composition outperforms conventional methods.