We present WSQ/DSQ (pronounced "wisk-disk"), a new approach for
combining the query facilities of traditional databases with existing
search engines on the Web.  WSQ, for Web-Supported (Database) Queries,
leverages results from Web searches to enhance SQL queries over a
relational database.  DSQ, for Database-Supported (Web) Queries, uses
information stored in the database to enhance and explain Web
searches.  This paper focuses primarily on WSQ, describing a simple,
low-overhead way to support WSQ in a relational DBMS, and
demonstrating the utility of WSQ with a number of interesting queries
and results. The queries supported by WSQ are enabled by two virtual
tables, whose tuples represent Web search results generated
dynamically during query execution.  WSQ query execution may involve
many high-latency calls to one or more search engines, during which
the query processor is idle.  We present a lightweight technique
called asynchronous iteration that can be integrated easily into a
standard sequential query processor to enable concurrency between
query processing and multiple Web search requests.  Asynchronous
iteration has broader applications than WSQ alone, and it opens up
many interesting query optimization issues.  We have developed a
prototype implementation of WSQ by extending a DBMS with virtual
tables and asynchronous iteration; performance results are reported.