Browse Prior Art Database

Effective Approach to Find Join Reducers for Tree Queries

IP.com Disclosure Number: IPCOM000101327D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 3 page(s) / 100K

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+2]

Abstract

In the light of the tree structure, an efficient algorithm is proposed to determine a sequence of join reducers to reduce the amount of data transmission required for the processing of tree queries in a distributed database environment.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Effective Approach to Find Join Reducers for Tree Queries

       In the light of the tree structure, an efficient
algorithm is proposed to determine a sequence of join reducers to
reduce the amount of data transmission required for the processing of
tree queries in a distributed database environment.

      Semijoin has traditionally been the major means to reduce the
communication cost required for distributed query processing.  We
have found that judiciously applying join operations as reducers can
lead to further reduction in the communication cost required (*).
The preceding article proposed a heuristic algorithm to determine a
sequence of join reducers for general query graphs.  In view of the
fact that tree queries (i.e., those queries whose join query graphs
are trees) are the most prevalent cases in a distributed database
environment, we propose in this disclosure a fast heuristic algorithm
which fully exploits the structure of a tree query and determines a
sequence of join reducers specifically for tree query graphs.  A cut
to

                            (Image Omitted)

 a graph, denoted by (VA,V - VA),
or VA when V is given, is a separation of a node set VA  V
from the node set V of the graph.  A complete and feasible (CF) set
of cuts to a graph of n nodes is a set of cuts to that
graph such that (1) there are exactly n-1 cuts in the set, (2) any
two nodes in the graph are divided by at least one cut, and (3) for
any two cuts VA and VB in the set either (i) VA  VB, (ii) VB
VA or (iii) VA  VB = d.  Using the concept of a CF set of
cuts, the problem of determining a sequence of join reducers for a
query graph can be transformed to the one of finding a CF set of cuts
to that graph (see the preceding article).  In the light of this
fact, we developed the algorithm M1 below to determine a sequence of
join reducers for tree query graphs.  This algorithm, based on the
tree structure, uses a bottom-up approach to find a CF set of cuts,
which not only achieves polynomial execution time but also leads to a
more efficient solution than the one obtained in the preceding
article.

      To find a set of cuts, algorithm M1 employ...