\documentstyle[vldb]{article}
\input{psfig}

\newif\iffullversion
\fullversionfalse
%\fullversiontrue

\newtheorem{EXAMPLE}{Example}[section]
\newenvironment{example}{\begin{EXAMPLE}\rm}{\defend\end{EXAMPLE}}

\newcommand{\eat}[1]{}
\newtheorem{THEOREM}{Theorem}[section]
\newenvironment{theorem}{\begin{THEOREM} \hspace{-.85em} {\bf :} }%
                        {\end{THEOREM}}

\newcommand{\Set}[1]{{\mbox{$\{ #1 \}$}}}
\newcommand{\Sel}[2]{{\mbox{$ \sigma_{#1}(#2) $}}}
\newcommand{\Proj}[2]{{\mbox{$ \pi_{#1}(#2) $}}}
\newcommand{\Fd}[2]{{\mbox{$#1 \rightarrow #2$}}}
\newcommand{\Ind}[2]{{\mbox{$#1 \subseteq #2$}}}
\newcommand{\const}[1]{{\sf #1}}
\newcommand{\Vec}[1]{{\mbox{$\overline{#1}$}}}
\newcommand{\tup}[1]{{\mbox{$\langle #1 \rangle$}}}
\newcommand{\defend}{\ \ $\Box$}
\def\qif{{\mbox{$\;\leftarrow\;$}}}
\def\qand{{\mbox{$, \; $}}}
\def\qsub{{\mbox{$\;\subseteq\;$}}}
\def\IM{Information Manifold}
\newcommand{\rel}[1]{{\it #1\/}}
\def\rA{\rel{Automobile}}
\def\rC{\rel{Car}}
\def\rM{\rel{Motorcycle}}
\def\rP{\rel{Product}}
\def\rN{\rel{NewCar}}
\def\rU{\rel{UsedCar}}
\def\rS{\rel{CarForSale}}
\def\rMo{\rel{Model}}
\def\rPr{\rel{Price}}
\def\rCo{\rel{Country}}
\def\rYe{\rel{Year}}
\def\rOw{\rel{SellerContact}}
\def\rRe{\rel{ProductReview}}
\def\rCa{\rel{Category}}
\pagestyle{empty}
\title{\bf Querying Heterogeneous Information Sources Using Source
  Descriptions} 
\author{
{\bf Alon Y. Levy} \\
{\small AT\&T Research} \\
{\small levy@research.att.com} \\
\and
{\bf Anand Rajaraman}\thanks{Part of this work was done while this author was
visiting AT\&T Bell Laboratories.}\\
                       {\small Stanford University}\\
                        {\small anand@cs.stanford.edu}
\and
{\bf Joann J. Ordille} \\
{\small  Bell Laboratories} \\
{\small joann@research.att.com}
}

%\institution{}

%\date{}

%%
\begin{document}
\bibliographystyle{alpha}


\maketitle

\begin{abstract}\small
  We witness a rapid increase in the number of structured information
  sources that are available online, especially on the WWW.  These
  sources store interrelated data on topics such as  product information, stock
  market information, entertainment, etc. We would like to use the data stored in
  these databases to answer complex queries that go beyond keyword
  searches.  We describe the Information Manifold, an implemented
  system that provides uniform access to a heterogeneous collection of
  more than 100 information sources,  on the WWW. IM
  contains declarative descriptions of the contents and capabilities
  of the information sources.  We describe algorithms that use the
  source descriptions to prune efficiently the set of information
  sources for a given query and practical algorithms to generate
  executable query plans.  We also present experimental studies that
  indicate that the architecture and algorithms used in the
  Information Manifold scale up well to several hundred information
  sources.

\eat{
We face the following challenges: (1) Several
  information sources store interrelated data, and any query-answering
  system must understand the relationships between their contents.  (2) Many
  sources are not full-featured database systems and can answer only a small
  set of queries over their data (for example, forms on the WWW restrict the
  set of queries one can ask).  (3) Since the number of sources is very
  large, effective techniques are needed to prune the set of information
  sources accessed to answer a query.  (4) The details of interacting with
  each source vary greatly.
}

\end{abstract}

\section{Introduction}
\label{sec:intro}

We witness a rapid increase in the number of structured information sources
that are available online.  The World-Wide Web (WWW), in particular, is a
popular medium for interacting with such sources. The WWW is usually
regarded as an interconnected collection of unstructured documents. However,
a large number of structured information sources are now becoming available
on the Web.\eat{See  {\tt
http://www.intbc.com/sleuth/} for an index that focuses mostly on such
sources.} 
   These sources include both free and commercial databases on
product information, stock market information, real estate, automobiles, and
entertainment.  The interface to such sources is typically a collection of
{\em fill-out forms}.
%, which we view as a query interface in the flavor of
%Query-by-Example systems~\cite{QBE}. 
The query answer usually takes the form of an HTML document that is
very structured, and can be parsed and converted into a set of tuples
or more complex data types.  There are other structured information
sources that are available not on the WWW such as name servers,
bibliographic sources, and university-wide and company-wide
information systems, and they too  provide query interfaces.

Most search tools available for the WWW today (e.g., AltaVista, Lycos,
Inktomi, Yahoo) are based on keyword search. Keyword search is a useful
way to search a collection of unstructured documents, but is not
effective with structured sources.  Currently, the interaction with
such a large collection of structured sources is done manually.  The
user must consider the list of sources available, decide which ones to
access, interact with each one individually, and manually combine
answers from different sources.  We would like to use the data stored
in these databases to answer complex queries, and provide a {\em
uniform\/} interface to the sources.  In particular, the user should
be able to express {\em what\/} he or she wants, and the system will
find the relevant sources and obtain the answers, possibly by
combining data from multiple sources.


\begin{figure*}
\begin{center}
\begin{tabular}{|l|} \hline
{\bf Source 1:} {\sf Used cars for sale.}\\
Accepts as input a category or model of car, and optionally a price range
and a year range.\\ For each car that satisfies the conditions, gives 
model, year, price, and seller contact information.\\ 
\hline
{\bf Source 2:} {\sf Luxury cars for sale. All cars in this
  database are priced above \$20,000}\\
Accepts as input a category of car and an optional price range. \\
For each car that
satisfies the conditions, gives model, year, price, and seller contact
information.\\
\hline
{\bf Source 3:} {\sf Vintage cars for sale (cars 
  manufactured before 1950).}\\
Accepts as input a model and an optional year range. \\ Gives model, year,
price, and seller contact information for qualifying cars.\\
\hline
{\bf Source 4:} {\sf Motorcycles for sale.}\\
Accepts as input a model and an optional price range. \\
Gives model, year, price, and
seller contact information.\\
\hline
{\bf Source 5:} {\sf Car reviews database. Contains reviews for
  cars manufactured after 1990.}\\
Accepts as input a model and a year. \\
Output is a car review for that model
and year.\\
\hline
\end{tabular}
\end{center}
\caption{Example information sources.}
\label{fig:info-sources}
\end{figure*}

\begin{example}
\label{motivating-eg}
Suppose we are interested in purchasing a car. The parameters of
interest to us 
are its category  (sportscar or sedan),  price, 
year of manufacture,  model, and the car reviews. 
We ask query $Q$: {\em Get the price and reviews of sportscars for
sale that were
  manufactured no earlier than 1992}.
Suppose we have access to the online information  sources shown in
Figure~\ref{fig:info-sources}, among many others. 
Some of the sources are obviously not useful to
answer $Q$. We can straightaway determine that Source 4 is not useful
to answer this query, because it has no information about cars. We can also
conclude that Source 3 is not relevant. Here the reasoning is more subtle:
we are interested only in cars manufactured after 1992, whereas Source 3 has
information only on cars manufactured before 1950.
We are left with sources 1, 2, and 5 and two possible plans to answer
$Q$:
\begin{enumerate}
\item Ask Source 1 for the models and prices of all sportscars manufactured
  after 1992. For each model, obtain a
  review from the Source 5.
% Produce a set of \tup{\rMo, \rPr, \rRe} tuples.
\item Ask Source 2 for the models, years, and prices of sportscars.
  From the \tup{\rMo, \rYe, \rPr} tuples that result, select only
  those where $\rYe \geq 1992$. For each model in the selected tuples,
  obtain a review from Source 5. 
%Produce a set of \tup{\rMo, \rPr, \rRe}
%  tuples.
\end{enumerate}
Notice that in plan 1 we took advantage of the capability of Source 1
to select a specified year range, whereas in plan 2 we had to do the
selection ourselves because Source 2 cannot do it for us.  Also note
that the outputs of Sources~1 and~2 are enough to satisfy the inputs
requirements of Source~5 (i.e., the year and model of the car). For
example, if Source~5 would also require more specific information
about the car (e.g., number of doors, engine type) in order to return
a review, we would not be able to combine information from these three
sources.  It is possible to verify that these are the only two 
query plans to answer $Q$ using these information sources. The answer
to $Q$ is the union of the sets of tuples produced by executing these
two plans.
\end{example}

One of the key difficulties in providing access to a large collection
of information sources is that several sources store interrelated data, and any
  query-answering system must understand and exploit the relationships
  between their contents. In particular, since the number of sources
is very large,  we must have enough
information about the sources that enables us to prune the sources
accessed in answering a specific query, and we must have effective
techniques for pruning sources. Second, 
many sources are not full-featured database systems and can answer
  only a small set of queries over their data (for example, forms on the WWW
  restrict the set of queries one can ask). Moreover, most sources contain
  {\em incomplete information}. For example, there are several information
  sources advertising cars for sale. No single source contains information
  on all cars for sale.


We describe the Information Manifold (IM), a fully implemented system
that provides uniform access to a heterogeneous collection of more
than 100 information sources on the WWW. IM tackles the above problems
by providing a mechanism to describe declaratively the contents and
query capabilities of available information sources. There is a clean
separation between the declarative source description and the actual
details of interacting with an information source. The system uses the
source descriptions to prune efficiently the set of information
sources for a given query and to generate executable query
plans. Specifically, we make the following contributions. First, we
present a practical mechanism to describe declaratively the {\em
contents} and {\em query capabilities} of information sources.  In
particular, the contents of the sources are described as {\em
queries\/} over a set of relations and classes. Consequently, it is
possible to model the fine-grained distinctions between the contents
of different sources, and it is easy to add and delete sources.
Modeling the query capabilities of information sources is crucial in
order to interact with many existing sources.  Second, we describe an
efficient algorithm that uses the source descriptions to create {\em
query plans} that can access several information sources to answer a
query.  The algorithm prunes the sources that are accessed to answer
the query, and considers the capabilities of the different sources.
Finally, we describe experiments that show that our query planning
algorithm will scale up as the number of information sources
increases. The experiments show the performance of our query planning
algorithm using 100 information sources.


There are several important issues in building 
a system that provides  a uniform interface
to multiple information sources, that are not discussed here.
In particular, the issue of 
 deciding that two constants in two
different information sources refer to the {\em same\/} object in the
world (e.g., the same person appearing in two different information
sources). Briefly, our implementation tries first to find unique
identifiers for each constant (e.g., social security number of a
person). When it cannot find such identifiers it uses heuristic {\em
correspondence functions} as in the Remote-Exchange
system~\cite{mcleod94}.  

%We do not discuss issues of consistency
%between the information sources or payment for information. 

\eat{
 In particular, the goal of \IM\ is to provide only a {\em
query\/} interface, and not update or transaction facilities. As a
consequence, we do not address issues such as consistency and
transaction processing which are addressed by research on
multidatabase systems.  
\eat{We do not also concern ourselves with how
descriptions of information sources are
obtained\footnote{See~\cite{lo95} for a first large-scale experiment
in obtaining descriptions of information sources that provide name
services.}  and where they are stored, and issues concerning the
design of the programs that actually interface with the sources.}
Issues of security and payment for information are also
beyond the scope of this paper.

An important issue that is addressed in our system but we do not
discuss in this paper is how we}



\eat{
This paper is organized as follows. Section~\ref{motivating-eg} presents a
concrete example of the notion of queries, source descriptions, and query
plans. The treatment in Section~\ref{motivating-eg} is
informal. Section~\ref{sec:data-model} describes our data model.
Section~\ref{sec:descriptions}
formalizes the notion of queries, source descriptions, and query
plans. Section~\ref{sec:algos} presents our algorithms for pruning
sources and generating query plans. In Section~\ref{sec:implementation} 
we describes the implemented Information Manifold system and present
our experimental results. Section~\ref{sec:related-work} discusses related
work, while Section~\ref{sec:conclusions} concludes with some ideas for
future work.}

\eat{
\section{Motivating Example}
\label{motivating-eg}
% There are several information sources available relating to purchasing
% products (such as automobiles and computers). These information sources are
% autonomous and are typically managed by different organizations. There are
% several databases available describing used cars for sale and their
% properties (e.g., {\tt http://www.sjmercury.com/class/trans/today}), and
% several others providing reviews of cars and other products (e.g., the
% Consumer Reports).

\begin{figure}
\begin{center}
\begin{tabular}{|l|} \hline
{\bf Source 1:} {\sf Used cars for sale.}\\
Accepts as input a category or model of car, and optionally a price range
and a year range.\\ For each car that satisfies the conditions, gives 
model, year, price, and seller contact information.\\ 
\hline
{\bf Source 2:} {\sf Luxury cars for sale. All cars in this
  database are priced above \$20,000}\\
Accepts as input a category of car and an optional price range. \\
For each car that
satisfies the conditions, gives model, year, price, and seller contact
information.\\
\hline
{\bf Source 3:} {\sf Vintage cars for sale (cars 
  manufactured before 1950).}\\
Accepts as input a model and an optional year range. \\ Gives model, year,
price, and seller contact information for qualifying cars.\\
\hline
{\bf Source 4:} {\sf Motorcycles for sale.}\\
Accepts as input a model and an optional price range. \\
Gives model, year, price, and
seller contact information.\\
\hline
{\bf Source 5:} {\sf Car reviews database. Contains reviews for
  cars manufactured after 1990.}\\
Accepts as input a model and a year. \\
Output is a car review for that model
and year.\\
\hline
\end{tabular}
\end{center}
\caption{A set of related information sources. These information sources are
  typical of those found on the World-Wide Web.}
\label{fig:info-sources}
\end{figure}

Suppose we are interested in purchasing a car. The parameters of
interest to us 
are the category of car (sportscar or sedan), the price, the 
year of manufacture, the model, and the car reviews. 
We ask query $Q$: {\em Get the price and reviews of sportscars for
sale that were
  manufactured no later than 1992}.
Suppose we have available the information sources shown in
Figure~\ref{fig:info-sources}, among many others. These sources may be
available as WWW forms, for instance.

Let us try to eliminate sources that are obviously not useful to
answer $Q$. We can straightaway determine that Source 4 is not useful
to answer this query, because it has no information about cars. We can also
conclude that Source 3 is not relevant. Here the reasoning is more subtle:
we are interested only in cars manufactured after 1992, whereas Source 4 has
information only on cars manufactured before 1950, and the two year ranges
do not intersect.

We are left with sources 1, 2, and 5. We come up with two query plans:
\begin{enumerate}
\item Ask Source 1 for the models and prices of all sportscars manufactured
  after 1992. For each model, obtain a
  review from the Source 5. Produce a set of \tup{\rMo, \rPr, \rRe} tuples.
\item Ask Source 2 for the models, years, and prices of sportscars.
  From the \tup{\rMo, \rYe, \rPr} tuples that result, select only
  those where $\rYe \geq 1992$. For each model in the selected tuples,
  obtain a review from Source 5. Produce a set of \tup{\rMo, \rPr, \rRe}
  tuples.
\end{enumerate}
Notice that in plan 1 we took advantage of the capability of Source 1
to select a specified year range, whereas in plan 2 we had to do the
selection ourselves because Source 2 cannot do it for us.  Also note
that the outputs of Sources~1 and~2 are enough to satisfy the inputs
requirements of Source~5 (i.e., the year and model of the car). For
example, if Source~5 would also require more specific information
about the car (e.g., number of doors, engine type) in order to produce
a review, we would not be able to combine information from these three
sources.  It is possible to verify that these are the only two valid
query plans to answer $Q$ using these information sources. The answer
to $Q$ is the union of the sets of tuples produced by executing these
two plans.

\eat{
In the sections that follow, we formalize the notions introduced in this
example. Section~\ref{sec:data-model} describes our data model and how
queries such as $Q$ are posed. Section~\ref{sec:descriptions} explains how
we describe the contents and query capabilities of sources as in
Figure~\ref{fig:info-sources}, and also formalizes the notion of a valid
query plan for a query. Section~\ref{sec:algos} presents algorithms that
generate plans like the ones above. The algorithms proceed in two stages,
exactly as we did in the example: in the first stage, we prune away sources
that are {\em irrelevant} to the query at hand, and in the second stage, we
generate valid query plans using only the relevant sources. 
}
}

\iffullversion
\subsection{Related Work}
The fundamental difference between our work and other work that
attempts to provide access to collections of information sources is
our focus on {\em describing} declaratively the contents of an
information source (e.g., ``used cars for sale priced over \$20,000'')
and its query capabilities. Given a query, our algorithm uses the
descriptions to generate plans to answer the query. Thus our approach
is source-centric rather than query-centric. Other projects (e.g.,
TSIMMIS~\cite{tsimmis}, HERMES~\cite{hermes96}) are query-centric:
they choose a set of queries, and for each such query they provide a
procedure to answer the query using the available sources. Given a new
query, their algorithms answer it by trying to relate it to existing
queries. Our approach has two main advantages.  First, we are not
restricted by which queries can be answered by the system. Second, it
is easier to add or delete sources because we do not have to modify
the query-specific procedures to accommodate the changes.  A more
detailed discussion of related work appears in
Section~\ref{sec:related-work}.

\subsection{Paper Organization}
This paper is organized as follows.  Section~\ref{sec:data-model} 
describes the data model underlying the
Information Manifold, and 
Section~\ref{sec:descriptions}   formally describes the source
descriptions and query plans.
 Section~\ref{sec:algos} presents our algorithm for pruning
sources and generating query plans. In Section~\ref{sec:implementation} 
we describe the implemented Information Manifold system and present
our experimental results. Section~\ref{sec:related-work} discusses related
work, while Section~\ref{sec:conclusions} contains concluding remarks.
\fi                                   


\section{Data Model}
\label{sec:data-model}

We use the relational model, augmented with certain object-oriented
features that are useful for describing and reasoning about the
contents of information sources. The data model includes (1) {\em
relations} of any arity, (2) {\em classes} and a class hierarchy.
There is a partial order $\prec$ such that $C \prec D$ whenever class
$C$ is a subclass of class $D$, and (3) a set of {\em attributes}
associated with each class.  A class also inherits attributes from its
superclasses. Attributes may be {\em single-valued\/} or {\em
multi-valued}.

Relations contain tuples while classes contain objects. Each object
has a unique identifier. The attribute values of a relation or a class
can be either atomic values (strings or integers) or object
identifiers.  An object may belong to more than one class (even if the
classes are not related via $\prec$).  It is possible to declare a
pair of classes to be {\em disjoint}, meaning that no object can
belong to both classes.

In order to be able to treat relations and classes uniformly, we
 associate a unary relation
with each class and a binary relation with each attribute.
 The contents of these relations are as follows (we use the same name
for the class and its associated relation):
\begin{itemize}
\item For class $C$, $\tup{X} \in C$ whenever $x$ is the identifier of an
  object $o$ and $C$ is one of the classes of $o$.
\item For attribute $A$ on class $C$, $\tup{X,Y} \in A$ whenever 
  $\tup{X} \in C$ 
  and $x.A = y$ ($y$ is called the {\em $A$-filler} of $x$).
\end{itemize}

For single-valued
attributes we often use  $A(x)$ to denote the only value for which
$A(x,y)$ can hold.
 In
order that these relations fully capture the semantics of the class
hierarchy, we also  enforce certain integrity constraints.
 These constraints take the form of {\em inclusion dependencies}
and {\em functional dependencies}. In particular:
\begin{itemize}
\item Whenever $C \prec D$ when $C$ and $D$ are viewed as classes, the
  inclusion dependency \Ind{C}{D}\ holds when $C$ and $D$ are viewed as
  relations.
\item For each auxiliary relation $\rel{A}(X,Y)$ corresponding to a
single-valued attribute $A$, we have the  functional dependency $A:\Fd{X}{Y}$.
\item For each pair of disjoint classes $C$ and $D$, 
  $C \cap D = \emptyset$ holds when $C$ and $D$ are viewed as relations.
\end{itemize}

\eat{
Thus, although our data model includes the notion of classes and
inheritance, we can capture exactly the same semantics in the augmented set
of relations, provided that we allow functional and inclusion dependencies.
Therefore, the algorithms in this paper can take advantage of the formal
tools developed for the relational model (such as containment of
conjunctive queries in the presence of functional and inclusion
dependencies). In the rest of the paper, we will use the term ``relation''
to refer either to a true relation or to an auxiliary relation. }

\begin{table*}
\begin{center}
\begin{tabular}{|l|l|l|l|} \hline
Class & Subclass of & Attributes & Disjoint from \\ \hline
\rel{Product} &  & \rel{Model} & \rel{Person} \\
\rel{Automobile} & \rel{Product} & \rel{Model}, \rel{Year}, \rCa &
\rel{Stereo}\\
\rel{Motorcycle} & \rel{Automobile} & \rel{Model}, \rel{Year} &
\rel{Car} \\
\rel{Car} & \rel{Automobile} &\rel{Model}, \rel{Year}, \rCa &
 \rel{Motorcycle} \\
\rel{NewCar} & \rel{Car} &\rel{Model}, \rel{Year}, \rCa &
 \rel{UsedCar} \\
\rel{UsedCar} & \rel{Car} &\rel{Model}, \rel{Year}, \rCa &
 \rel{NewCar} \\
\rel{CarForSale} & \rel{Car} & \rel{Model}, \rel{Year}, \rCa,
\rel{Price}, \rel{SellerContact} & \\ \hline
\end{tabular}
\end{center}
\caption{A class hierarchy. The classes \rel{Person} and \rel{Stereo} are not
  shown.} 
\label{world}
\end{table*}

Table~\ref{world} shows the classes and attributes we use throughout
the paper.

\iffullversion
\begin{example}
Table~\ref{world} shows some classes and their attributes. In this example, 
we have $\rC \prec \rA$ and $\rA \prec \rP$, among other such
relationships. 
Since $\rA \prec \rP$, \rA\ inherits the attribute \rMo\ from \rP.
Classes \rN\ and \rU\ are declared to be disjoint, reflecting the fact that a
car cannot be both new and used. However, class \rS\ is disjoint with neither
\rN\ or \rU.
Disjointness information can also be inferred from the class hierarchy:
\rU\ and \rM\ are disjoint because $\rU \prec \rC$ and 
\rC\ is disjoint from \rM. 
\end{example}
\fi

\noindent
{\bf The World View:}
In the \IM, the user poses queries in terms of a {\em world view}
which is a collection of virtual relations and classes. Thus, the
world view is like a schema. We use the term world view instead of
schema to emphasize the fact that no data is actually stored in the
relations and classes of the world view.\footnote{However we do not
mean to imply that the world view is a schema for {\em all\/}
domains.}  It serves as the schema against which the user poses
queries (thereby freeing the user from having to interact with each
source schema individually), and it is used for
describing the contents of the information sources.



\begin{example}
  The world view we use throughout this paper 
  consists of the classes in Table~\ref{world} (all the attributes of
which are single-valued) and the relation $\rRe(\rMo,
  \rYe, \rel{Review})$. 
\end{example}
\iffullversion
This relation contains triples $(M, Y, R)$ such that
  $R$ is a review of a product of model $M$ manufactured in year $Y$ (for
  example, a product review in the Consumer Reports). 
\fi


%\subsection{Queries}

In this paper, a {\em query} is a conjunctive query over the
world-view relations  and the built-in predicates $<$, $\leq$.
 We require the queries to be range-restricted.

\begin{example}
  The following query asks for models, prices, and reviews of sportscars for
  sale that were manufactured no earlier than 1992 (query $Q$ of
Example~\ref{motivating-eg}): 
\begin{eqnarray*}
q(m, p, r) & \qif & \rS(c)\qand \rCa(c, \const{sportscar})\qand  \\
           &      & \rYe(c, y)\qand y \geq \const{1992}\qand \rPr(c,p)\qand\\
           &      &  \rMo(c,m)\qand \rRe(m, y, r)
\end{eqnarray*}

\end{example}

We use {\sf this} font to denote constants,  lowercase letters for
variable names, and uppercase letters with bars to denote tuples of
variables and constants.
Formally, a query is of the form:
$$ Q(\Vec{X}) \qif R_1(\Vec{Z}_1)\qand \ldots\qand R_n(\Vec{Z}_n)\qand C_Q$$
where: (1)
 $R_1,\ldots, R_n$ are relations in the world view, (2)
 $C_Q$ is a conjunction of {\em order subgoals} of the form
      $u \theta v$, where $\theta \in \{<, >, \leq, \geq\}$ and
      $u, v \in \bigcup_{1 \leq i \leq n} \Vec{Z}_i$, and (3)
 $\Vec{X} \subseteq \bigcup_{1 \leq i \leq n} \Vec{Z}_i$.

 
\section{Describing Information Sources}
\label{sec:descriptions}

Queries are posed to the system in terms of the world view. However, the
data to answer these queries is actually stored in external information
sources. Therefore, to answer a query, we need descriptions that relate
the contents of
each information source to  the classes, attributes and relations
in the world view. Furthermore, since sources may not be able to
answer arbitrary queries about their contents, we need to describe the {\em
capabilities\/} of the information sources in order to create plans
that can actually be executed.


\subsection{Contents of Information Sources}

 There are several desiderata for descriptions of the contents of
information sources. First, since the number of information sources is
large and frequently changing, we should be able to add new
information sources without changing the world view, 
and without affecting the descriptions of other
information sources. Second, since many sources contain closely
related information, the descriptions should be able to model
fine-grained differences between their contents, so that the set of
sources relevant to a query can be determined as ``tightly'' as
possible.

\iffullversion
\item We should be able to develop efficient  algorithms to determine the set of
  sources relevant to a query and to generate query plans that access these
  sources. 
\fi


\iffullversion
Two challenges arise in 
precisely describing contents of sources in terms of the world view:
\begin{enumerate}
\item When adding a new information source, it is often the case that the
  tuples in the source do not correspond directly to tuples in any one
  relation of the world view. For example, suppose our world view includes
  the relation $\rel{Teaches}(\rel{Course}, \rel{Teacher}, \rel{Hour},
  \rel{Room})$, but the online course listing makes available only 
  $(\rel{Course}, \rel{Teacher})$ pairs. We could introduce a new relation
  corresponding to these pairs in the world view, but doing so means
  modifying the world view. Furthermore, that would require having
many relations in the world view and expressing complex dependencies
between them in order to capture the relationship between contents of
different sources. Our solution is to describe 
  the online course listing as containing tuples in the relation
  \Proj{\rel{Course}, \rel{Teacher}}{\rel{Teaches}}.

\item Even when the objects or tuples in an information source may be
  thought of as belonging directly to a relation or class in the world view,
  we may wish to specify certain additional constraints that these objects
  or tuples satisfy. For example, consider the vintage car information source
  from Example~\ref{motivating-eg}. Even though each object in the source
  belongs to class \rS, we would like to specify that all the cars in this
  source were manufactured before 1950; we saw how we could use this additional
  information to prune this source as irrelevant to the query in 
  Example~\ref{motivating-eg}. 
\end{enumerate}
\fi


\iffullversion
 For example, we say that the online course listing source
discussed above contains tuples in the relation 
$\rel{CourseList}(\rel{Course}, \rel{Teacher})$, such that:
\begin{tabbing}
1234\= \kill
$ \rel{CourseList}(\rel{course}, \rel{teacher}) \qsub$ \\
\> $\rel{Teaches}(\rel{course}, \rel{teacher}, \rel{hour}, \rel{room})$
\end{tabbing}
We describe the vintage car source as containing tuples of relation
$\rS(c)$ such that:
$$ \rel{VintageCar}(c) \qsub \rS(c)\qand \rYe(c,y)\qand y \leq
\const{1950}$$
\fi

\begin{figure*}
\begin{center}
\begin{tabular}{|l|} \hline
{\bf Source 1:} {\sf Used cars for sale.}\\
{\bf Contents:} $V_1(c) \qsub \rS(c)\qand \rU(c)$\\
{\bf Capabilities:} $(\Set{\rMo(c), \rCa(c)}$, 
  $\Set{\rMo(c), \rCa(c), \rYe(c), \rPr(c), \rOw(c)},$\\
  $ \Set{\rYe(c), \rPr(c)}, 1,4) $\\ \hline
{\bf Source 2:} {\sf Luxury cars for sale. All cars in this
  database are priced above \$20,000}\\ 
{\bf Contents:} $V_2(c) \qsub \rS(c)\qand \rPr(c,p)\qand 
p \geq \const{20000}$\\
{\bf Capabilities:} $(\Set{ \rCa(c)}$, 
  $\Set{\rMo(c), \rCa(c), \rYe(c), \rPr(c), \rOw(c)},$\\
  $ \Set{ \rPr(c)}, 1,3) $\\ \hline
{\bf Source 3:} {\sf Vintage cars for sale (cars 
  manufactured before 1950).}\\
{\bf Contents:} $V_3(c) \qsub \rS(c)\qand \rYe(c,y)\qand 
y \leq \const{1950}$\\
{\bf Capabilities:} $(\Set{\rMo(c)}$, 
  $\Set{\rMo(c), \rCa(c), \rYe(c), \rPr(c), \rOw(c)},$\\
  $ \Set{ \rYe(c)}, 1,2) $\\ \hline
{\bf Source 4:}  {\sf Motorcycles for sale.}\\ 
{\bf Contents:} $V_4(c) \qsub \rM(c)$\\
{\bf Capabilities:} $( \Set{\rMo(c)}, \Set{\rMo(c), \rYe(c), \rPr(c),
\rOw(c)}, \Set{\rPr(c)}, 1, 2)$ \\ \hline
{\bf Source 5:} {\sf Car reviews database. Contains reviews for
  cars manufactured after 1990.}\\
{\bf Contents:}
$V_5(m, y, r) \qsub \rC(c)\qand \rMo(c,m)\qand
\rYe(c,y)\qand \rRe(m, y, r)$\\
{\bf Capabilities:} $(\Set{m,y}, \Set{m,y,r}, \Set{}, 2, 2 )$\\ \hline
\end{tabular}
\end{center}
\caption{Source descriptions for the sources in Figure~1}
\label{fig:descriptions}
\end{figure*}




We model the contents of an information source as tuples in one or
more relations. The key to the flexibility in our source descriptions
is that we describe relations in the sources  as 
{\em queries} over the world-view relations and the comparison
predicates. 
Formally, each source is modeled as containing tuples of a
relation (or several relations) which we call {\em source
relations}. The names of the source relations are disjoint from the
names of the world view relations.  For each source relation, we
specify a conjunctive query over the world view relations that describes the
conditions the tuples in the
relation must satisfy. Note that the source need not contain {\em all}
the tuples that satisfy the query; for example, no database of cars
for sale contains all cars for sale. We emphasize this incompleteness
by using the connective $\subseteq$ to relate the head and body of the
description instead of the conventional $\leftarrow$ used in
queries. Figure~\ref{fig:descriptions} shows the content descriptions
corresponding to the informal descriptions in
Figure~\ref{fig:info-sources}.

It should be emphasized that the features of our data model (the class
hierarchy, disjointness of classes and built-in predicates) and the
fact that we describe contents as queries enables us to describe very
tightly the contents of the sources, and therefore to be able to prune
the sources relevant to a given query. Furthermore, adding sources
does not affect the descriptions of other information sources. 

\iffullversion In
Section~\ref{sec:algos} we show that we can effectively use the
descriptions to create query plans.  Finally, it should be noted that
we do not claim that our data model {\em integrates\/} the relational
and object oriented data model. It simply provides a mechanism
necessary to {\em describe\/} sources using those data models, so that
we can query them.
\fi

\subsection{Capabilities of Information Sources}
\label{sec:capabilities}
The content description tells us {\em what} is in an information
source, but it does not tell us {\em which queries} the source can
answer about its contents. Many information sources permit only a
subset of the possible queries on their databases.  For example, the
used car database in Example~\ref{motivating-eg} requires either the
category or model of the car as an input.  When generating query plans
it is important to adhere to the capabilities of the information
sources, and exploit them as much as possible.  In
Example~\ref{motivating-eg}, the query plan involving sources 2 and 5
was different from the plan involving sources 1 and 5 because source~1
was able to perform the selection on the year of the car.


\iffullversion
answers the query:
{\sf Given a price range and a category of car, what cars of this
category are available for sale within this price range?} However, the
source will not answer the query: {\sf List all cars in the database.}
Furthermore, when a source contains instances of a class, it may be
able to answer queries only about a subset of the attributes of the
class.
\fi

We describe the capabilities of an information source using {\em
capability records}. Capability records are meant to capture the two
kinds of capabilities encountered most often in practice: the ability
of sources to apply a (perhaps limited) number of selections, and the
limited forms of variable bindings that an information source can
accept. The capability records specify which inputs can be given to
the source, the minimum and maximum number of inputs allowed, the
possible outputs of the source and the selections the source can
apply.  Sources with capabilities to perform arbitrary relational
operators (e.g., full fledged databases) are considered
in~\cite{lru96:capabilities}.

Formally, a capability record specifies which {\em parameters\/} can
be given to the source.  A {\em
  parameter} of a source relation $R(\Vec{X})$ is either a variable $x \in
\Vec{X}$ or $A(x)$ where $A$ is an attribute name and $x \in
\Vec{X}$. With every source relation we associate exactly one
capability record of the form 
$(S_{in},  S_{out},S_{sel},min, max)$, where $S_{in}$, $S_{out}$ and
$S_{sel}$ are sets of parameters of $R$, and $min$ and $max$ are
integers. 
Every variable in $\Vec{X}$  must appear in a parameter either $S_{in}$
or $S_{out}$. 

The
meaning of the capability description is the following. In order to
obtain a tuple of $R$ from the information source, the information
source  must be given  bindings for at least $min$  elements of $S_{in}$.
\iffullversion
 If we provide the values $a_1,\ldots,a_n$ for
the elements $\alpha_1,\ldots,\alpha_n$ in $S_{in}$, we will obtain
all the tuples in the information source that satisfy $\alpha_1=a_1 \qand
\ldots \qand \alpha_n=a_n$. 
\fi
The elements in $S_{out}$ are the parameters that can be 
{\em returned\/} from the information source. The elements of $S_{sel}$, which
must be a subset of $S_{in} \cup S_{out}$, are
parameters on which the source can apply selections of the form
$\alpha \, op \, c$, where $c$ is a constant and $op \in \{\leq, <, \not =,
=\}$. Given a source relation $R$, 
 providing the information source with the values 
$a_1,\ldots,a_n$ for the elements $\alpha_1,\ldots,\alpha_n$ in
$S_{in}$,  asking for the values of $\beta_1,\ldots,\beta_l$ in
$S_{out}$, and passing the selections
$\gamma_1,\ldots,\gamma_k$ to the source 
 will produce the tuples $(Y_1,\ldots,Y_l)$ that satisfy the
following conjunction:
\begin{tabbing}
ffffff\= \kill
$R'(Y_1,\ldots, Y_l)  :- R(X_1,\ldots,X_m)\qand \alpha_1=a_1\qand
\ldots\qand$ \\
\> $ \alpha_n=a_n\qand \beta_1=Y_1 \qand \ldots\qand \beta_l=Y_l\qand 
\gamma_1\qand \ldots\qand \gamma_k.$
\end{tabbing}

Given a content description of the form $R \subseteq Q_R$ and
input/output specifications as described above, the following is
called the {\em augmented description\/} of $R$ w.r.t.\ the
input/output specifications:
\begin{eqnarray*}
R'(Y_1,\ldots, Y_l) & \subseteq &
Q_R \qand \alpha_1=a_1 \qand \ldots \qand
\alpha_n=a_n \qand\\
& & \beta_1=Y_1 \qand \ldots \qand \beta_l=Y_l
\qand \gamma_1  \qand \ldots \qand \gamma_k
\end{eqnarray*}
In our query-planning algorithm we use a specific {\em canonical\/}
augmented description of
$R$ in which the inputs include all of $S_{in}$, the outputs include
all of $S_{out}$ and there are no selections (note that this does not
mean that our query plans necessarily provide all the inputs and
extract all the outputs from a source).
 Figure~\ref{fig:descriptions} lists the capability
records describing the information sources in our example.

\eat{Finally, the set $S_{sel}$ denotes on which parameters of $R$
 the information source can perform
selections.\footnote{In the implementation we also specify which kinds
of selections can be performed on each argument.}  The number of
inputs given to the source from $S_{in} \cup S_{sel}$ cannot exceed
$max$.  We assume conjunctive selections that use the interpreted
order relations ($\{\leq, <, \not =, =\}$).  Note that the elements of
$S_{in}$ can be viewed also arguments on which the source can perform
equality selections.}

\iffullversion
\begin{example}
The vintage-car information source can handle any query on
relation ${\em VintageCar}(c)$ that bind at least
one of {\em model} and {\em category} and can also handle range selections
on {\em year} and {\em price}. It can return the model, year, price, category
and seller contact information of the car. We can describe it using the capability
record:
\begin{tabbing}
jjj\= \kill
$\langle  \Set{\rMo(c), \rCa(c)}, \Set{\rMo(c), \rYe(c),$\\
\> $\rPr(c), \rCa(c), \rOw(c)},
  \Set{\rYe(c), \rPr(c)}, 1, 4 \rangle$
\end{tabbing}
 Figure~\ref{fig:descriptions} lists the capability
records describing the information sources in our example.
\end{example}
\fi

\eat{An information source can in general answer
an infinite number of queries. In many practical cases, we can describe this
infinite set using a finite set of {\em query templates} as
in.}

\eat{
\begin{example}\label{template}
The query template:
$$ Q^{bbf}(m,y,p) \qif {\em VintageCar}(c)\qand \rMo(c,m)\qand
\rPr(c,P)\qand \rYe(c,y')\qand y' \geq y$$
describes queries that give as input a model $m$
and a year $y$ and produce as output the prices of vintage cars of model $m$
manufactured after year $y$. The superscript $bbf$ of $Q$ is called a
{\em binding pattern}. A $b$ in the $i$th position of the binding pattern
declares the $i$th argument of $Q$ a {\em bound argument} and an $f$
declares it a {\em free argument}. A query corresponding to a template
accepts the bound arguments of the template as inputs and produces the free
arguments as outputs. In this example, $m$ and $y$ are bound arguments and
$p$ is a free argument of $Q$.
\end{example}

We now define query templates formally.  Let $R(\Vec{X})$ be a relation in
the contents of some information source, and let \Vec{Y} and \Vec{Z} be
finite disjoint sets of variables. For our purposes, a query template over
the relation $R$ is an expression:
$$ Q^\alpha(\Vec{Y}) \qif R(\Vec{X})\qand B(\Vec{X}, \Vec{Y}, \Vec{Z}) $$
where $\alpha$ is a binding pattern
({\em adornment} in~\cite{Ullman})
which declares each $y \in \Vec{Y}$ to be either an input or an output
to the query, and
$B$ is a conjunction of literals of one of the following forms:
\begin{enumerate}
\item $A(x,w)$, where $x \in \Vec{X}$. $w \in \Vec{Y} \cup \Vec{Z}$, and
  $A$ is an attribute name.
\item $u \theta v$ where $u, v \in \Vec{X}\cup \Vec{Y}\cup \Vec{Z}$ and
  $\theta \in \{<, >, \leq, \geq\}$.
\end{enumerate}

We could describe the query capabilities of a source by listing all the
query templates associated with it. Unfortunately, there could be a very
large number of query templates for a given relation in the contents of a
source. For example, if the {\em VintageCar} source can answer all queries
where a value is specified for at least one of {\em model}, {\em year}, or
{\em price}, we would have 8 query templates for this relation. The
number of query templates is in general exponential in the arity of the
underlying relation and the number of attributes in the world view. As a
compromise, we have adopted the following approach in the \IM. A {\em
  parameter} of a content relation $R(\Vec{X})$ is either a variable $x \in
\Vec{X}$ or $A(x)$ where $A$ is an attribute name and $x \in
\Vec{X}$.
We associate
with $R(\Vec{X})$  exactly one {\em capability record} of the form
$\langle P, P^b, {\em min}_b, P^s \rangle$, where
 $P$, $P^b$ and $P^s$ are sets of parameters. The source can answer any
 query of the form
$$ Q^\alpha(\Vec{Y}) \qif R(\Vec{X})\qand B(\Vec{X}, \Vec{Y}, \Vec{Z}) $$
such that, in addition to the conditions we imposed earlier:
\begin{enumerate}
\item For each subgoal $A(x,y)$ in $B$, $A(x) \in P$.
\item For each pair of subgoals $A(x,y)$ and $y \theta y'$ in $B$,
$A(x) \in P^s$ and $y' \in \Vec{Y}$ is a bound argument of $Q$.
\item No attribute name occurs more than once in $B$.
\item A {\em bound parameter} of $Q$ is either a bound argument 
$x \in \Vec{Y} \cap P^b$ or a bound argument $y \in \Vec{Y}$ such that
$A(x) \in P^b$ and $A(x,y) \in B$ for some attribute name $A$. The number of
bound parameters of $Q$ should be at least ${\em min}_b$.
\end{enumerate}


Using capability records to describe query templates represents a tradeoff.
On one hand, we cannot describe all possible sets of query templates using
capability records. On the other, we get a compact representation of the
kinds of query capabilities we actually encounter in practice, since each
capability record describes a number of query templates that is exponential
in the size of the record.  In particular, it is very easy and natural to
describe {\em forms} on the WWW using capability records.  In addition,
given a query template, it is easy to determine in polynomial time (in the
sizes of the record and the template) whether the template ``matches'' the
record, that is, whether the template is one of the templates described by
the record (we omit the details in this paper due to lack of space).  In a
later section, we show that this feature reduces significantly the
complexity of our algorithms.}

\subsection{Query Plans}
\label{sec:query-plans}

  A query plan is a sequence of accesses to information sources
interspersed with local processing operations. A query plan must
combine information from various sources in a way that guarantees
semantically correct answers, and must adhere to the capabilities of
the information sources. We explain these notions below.
Given a query $Q$ of the form
$$ Q(\Vec{X}) \qif R_1(\Vec{Z}_1)\qand \ldots\qand R_n(\Vec{Z}_n)\qand C_Q$$
a plan to answer it consists of a set of {\em conjunctive
plans}. Conjunctive plans are like conjunctive queries except that we
also specify the inputs and outputs to every subgoal. An {\em executable}
conjunctive plan is of the form:
\begin{tabbing}
$P: Q(\Vec{X}) \qif$\= $V_1(\Vec{U}_1)$ foobar\= \kill
$P: Q(\Vec{X}) \qif V_1(\Vec{U}_1)$   $(in_1, out_1, sel_1)$ $\qand
\ldots \qand $ \\ 
\> $V_m(\Vec{U}_m)$  $(in_m, out_m, sel_m)$ $\qand$ $C_P.$
\end{tabbing}


Each of the $V_i$'s is a source relation corresponding toan
information source. The elements of the sets $in_i$ are of the form
$p_1:p_2$, where $p_1$ is one of the parameters in the set $S_{in}$ of
the information source of $V_i$, and $p_2$ is either a value appearing
in the query, or a parameter that appears in $out_1 \cup \ldots \cup
out_{i-1}$. The set $out_i$ is a subset of $S_{out}$ in the capability
record of the information source $V_i$, and $sel_i$ is a set of
selections to be passed to the information source. Finally, the
cardinalities of $in_i, out_i$ and $sel_i$ must be consistent with the
capability record of the information source of $V_i$. $C_P$ is a set
of selections that are applied locally by the query executor.

\iffullversion
and $out_i$
are parameters on $\Vec{U}_i$, and $sel_i$ is set of selections applied
to the parameters of $\Vec{U}_i$.  An element of $in_i$ is of the form
$p_1:p_2$, where $p_1$ is one of the parameters that can be passed to
the information source, and
$C_P$ is a set of selections that are applied locally by the 
query executor. A plan $P$ is {\em executable\/} if the capabilities of the sources
are satisfied, i.e., for every $i$, $1 \leq i \leq m$,
$(in_i,out_i,sel_i)$ is  consistent with the capability record
of  the source $V_i$, and 
\begin{itemize}
\item $in_i \subseteq Q_{in} \cup out_1 \cup \ldots \cup out_{i-1}$,  where
$Q_{in}$ is the set of parameters available explicitly in the query.
\end{itemize}
\fi
\eat{
\item if a variable $X$ appears in more than one of the $\Vec{U}_i$'s
or in $\Vec{X}$, then it is functionally determined 
\item $Q_{out} \subseteq Q_{in} \cup {\sf v}^1_{out} \cup \ldots \cup
{\sf v}^n_{out}$, and 


\item If a variable $X$ appears in two subgoals ${\sf v}_i$ and ${\sf v}_j$ then
the two occurrences are {\em connected}. The connection relation is
the transitive closure of the {\em directly-connected\/} relation,
defined as follows.  An occurrence of $X$ in ${\sf v}_i$ and
in ${\sf v}_j$ are said to be  directly connected if ${\sf v}^i_{in} \cup
{\sf v}^i_{out}$ contains a key on $X$ that is also in ${\sf v}^j_{in} \cup
{\sf v}^j_{out}$. 
}


To define the semantic correctness of a conjunctive plan, we consider
the canonical augmented content descriptions of the information
sources. Recall that given the input and output specifications, each
information source is modeled as containing a subset of the relation
defined by a conjunctive query $Q_i$. Therefore, we can consider the
{\em expansion\/} of the plan $P$ as the query $P'$ obtained by
expanding the definitions of the subgoals $V_i$. Formally $P'$ is
obtained by replacing the subgoal $V_i(\Vec{U}_i)$ by the body of the
query $Q_i$ after unifying the head variables of $Q_i$ with
$\Vec{U}_i$. The conjunctive plan $P$ is said to be {\em semantically
correct\/} if $P'$ is contained in $Q$, i.e., for any extension of the
world view relations that satisfies the integrity constraints, the
answer to $P'$ would be a subset of $Q$.

\begin{example}
\label{exam:containment}
Consider our query asking for sports cars manufactured in~1992 or
later:
\begin{eqnarray*}
q(m, p, r) & \qif
 & \rS(c)\qand \rCa(c, \const{sportscar})\qand\\ 
& & \rYe(c, y)\qand y \geq \const{1992}\qand  \rPr(c,p)\qand\\
           &      &\rMo(c,m)\qand \rRe(m, y, r)
\end{eqnarray*}
 The following is a semantically correct plan for  the query:
\begin{tabbing}
$P_1: \; Q(m,p,r) \, \qif$ \\
{\bf $V_1(c)$} \= $(\{ Category(c): {\sf
sportscar}\},\{ Price(c), Model(c)\},$ \\
\> $ \{Year(c) \geq 1992 \}) \qand$ \\
{\bf $V_5(m,y,r)$}  $(\{m:Model(c),y:Year(c)\}, \{r\}, \{\}).$
\end{tabbing}
To see why, we can verify that  the expansion query $P'_1$ of $P_1$ obtained by
unfolding the augmented descriptions  of $V_1$ and $V_5$ is contained
in the original query:
\begin{tabbing}
fff \= \kill
$ P'_1: \; Q(m,p,r) \qif  \rS(c)\qand \rU(c)\qand $ \\
\>$ \rMo(c,m)\qand \rCa(c,t)\qand t={\sf sportscar}\qand \rYe(c,y)\qand$\\
\>$ \rPr(c,p)\qand \rRe(m,y,r) \qand y \geq 1992. $
\end{tabbing}
\end{example}
\iffullversion
The query $P'_1$ is contained in $Q$. To see why, suppose
 $t$ is a tuple generated by $P'_1$; then $t$ satisfies all the
conjuncts in the body of $P'_1$. 
The body of $P'_1$ contains all the conjuncts in the body of the query $Q$ (it
also contains additional conjuncts), and so $t$ must also satisfy the query
$Q$.
\fi



\eat{
  The query plan $P$ in Example~\ref{query-plan} is a valid plan for the
  query $Q$ in Example~\ref{query}. It is easy to see that it uses the
  binding patterns on the templates $S_1$ and $S_2$ appropriately. We need to
  verify that every tuple produced by $P$ satisfies the query $Q$.
  Example~\ref{query-plan} presents an informal argument why this is so.  To
  verify the condition formally, we {\em expand} $P$ to obtain the query
  $E$ as follows: replace the query templates $S_1$ and $S_2$ in $P$ by
  their definitions in Example~\ref{query-plan}; in the resulting expression,
  replace the views $V_1$ and $V_5$ in the resulting query by their 
  definitions in Figure~\ref{fig:descriptions}. }

\eat{
asking queries of information
sources and combining their answers. The query we ask an information source
may depend on answers to previously asked queries. In this paper, we
restrict our attention to {\em conjunctive plans} (just as we restrict
ourselves to conjunctive queries), which are conjunctive queries over 
the source query templates. 
A query plan $P$ is an expression of the
form:
$$ P: \;\; Q(\Vec{X}) \qif Q_1^{\alpha_1}(\Vec{Y}_1)\qand \ldots\qand
Q_m^{\alpha_m}(\Vec{Y}_m)\qand C_P$$
where each $Q_i^{\alpha_i}(\Vec{Y_i})$ is a query template associated with
information source $S_i$.

\eat{ $\Vec{X} \subseteq \bigcup_{1 \leq i \leq
  m}\Vec{Y}_i$, and $C$ is a conjunction of order subgoals of the form
$u \theta v$ where $\theta \in \Set{<, >, \leq, \geq}$.\footnote{We also
  require that $u$ and $v$ occur in $\bigcup_{1 \leq i \leq
  m}\Vec{Y_i}$.}
}

Informally, the above plan is executed from left to right in $m$ stages.  At
stage $i$, we ask information source $S_i$ the query
$Q_i^{\alpha_i}(\Vec{Y_i})$.  The formal execution semantics of query plans
is defined in terms of {\em sideways information passing} (SIPS) (e.g.,
\cite{Ullman}, Chapter 13).  We illustrate the semantics of query plans by
an example.

\begin{example}\label{query-plan}
Consider the query plan $P$:
\begin{eqnarray*}
P: \; Q(m,p,r) & \qif & S_1^{bfff}({\sf sportscar},m,y,p)\qand 
S_2^{bbf}(m,y,r)
\end{eqnarray*}
where $S_1^{bfff}$ and $S_2^{bbf}$ are query templates defined as follows:
\begin{eqnarray*}
S_1^{bfff}(t,m,y,p) & \qif & V_1(c)\qand \rCa(c,t)\qand \rMo(c,m)\qand
\rYe(c,y)\qand y \geq 1992 \qand \rPr(c,p)\\
S_2^{bbf}(m,y,r) & \qif & V_5(m,y,r)
\end{eqnarray*}
It is easy to verify that
$S_1^{bfff}$ is a query template for Source 1, since it matches the
capability record for Source 1 in Figure~\ref{fig:descriptions}. 
Similarly $S_5^{bbf}$ is a query template for Source 5. 

The query plan $P$ is executed as follows. First we ask Source 1 the query
that retrieves the \rMo, \rYe, and \rPr\ of cars in the relation
$V_1$ (the set of cars Source 1 knows about)
whose \rCa\ is {\sf sportscar} as a set of $\tup{m,y,p}$ tuples.
For each tuple in this set, we ask Source 5 the query that retrieves the 
\rRe\ $r$ for the car with model $m$ manufactured in year $y$ (that is, the
review $r$ such that $V_5(m,y,r)$ holds). The result of the plan is a 
set of $\tup{m,p,r}$ tuples. The year of manufacture is not needed in the
final result and is projected out.
\end{example}


Not all query plans will result in a meaningful execution as in
Example~\ref{query-plan}. A query plan $P$ for a query $Q$ is {\em valid}
if it satisfies the following conditions:
\begin{enumerate}
\item The binding patterns must be appropriate. That is, if the $i$th
  subgoal is $Q_i^{\alpha_i}(\Vec{Y}_i)$, and the binding pattern
  $\alpha_i$ requires the $j$th position in $\Vec{Y}_i$ to be bound, then 
  the argument in that position must occur in at least one of the
  first $i-1$ subgoals.\footnote{The issue of implied equalities is not
    mentioned anywhere. It should be mentioned at the appropriate places.}
\item Every tuple produced by executing $P$ must be an answer to query $Q$.
\end{enumerate}


As we saw in the foregoing example, it is easy to check condition 1
syntactically.  Checking condition 2 requires more work.  The {\em
  expansion} of $P$ is the query $E$ obtained by replacing each query
template in the body of $P$ by the definition of the template in terms of
world view relations. Condition 2 is satisfied if and only if for every
database instance over the world view, the answer derived by the expansion
of $P$ is contained in the answer to query $Q$, written as $E \subseteq Q$.

We call a plan $P$ a {\em logical query plan} if $E \subseteq Q$. Not every
logical query plan $P$ is a valid query plan, because condition 1 may not
hold for $P$, that is, the binding patterns may not be appropriate. However,
it may be possible to reorder the subgoals of $P$ to make it valid. We call
such an ordering of subgoals an {\em executable ordering} for the logical
plan $P$.

It is well-known that testing containment of conjunctive
queries without order predicates is an NP-complete problem.
With the order predicates, the problem is complete for 
$\Pi^p_2$. Hence testing containment takes time exponential in the length
of the queries when there are no order predicates, and doubly exponential
time when order predicates are present. In practice, however, queries and
query plans tend to be small, and the exponential algorithms still remain
feasible. 
}
%\subsection{Answers to a query}

Semantically correct plans  required only that
$P'$ be {\em contained\/} in $Q$ and not {\em equivalent\/} to
$Q$ for the following reasons. First, even if $P'$ were
equivalent to $Q$, the answer obtained by executing 
 $P$ may not be complete because the sources may be
incomplete. Second,  conjunctive plans that produce only a subset of
the answer are also useful. For example, if we are searching for sports
cars manufactured after 1992, and we have an information source with
cars manufactured after 1994, we would still want to query it. 
We  define the set of answers to the query
$Q$ as all the tuples that can be obtained by some {\em executable\/} and
{\em semantically correct\/} conjunctive plan for $Q$. 

\eat{
reason for this is tw
We did not require that a valid plan be {\em equivalent} to the original
query, only that it be contained in the query.  The motivation for this
relaxation is that information sources are incomplete, and therefore no one
plan plan may yield all the answers. We must therefore rethink the
definition of the {\em answer} to a query. In a conventional database, the
same set of tuples is obtained by every query plan that is equivalent to a
query $Q$, and we can define the answer to $Q$ as the set of tuples obtained
by any query plan that is equivalent to $Q$. However, when sources are
incomplete, each plan may produce a different set of tuples.  We define the
{\em answer} to a query $Q$ as the set 
$\Set{t\:|\:t \; \mbox{\rm can be obtained by some valid query plan}}$.
}
\eat{
The fundamental question we ask is the following: Given a world view and
descriptions of several information sources, and a query $Q$ over the world
view relation, we wish to find the answer to query $Q$.
In principle, we have to generate every valid plan for $Q$ in order to
obtain the complete answer to $Q$. However, it is most often the case that
in our environment, users are interested in only the first few answers to a
query, rather than all possible answers. Therefore it is often necessary
only to generate a small number of valid plans.
(Need to justify here that most of the time we are happy to have a partial
answer. Also put in a forward reference to the algorithms section.)}

\noindent
{\bf Interface Programs:} Describing source query capabilities in
terms of capability records provides a clean separation between query
planning and the actual details of interacting with each information
source. These details are encoded in {\em interface
programs}. Logically, there is one interface program that accepts any
query template available at the source and returns the appropriate
answer. The interface program accepts the bound parameters to a query
corresponding to the template, interacts with the information source,
and produces a relation corresponding to the free parameters in the
query template.

%In the implementation, usually all the
%interface programs for a given information source are combined into one
%module. 
\iffullversion
Interface programs also handle details such as contacting replicas
if an information source is unavailable. Some of the details are given in
Section~\ref{sec:implementation}. \fi

\section{Algorithms for Answering Queries}
\label{sec:algos}

Our algorithm for generating executable query plans has two steps. In
the first we generate semantically correct conjunctive plans, and in
the second we try to order the conjuncts of the plan to ensure that
they are executable.  The first step of the algorithm is described in
detail in a companion paper~\cite{lro96}. Here we only describe the
aspects of this step that are needed to understand the second step and
the experimental results.

\iffullversion
In this section, we present the algorithm used in the \IM\ to generate
semantically correct and executable
query plans for a given query $Q$. Our algorithm proceeds in two stages. In
the first stage, we generate conjunctive plans that are semantically
correct.
In the second stage
\fi

\eat{ of the  planslogical query plan $P$. In the second stage,
we try to find an executable ordering that makes $P$ a valid query plan for
$Q$. We then repeat the process, either until we can generate no more
logical query plans or until we have generated a sufficient number of valid
plans.
Section~\ref{sec:logical-plans} describes logical plan generation and
Section~\ref{sec:valid-plans} describes how we find an executable ordering. }

%\subsection{Generating Semantically Correct Query Plans}
%\label{sec:logical-plans}

A semantically correct plan guarantees that the answers produced will
actually be answers to the query.  Finding a semantically correct
query plan amounts to finding a conjunctive query $Q'$ that uses only
the source relations and is {\em contained\/} in the given query
$Q$. Therefore, our problem is closely related to the problem of
answering queries using
views~\cite{lmss95,rsu95,Larson87,Chaudhuri-views}, where the source
relations play the role of the views.  However, the problem of
answering queries using views is known to be NP-complete
in~\cite{lmss95}, even for conjunctive queries without built-in atoms.
\iffullversion The algorithm suggested there is not very practical
since it requires guessing a rewriting $Q'$, and then checking whether
it is a semantically correct solution. 
 \fi 
The main source of
complexity is the fact that there are an exponential number of
candidate rewritings that need to be considered.  This is especially
significant in our context because that algorithm would be exponential
in the number of information sources.  Our algorithm drastically
reduces the number of candidate rewritings considered by proceeding as
follows.  First, the algorithm computes a {\em bucket\/} for each
subgoal in the query, each containing the information sources from
which tuples of that subgoal can be obtained. In the second step, we
consider all the possible combinations of information sources, one
from each bucket, and check whether it is a semantically correct plan,
or can be made semantically correct if additional built-in atoms are
added to the plan. As we see in Section~\ref{sec:implementation}, the
first step, considerably reduces the number of possibilities
considered in the second step. The details of the first step are given
in Figure~\ref{algo:buckets}.


\iffullversion In our discussion about semantically correct plans we ignore
the input/output specifications of each subgoal in the plan (which
will be computed in Section~\ref{sec:valid-plans}). Thus,
in our discussion plans can be viewed as conjunctive
queries.\footnote{We use the canonical augmented description of each
source for testing correctness.}

The problem of answering queries using views is the following. Given a
query $Q$ using the relations $E_1,\ldots,E_m$, and a set
of view definitions $V_1,\ldots,V_n$, over the same
relations, find a query $Q'$ that uses $V_1,\ldots,V_n$, 
such that $Q$ is equivalent to $Q'$. 
There are two  differences between our
problem and previous treatments of the view rewriting problem. First,
we require the rewriting only to contained in the query (but be a
satisfiable query!), and not necessarily
equivalent to the query. Second,  we want to find {\em all\/} the
rewritings of the query using the source relations, two equivalent
plans (that use different information sources) will not necessarily
produce the same set of answers.
\fi

\eat{
previous the problem
As the formulation of our problem shows, the problem
A query $Q$ is posed to the \IM\ using the relations in the
world-view. The contents of the information sources are described as
queries over the world-view relations. Finding a logical solution, i.e.,
a combination of information sources that produce answers to the
query, means finding a query $Q'$ that uses only the views in the
content descriptions (and interpreted relations), such that every
answer to $Q'$ is an answer to $Q$.  Described in this way, the
problem of finding a logical solution is closely related to the
problem of answering queries using
views~\cite{lmss95,rsu95,Larson87,Chaudhuri-views,qian95}.}



\begin{figure*}[bht]
\begin{center}
\fbox{
\begin{minipage}{5.5in}
\begin{tabbing}
{\bf Algorithm CreateBuckets}(${\cal V}$,$Q$) \\
{\bf Inputs:}
${\cal V}$ is a set of content descriptions, and $Q$ is a
conjunctive query of the form\\
$Q: Q(\bar X) \qif R_1(\bar X_1)\qand \ldots\qand R_m(\bar X_m)\qand C_Q.$ \\
\\
123\=123\=123\=123\=123\=123\= \kill
Set ${\em Bucket}_i$ to $\emptyset$ for $1 \leq i \leq m$.\\
For $i = 1, \ldots, m$ do:\\
\>For each  $V \in {\cal V}$\\
\>\> Let $V$ be  of the form: $V(\vec{Y}) \subseteq  S_1(\bar
Y_1)\qand \ldots\qand S_n(\bar Y_n)\qand C_V$\\ 
\>\> For $j = 1, \ldots, n$ do\\
\>\>\> If $R_i = S_j$ or $R_i$ and $S_j$ are nondisjoint classes\\ 
\>\>\>\> Let $\psi$ be the mapping defined on the
variables of $V$ as follows: \\
\>\>\>\> If $y$ is the $k$'th variable in $\bar Y_j$ and $y \in \bar Y$\\
\>\>\>\>\> then $\psi(y)=x_k$, where $x_k$ is the $k$'th
variable in $\bar X_i$. \\
\>\>\>\>\> else $\psi(y)$ is a new variable that does not
appear in $Q$ or $V$. \\
\>\>\>\> Let $Q'$ be the $0$-ary query:\\
\>\>\>\> $Q' \qif R_1(\bar X_1)\qand \ldots\qand R_m(\bar X_m)\qand C_Q\qand
           S_1(\psi(\bar Y_1))\qand \ldots\qand S_n(\psi(\bar Y_n))\qand 
           \psi(C_V)$\\
\>\>\>\> If ${\em Satisfiable}(Q')$ then add $\psi(V)$ to ${\em Bucket}_i$.\\
{\bf End.}
\end{tabbing}
\end{minipage}
}  
\end{center}
\caption{Algorithm to create the relevant buckets for each query subgoal.
The procedure ${\em Satisfiable}(Q')$ tests whether a query $Q'$ is
satisfiable. It tests that the conjunction of built-in atoms is
satisfiable, and that there are no two subgoals $C(x)$ and $D(x)$ where
$C$ and $D$ are disjoint classes. We assume that the source descriptions are
given to the algorithm in their canonical augmented form.}
%(Section~\protect~\ref{sec:capabilities}).}  
\label{algo:buckets}
\end{figure*}


\begin{example}
We illustrate the algorithm on our example.
Consider our query asking for sports cars manufactured no sooner
than~1992:
\begin{tabbing}
fff\=\kill
$q(m_1, p_1, r_1)\qif \rS(c_1)\qand \rCa(c_1, \const{sportscar})\qand$\\ 
\>$ \rYe(c_1, y_1)\qand y \geq \const{1992}\qand \rPr(c_1,p_1)\qand$\\
\>$ \rMo(c_1,m_1)\qand \rRe(m_1, y_1, r_1).$
\end{tabbing}
 and consider what happens when algorithm {\bf
CreateBuckets\/}  looks at Source~1 and the first subgoal of our query
$\rS(c_1)$. The canonical augmentation of the content description of
Source~1 is:
{\small
\begin{tabbing}
%$V'_1(m,t,y,p,s) \subseteq$\=\kill
34\= \kill
$V'_1(m,t,y,p,s) \subseteq \rS(c)\qand \rU(c)\qand \rPr(c,p)\qand$\\
\>  $\rCa(c,t)\qand\rYe(c,y)\qand \rMo(c,m)\qand \rOw(c,s)$
\end{tabbing}}
\noindent
therefore, the algorithm will find the mapping $c \rightarrow c_1$ and
check whether the following  is satisfiable:\footnote{Note
that some variables (e.g., $y_1$ and $y$) get equated because of the
single-valued attributes.}
\begin{tabbing}
$ \rS(c_1)\qand \rCa(c_1, \const{sportscar})\qand$\\
$\rYe(c_1, y_1)\qand y_1 \geq \const{1992}\qand \rPr(c_1,p_1)\qand $\\
$\rMo(c_1,m_1)\qand \rRe(m_1, y_1, r_1) \qand $ \\
$\rU(c_1)\qand \rOw(c_1,s)$
\end{tabbing}
Since the classes $\rS$ and $\rU$ are not disjoint, the conjunction is
satisfiable and Source~1 is added to $bucket_1$. In a similar fashion,
Source~2 is added to $bucket_2$. Source~3 does not get added because
$(y \leq 1950 \qand y \geq 1992)$ is not satisfiable, and Source~4 does
not get added because $\rS$ and $Motorcycle$ are disjoint classes.
Source~5 is the only source in the bucket of the subgoal
$\rRe(m_1,y_1,r_1)$. 

The algorithm will now check the cartesian product of the buckets. For
example, as shown in  Example~\ref{exam:containment}, the plan resulting from
combining sources~1 and~5 is contained in the original query, and is
therefore a semantically correct plan. 
\iffullversion Note that as a first step in
the containment check we propagate the functional dependencies enforced
by the single-valued attributes, and then we remove multiple
occurrences of identical conjuncts. \fi
\end{example}

\iffullversion
\noindent
In the second step of the algorithm we consider every conjunctive
query $Q'$ of the form
\begin{eqnarray*}
Q': q'(\bar X) & :- & V_1(\bar Y_1) \qand \ldots \qand V_n(\bar
Y_n) \qand C_q
\end{eqnarray*}
where $V_i$ is the head of a description in the bucket of the $i$th subgoal of $Q$.
Any minimal subset of $Q'$ that is either
\begin{itemize}
\item contained in
$Q$, or
\item can be made to be contained in $Q$ by adding  subgoals of 
built-in predicates
\end{itemize}
is added to the list of semantically correct solutions.
To test containment, we can use an extension of 
 a containment algorithm for conjunctive
queries with built-in predicates~\cite{LS93} that considers the the
functional dependencies (as in~\cite{Chandra77}) and the inclusion
dependencies.  Although containment is known to
be intractable in general, its intractability is in the size of the
query (which tends to be small), and only occurs when queries have
multiple occurrences of the same relations. Consequently, the
complexity of containment is not a problem in practice.

\begin{example}
As shown in Example~\ref{exam:containment} the query resulting from
combining sources~1 and~5 is contained in the original query, and is
therefore a semantically correct plan. Note that as a first step in
the containment check we propagate the functional dependencies enforced
by the single-valued attributes, and then we remove multiple
occurrences of identical conjuncts.
\end{example}

Our algorithm considers rewritings that have at most one source from
each bucket. Consequently, we consider only rewritings that have at
most the number of subgoals in the query (not counting the built-in
subgoals). The result of~\cite{lmss95} implies that when functional
dependencies are not present and built-in predicates do not appear in
the content descriptions, it suffices to consider only rewritings of
this length. This means that although they may be longer rewritings
that produce semantically correct conjunctive plans, any answer that
would be obtained from a longer rewriting would also be produced by a
rewriting whose length is bounded by the size of the query. However,
as shown in~\cite{lmss95,rsu95}, in theory, the bound on the size of
the rewriting does not hold when either functional dependencies,
built-in subgoals or binding patterns occur. In such cases, we would
need to take more than one source from each bucket in order to
guarantee that we find all solutions. It should be noticed that in
practice we have not found that we missed solutions because of
bounding the length of rewritings we consider.
\fi


\eat{
To test whether this query is contained in $Q$, we expand it with the
definitions of the views, to obtain the following equivalent form, on
which we check containment. Recall that we are using the abbreviated
notation for attribute values, i.e., ${\sf model}(Car)$ will actually
be replaced by a variable $Y$, and the subgoal ${\sf model}(Car,Y)$
would be in the query for the containment check.\footnote{Note that
for clarity, 
in {\sf q''\/} we have omitted some of the subgoals that were added to ${\sf
v}_1$ during the view augmentation, since they are not needed for the
containment test.}


consider  all possible combinations of information sources for each
subgoal in the query, and check for each one whether it is a
semantically correct solution. The first step of the algorithm 
Formally, suppose our query $Q$ is
\begin{eqnarray*}
Q: {\sf q}(\bar X) & :- & {\sf g}_1(\bar X_1) \, \& \, \ldots \, \& \, {\sf
g}_m(\bar X_m) \, \& \, C_q.
\end{eqnarray*}
}

\eat{
The problem we need to solve here is different in two ways. First, we
do not require that $Q'$ be equivalent to $Q$, but only that it is
{\em contained\/} in $Q$, i.e., that for any instantiation of the
relations ${\sf e}_1,\ldots,{\sf e}_m$, the answers produced by the
logical solution $Q'$
are a {\em subset\/} of those produced for $Q$. To see why, consider
an example in which we are looking for Japanese cars, and have access
to a database of Toyotas for sale. The second difference is that since
information sources usually provide only a subset of the views by
which they are described, we need all possible $Q'$ that can generate
answers for $Q$. For example, if we are looking for used cars, and we
have two information sources that say that they give Japanese cars, we
need to consider {\em both\/} of them, since neither of them contains
{\em all\/} Japanese cars. 

The basic idea behind our approach is to generate candidate logical plans
and test whether each candidate plan is a logical plan. We saw in
Section~\ref{sec:query-plans} that this test requires a query containment
check that takes time exponential in the size of the query $Q$ and the plan
$P$. In order to achieve reasonable running times, therefore, it is
essential to test as few candidate plans as possible.


We can reduce the space of candidate query plans considerably by removing
from consideration plans that are {\em irrelevant} to the
query at hand. Formally,
a query plan $P$ is {\em relevant} to a query $Q$ if the following
conditions hold:
\begin{enumerate}
\item $P$ is a logical query plan for $Q$.
\item $P$ is minimal with respect to condition (2). That is, we cannot
  remove a subgoal from $P$ and still have a logical query plan.
\item $P$ is satisfiable, that is, there is some instance of the content
  relations satisfying the constraints in the world view, such that 
  the answer to $P$ is not empty.
\end{enumerate}
Note that we do not require $P$ to be a  query plan for $Q$ in the
definition. (Need to justify the definition. Or maybe I got it wrong?)

We now present an algorithm that generates relevant query plans. 
The algorithm assumes that the information source descriptions have been
preprocessed to construct the {\em canonical view definition} corresponding
to each content relation. Suppose $R(\Vec{X})$ is a content relation with
the capability record $\langle P, P^b, {\em min}_b, P^s\rangle$. The
canonical view definition corresponding to $R$ is:
$$ V_R(\Vec{Y}) \qif E_R\qand B_R $$
where:
\begin{enumerate}
\item $E_R$ is the expansion of $R(\Vec{X})$ in terms of world view
relations.
\item For each parameter of the form $A(x) \in P$, there is a new variable
  $w$ such that $w \in \Vec{Y}$ and $A(x,w)$ is in $B_R$.
\item For each parameter of the form $x \in P$, $x \in \Vec{Y}$.
\end{enumerate}
}
\eat{
\begin{example}
The canonical view definition corresponding to the content relation $V_1$ 
in Figure~\ref{fig:descriptions} is:
$$U_1(m,t,y,p,s) \qif \rS(c)\qand \rU(c)\qand \rMo(c,m)\qand \rCa(c,t)\qand
\rYe(c,y)\qand \rPr(c,p)\qand \rOw(c,s)$$
The canonical view definition corresponding to $V_5$ is:
$$U_5(m,y,r) \qif \rC(c)\qand \rMo(c,m)\qand \rYe(c,y)\qand \rRe(m,y,r)$$
\end{example}
}
\eat{
The algorithm to generate logical query plans works in two stages. In the
first stage, we generate, corresponding to each subgoal in the query, a 
{\em relevant bucket} of canonical views. In the second stage, we combine
the views in the buckets to obtain logical solutions. The algorithm to
compute the relevant buckets for each subgoal of a query is shown in
Figure~\ref{algo:buckets}. The algorithm calls the procedure 
{\em Satisfiable}$(Q)$ to test whether a query is satisfiable, given the
functional and inclusion dependencies and disjointness constraints associated
with world view relations. Due to space constraints, we do not show the
details of procedure {\em Satisfiable}$(Q)$ in this paper. Informally, we
need to propagate the functional and inclusion dependencies on $Q$, to
obtain a query $Q'$, and then
test whether:
\begin{enumerate}
\item $Q'$ contains a pair of subgoals of the form $C(x)$ and $D(x)$ where
  $C$ and $D$ are 
  disjoint classes; or
\item The conjunction of order subgoals in $Q'$ is unsatisfiable
  (\cite{Ullman}).
\end{enumerate}
The above procedure can be executed in time that is polynomial in the size
of $Q$, and so procedure {\em CreateBuckets} can be executed in time that is
polynomial in the sizes of the query, the source descriptions, and the world
view. (Note to Alon: We may wish to move the details of Procedure {\em
  Satisfiable} to an appendix and only refer to it here.)
}

\eat{
\begin{example}
Show that the views $U_1(m,t,y,p,s)$ and $U_5(m,y,r)$ get added to the
the right buckets. Show that $U_3$ corresponding to source 3 is not added to
any bucket.
\end{example}

(Note to Alon: Describe second step of algorithm here. Check all possible
solutions that combine views from the buckets and additional order subgoals.
We don't need to use new constants. I don't know what claim to make here:
clearly our algorithm is not complete. Should we point that out? Also, an
example is needed here. The example should probably just continue the
running example.)

\begin{example}
Show that the logical solution:
$$ Q(m,p,r) \qif U_1(m,t,y,p,s)\qand U_5(m,y,r)\qand y \geq 1992 $$
is generated.  
\end{example}
}

\subsection{Finding an Executable Ordering}
\label{sec:valid-plans}


In the second step of creating query plans we consider the
semantically correct plans and try to order the subgoals in such a way
that the plan will be executable, i.e., will adhere to the capability
requirements of the information sources.
Figure~\ref{fig:algo:capabilities} describes an algorithm that given a
 semantically correct plan, finds an ordering on its subgoals that is
executable, if such an ordering exists. The algorithm proceeds by
maintaining a list of available parameters, and at every point adds to
the ordering any subgoal whose input requirements are
satisfied. Finally, the algorithm pushes as many selections as
possible to the sources.



\eat{\begin{figure*}[bht]
\begin{center}
\fbox{
\begin{minipage}{5.5in}
\begin{tabbing}
123\=123\=123\=123\=123\=123\= \kill
{\bf Algorithm ExecOrder}$(P)$\\
{\bf Input:} $P$ is a logical query plan of the form:
 $Q(\Vec{X}) \qif U_1(\bar X_1)\qand \ldots\qand  U_n(\bar X_n)\qand
C_Q$\\
\\
Propagate all the functional and inclusion dependencies in $Q$.\\
${\em bound} := \emptyset$.\\
Subgoals $U_1(\bar X_1)\qand \ldots\qand  U_n(\bar X_n)$ are marked 
{\em not chosen}.\\
For $i = 1, \ldots, m$ do\\
\> For each subgoal $U(x_1\ldots x_k)$ marked {\em not chosen}\\
\>\> Construct the binding pattern $\alpha = s_1\ldots s_k$ where:\\
\>\>\> $s_i = b$ if $x_i \in {\em bound}$ or $x_i$ is a constant\\
\>\>\> $s_i = f$ otherwise.\\
\>\> Let ${\cal C} = \langle P, P^b, {\em min}_b, P^s \rangle$ be the
capability record corresponding to view $U$.\\
\>\> If the query template $U^\alpha(x_1\ldots x_k)$ 
matches the capability record $\cal C$\\
\>\>\> Set $V^\alpha(x_1\ldots x_k)$ to be the identical query template to
$U^\alpha(x_1\ldots x_k)$ \\
\>\>\> For each subgoal $A(x_i, y)$ in the body of 
$U^\alpha(x_1\ldots x_k)$\\ 
\>\>\>For each subgoal $y \theta c$ that appears in $C_Q$ for some constant
$c$\\
\>\>\>\> If $A(x_i) \in P^s$ add the subgoal $y \theta c$ to the body of
$V^\alpha(x_1\ldots x_k)$\\
\>\>\> $S_i := V^\alpha(x_1\ldots x_k)$\\
\>\>\> Add $x_1,\ldots,x_k$ to {\em bound}.\\
\>\>\> Mark $U(x_1\ldots x_k)$ {\em chosen}.\\
If there is a subgoal marked {\em not chosen}, output ``No executable
ordering''.\\
Output the ordering $S_1, \ldots, S_n$.\\
{\bf End.}
\end{tabbing}
\end{minipage}
}    
\end{center}
\caption{Algorithm to compute an executable ordering for a logical query
  plan.}
\label{algo:ordering}
\end{figure*}
}


\begin{figure*}[hbt]
\begin{center}
\fbox{
\begin{minipage}{5.5in}
{\small
\begin{tabbing}
{\bf procedure create-executable-plan}($Q'$) \\
/$*$ \=\kill
/$*$ {\bf Input:} $Q'$ is a semantically correct conjunctive plan
whose non-interpreted subgoals  are 
$U_1,\ldots,U_n$. $*$/ \\
\> The capability record of the information source of $U_i$ is $(in_i,
out_i, sel_i, min_i, max_i)$. \\
\> We assume all bindings in $Q'$ are given explicitly using the $=$
relation as a conjunct. \\\\
\> {\bf Output:} an executable query plan $P'$, which is an ordering
$V_1,\ldots,V_n$ of $U_1,\ldots,U_n$, \\ \> and triplets
$(V^i_{in},V^i_{out},V^i_{sel})$ specifying the inputs and outputs of
the conjuncts. \\
\> $C_{P'}$ is the set of selections that will be applied locally. $*$/ \\ \\

$QueryBindings$ = The set of variables in $Q'$ bound by values in the
query. \\
$Q_{out}$ = The head variables of $Q'$. \\
$QuerySelections$ = The set of variables in $Q'$ for which the query
contains a selection. \\
$BindAvail_0 = QueryBindings$. \\
{\bf for\/} \= $i = 1, \ldots, n$ \\
\> The $i$'th subgoal in the ordering, $V_i$, is any subgoal $U_j$ of
$Q'$  that was not chosen earlier and \\
\> at least $min_j$ of the parameters in $in_j$ are in
$BindAvail_{i-1}$. \\
\> {\bf if \/} \= there is no such subgoal, {\bf return\/} {\tt
plan not executable}, {\bf else} \\
\>\> $BindAvail_i =BindAvail_{i-1} \cup out_j$. \\
\>\> $V^i_{in}=$ A minimal set of parameters in
$BindAvail_{i-1}$ that satisfied the input requirement of $U_j$. \\
\>\> $V^i_{out}=$ All the parameters in $out_j$. \\
{\bf end for} \\
{\bf if\/} $Q_{out} \not \subseteq BindAvail_n$ {\bf return\/} {\tt
plan not executable}. \\
{\bf for\/} $i= 1, \ldots n$ \\
\> Remove any element from $V^i_{out}$ that is not needed as an input to
a subsequent subgoal or for $Q_{out}$. \\
\> Add \=to as many parameters as possible from $QuerySelections \cup
BindAvail_{i-1}$ 
to $V^i_{in}$ \\ \>\>
 and selections using these parameters 
to $V^i_{sel}$ 
 such that the cardinality of $V^i_{in} \cup V^i_{sel}$ does \\
\> \>
not exceed  the input capacity of its source. \\
$C_{P'}$ includes all the built-in atoms in $Q'$ that are not in one
of the $V^i_{sel}$'s. \\
%{\bf return\/}
%$({\sf v}_1,{\sf v}^1_{in},{\sf v}^1_{out},{\sf
%v}^1_{sel}),\ldots,({\sf v}_n,{\sf v}^n_{in},{\sf v}^n_{out},{\sf
%v}^n_{sel})$. \\
{\bf end create-executable-plan.}
\end{tabbing}
}
\end{minipage}
}
\end{center}
\caption{An algorithm for computing an executable ordering of a semantically
correct plan. We assume that any pair of variables that are forced to
be equal because of the functional dependencies have already been
equated in the input.}
\label{fig:algo:capabilities}
\end{figure*}

\begin{example}
Consider the semantically correct plan  for answering our sportscar query:
\begin{tabbing}
$P_1: \; Q($ \= \kill
$P_1: \; Q(m,p,r) \, \qif \, V_1(c) \qand V_5(m,y,r) \qand Model(c,m)\qand$\\
\> $Year(c,y), Category(c,{\sf sportscar}) \qand y \geq 1992.$
\end{tabbing}
The bindings available in the query are
$\{Category(c)\}$. Therefore, the input requirements of $V_1(c)$ are
satisfied and so it is put first. The outputs of $V_1(c)$ are
$\{Model(c)$, $Price(c),$ $Year(c),$ $SellerContact(c)\}$, therefore
$BindAvail_1= \{Category(c),$ $Model(c),$ $Price(c),$ $Year(c),$
$SellerContact(c)\}$, and so the input requirements of $V_5(m,y,r)$
are satisfied. Since the second information source provides the
review, the ordering is executable. Finally, we add $y \geq 1992$ to
the selections of the first source. We remove $SellerContact(c)$ from
the outputs of the first subgoal because it is not needed anywhere in
the query.
\end{example}


The following theorem shows that our algorithm will find an ordering
of a plan whenever an executable ordering exists, and 
 will do so in polynomial time. The proof is omitted because of space
limitations.

\begin{theorem}
\label{thm:ordering}
Let $Q'$ be a semantically correct plan. If there is an ordering of
the subgoals of $Q'$ that results in an executable plan, then procedure {\bf
create-executable-plan\/} will find it. The running time of the
procedure is polynomial in the size of $Q'$. $\Box$
\end{theorem}

Algorithm {\bf create-executable-plan\/} is a generalization of
 an algorithm by
Morris~\cite{Morris88} for ordering subgoals in the presence of
binding constraints. The key difference is that our capability records
encode a {\em set\/} of possible binding patterns for each subgoal,
and we find an ordering that chooses one pattern from every such
set. Furthermore, our binding patterns involve not only variables
occurring in the  query, but also attributes on them, and also the
possibility of pushing selections on parameters.

\eat{while,  in two ways. First, in our case, the values passed
to the subgoals are not simply values of variables, but possibly
fillers of role-chains on these variables, and there are requirements
on which sets of role-chains are sufficient.  Second, we need to
ensure that multiple occurrences of values of the same variable from
different sources can be compared via keys, which is a problem that
does not arise in Morris' context.}

Our descriptions allow only one capability record for every source
relation.  This restriction essentially means that the parameters that
can be obtained from the source do not depend on how we chose to
satisfy the input requirements of the source.  In practice, we have
found this to be sufficient to describe the sources we
encountered. Conceivably, there may be situations in which it will not
suffice, and the output set depends on which set of input parameters
we used.  The following theorem shows that in such a case, the problem
of determining whether there exists an executable ordering for a plan
is intractable, and therefore the choice we made also has important
computational advantages.


\begin{theorem}
\label{thm:np-completeness}
If every source relation in the content descriptions of information
sources could have more than one capability record of the form
$(S_{in},  S_{out}, S_{sel}, min, max)$, then the
problem of determining whether a semantically correct plan can have an
executable ordering is NP-complete. $\Box$
\end{theorem}



\section{Implementation and Experiments}
\label{sec:implementation}

%\subsection{The \IM\ System}

\begin{figure*}[t]
\centerline{\psfig{figure=im-arch.pstex,height=3.8in}}
\caption{Architecture of the Information Manifold}
\label{fig:im-arch}
\end{figure*}


The \IM\ system, whose architecture is shown in
Figure~\ref{fig:im-arch} uses the techniques described in the previous
sections to provide a uniform query interface to 100 structured
information sources on the WWW.  When a query is posed, the system
uses the descriptions of information sources to compute executable
query plans.  An important aspect of the system is that it provides a
{\em stream\/} of answers to the user, and therefore tries to minimize
the time taken to begin and sustain the stream, as opposed to
minimizing the time taken to provide {\em all\/} the answers to the
query.  Minimizing the time to the early tuples is important because
the user is likely to find a satisfactory answer before all answers
are exhausted.

\eat{,  as explained in the previous section, in order to decide
which sources are relevant, and to compute the various ways in which
answers to the query can be found (i.e., the executable solutions).}
\eat{It does so by
generating the executable solutions in the order of their likelihood
to find answers to the query, and executing them as soon as they are
available.  The likelihood of the executable solutions is based on
estimates on how likely a source is to contain tuples of a certain
view (these estimates are given with the descriptions). For example,
when looking for books, the Library of Congress is very likely to have
a given book in comparison with other bibliography servers.
The plan executor also tries to access information sources in parallel,
whenever the plan allows for parallelism.}

\iffullversion
Users  interact with the \IM\ through a web based interface. The
interface enables  users to browse the categories of information
available (i.e., the world view), and to see which 
information sources are available.  Users can formulate queries
either using templates that are available for classes in the
world-view, or by combining such templates into an arbitrary
conjunctive query. 
\fi


\eat{ Another
important optimization is based on interleaving planning and
execution. When the planner identifies a subgoal in the query that has
many information sources relevant to it, the planner will ignore that
subgoal in the query and will create plans for the query without that
subgoal. After finding intermediate results of the simpler query, the
planner is able to prune the number of information sources relevant to
that subgoal.  This leads to savings both in planning time and in the
number of information sources accessed.  Interleaving planning and
execution is achieved by including, in addition to the usual plan
operators, instructions to the executor to return to the planner.}

\eat{ The
planner also puts {\em landmarks\/} between sets of plans, separating
the more promising plans from the ones less likely to provide
answers. The plan executor considers plans that are after a landmark
only if the system or the user tell it explicitly to do so (e.g., the
user may be happy with the answers obtained thus far).}

\iffullversion
The system currently provides access to over~100 information sources in
various domains, including name servers, publication databases, market
databases and entertainment sources (e.g., movie and video databases,
CD stores). Our method of  describing information sources
has proved to be useful in practice by enabling us to quickly and
accurately model a large number of sources, while leaving the
world-view relatively stable.  We have developed a set of tools which
enable us to speed up the process of generating interface programs to
information sources on the WWW. In particular, many sources on the WWW
have a form-based interface. We have developed a tool in which we
simply determine the correspondence between the variables used in the
form and the world view, and then specify a grammar describing the
format of the answers obtained from the source, and the bulk of the
interface program is generated automatically.  Several of the
interface programs use an outerjoin-based technique~\cite{ru95} to
convert hierarchically structured documents into relations. \fi



%\subsection{Experimental Results}
%\label{sec:experiments}

In order to experimentally evaluate our algorithms, we selected a set of
queries and studied how various parameters varied as we increased the number
of information sources available to the system. 
Here we illustrate our results using 
three representative queries:
\begin{enumerate}
\item  {\em Find titles and years of movies featuring Tom Hanks.}
\item  {\em Find titles and reviews of movies featuring Tom Hanks.}
\item  {\em Find telephone number(s) for Alaska Airlines.}
\end{enumerate}


\begin{table*}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
Query & Number of & Max. bucket & Plans & Plans & Time per & Total time\\ 
      & sources   & size &  enumerated & generated     &  plan (sec.)&
(sec.)\\
\hline
 &  20 &  1 & 7 & 1 & 0.55 & 0.55 \\ \cline{2-7}
 &  40 &  1 & 7 & 1 & 0.56 & 0.56 \\ \cline{2-7} 
1 & 60 &   2 & 26 & 2 & 0.85 & 1.70 \\ \cline{2-7}
 & 80 &   2 & 26 & 2 & 0.85 & 1.70 \\ \cline{2-7}
 & 100 &  2 & 26 & 2 & 0.85 & 1.70 \\ \hline
 & 20 &  2 & 7 & 1 & 0.57 & 0.57 \\ \cline{2-7}
 & 40 &  3 & 11 & 2 & 0.48 & 0.96 \\ \cline{2-7}
2 & 60 & 5 & 35 & 6 & 0.49 & 2.95 \\ \cline{2-7}
 & 80 &  6 & 44 & 8 & 0.40 & 3.20 \\ \cline{2-7}
 & 100 & 7 & 72 & 8 & 0.75 & 6.00 \\ \hline
 & 20 &  2 & 8 & 2 & 0.28 & 0.56 \\  \cline{2-7}
 & 40 &   2 & 8 & 2 & 0.28 & 0.56 \\  \cline{2-7}
3 & 60 &  2 & 8 & 2 & 0.28 & 0.56 \\  \cline{2-7}
 & 80 &   6 & 49 & 6 & 0.22 & 1.32 \\  \cline{2-7}
 & 100 & 10  & 120  & 10  & 0.22 & 2.20 \\ \hline
\end{tabular}
\end{center}
\caption{Query planning statistics for queries 1, 2, and 3 as the number of
  available information sources is varied between 20 and 100.}
\label{tbl:stats}
\end{table*}

For each query, we varied the number of information sources available
to the system from 20 to 100 and measured various parameters. The
results are shown in Table~\ref{tbl:stats}.  Our experiments were run
on a SGI Challenge 150MHz computer.  {\em Maximum bucket size} is the
number of sources in the largest bucket created using Algorithm {\bf
CreateBuckets}. {\em Plans enumerated} is the number of candidate
plans enumerated in the second stage of the query planning algorithm,
while {\em plans generated} is the total number of semantically
correct and executable query plans actually generated for a given
query. Table~\ref{tbl:stats} also gives the total time taken to
generate all query plans and the time per plan.

We note that the number of information sources relevant to a query generally
increases with the total number of sources available. However, Algorithm
{\bf CreateBuckets} is extremely effective in pruning away irrelevant
sources. The effectiveness of the pruning is measured in terms of the
reduction in the number of candidate plans that are enumerated when
creating semantically correct plans. 
 If there were no pruning (as suggested by the
nondeterministic algorithm in~\cite{lmss95}), we would have to
enumerate $O(n^{|Q|})$ plans for query $Q$, where $n$ is the total number of
information sources and $|Q|$ is the number of subgoals in $Q$. For example,
with 100 sources, we would have to enumerate more than 1 million
plans for Query 1. However, the number of plans we actually enumerate is
only 26 (a function of the product of the bucket sizes). 
\iffullversion
This pruning is
extremely important to ensure the {\em scalability} of our system, since we
have to do an expensive query containment check for each enumerated plan.
\fi

Observe also that although Query 1 and Query 2 both ask about movies, the
number of sources relevant to Query 2 is  more than the number of
sources relevant to Query 1 (7 versus 2 with 100 sources, for example).
This difference is due to our ability to model fine-grained distinctions
among movie sources, which enables us to prune away certain sources for
Query 1 that are relevant to Query 2.

\begin{figure}
%\begin{center}
%\input{total-time}
%\end{center}
\centerline{\psfig{figure=total-time.eps}}
\caption{Total query planning time in seconds versus number of information
  sources.} 
\label{fig:total-time}
\end{figure}




\iffullversion
\begin{figure}
\begin{center}
\input{total-time}
\end{center}
\caption{Total query planning time in seconds versus number of information
  sources.} 
\label{fig:total-time}
\end{figure}


\begin{figure}
\begin{center}
\input{time-per-plan}
\end{center}
\caption{Average time per plan in seconds versus number of information
  sources.} 
\label{fig:time-per-plan}
\end{figure}
\fi

Figure~\ref{fig:total-time} plots the total time to generate all query plans
for each query against the number of information sources available to the
system. It is seen that the overall time generally increases with the number
of information sources, but not exponentially. Due to the effective
pruning, the time for plan generation is more a function of the number of
{\em relevant} information sources than of {\em total} number of information
sources. 

The total time for query planning is not a very good indicator of system
response time. In the \IM, each query plan is executed a soon as it is
generated, in parallel with further planning and executing other plans.
Thus, a better measure of response time is the average time to generate one
query plan. We plot the average time per plan against the number of
information sources in Figure~\ref{fig:time-per-plan}. In contrast to the
total query planning time, we observe that the average plan time does not
always increase with the number of information sources, nor does it increase
as rapidly. This effect is due to the fact that increasing the number of
sources available generally also increases the number of possible query
plans. Finally, we observe that the average time per plan is within a tight
range of less than 1 second for the queries we study, even when the number
of information sources is large. This time is to be contrasted with the time
taken to execute a query plan, which typically involves going over a
network. 
\iffullversion
For example, executing a query plan for Query 2, which involves
querying multiple sources, parsing their answers, and computing a join,
takes as much as 30 seconds with typical wide area network speeds.
\fi



\section{Related Work}
\label{sec:related-work}

\iffullversion
Our approach to integrating multiple information sources can be seen
as treating the sources as a multidatabase or as a federated database
(e.g.,~\cite{pegasus91,mcleod94,hbp94,Litwin90}). In fact, the content
descriptions of information sources can be viewed as a generalization
of {\em exported schemas\/} in multidatabases.  However, in
multidatabases the correspondence between the contents of the
individual databases and the global schema is more direct. As one
example, in the Pegasus system~\cite{pegasus91} every external
database is modeled as a class in the class hierarchy, which is
disjoint from other classes. It is then possible to define
superclasses that represent {\em unions\/} of databases. In the \IM\
the contents of an information source can be defined as an arbitrary
conjunctive query on classes and relations in the
world-view. Therefore we do not have to create a class for every
source, and we are able to make more fine-grained distinctions between
the contents of sources. This difference has proven very important in
practice in order to quickly add information sources. In Pegasus,
determining the set of databases to access in order to answer a query
is simple, because it is immediate from the query. One of the key
difficulties in the \IM\ is determining which information sources are
relevant to a query. Finally, source capabilities are not considered
in the multidatabase literature. The upshot of these differences is
that in the \IM\ the user can more easily specify {\em what\/} he or
she wants, rather than having to formulate a query in a way that would
guarantee that all the relevant information sources are accessed. On
the other hand, it should be noted that since our goal is only to
provide a {\em query} interface to the information sources, we are not
concerned with issues of consistency and updating the information
sources as in multidatabases.
\fi

\eat{
The key difference between the \IM\ and multidatabases 
However, our content descriptions are more expressive
than exported schemas, since the have a rich constraint language, and
describe the information sources as views on the world-view
relations. Both of these aspects enable us to capture more fine
grained distinctions between contents of information sources.
Furthermore, capability descriptions, that are crucial in our setting,
have not been considered in multidatabase systems.  As a consequence of that, the information
sources are much more loosely connected than in multidatabase systems,
and it becomes easier to add information sources.}




\eat{Is the following really true?

In contrast, when querying a multidatabase system, the user has to be
explicitly aware of the existence and the contents of the conceptual
schemas in each of the autonomous databases.  While the multidatabase
approach to querying multiple autonomous site relations is feasible
when the number of site relations is small, it is not appropriate in
the presence of a large number of site relations.}

\eat{Read about tsimmis, hermes, carnot and the Internet
softbot}

Several systems (e.g., TSIMMIS~\cite{pggu95}, 
HERMES~\cite{hermes96},
CARNOT~\cite{Carnot}, DISCO~\cite{frv95a}, Nomenclator~\cite{OM93}) for
integrating multiple information sources are being built on the notion
of a {\em mediator}.  The key aspect
distinguishing \IM\ from the other systems is its generality, i.e.,
that it provides a  source independent, query independent
mediator. Instead of being tailored to specific information sources
and/or specific queries on these information sources, the input to \IM\
is a set of descriptions of the contents and capabilities of the
sources. Given a query, the \IM\ will consider the descriptions and the
query, and will create a plan for answering the query using the
sources. Consequently, we do not have to build a new mediator for
different queries or information sources.  For example, the
Nomenclator system incorporates multiple CCSO, X.500 and relational
name servers.  Source descriptions are given as equality selections on
a {\em single\/} relation, and queries can only reference one
relation.

\begin{figure}
%\begin{center}
%\input{time-per-plan}
%\end{center}
\centerline{\psfig{figure=time-per-plan.eps}}
\caption{Average time per plan in seconds versus number of information
  sources.} 
\label{fig:time-per-plan}
\end{figure}

The SIMS system~\cite{ACHK93} also describes information sources
independently of the queries that are subsequently asked on them.
 The descriptions in the \IM\ are richer than those
in SIMS because they allow relations of arbitrary arity, and in
particular allow us to express the fact that an information source
contains a conjunctive view over world-view relations (either classes,
roles or relations of higher arity). SIMS does not
consider capability descriptions of the sources. SIMS, as well as the
Internet Softbot~\cite{etzioniweld94} use Artificial Intelligence
planning techniques for determining the relevant information sources
and creating a query plan. These approaches do not provide the
guarantees of ours, that is that we find {\em all\/} and {\em only\/}
the relevant sources. 
\iffullversion
Furthermore, it is not clear how their
techniques will scale up to large numbers of information sources. In
contrast, most of the algorithms we use are efficient, and the sources
of complexity (e.g., containment checks) are well understood and are
limited in practice. The advantage of general purpose planning
techniques is the flexibility in dealing with unexpected problems
during query evaluation~\cite{knoblock95}.
\fi

In~\cite{lsk95} a language for
describing information sources that was less expressive than the one
we describe here was proposed. The language  did not consider the capability
descriptions, and the  algorithms described  for finding
relevant information sources did not deal with the case where source
descriptions are given as queries on the world-view
relations. Consequently,  only a 
limited range of information sources could be incorporated. Practical
algorithms and evaluation were also not discussed there.

\eat{how do we deal with runtime stuff? What else can we say
here? Expressive power?}

\iffullversion
Finally, there are several indexing systems for finding information on
the World Wide Web (e.g.,  Yahoo, Lycos, Altavista).
However, all these systems are based on keyword searches on contents
or annotations of documents, and are only able to retrieve documents
that match these keywords. They cannot answer semantically meaningful
queries that require considering the contents of the sources. 
\fi
A related line of work is on Web query languages. For example, 
W3QS~\cite{shmueli95} is a system for specifying high-level queries
over unstructured information sources. This system enables the user to
specify in the query patterns of nodes on the web and properties of
such nodes. W3QS
is a  useful tool that enables a lot of otherwise manually done
search to be done by a search engine, but it does not make
use of contents of structured sources, and combine information from
multiple sources.

\eat{
Interleaving query planning and execution: Striking a balance between
  AI planning and traditional DB query planning approaches. An absolute must
  for our environment.}



\section{Conclusions and Future Work}
\label{sec:conclusions}



We described the query planning algorithms used in \IM, a novel system
that provides a uniform query interface to distributed structured
information sources. The \IM\ frees the user from having to interact
with each information source separately, and to combine information
from multiple sources.  The techniques underlying the \IM\ are
applicable to sources on the WWW as well as other collections of
information sources such as company-wide databases. The key aspect of
our system is a mechanism for describing the contents and capabilities
of the available information sources.  This  enables
expressing fine-grained distinctions between the contents of different
information sources, thereby enabling us to prune the sources that are
irrelevant to a given query.  A novel aspect of our system is that it
describes the capabilities of information sources in addition to their
contents, which is crucial in order to interact with remote
sources. 
\iffullversion
Our contributions include practical algorithms for deciding
which information sources are relevant to a query, and how to combine
them in a way that adheres to the capabilities of the sources and
exploits them when possible.
\fi
 Our architecture and algorithms have been
useful in practice, allowing us to describe many existing information
encountered. The end result is the first system that provides a
database-like interface to over~100 structured information sources on
the WWW.

\iffullversion
An important issue is designing tools to obtain
descriptions of information sources easily. In~\cite{lo95} we describe one
such fielded tool designed to obtain descriptions of name server
sources. The tool is based on asking the administrators of the
name servers to annotate example entries from their databases so
that we can infer the content descriptions of the source from the
annotations. 

The world-view with which the user interacts is designed with respect
to the set of information sources to which we expect to provide
access. 
\fi


There are several important areas of research we are currently
pursuing.   One issue 
 is how to obtain source
descriptions. Currently, we are providing the source descriptions, but
an active area of research is the design of  tools for automating this
process.
We are also considering how to extend our source descriptions
 so that we will be able to infer that a source is
relevant to a query with some degree of likelihood. For example, if we
are searching for papers on database systems, and have access to a
repository of papers on operating systems, we cannot completely ignore
the repository, because we cannot state that these two fields are
disjoint. However, we would like to access this repository only after
we have accessed all other repositories that are closer to database
systems.
\iffullversion
 The second extension we are considering is extending our 
modeling mechanism and algorithms to be able to deal partially with
unstructured information sources. 
\fi
\eat{Doing so requires that we extend our
language for describing capabilities of sources, which can be viewed
as being  extremely
limited in the case of unstructured sources. }


\section*{Acknowledgments}

We thank Marie-Christine Rousset, Arnie Rosenthal, Avi
Silberschatz, Anthony Tomasic and Jeff Ullman for comments on earlier
versions of this paper.

\iffullversion
\section*{Appendix}

\noindent
{\bf Proof Sketch of Theorem~\ref{thm:ordering}:\/}
The main observation  underlying the proof is that if
there is an ordering of the subgoals of $Q'$, and a subgoal $V_i$
appears in the $i$'th position, then its input requirements will
still be satisfied even if other subgoals are pushed in front of it.
 This property is because the set of available parameters
increases monotonically. 

Given this observation, suppose there is an executable ordering
$V_1,\ldots,V_n$ of the subgoals of $Q'$. The subgoal $V_1$ will be
added at some point to the ordering by the algorithm because its input
requirements are already satisfied by the explicit bindings in the
query. Inductively, if the subgoals $V_1,\ldots,V_{i-1}$ are added at
some point to the ordering, then the algorithm will ultimately add
$V_i$ to the ordering, since its input requirements are
satisfied after $V_1,\ldots,V_{i-1}$ have been
added. Therefore, since all subgoals will be added at some point, some
ordering will be found.  $\Box$


\paragraph{Proof of Theorem~\protect\ref{thm:np-completeness}:}

The problem is in NP because we can simply guess an ordering, and check
whether it satisfies the requirements of the information sources in
polynomial time.

We show the NP-hardness by reducing the satisfiability problem of 3CNF
formulas to our problem. Let $\Delta$ be a set of 3CNF formulas, with
the propositional variables $p_1,\ldots,p_n$ and clauses
$c_1,\ldots,c_m$.  We construct a semantically correct plan with $n+m$
subgoals. Each subgoal uses a different information source, and all
subgoals have exactly one variable, $X$. For each of the first $n$
subgoals, we have the following capability record: $(\emptyset,
 \{p_i^1(X)\}, \emptyset,0, 0)$, $(\emptyset, 
\{p_i^2(X)\},\emptyset, 0, 0)$ that is, there are no requirements on the
input or selection parameters, but there are two possible outputs,
either the $p_i^1$ or $p_i^2$ parameter.  Intuitively, the choice of
output determines the truth value of the proposition $p_i$. The next $m$
subgoals are one for each clause. Suppose the $i$'th clause is
$\{L_1,L_2,L_3\}$, where each $L_i$ is a literal. The $(n+i)$'th subgoal
has one capability record. The input set $S_{in}$ contains three
elements: for $1 \leq j \leq 3$ it contains $p_i^1(X)$ if $L_i=p_i$
and $p_i^2(X)$ if $L_i= \neg p_i$. The minimum number of inputs is~1
and the maximal number is~3. There are no output or selection
parameters. 

Clearly, if $\Delta$ is satisfiable, there is a way to satisfy the
capability requirements in the query. We choose the capabilities of the first $n$
subgoals to produce exactly the satisfying assignment to the variables
of $\Delta$ (i.e., $p_i^1(X)$ if $p_i$ is assigned $True$, and
$p_i^2(X)$ otherwise). The next $m$ subgoals are satisfied, since each
of the clauses in $\Delta$ are satisfied by the truth
assignment. Similarly, if there is a way to satisfy the requirements
of the information sources then we can build a satisfying assignment
in a straightforward fashion. Finally, our reduction is polynomial
because the query we produced is polynomial in the size of
$\Delta$. $\Box$
\fi

{\small
\bibliography{short}
}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 






