Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Computation of Generalized Joins of Relations

IP.com Disclosure Number: IPCOM000086378D
Original Publication Date: 1976-Aug-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 51K

IBM

Related People

Chandra, AK: AUTHOR

Abstract

A generalized join of two relations is an eq-join on several designated columns, followed by the deletion of certain columns of the resulting relation. A way of computing the generalized join faster than known methods for large relations is described subsequently. (Image Omitted) (Image Omitted)

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

Computation of Generalized Joins of Relations

A generalized join of two relations is an eq-join on several designated columns, followed by the deletion of certain columns of the resulting relation. A way of computing the generalized join faster than known methods for large relations is described subsequently.

(Image Omitted)

(Image Omitted)

The generalized join includes, as special cases, the simple eqjoin, projection. restriction, Cartesian product (or concatenation), and intersection [1], and a set of generalized joins characterizes the important subclass of queries called conjunctive queries. Hence an efficient algorithm for computing joins provides a way for efficiently answering queries in general, and conjunctive queries in particular.

(Image Omitted)

The main advantages of this method are: (i) Reducing generalized joins to boolean matrix multiplication. (ii) An algorithm that compares well with obvious algorithms on sparse relations, and runs substantially better on dense relations. Bibliography. [1] Codd, "A Relational Model of Data", CACM, 13, 6. [2] Strassen, "Gaussian elimination is not optimal", Numerische Mathematik, 13, 354-356.

1

Page 2 of 2

2