A Comparison of Composition and Join Operations

Abstract

In relational databases, a composition requires there operations:join, projection and duplicate elimination. An external sort is required to eliminate duplicates in a large file. Both join and external sort are expensive because they incur a nonlinear I/O overhead. Most conventional composition algorithms take join and duplicate elimination as separate operations to achieve savings on either operation but not both. Direct composition algorithms outperform all these algorithms by executing the composition as a single primitive. In this paper, we show that direct composition can even outperform its component operation, the join operation, when there is a high degree of duplication after join and projection operations. The result can encourage the correct implementation of join operation to preserve the integrity of relational data model in real DBMSs where duplicate tuples are usually not removed.