Name
Abstract | ||
|---|---|---|
Query optimization that involves expensive predicates have received considerable attention in the database community. Typically, the output to a database query is a set of tuples that satisfy certain conditions, and, with expensive predicates, these conditions may be computationally costly to verify. In the simplest case, when the query looks for the set of tuples that simultaneously satisfy k expensive predicates, the problem reduces to ordering the evaluation of the predicates so as to minimize the time to output the set of tuples comprising the answer to the query. Here, we give a simple and fast deterministic k-approximation algorithm for this problem, and prove that k is the best possible approximation ratio for a deterministic algorithm, even if exponential time algorithms are allowed. We also propose a randomized, polynomial time algorithm with expected approximation ratio 1 + root2/2 approximate to 1.707 for k = 2, and prove that 3/2 is the best possible expected approximation ratio for randomized algorithms. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-24698-5_5 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
latin american,satisfiability,query optimization | Query optimization,Approximation algorithm,Randomized algorithm,Combinatorics,Knowledge representation and reasoning,Database query,Tuple,Computer science,Time complexity,Database,Boolean conjunctive query | Conference |
Volume | ISSN | Citations |
2976 | 0302-9743 | 2 |
PageRank | References | Authors |
0.43 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Sany Laber | 1 | 229 | 27.12 |
| Renato Carmo | 2 | 19 | 3.26 |
| Yoshiharu Kohayakawa | 3 | 477 | 64.87 |