A new way to compute the product and join of relations
Won Bae Kim · 1980
This paper presents a new method of computing the product or join of n relations in a paged-memory environment. The method, termed the nested-block method, is an attempt to take maximum advantage of available main-memory buffer space. The problem of finding an optimal allocation of main-memory buffer space for the nested-block method of scanning n relations poses a nonlinear integer-programming problem. This paper first describes the operation of the nested-block method, and derives corresponding cost formula. It then presents an efficient heuristic algorithm for determining a near-optimal allocation of main-memory buffer space. The need to compute the product of relations arises naturally in processing n-relation queries. Conventional techniques for computing the join of relations can be complemented by the nested-block method. This paper examines these two important applications of the nested-block method.