Query Optimization Using Local Completeness

Abstract

We consider the problem of query plan optimization in information brokers. Information brokers are programs that facilitate access to collections of information sources by hiding source-specific peculiarities and presenting uniform query interfaces. It is unrealistic to assume that data stored by information sources is complete. Therefore, current implementations of information brokers query all possibly relevant information sources in order not to miss any answers. This approach is very costly. We show how a weaker form of completeness, local completeness, can be used to minimize the number of accesses to information sources. Introduction We consider the problem of query plan optimization in information integration. The goal of information integration is to provide the illusion that data stored by distributed information sources is stored in a single "global" database. Users can pose queries in terms of the global database scheme. These queries then need to be translated into queries...