Design and Analysis of Relational Join Operations of a Database Computer (DBC).

摘要

This paper repeats in detail the algorithm earlier employed in the database computer (DBC) in order to perform relational equality joins. Two improvements of the algorithm are proposed herein. The first improvement is achieved by adding a new memory component, called the C-memory, for each processor of the algorithm. The C-memory is used to store the results of the join operation. Also, it is a vital component during the execution of a m-way join operation. The second improvement involves the replacement of a single associative memory (AM) by several smaller associative memories (ams). Two advantages accrue as a result of this replacement. First, we show that each of the ams needs to operate at a slower rate than the single AM. This implies that we may use random-access memory (RAM) to realize ams, instead of the true and expensive associative hardware. The second advantage is due to an improvement in the complexity of the join operation when the ams are used. It is shown that the time complexity of the join is linear in the cardinalities of the source, target and result sets (relations). We therefore postulate that no join algorithm can have better time complexity than this. The paper also provides a thorough queueing analysis of the join algorithm as it is carried out in a specialized DBC component known as the post processor (PP).