Answering queries using limited external query processors

When answering queries using external information sources, the contents of the queries can be described by views. To answer a query, we must rewrite i t using the set of views presented by the sources. When the external inform ation sources also have the ability to answer some (perhaps limited) sets o f queries that require performing operations on their data, the set of view s presented by the source may be infinite (albeit encoded in some finite fa shion). 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, we consider the prob lem of answering conjunctive queries using infinite sets of conjunctive vie ws. Our first result is that an infinite set of conjunctive views can be pa rtitioned into a finite number of equivalence classes, such that picking on e view from every nonempty class is sufficient to determine whether the que ry can be answered using the views. Second, we show how to compute the set of equivalence classes for sets of conjunctive views encoded by a datalog p rogram. Furthermore, we extend our results to the case when the query and t he views use the built-in predicates <, less than or equal to, =, and not e qual, and they are interpreted over a dense domain. Finally, we extend our results to conjunctive queries and views with the built-in predicates <, le ss than or equal to, and = interpreted over the integers. In doing so we pr esent a result of independent interest, namely, an algorithm to minimize su ch queries. (C) 1999 Academic Press.