Stanford InfoLab Publication Server

An Algorithm for Efficiently Answering Queries Using Views.

Mitra, P. (1999) An Algorithm for Efficiently Answering Queries Using Views. Technical Report. Stanford.




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.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:query reformulation, information integration, views,
Subjects:Computer Science > Data Integration and Mediation
Related URLs:Project Homepage
ID Code:402
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 09:49

Download statistics

Repository Staff Only: item control page