Querying Priced Information in Databases: the Conjunctive Case (Extended Abstract)
Eduardo Sany Laber, Renato Carmo, Yoshiharu Kohayakawa, Curitiba Pr · 2003
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 con- ditions, and, with expensive predicates, these conditions may be com- putationally 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 algo- rithm for this problem, and prove that k is the best possible approxi- mation ratio for a deterministic algorithm, even if exponential time al- gorithms are allowed. We also propose a randomized, polynomial time algorithm with expected approximation ratio 1+ p 2=2 1:707 for k = 2, and prove that 3=2 is the best possible expected approximation ratio for randomized algorithms.