Performance evaluation of a relational associative processor

ABSTRACT

An associative processor called RAP has been designed to provide hardware support for the use and manipulation of databases. RAP is particularly suited for supporting relational databases. In this paper, the relational operations provided by the RAP hardware are described, and a representative approach to providing the same relational operations with conventional software and hardware is devised. Analytic models are constructed for RAP and the conventional system. The execution times of several of the operations are shown to be vastly improved with RAP for large relations.

REFERENCES

• 1: M. M. Astrahan , D. D. Chamberlin, Implementation of a structured English query language, Communications of the ACM, v.18 n.10, p.580-588, Oct. 1975 [doi>10.1145/361020.361215]
• 2: Raymond F. Boyce , Donald D. Chamberlin , W. Frank King, III , Michael M. Hammer, Specifying queries as relational expressions: the SQUARE data sublanguage, Communications of the ACM, v.18 n.11, p.621-628, Nov. 1975 [doi>10.1145/361219.361221]
• 3: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 4: 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]
• 5: 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
• 6: CZARNIK, B., SCHUSTSR, S.A., AND TSICHRITZ~S, D. ZETA: A relational data base management System. Proc. ACM: Pacific Conf., 1975, pp. 21-25.
• 7: DAT~, C.J. An Introduction to Data Base Systems. Addison-Wesley, Reading, Mass., 1975.
• 8: DEFIORS, C.F., AND BERRA, P.B. A data management system utilizing an associative memory", Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 181-185.
• 9: DE FIoRd, C.R., AND BERRA, P.B. A quantitative analysis of the utilization of associative memories in data management. IEEE Trans. Computers C-23, 2 (Feb. 1974), 121-133.
• 10: FULL~R, R.H. Associative parallel processing. Computer Design 6 (Dec. 1967), 43-46.
• 11: L. Kerschberg , E. A. Ozkarahan , J. E.S. Pacheco, A Synthetic English query language for a relational associative processor, Proceedings of the 2nd international conference on Software engineering, p.505-519, October 13-15, 1976, San Francisco, California, United States
• 12: Chyuan Shiun Lin , Diane C. P. Smith , John Miles Smith, The design of a rotating associative memory for relational database applications, ACM Transactions on Database Systems (TODS), v.1 n.1, p.53-65, March 1976 [doi>10.1145/320434.320447]
• 13: LIND,, R.R., GATES, R. AND P~N(~, T., Associative processor applications to real-time data management. Proc. AFIPS 1973 NCC, Vol. 42, pp. 187-195.
• 14: LovE, H.H. An efficient associative processor using bulk storage. Proc. Sagamore Comptr. Conf. on Parallel Processing, 1973, pp. 103-112.
• 15: MINSKY, N. Rotating storage devices as partially associative memories. Proc. AFIPS 1972 FJCC, Vol. 41, Pt. I, AFIPS Press, Montvale, N.j., pp. 587-595.
• 16: OZ~RAHAN, E.A. An associative processor for relational data bases~RAP. Ph.D. Th., Dep. Comptr. Sci., U. of Toronto, Toronto, Canada, Jan. 1976.
• 17: OZKARAHAN, E.A., SCHUSTEr, S.A., AND SMIT~, K.C. RAP--An associative processor for data base management. Proc. AFIPS 1975 NCC, ~ol. 44, AFIPS Press, Montvale, N.J., pp. 379-387.
• 18: OZKARA~{AN, E.A., SCHUSTEa, S.A., AND S~IT~, K.C. A data base processor. Tech. Rep. CSRG43, Comptr. Syst. Res. Group, U. of Toronto, Toronto, Canada, Sept. 1974.
• 19: E. A. Ozkarahan , K. C. Sevcik, Analysis of aarchitectural features for enhancing the performance of a database machine, ACM Transactions on Database Systems (TODS), v.2 n.4, p.297-316, Dec. 1977 [doi>10.1145/320576.320577]
• 20: PAI~H~,MI, B. A highly parallel computing system for information retrieval. Proc. AFIPS 1972 :FJCC, Vol. 41, Pt. II, AFIPS Press, Montvale, N.J., 1972, pp. 681-690.
• 21: P~K~R, J.L. A logic-per-track retrieval system. Information Processing 71, North- Holland Pub. Co., Amsterdam, 1971, pp. 711-716.
• 22: 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.
• 23: SCHUSTV.R, S.A., OZ~AR~N, E.A., ~ND SMI~, K.C. A virtual memory system for a relational associative processor. Proc. AFIPS 1976 NCC, Vol. 45, AFIPS Press, Montvale, N.J., pp. 855-862.
• 24: SLOVNICK, D. L. Logic per track devices. In Advances in Computers, Vol. i0, Academic Press, New York, 1970, pp. 291-296.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

General Terms:
Design, Performance

Keywords:
associative processors, database machines, performance evaluation, relational databases