Parallel Implementation of Relational Algebra Operations on a Multi-Comparand Associative Machine

Abstract

In this paper, we propose a new multi-comparand associative machine (MCA-machine) and its application to relational algebra operations. We first offer a new efficient associative algorithm for the multi-comparand parallel search. It generalizes the Falkoff associative algorithm that performs a parallel search in a matrix based on the exact match with a given pattern. Then we apply the new associative algorithm to implement one group of the relational algebra operations on the MCA-machine. Then, we propose efficient associative algorithms for implementing another group of the relational algebra operations. The proposed algorithms are represented as corresponding procedures for the MCA-machine. We prove their correctness and evaluate their time complexity.