A relational database machine architecture

ABSTRACT

Algorithms are described and analyzed for the efficient evaluation of the project and join 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 cases 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.

REFERENCES

• 1: Baum, Richard I. and Hsiao, David K., "Data base computers—a step towards data utilities", IEEE Trans. Computers, v. C-25, December, 1976.
• 2: Codd, E. F., "A Data Base Sublanguage Founded on the Relational Calculus", Proceedings of the 1971 ACM SIGFIDET Workshop on Data Description, Access and Control, 1971.
• 3: DeFiore, Casper R. and Berra, P. Bruce, "A data management system utilizing an associative memory", Proc. AFIPS National Computer Conference, v. 42, 1973.
• 4: DeWitt, David J., "DIRECT—A multiprocessor organization for supporting relational database management systems", IEEE Trans. Computers, v. c-28, no. 6, June, 1979.
• 5: Caxton C. Foster, Content Addressable Parallel Processors, John Wiley & Sons, Inc., New York, NY, 1976
• 6: Lin, Chyuan Shiun, and Smith, Diane C. P., "The design of a rotating associative array memory for a relational data base management application", Proc. International Conference on Very Large Data Bases, v. 1, no. 1, September., 1975.
• 7: Moulder, Richard, "An implementation of a data management system on an associative processor", Proc. AFIPS National Computer Conference, 1973.
• 8: E. A. Ozkarahan , S. A. Schuster , K. C. Sevcik, Performance evaluation of a relational associative processor, ACM Transactions on Database Systems (TODS), v.2 n.2, p.175-195, June 1977 [doi>10.1145/320544.320553]
• 9: Ozkarahan, Esen A., Schuster, Stewart A., and Smith, Kenneth C., "A data base processor", Technical Report CSRG-43, Computer Systems Research Group, Univ. Toronto, Sept. 1974.
• 10: Rudolph, J. A., "A production implementation of an associative array processor: STARAN", Proc. AFIPS Fall Joint Computer Conference, v. 41, pt. 1, AFIPS Press, Montvale, NJ, pp. 229-241, 1972.
• 11: David E Shaw, A hierarchical associative architecture for the parallel evaluation of relational algebraic database primitives, Stanford University, Stanford, CA, 1979
• 12: Su, Stanley Y. U., Copeland, George P., and Lipovski, G. J., "Retrieval operations and data representations in a content-addressed disc system", Proc. International Conference on Very Large Data Bases, Framingham, MA, September, 1975.
• 13: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
• 14: S. S. Yau , H. S. Fung, Associative Processor Architecture—a Survey, ACM Computing Surveys (CSUR), v.9 n.1, p.3-27, March 1977 [doi>10.1145/356683.356685]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.6 Database Machines

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

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

General Terms:
Design