Capability Sensitive Query Processing on Internet Sources

Abstract

On the Internet, query processing capabilities of sources may be limited in diverse ways, and this makes answering even the simplest queries challenging. In this paper, we present a scheme called GenCompact for generating capability sensitive plans for selection queries. The generated query plans may be better than what existing query processing systems produce for three reasons: (1) the sources are guaranteed to support the query plans; (2) the plans take full advantage of the source capabilities; and (3) the plans may be more efficient since a larger space of plans is examined. Even though GenCompact considers many plans, it is relatively efficient because it uses effective data structures and pruning rules. We study the optimality of the plans generated as well as the efficiency of the plan generation process