The design of a rotating associative memory for relational database applications

ABSTRACT

The design and motivation for a rotating associative relational store (RARES) is described. RARES is designed to enhance the performance of an optimizing relational query interface by supporting important high level optimization techniques. In particular, it can perform tuple selection operations at the storage device and also can provide a mechanism for efficient sorting. Like other designs for rotating associative stores, RARES contains search logic which is attached to the heads of a rotating head-per-track storage device. RARES is distinct from other designs in that it utilizes a novel “orthogonal” storage layout. This layout allows a high output rate of selected tuples even when a sort order in the stored relation must be preserved. As in certain other designs, RARES can usually output a tuple as soon as it is found to satisfy the selection criteria. However, relative to these designs, the orthogonal layout allows an order of magnitude reduction in the capacity of storage local to the search logic.

REFERENCES

• 1: BERRA, P.B. Some problems in associative processor applications to data base management. Proc. AFIPS 1974 NCC, Vol. 43, AFIPS Press, Montvale, N.J., pp. 1-5.
• 2: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 3: George P. Copeland, Jr. , G. J. Lipovski , Stanley Y.W. Su, The architecture of CASSM: A cellular system for non-numeric processing, Proceedings of the 1st annual symposium on Computer architecture, p.121-128, December 09-11, 1973
• 4: DAvis, E.W. STARAN parallel processor system software. Proc. AFIPS 1974 NCC, Vol. 43, AFIPS Press, Montvale, N.J., pp. 16-22.
• 5: DEFIORE, C.R., AND BERRA, P.B. A data management system utilizing an associative memory. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 121-128.
• 6: HEALr, L.D., DoTr, K.L., AnD LIPOVSK{, G.J. The architecture of a context addressed segment sequential storage. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. II, AFIPS Press, Montvale, }N.J., pp. 691-701.
• 7: LIN, C.S. The design of a rotating associative array memory for relational data base applications. Utah Tech. Rep., Comput. Sci. Dep., U. of Utah, Salt Lake City, Utah (in preparation).
• 8: MOULDER, R. An implementation of a data management system on an associative processor. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 171-176.
• 9: OZKARAHA~, E.A., SCHUSTER, S.A., AND SMITH, K.C. RAP--An associative processor for data base management. Proc. AFIPS 1975 NCC, Vol. 44, AFIPS Press, Montvale, N.J., pp. 379-387.
• 10: PARHAMI, B. A highly parallel computer system for information retrieval. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. II, AFIPS Press, Montvale, N.J., pp. 681-690.
• 11: PARKER, J.L. A logic per track retrieval system. Proc. IFIP Cong. 1971, North-Holland Pub. Co., Amsterdam, pp. TA4-I46-TA4-150.
• 12: RUDOLPH, J.A. A production implementation of an associative array processor-STARAN. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. I, AFIPS Press, Montvale, N.J., pp. 229-241.
• 13: SLOT~ICK, D.L. Logic per track devices. In Advances in Computers, Vol. 10, Franz Alt, Ed., Academic Press, New York, 1970, pp. 291-296.
• 14: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 15: Su, S.Y.W., AND LIPOVSKI, G.J. CASSM: A cellular system for very large data bases. Proc. of Very Large Data Base Conf., Sept. 1975, pp. 456-472.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design

Keywords:
associative memory, content addressability, data organization, head-per-track disks, memory systems, relational database, rotating devices, search logic, sorting technique