Browse Prior Art Database

Applying Data Flow Techniques to Data Base Machines

IP.com Disclosure Number: IPCOM000131527D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Nov-11
Document File: 11 page(s) / 40K

Publishing Venue

Software Patent Institute

Related People

Haran Boral: AUTHOR [+4]

Abstract

University of Wisconsin, Madison

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1982 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

Applying Data Flow Techniques to Data Base Machines

Haran Boral and David J. Dewitt

University of Wisconsin, Madison

Processor allocation based on data-driven execution can enhance parallelism and improve access to large nonnumerical data bases.

Recently, data flow languages and architectures have been the subject of much research. Although most projects set out to produce a general-purpose, data flow machine, the primary goal has been to reduce the execution time of large numerical computations. In this article, we describe a different line of research: the application of data flow machine principles towards improving access to large nonnumerical data bases.

For the past four years we have researched the problems associated with providing efficient access to relational data bases that are too large to be handled by a single conventional processor. The result of that research is Direct, a multiprocessor multiple instruction stream multiple data stream relational data base machine.) A prototype of this MIMD machine that supports the relational data base system Ingres2 became operational in June 1980 using a POP 11/40 and eight PDP I 1/23's.

All previous data base machines were single instruction stream multiple data stream machines and could thus execute only one data base operation at a time. One consequence of an SIMD design data base machine is that the activities of the processors do not have to be scheduled; during each time unit, all processors execute the same instruction. With an MIMD design, such as Direct, groups of processors can work on different instructions from the same query, from different queries, or both. Therefore, after the design of Direct was completed, alternative processor allocation strategies for MIMD data base machines were explored. The goal of this research was to determine what strategy would allow the greatest number of queries to be executed per time unit.

One of the strategies examined was based on data flow machine principles. In this article, we describe some of the results obtained from our experiments with the various strategies,3 in particular, experiences with variations of a strategy based on data flow techniques for processor allocation.

Relational data bases and data base machines

Relational data bases.

A relational data base4 consists of a number of normalized relations. Each relation is characterized by a fixed number of attributes and contains an arbitrary number of unique tuples. Thus, a relation can be viewed as a two-dimensional table in which the attributes are th...