Carnegie Mellon University
Browse
- No file added yet -

Randomized Approximation Algorithms for Query Optimization Problems on Two Processors

Download (268.11 kB)
journal contribution
posted on 1990-01-01, 00:00 authored by Eduardo Laber, Ojas Parekh, Ramamoorthi RaviRamamoorthi 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

1990-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC