Randomized Approximation Algorithms for Query Optimization Proble.pdf.pdf' (268.11 kB)

Randomized Approximation Algorithms for Query Optimization Problems on Two Processors

Download (268.11 kB)
journal contribution
posted on 01.01.1990 by Eduardo Laber, Ojas Parekh, Ramamoorthi Ravi
Query optimization problems for expensive predicates have received much attention in the database community. In these situations, the output to the database query is a set of tuples that obey certain conditions, where the conditions may be expensive to evaluate computationally. In the simplest case when the query looks for the set of tuples that simultaneously satisfy two expensive conditions on the tuples and these can be checked in two different distributed processors, the problem reduces to one of ordering the condition evaluations at each processor to minimize the time to output all the tuples that are answers to the query. We improve upon a previously known deterministic 3-approximation for this problem: In the case when the times to evaluate all conditions at both processors are identical, we give a 2-approximation; In the case of non-uniform evaluation times, we present a 8/3 -approximation that uses randomization. While it was known earlier that no deterministic algorithm (even with exponential running time) can achieve a performance ratio better than 2, we show a corresponding lower bound of 3/2 for any randomized algorithm.

History

Date

01/01/1990

Exports

Exports