An algorithm for answering queries efficiently using views
Prasenjit Mitra · 2001
Algorithms for answering queries using views have been used to integrate information from multiple sources. The bucket algorithm, predominantly used to reformulate queries, has two drawbacks. It generates a large number of candidate solutions, even when the number of sound solutions is small, and then checks for their soundness using an exponential conjunctive-querycontainment test. Leser [1] presents an algorithm that generates a smaller number of candidate solutions and also eliminates the conjunctive-query-containment-test, but does not guarantee the soundness of all generated solutions. We introduce the concept of shared variable buckets(SVB) covering all subgoals that share a variable in order to ensure that only sound solutions are generated and thus avoid the conjunctive-query containment test. The algorithm presented has the advantage that it avoids generation of a large set of candidate solutions whenever possible. Experimental results prove the superiority of this algorithm over previous solutions.