Stanford InfoLab Publication Server

Answering Queries Using Limited External Query Processors

Levy, A. and Rajaraman, A. and Ullman, J. (1996) Answering Queries Using Limited External Query Processors. In: Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'96), June 3-5, 1996, Montreal, Canada.




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

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science > Data Integration and Mediation
Computer Science > Query Processing
Projects:Information Integration
Related URLs:Project Homepage
ID Code:190
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:09 Dec 2008 09:09

Download statistics

Repository Staff Only: item control page