Answering Queries using Templates with Binding Patterns

) Anand Rajaraman Yehoshua Sagiv Jeffrey D. Ullman Department of Computer Science Stanford University ABSTRACT 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. I. Motivation A data-integration system such as Tsimmis (Papakonstantinou, Garcia, and Widom [1994], Chawathe et al. [1994]) translates information sources of arbitrary type into a common data model and language. If a source is an SQL database, then its interface with the Tsimmis s...