skip to main content
10.1145/1500774.1500852acmotherconferencesArticle/Chapter ViewAbstractPublication PagesafipsConference Proceedingsconference-collections
research-article
Free access

Spirit-III: an advanced relational database machine introducing a novel data-staging architecture with Tuple Stream Filters to preprocess relational algebra

Published: 07 June 1982 Publication History

Abstract

This paper proposes an advanced architecture of the relational database machine (RDBM), named SPIRIT-III, which is basically organized into a three-level memory hierarchy with a sophisticated data-staging and preprocessing architecture for executing relational algebra. SPIRIT-III aims at totally improving both I/O and CPU processing boundary problems and has two major architectural features. One is the introduction of the relational-database-oriented data-staging mechanism, called the look-ahead data-staging mechanism, which can optimally schedule data movement in the memory hierarchy. The other is to attach refined preprocessing mechanisms for relational algebra operations to data transfer lines connected between each memory stage. When a relation stages up or down in the memory hierarchy, these preprocessing mechanisms can function to select tuples and attributes needed by a query and to arrange the relation for parallel processing. SPIRIT-III provides three basic preprocessing filters, called as a whole the Tuple Stream Filter: the tuple selector, the attribute selector, and the grouping filter, implemented with a hash function, which rearranges an original relation and groups the relation into subrelations. The operation of this grouping filter is the primitive preprocessing operation for executing Join and Projection. Then, without the overhead of interprocessor communications, each microprocessor can execute relational algebra operations to a few subsegments assigned to it in parallel. Therefore, SPIRIT-III can perform Join and Projection operations by O (N/L) (L = number of microprocessors), whereas the early RDBMs required O (N X N/L). The proposed SPIRIT-III, which includes features from data-staging architecture to relational algebra execution architecture under the total concept, is the most powerful RDBM based on the state of the art.

References

[1]
Codd, E. F. "A Relational Model of Data for Large Shared Data Banks." Communications of the ACM, 13 (1970), pp. 377--397.
[2]
Smith, T. M., and P. Y. Chang. "Optimizing the Performance of a Relational Algebra Database Interface." Communications of the ACM, 18 (1975), pp. 568--579.
[3]
Schuster, S. A., F. A. Ozakarahan, and K. C. Smith. "RAP---An Associative Processor for Database Management." AFIPS Proc. NCC, 44, (1975), pp. 379--388.
[4]
Schuster, S. A., H. B. Nguyen, F. A. Ozakarahan, and K. C. Smith. "RAP.2---An Associative Processor for Database and Its Applications," IEEE Transactions on Computers, C-28 (1979), pp. 446--458.
[5]
Dewitt, D. J. "DIRECT---A Multiprocessor Organization for Supporting Relational Database Management Systems." IEEE Transactions on Computers, C-28 (1979), pp. 395--406.
[6]
Bobb, E. "Implementing a Relational Database by Means of Specialized Hardware." ACM Transactions on Database Systems, 4 (1979), pp. 1--29.
[7]
Tanaka, Y., Y. Nazuka, and A. Masuyama. "Pipeline Searching and Sorting Modules as Components of a Data Flow Database Computer." Proceedings of the IFIP-80, pp. 427--432.
[8]
Kamibayashi, N., H. Kato, Y. Kiyoki, H. Ozawa, K. Seo, and H. Aiso. "SPIRIT: A New Relational Database Computer Employing Functional-Distributed Multi-Microprocessor Configuration." Proceedings of the First International Conference on Distributed Computing Systems, (1979), pp. 757--771.
[9]
Kiyoki, Y., N. Kamibayashi, K. Tanaka, and H. Aiso. "Design and Evaluation of a Relational Database Machine Employing Advanced Data Structures and Algorithms." Proceedings of the 8th International Symposium on Computer Architecture, 1981, pp. 407--423.
[10]
Seo, K., N. Kamibayashi, A. Minematsu, and H. Aiso. "A Look-Ahead Data Staging Architecture for Relational Database Machines." Proceedings of the 8th International Symposium on Computer Architecture, 1981, pp. 389--406.
[11]
Teorey, T. J., and T. B. Pinkerton. "A Comparative Analysis of Disk Scheduling Policies." Communications of the ACM, 15 (1972), pp. 177--184.
[12]
Brice, R. S., and S. W. Sherman. "An Extension of the Performance of a database manager in a virtual memory system using partially locked virtual buffers." ACM Transactions on Database Systems, 2 (1977), pp. 196--207.
[13]
Law, S. Y., and S. E. Madnick. "Properties of Storage Hierarchy Systems with Multiple Page Sizes and Redundant Data." ACM Transactions on Database Systems, 4 (1979), pp. 345--367.

Cited By

View all
  • (1987)A Tree-structured Database Machine for large relational database systemsJournal of Computer Science and Technology10.1007/BF029433212:4(265-275)Online publication date: Oct-1987
  • (1986)Hardware Implementation of Relational Algebra OperationsDatabase Machines10.1007/978-3-642-82937-6_15(341-380)Online publication date: 1986

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
AFIPS '82: Proceedings of the June 7-10, 1982, national computer conference
June 1982
857 pages
ISBN:088283035X
DOI:10.1145/1500774
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

  • AFIPS: American Federation of Information Processing Societies

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 1982

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)47
  • Downloads (Last 6 weeks)13
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (1987)A Tree-structured Database Machine for large relational database systemsJournal of Computer Science and Technology10.1007/BF029433212:4(265-275)Online publication date: Oct-1987
  • (1986)Hardware Implementation of Relational Algebra OperationsDatabase Machines10.1007/978-3-642-82937-6_15(341-380)Online publication date: 1986

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media