Browse Prior Art Database

Retrieval Algorithm for Relational Data Bases

IP.com Disclosure Number: IPCOM000081373D
Original Publication Date: 1974-May-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 4 page(s) / 33K

IBM

Related People

Palermo, FP: AUTHOR

Abstract

A retrieval algorithm is given for responding to queries of arbitrary complexity on a shared data base, composed of relations of assorted degrees. The algorithm described below converts a query (given as a relation defining expression in the relational calculus) into a retrieval program, for creating the response relation to the query.

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 44% of the total text.

Page 1 of 4

Retrieval Algorithm for Relational Data Bases

A retrieval algorithm is given for responding to queries of arbitrary complexity on a shared data base, composed of relations of assorted degrees. The algorithm described below converts a query (given as a relation defining expression in the relational calculus) into a retrieval program, for creating the response relation to the query.

The input to the algorithm is a query in the form of a gamma-expression. A gamma expression consists of a set of target lists and a qualification formula. Each target list is a sequence of tuple variables and indexed tuple variables. Each variable appearing in a target list appears in the qualification formula as a free variable. Each variable in the qualification formula appears in at least one range term and is, therefore, coupled to at least one data base relation.

Each variable is related to a set of universe compatible data base relations. This correspondence is called the V-R relation. Each variable is also related to a set of local ranges. This relationship is called the L-V relation. Thus each data base relation is associated with a set of local range relations.

The join terms define the joins of local ranges which are to be constructed. Each join term schedules the formation of a semi-join for each local range, corresponding to the variables in the join term. Each target list defines a projection of the cartesian product of the ranges for the variables v1,...,vp. The response relation is the union of the relations defined by the set of target lists.

Initially a work list is created by scheduling the construction of a semi-join for each variable in each join term. If the variable is free, the reference relation is taken to be the projection of the local range for the variable defined by the target lists. In this case, the projection of each local range is scheduled for saving as an intermediate relation. If the variable is bound the local range is used as the reference relation.

Thus the work list consists of the following items:
1. A set of semi-joins to be constructed.
2. A set of target relations to be saved as reference

relations.
3. A set of joins to be formed because a

complementary semi-join has already been formed.

As a relation is explored, the scheduled operations are performed and the work list is modified to incorporate the results of the exploration. These include the scheduling of joins to be constructed for ranges which are connected to the newly constructed joins, and the removal of the semi-joins already formed from the work list.

At this time, the evaluation criterion is updated to reflect the current state of exploration and the next relation scheduled for exploration is determined. This process continues until all relations have been explored. At this time, the union of the individual components are formed and the quantifier operations are applied, to obtain the indirect relations for the target relation. The response

1

Page 2...