An Algorithm for Efficiently Answering Queries Using Views.

Abstract

Algorithms for answering queries using views have been suggested and used to integrate information from multiple sources. Each source exports a view of the data it contains. A query answering algorithm needs to select which sources to consult in order to construct the solution. This is done by reformulating the query in terms of the views. The bucket algorithm has been predominantly used to reformulate queries. It involves generating candidate solutions and testing their validity to reject the irrelevant ones. The validation is performed using an expensive containment test for conjunctive queries. Scalability of such algorithms is largely dependent upon the efficiency with which the irelevant solutions can be pruned out before performing the costly validation. In this paper, an algorithm is highlighted that eliminates the necessity of performing a conjunctive query containment test and significantly reduces the number of irrelevant candidate solutions to be considered. Experimental results prove the superiority of this algorithm over previous solutions.