Browse Prior Art Database

DATABASE PROCESSING ON A CUBE-CONNECTED MULTICOMPUTER

IP.com Disclosure Number: IPCOM000128759D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-19

Publishing Venue

Software Patent Institute

Related People

Ophir Frieder: AUTHOR [+3]

Abstract

by Ophir Frieder Chairman: Chaitanya Baru A boolean cube-connected relational database machine is developed. Strategies for performing the basic relational database operations are presented. The strategies are termed "dynamic" and are novel in that they account for the non-uniform data distribution across parallel paths by redistributing the data as part of the database algorithms. Obtaining uniform data distributions is important in parallel architectures in order to attain close to optimal performance. The cube interconnection scheme employed subsumes many other interconnection structures such as the tree, ring, etc. This property is exploited in order to efficiently support the various database operations such as Select, Aggregate, Join, and Project. Results from a simulation which was developed demonstrate the improvement in the performance of the costly join operation achieved via the two main data redistribution operations viz., tuple balancing and merging. For the four database operations considered, it is shown that each can be represented in terms of a few "basic" operations and the set of all "basic" operations is identified. Within the proposed architecture, an overall query processing approach using these algorithms and a flexible "cube controlling a cube" control structure are presented. The scheduling method used groups the needed database operations to reduce scheduling complexity, while still supporting intra-and inter-query concurrency and minimizing communication delay. Besides being novel by "dynamically" redistributing data resulting from intermediate calculations, this research demonstrates the possibility of implementing fast database operations on a general, multi-purpose multicomputer system with lower response times than special purpose database architectures. To my family, Dalia, Gideon, Gony, and Tally Frieder

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 2% of the total text.

Page 1 of 55

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

©; Copyright Ophir Frider 1987, All Rights Reserved; used with permission

DATABASE PROCESSING ON A CUBE-CONNECTED MULTICOMPUTER

By Ophir Frieder

A dissertation submitted in partial fulfillment of the requirements for the -degree of Doctor of Philosophy Computer Science and Engineering in The University of Michigan

Doctoral Committee

Assistant Professor C. K. Baru, Chairman Professor B. A. Galler Assistant Professor Y. C. Lee Associate Professor V. Rosenberg Associate Professor Q. F. Stout

© Ophir Friede 1987 All Rights Reserved

ABSTRACT DATABASE PROCESSING ON A CUBE-CONNECTED MULTICOMPUTER

by Ophir Frieder

Chairman: Chaitanya Baru

A boolean cube-connected relational database machine is developed. Strategies for performing the basic relational database operations are presented. The strategies are termed "dynamic" and are novel in that they account for the non-uniform data distribution across parallel paths by redistributing the data as part of the database algorithms. Obtaining uniform data distributions is important in parallel architectures in order to attain close to optimal performance. The cube interconnection scheme employed subsumes many other interconnection structures such as the tree, ring, etc. This property is exploited in order to efficiently support the various database operations such as Select, Aggregate, Join, and Project. Results from a simulation which was developed demonstrate the improvement in the performance of the costly join operation achieved via the two main data redistribution operations viz., tuple balancing and merging. For the four database operations considered, it is shown that each can be represented in terms of a few "basic" operations and the set of all "basic" operations is identified.

Within the proposed architecture, an overall query processing approach using these algorithms and a flexible "cube controlling a cube" control structure are presented. The scheduling method used groups the needed database operations to reduce scheduling complexity, while still supporting intra-and inter-query concurrency and minimizing communication delay. Besides being novel by "dynamically" redistributing data resulting from intermediate calculations, this research demonstrates the possibility of implementing fast database operations on a general, multi-purpose multicomputer system with lower response times than special purpose database architectures. To my family, Dalia, Gideon, Gony, and Tally Frieder

ACKNOWLEDGMENTS

I wish to thank my doctoral advisor Dr." C. K. Baru, and all my committee members Drs. B. A. Galler, Y. C. Lee, V. Rosenberg, and Q. F. Stout for their vital feedback. I also wish to thank

Dec 31, 1987

Page 1

Page 2 of 55

DATABASE PROCESSING ON A CUBE-CONNECTED MULTICOMPUTER

Bernie Galler and Chaitanya Baru for their personal care throughout and even before the dissertation process. Additional special thanks are given to my fath...