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

Effective Approach to Find Join Reducers for General Queries

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

Publishing Venue

IBM

Related People

Chen, MS: AUTHOR [+2]

Abstract

A new approach to find a sequence of join reducers for general query graphs is proposed to reduce the amount of data transmission in a distributed database environment. In the light of the proposed problem mapping, the algorithm developed uses the concept of divide and conquer to achieve polynomial execution time.

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 General Queries

       A new approach to find a sequence of join reducers for
general query graphs is proposed to reduce the amount of data
transmission in a distributed database environment.  In the light of
the proposed problem mapping, the algorithm developed uses the
concept of divide and conquer to achieve polynomial execution time.

      In a distributed database environment, semijoin has
traditionally been relied upon for reducing the communication cost.
We have found that judiciously applying join operations as reducers
can lead to further reduction in the communication cost required (*).
However, the problem of finding an optimal sequence of join reducers
is proven to have exponential complexity.  In this disclosure, we
propose a fast heuristic algorithm to determine a sequence of join
reducers for general query graphs (i.e., tree and cyclic

                            (Image Omitted)

 query graphs).  A cut to 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.  In the light of this problem transformation,
we developed the algorithm A1 below to determine a sequence of join
reducers for general query graphs.  This algorithm, based on the
mapping, employs a divide-and-conquer approach to find a CF set of
cuts and has polynomial time complexity. This is in sharp contrast to
the state space-search type-approach which is, in general,
intractable.

      In A1 the set S(ni) is the global variable that is used to keep
track of the set of nodes which are included in the same cut as ni
. A CF set of cuts is obtained by the recursive procedure FG shown
below.  A set C is used to keep the set of cuts determined.  We check
in the beginning of each iteration of procedure...