Report Number: CS-TR-79-778
Institution: Stanford University, Department of Computer Science
Title: A hierarchical associative architecture for the parallel evaluation of relational algebraic database primitives
Author: Shaw, David Elliot
Date: October 1979
Abstract: Algorithms are described and analyzed for the efficient evaluation of the primitive operators of a relational algebra on a proposed non-von Neumann machine based on a hierarchy of associative storage devices. This architecture permits an O(log n) decrease in time complexity over the best known evaluation methods on a conventional computer system, without the use of redundant storage, and using currently available and potentially competitive technology. In many eases of practical import, the proposed architecture may also permit a significant improvement (by a factor roughly proportional to the capacity of the primary associative storage device) over the performance of previously implemented or proposed database machine architectures based on associative secondary storage devices.
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/778/CS-TR-79-778.pdf