Stanford InfoLab Publication Server

Answering Queries using Templates with Binding Patterns

Rajaraman, A. and Sagiv, Y. and Ullman, J. (1995) Answering Queries using Templates with Binding Patterns. In: Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems., May 22-25, 1995, San Jose, California.




When integrating heterogeneous information resources, it is often the case that the source is rather limited in the kinds of queries it can answer. If a query is asked of the entire system, we have a new kind of optimization problem, in which we must try to express the given query in terms of the limited query templates that this source can answer. For the case of conjunctive queries, we show how to decide with a nondeterministic polynomial-time algorithm whether the given query can be answered. We then extend our results to allow arithmetic comparisons in the given query and in the templates.

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:103
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:04 Dec 2008 14:48

Download statistics

Repository Staff Only: item control page