Answering Queries Using Limited External Query Processors

Abstract

When answering queries using external information sources, their contents can be described by views. To answer a query, we must rewrite it using the set of views presented by the sources. When the external information sources also have the ability to answer some (perhaps limited) sets of queries that require performing operations on their data, the set of views presented by the source may be infinite (albeit encoded in some finite Previous work on answering queries using views has only considered the case where the set of views is finite. In order to exploit the ability of information sources to answer more complex queries, e consider the problem of answering conjunctive queries using infinite sets of views. Our first result is that an infinite set of views can be partitioned into a finite number of equivalence classes, such that picking one view from every nonempty class is suffcient to determine whether the query can be answered using the views. Second, we show how to compute the set of equivalence classes for sets of views encoded by a datalog program. Furthermore, we extend our results to the case when the query and the views use the built-in predicates <, , =, and 6=, and they are interpreted over a dense domain. Finally, we extend our results to conjunctive queries and views with the built-in predicates <, , and = interpreted over the integers. In doing so we present a result of independent interest, namely, an algorithm to minimize such queries. The work of the second and third authors was supported by NSF grant IRI{92{23405, ARO grant DAAH04{95{1{0192, and USAF contract F33615{93{1{1339