\documentstyle[vldb,psfig]{article}

\title{Object Fusion in Mediator Systems\footnote{
Research sponsored by the Wright Laboratory, Aeronautical Systems Center,
Air Force Material Command, USAF, under Grant Number F33615-93-1-1339.
This work was also supported by an equipment grant
and a fellowship from IBM Corporation.
}}

\author{
Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina \\
{\it Computer Science Department}\\
{\it Stanford University}\\
{\it Stanford, CA 94305-2140, USA}\\
{\it \{yannis,abitebou,hector\}@db.stanford.edu}\\
}

\institution{}

\newtheorem{algorithm}{Algorithm}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{defin}{Definition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
\newenvironment{definition}[1]{\begin{defin}\begin{rm}({\bf
    #1})}{{\hfill$\Box$}\end{rm}\end{defin}}

\newcounter{query}
\newcounter{dr}

\begin{document}
\bibliographystyle{alpha}

\maketitle

\begin{abstract}
One of the main tasks of mediators is to fuse information from heterogeneous
information sources. This may involve, for example, removing redundancies,
and resolving inconsistencies in favor of the most reliable source.
The problem becomes harder when the sources are unstructured/semistructured
and we do not have complete knowledge of their contents and structure.
In this paper we show how many common fusion operations can be specified
non-procedurally and succinctly. The key to our approach is to assign
semantically meaningful object ids to objects as they are ``imported''
into the mediator. These semantic ids can then be used to specify how various
objects are combined or merged into objects ``exported'' by the mediator.
In this paper we also discuss the implementation of a mediation system
based on these principles. In particular, we present key optimization
techniques that significantly reduce the processing costs associated
with information fusion.
\end{abstract}


\section{Introduction}
\label{intro}

The TSIMMIS system provides integrated access to heterogeneous
information, stored not only in conventional databases but also in
file systems, the Web, and legacy systems.  The TSIMMIS architecture
is shown in Figure~\ref{fig:arch}.  {\em Wrappers}\
\cite{Garlic} convert data from each
source into a common model and also provide a common query language.
Applications can access data directly through wrappers, but they may
also go through mediators \cite{medmaker-no-oid,HERMES},
which provide an integrated view of the data exported by wrappers.

\begin{figure}
\centerline{\psfig{figure=arch.ps,height=2.0in}}
\caption{The TSIMMIS architecture}
\label{fig:arch}
\end{figure}

The architecture of Figure~\ref{fig:arch} is common in many
integration
projects~\cite{de95,Garlic,Pegasus,HERMES,LitwinMarkRoussopoulos,KimResolve}. However,
the focus of our project is on semi-structured and/or unstructured
information.  This is information that may not conform to a rigid
schema fixed in advance, and is frequently found, for instance, in the
World-Wide-Web, SGML documents, semi-structured repositories such as
ACeDB \cite{ACeDB} (very popular among biologists in the Human Genome
Project), and Lotus NOTES.  To represent such data, we use a
``schema-less'' object-oriented model, called {\em Object Exchange
Model (OEM)} \cite{de95}.

Mediators play the central role in information integration, and their
most important task is to perform {\em object fusion}.  This involves
grouping together information (from the same or different sources)
about the same real-world entity, possibly removing redundancies, or perhaps
resolving inconsistencies between sources in favor of the most
reliable source.
%or privileging access to a particular source if it
%provides information at a lower cost (either financial or
%computational).

In this paper, we present an approach to object fusion that is based
on semantic object identifiers.  The basic idea is as follows.  The
mediator is specified by a set of declarative, logic rules.  Each rule
maps objects at a source that pertain to some identifiable real world
entity, into a ``virtual'' object at the mediator.  The virtual object
is assigned a semantically meaningful object identifier.  Mediator
objects that have the same object-id are then fused together.  The
above description is conceptual; no objects are fused until a user
query arrives at the mediator.  (The mediator specification is like a
database view.)  Only when a query arrives are the sources queried
for the object fragments that are necessary for composing the selected
fused objects.

For our specifications, we use {\em MSL (Mediator Specification
Language)}~\cite{medmaker-no-oid}.  However, the original MSL did not
include semantic object-id's, hence making the specification of fusion
much harder. We extend MSL with semantic object-id's, specified as
skolem functions, that allow rules to specify object fragments that
can be fused together.  Construction of object-id's as skolem functions has
been extensively studied by the deductive and object-oriented database
systems community, hence providing us with a clear theoretical
foundation.

Our first contribution is to show that the single concept of
``object-id's as skolem functions,'' cast in the appropriate practical
framework, significantly increases the power of the specification
language.  This makes it relatively easy to stipulate powerful fusion
mediators.  For example, one of the most challenging aspects of fusion
is the integration of source objects that contain references to other
source objects.  We will show how semantic object-ids can be used to
translate source references into semantically meaningful references at
the mediator, allowing the integration of nested and cross-referenced
objects such as those found on the Web.  

A second contribution is the adaptation of {\em resolution} and {\em
subsumption} for the purpose of efficient query processing
against mediators that perform fusion.  

Our last contribution is a set of novel optimization strategies that
are specific to information fusion in an environment of semistructured
sources.  For example, with heterogeneous semistructured sources , it
may not be known in advance what source a particular condition should
be pushed to.  In this case traditional techniques force the query
processor to explore an exponential number of options for pushing
selections to the sources.  We demonstrate alternative query
processing policies that most often perform substantially better.  For
example, we precede the information fusion phase with an information
finding phase that attempts to rule out sources that can not
contribute some particular data required by the query.  We also
present intelligent schemes to avoid retrieving information that will
eventually be discarded. For example, if two sources {\tt s1} and {\tt
s2} provide conflicting information about some object and the
specification indicates that the conflicts are resolved in favor of
{\tt s1}, the mediator does not query {\tt s2} for information that is
already provided by {\tt s1}.


Before proceeding, we make a few remarks that may help position our
work.  The first is that our specification language, MSL, is not
intended as an end-user language.  As a matter of fact, our goal has
been to have a few simple but powerful language constructs.  This
simplicity has turned out to be essential for the development of
efficient optimizers and execution strategies.  

%To assist the person
%writing mediator specifications, we can add more ``user friendly''
%constructs to MSL.  Such an extended MSL is beyond the scope of the
%paper.

Second, the query processing algorithms, with the optimizations
described here, have been implemented as part of our TSIMMIS system.
The need for sophisticated processing algorithms became apparent as
the system was being built and tested, and most of the techniques
presented here were developed after an initial
version~\cite{medmaker-no-oid} identified important weaknesses.

Third, since there is not enough space to go into the full details, in
this paper we mainly use examples to demonstrate the power of MSL for
fusion problems and to explain the key ideas of our query
decomposition and optimization techniques.  The precise syntax and
semantics of the language can be found
in~\cite{medmaker-extended}. Further details on the underlying
algorithms can be found in~\cite{medmaker-extended} or in our
implementation that will soon be ftp-available.

The outline for our paper is as follows.
In Section~\ref{oem}, we give a brief overview of the OEM model.
Section~\ref{group-oid} covers typical fusion problems,
and shows how MSL and semantic ids can address them.
The query evaluation and optimization strategies are
then described in Sections~\ref{impl} and~\ref{incomplete-schema}.
In Section~\ref{conc} we briefly survey the prior work
that our system builds upon.

\section{The OEM Model}
\label{oem}

Most applications that have to deal with semi-structured information
use a {\em self-describing} model, where each data item has an
associated descriptive label.  Applications include tagged file
systems, Lotus NOTES, 
electronic mail, RFC1532 bibliographic records, and many more.  In
\cite{de95} we have defined a self-describing data model, 
called the {\em Object Exchange Model (OEM)}, that captures the
essential features of the self-describing models used in practice and
also generalizes them to allow nesting and to include object identity.

To illustrate the OEM model, consider a source that contains
bibliographic information. A wrapper, named {\tt s1}, exports this
information as a set of OEM objects, some of which are shown below 
(one object per line.)  Notice how the schema
information has now been incorporated into the labels of individual
OEM objects.
%
\vspace{-5mm}
\begin{tabbing}
{\tt <\&}\={\tt r1,report,set,\{\&r1n,\&r1a,\&r1t,\&r1r\}>} \\
  \> {\tt <\&r1n,rn,string,'AB-123'>} \\
  \> {\tt <\&r1a,}\= {\tt authors,set,\{\&r1a1\}>} \\
  \>	  \> {\tt <\&r1a1,author,string,'John Patriot'>} \\
  \> {\tt <\&r1t,title,string,'UN Conspiracies'>} \\
  \> {\tt <\&r1r,}\= {\tt rel,set,\{\&r2\}>} \\
{\tt <\&r2,report,set,\{\&r2n,\&r2a,\&r2t,\&r2r\}>}
\end{tabbing}
\vspace{-2mm}
%
Each OEM object consists of an {\em object-id} (e.g., {\tt \&r1n}), a
{\em label} that explains its meaning (e.g., {\tt rn} that stands for
report number), a {\em type} (e.g., {\tt string}), and a {\em value}
of the specified type (e.g., {\tt 'AB-123'}.)  Labels are strings
that are meaningful to applications or end-users.  Labels may have
different meanings at different sources.  Values may be either of an
atomic type (e.g., {\tt 'John Patriot'}), or be a set of sub-objects
object-id's (e.g., the value of the {\tt rel} object is {\tt
\{\&r2\}}).  To simplify the presentation, in the rest of this paper,
we assume that the type of all {\em atomic} objects is {\tt string}
and we omit type information from objects.

From the point of view of the OEM model, object ids are strings
(starting with {\tt \&}) that are used to link objects with their
sub-objects (e.g., {\tt \&r1t} links the {\tt report} to its {\tt
title}).  We may use semantically meaningful object-id's to facilitate
the integration tasks.  For example, if the report number {\tt rn} of
the report objects is a key and can be used to identify this report
with other reports that should be considered the same entity, then we
can use {\tt \&AB-123} as the id for the report (instead of {\tt
\&r1}). Furthermore, if this report object originally came from
another source {\tt sss}, then we extend the id to {\tt
\&AB-123@sss}.  This convention is easy to implement and
simplifies fusion: Objects that need to be fused can be identified by
their ids, yet the source of the information is clearly noted to avoid
confusion.

Some OEM objects (e.g., the objects identified by {\tt \&r1},
{\tt \&r2}) are ``root'' or {\em top-level} objects and are shown
with left-most indentation. They represent the starting point for
queries to the sources. 

Finally, note that OEM poses no restrictions on the labels of
sub-objects. For example, some {\tt report} objects have a single {\tt
title} object, others may not have any {\tt title}, and others may
have multiple {\tt title}s. In this way, OEM allows us to represent
and integrate information from unstructured sources.

\section{Object-Identity Based Fusion}
\label{group-oid}

In this section we explain how object fusion can be achieved
with semantic object ids.
We start with a simple example that introduces MSL and
demonstrates the basic principle of id based fusion.
We then present examples that illustrate a variety of
fusion operations.
%These examples are not exhaustive;
%they simply show how semantic ids can help in a
%variety of fusion scenarios.

\subsection{A Simple Example}
Let us consider a mediator called {\tt m} that exports technical
report objects with label {\tt tr}. The {\tt tr} objects fuse
information about reports that have the same report number and are
exported by the sources {\tt s1} and {\tt s2}. In particular, if
source {\tt s1} contains a report and its title, the exported {\tt
tr} object contains the corresponding {\tt title}.  If source
{\tt s2} contains the postscript for this report, then a {\tt
postscript} subobject is also included in the {\tt tr}.  Note,
the specification of the {\tt tr} object uses two rules. Each
rule describes the contribution of only one of the sources.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt (RN) tr \{<title T>\}>@m :-} 
	\` \refstepcounter{query}\label{med:simple}(MS\ref{med:simple}) (R\ref{med:simple}.1)\\
\>{\tt <report \{<rn RN> <title T>\}>@s1} \\
{\tt <trep}\={\tt (RN) tr \{<postscript P>\}>@m :-} 
	\` (R\ref{med:simple}.2)\\
\>{\tt <report \{<rn RN> <postscript P>\}>@s2}
\end{tabbing}
\vspace{-2mm}
%
A specification consists of {\em rules} that define the view exported by the
mediator. Each rule consists of a head followed by a {\tt :-} and a tail.
The head describes view objects, whereas the tail describes conditions 
that must be satisfied by the source objects.
In general, the heads and tails are based on patterns of the
form {\tt <}{\em object-id label value}{\tt >}. We may omit the
object-id field when it is irrelevant. If it is missing from a tail pattern
it means that we do not care about the object-id appearing at the source.
If it is missing from a head pattern it means that the mediator has to
invent an arbitrary, yet unique, object-id for the ``generated'' object. 
(The id's are invented using skolemization~\cite{medmaker-extended}.)

Going back to our example, rule (R\ref{med:simple}.1) declares
that {\em if} there is a pair of {\em bindings} $t$ and $r$ for
variables {\tt T} and {\tt RN} (variables are identifiers starting
with a capital letter) such that {\tt s1} contains a {\tt report}
top-level object that has a {\tt rn} subobject with value $r$ and a
{\tt title} subobject with value $t$, {\em then} mediator {\tt m}
exports a {\tt tr} object, with object-id {\tt trep($r$)}, that has a
{\tt title} subobject with value $t$ and a unique system-generated
object-id.

The semantics of rule (R\ref{med:simple}.2) are defined
accordingly.  Notice how {\tt tr} objects at the mediator are assigned
the semantic object id {\tt trep(RN)}.  ( We add the function symbol
{\tt trep} to the report number obtained from the source to uniquely
identify how this id was generated.)  Observe that
(R\ref{med:simple}.1) does not prevent the {\tt tr} with object-id
{\tt trep($r$)} to have subobjects other than {\tt title}, thus
allowing the second rule to add more subobjects to the same {\tt tr}
objects.  In general this is how object fusion is achieved: MSL allows
rules to incrementally and independently insert information into a
semantically identified mediator object.

In this example we assumed that source objects had some semantic key
(like {\tt rn}) that could be used for fusion.  Often keys
exist but are represented differently at sources.  As a trivial
example, report numbers could be represented as integers at {\tt s1}
whereas {\tt s2} may represent them in the string format.  In
this case, we can build and use an {\em external
predicate}~\cite{medmaker-no-oid} that converts the string format to integer
to map the key in {\tt s2} into the form used in the semantic id.
In the rest of our examples, we continue to assume that
matching keys already exist, but keep in mind that this is equivalent
to saying that keys can be converted to a canonical form.

%Those familiar with skolem functions will realize that our id-based
%fusion is just an application of the concept. In the rest of this
%section we show that this single concept can be gracefully combined
%with the rest of the MSL primitives and provide succinct solutions to
%a variety of fusion problems.

\subsection{Merging Information}
It is not necessary to know the structure of the source reports in
order to fuse them. Specification~(MS\ref{group-oid-simple})
demonstrates that we can group all information about reports into {\tt
tr} objects, without knowing the structure and contents of the reports
subobjects.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt (RN) tr V>@all :- } \` \refstepcounter{query}\label{group-oid-simple}(MS\thequery) (R\thequery.1) \\
\> {\tt <report V:\{<rn RN>\}>@s1} \\ 
{\tt <trep(RN) tr V>@all :- } \` (R\thequery.2) \\
\> {\tt <report V:\{<rn RN>\}>@s2}
\end{tabbing}
\vspace{-2mm}
%
Variable {\tt V} binds to set values that contain all subobjects
of {\tt report} provided that at least one of the subobjects has the
label {\tt rn}. Then, every object of the set value becomes a
subobject of the {\tt tr} object, regardless of whether the other
source also provides the same piece of information. 
%(Again, rules
%incrementally add information to the semantically identified mediator objects.)

Note, OEM provides the flexibility to integrate information without
having to worry about the simultaneous presence of subobjects with
same label.  In some cases this may be desirable.  For instance, say
each source contains a different {\tt title} for the same report.  We
may want to record these two potentially different titles in the fused
object.  In other cases, however, we may wish to eliminate one of the
titles.  We show next how this can be done.  The person writing the
mediator specification can decide if redundancies or inconsistencies
are allowed.

\subsection{Removing Redundancies}
(MS\ref{group-oid-simple}) generates one
redundancy that is not useful: each {\tt tr} object contains two {\tt
rn} subobjects with identical values but different object-id's.  This
redundancy can be eliminated as shown by mediator (MS\ref{med-group}).
It assigns the semantic object-id {\tt rnOID(RN)} to the {\tt rn}
subobjects with value {\tt RN}. In this way, the {\tt rn} subobjects
that have the same value are assigned the same object-id and hence
they degenerate into the same {\tt rn} object.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <}\={\tt trep(RN) tr \{}\={\tt <rnOID(RN) rn RN>} \`\refstepcounter{query}\label{med-group}(MS\thequery) (R\thequery.1)\\
\>\>{\tt <O1 L1 X1>\}>@n :-} \\
\>{\tt <report \{<rn RN><O1 L1 X1>\}>@s1 \& NOT L1=rn} \\ 
{\tt <}\={\tt trep(RN) tr \{<rnOID(RN) rn RN>} \`(R\thequery.2)\\
\>\>{\tt <O2 L2 X2>\}>@n :-} \\
\>{\tt <report \{<rn RN><O2 L2 X2>\}>@s2 \& NOT L2=rn}
\end{tabbing}
\vspace{-2mm}
%
Note, the variables {\tt L1} and {\tt L2} that appear in label positions
allow the patterns {\tt <O1 L1 X1>} and {\tt <O2 L2 X2>} to match with 
any subobject of the reports of {\tt s1} and {\tt s2}, provided that {\tt L1}
and {\tt L2} are not equal to {\tt rn}. Then, the subobjects
that are bound to {\tt <O1 L1 X1>} or {\tt <O2 L2 X2>} become 
subobjects of the {\tt tr} objects. (~If we did not have
explicit {\tt NOT} conditions the pattern {\tt <O1 L1 X1>} and
{\tt <O2 L2 X2>} would also match with {\tt rn} objects.)
 
{\bf Comparison of object-id based fusion with outerjoin:}
Outerjoin has also been suggested as a way to join information from
sources that may or may not contribute to the joined object.  MSL
contains a variant of outerjoin (see extended version
\cite{medmaker-extended}) that could be used to implement the example
above.  Using outerjoin we could, in a single rule, create a {\tt
tr} virtual object with report number $r$ if there is a report
with number $r$ at {\tt s1} or {\tt s2}.  However, we believe that the
object-id based fusion scheme we illustrated above is more powerful.
In particular, with object-id based fusion we can easily join objects
from the same source.  The need for this arises if, for example, {\tt
s1} has multiple {\tt report} objects that refer to the same
real-world report.  To do the same with outerjoin, we would have to
know the maximum number of outerjoins that we may need to apply.
This number is data-dependent.  Furthermore, object-id based fusion
is a more modular solution: If we want to add one more source we
simply introduce one more rule.

\subsection{Blocking Sources}
\label{block-and-inc}

More than one source may offer information about the same real world
entity.  If all sources offer roughly the same information we may want
to avoid retrieving information about an entity from some source(s) if
some other source provides us enough information about this
entity. Information sources that charge their users make this scenario
particularly important; if we can retrieve enough information from
some ``cheap'' source, we want to avoid retrieving similar information
from an ``expensive'' source. In this section we show specifications
where the presence of some data ``blocks'' the retrieval of other
data. We also show that MSL's flexibility allows blocking at various
levels of granularity, from blocking entire objects to selectively
blocking subobjects that meet various conditions.

As our example, assume that source {\tt s1} can be accessed for free
whereas {\tt s2} charges a fee for providing information.  In this case,
we may wish to have mediator {\tt s} that
collects from {\tt s2} only information about reports that do not
appear in {\tt s1}.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <tr}\={\tt ep(RN) tr V>@s :-} \`\refstepcounter{query}\label{ms:priority}(MS\thequery) \\
\>{\tt <report V:\{<rn RN>\}>@s1} \\
{\tt provides(RN) :- <report \{<rn RN>\}>@s1} \\ 
{\tt <tr}\={\tt ep(RN) tr V>@s :-}\\
\>{\tt <report V:\{<rn RN>\}>@s2 \& NOT provides(RN)} 
\end{tabbing}
\vspace{-2mm}
%
The first rule declares that every {\tt report} of {\tt s1}
becomes a {\tt tr} of {\tt s}. Then the second rule
collects in {\em relation} {\tt provides} the report numbers {\tt RN}
of all reports that come from {\tt s1}.  In general, MSL
specifications may define and use relations that serve as
``intermediate'' results.  We could as well use OEM objects for
storing intermediate results (e.g., {\tt <provides RN>@t}, where {\tt
t} is an ``intermediate'' mediator) but the use of relations often
makes the specification clearer.

Finally, the third rule exports a {\tt tr} for every {\tt
report} of {\tt s2} unless the report appears in the relation {\tt
provides}. Note, we use traditional ``negation as failure''
semantics. In effect, the relation {\tt provides} prevents (or blocks)
{\tt s2} from exporting a report via the third rule if the ``same''
report has been exported by {\tt s1} via the first rule.  In
Section~\ref{negation} we demonstrate techniques used by the query
optimizer that prevent the mediator from retrieving ``blocked'' data
from the wrappers. 

%For example, if the query specifies the report
%number $r$ of the required report we may first check if $r$ is
%provided by {\tt s1} and only if it is not we check whether it is
%provided by {\tt s2}. Alternatively, assuming that {\tt s1} provides
%$r_1,\ldots,r_n$ we may ask {\tt s2} for all reports except
%$r_1,\ldots,r_n$.

There are many variations for blocking data.  In
\cite{medmaker-extended} we present an example where an external
predicate assigns ``reliability degrees'' to the source reports and
then we create a view where only the most reliable copies appear.

\subsection{Removing Inconsistencies}

In Section~\ref{group-oid} we showed that specifications such as
(MS\ref{med:simple}) may cause the same {\tt tr} to have
multiple {\tt title} objects. In this section we show that using
negation and label variables we may block subobjects that come from
one source (presumably the less reliable source) in favor of
subobjects that come from the other source (the more reliable). 
In effect, we use fine-grained blocking, i.e., blocking where 
we individually access each subobject (using label variables) and
decide whether it must be blocked or not.

For example, (MS\ref{field-priority}) resolves all inconsistencies in
favor of {\tt s1}, i.e., if {\tt s1} provides some report subobject
with label {\tt F}, then {\tt s2} should not provide a subobject with
the same label. Note, in this example we assume that no report has
two subobjects with the same label and different values.\footnote{In
\cite{medmaker-extended} we generalize MSL to handle the case where multiple
subobjects with the same label exist.}
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt (RN) tr \{<f(RN,F) F V>\}>@p} \`\refstepcounter{query}\label{field-priority}(MS\ref{field-priority}) (R\ref{field-priority}.1)\\
\>{\tt :- <report \{<rn RN> <F V>\}>@s1} \\
{\tt provides(RN,F) :- <report \{<rn RN> <F V>\}>@s1} \\
{\tt <trep}\={\tt (RN) report \{<f(RN,F) F V>\}>@p} \`(R\ref{field-priority}.3)\\
\>{\tt :- }\={\tt <report \{<rn RN> <F V>\}>@s2} \\
\>\>{\tt \& NOT provides(RN,F)}
\end{tabbing}
\vspace{-2mm}
%
The subgoal {\tt NOT provides(RN,F)} blocks (R\ref{field-priority}.3)
from exporting any subobject with label $f$ of a {\tt report} with number
$r$ if the tuple  $(r,f)$ is in {\tt provides}, i.e., if
data about the $f$ subobject of the report with number $r$
can be found in {\tt s1}.


\subsection{Handling References}
\label{handling-ref}

When we import objects from sources and fuse them into mediator
objects we must be careful with the object references that are
imported.  For example, assume that reports stored in {\tt s1} have
references to related reports, also stored in {\tt s1}. From an OEM
point of view, each report contains a subobject {\tt rel} whose value
is a set containing the {\tt s1} object ids of the referenced
reports\footnote{OEM allows top-level objects to be subobjects as
well.} (see example OEM structure of Section~\ref{oem}.) If we
are not careful when we import {\tt rel} into the mediator, we
will end up with object references that point to the original objects
of {\tt s1} and not to the corresponding fused {\tt tr}
objects.

In this section we show two ways to resolve this problem.  The first
solution is more efficient but assumes that we know which
subobjects contain references to fused objects (the subobject
{\tt rel} in our example.) The second one is less efficient but it
works even if we do not know which subobjects contain references.  The
latter solution is very useful when we integrate structures that are
deeply nested and we do not have complete knowledge of their
structure (as is the case with World-Wide-Web).

The first solution is implemented
by~(MS\ref{sol-1}). Rule~(R\ref{sol-1}.1) puts in the {\tt tr}
objects all information of the source reports with the exception of
the {\tt rel} subobject and it also adds a semantic object-id,
namely {\tt trep(RN)}, that is used for object fusion.
Rule~(R\ref{sol-1}.2) creates {\tt rel} objects and inserts in them
the corresponding {\tt tr} objects. For simplicity we omit the
corresponding rules for {\tt s2}.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <t}\={\tt rep(RN) tr \{<L X>\}>@a :-} \`\refstepcounter{query}\label{sol-1}(MS\ref{sol-1}) (R\ref{sol-1}.1) \\
\>{\tt <report \{<rn RN> <L X>\}>@s1 \& NOT L=rel} \\
{\tt <}\={\tt trep(RN) }\={\tt tr} \`(R\ref{sol-1}.2)\\
\>\>{\tt \{<rel \{<trep(REL) tr \{\}>\}>\}>@a} \\
\>{\tt :- <report \{}\={\tt <rn RN>} \\
\>\>{\tt <rel \{<report \{<rn REL>\}>\}>\}>@s1}
\end{tabbing}
\vspace{-2mm}
%
Our second solution does not rely on knowing which subobjects refer
to source objects.  The basic idea is to create two
virtual objects for each {\tt tr}.  The first virtual object
(as before) has the id {\tt trep(RN)} and its {\tt rel} subobject
contains {\tt s1} object-ids.  The second mediator object contains the
same information except that its object-id is identical to the
object-id in {\tt s1}.  The first copy is needed for fusion, since its
semantic id is used to combine fragments from other sources.  The
second copy is simply used so that ids in the first refer to valid
mediator objects.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt (RN) tr \{<L X>\}>@a :-} \`\refstepcounter{query}\label{sol-2}(R\ref{sol-2}.1)\\
\>{\tt <report \{<rn RN> <L X>\}>@s1} \\
{\tt <O tr}\={\tt\ V>@a :- <tr V:\{ <rn RN> \}>@a} \`(R\ref{sol-2}.1)\\
\>{\tt \& <O report \{<rn RN>\}>@s1}
\end{tabbing}
\vspace{-2mm}
%
The first rule (and the analogous one for {\tt s2} that is not shown)
generates the first copy of each {\tt tr} fused object.  (Note
that these objects contain {\tt s1} ids.)  The second rule generates
the copy objects and simply changes the id.  If fused objects are
expected to contain {\tt s2} ids, then another rule would be needed to
generate virtual copies with {\tt s2} ids.  Note that we only create
copies of the top-level {\tt tr} objects; these ``reuse'' the
same subobjects, such as {\tt title}.  Furthermore, the copies are
virtual.

In summary, this section illustrated how fusion can be specified with
MSL.  In \cite{medmaker-extended} we give additional examples and
discuss how fusion can be done when there are no keys (like report
number) to aid us.

\begin{figure}
\centerline{\psfig{figure=msiarch.ps,height=2.0in}}
\caption{The basic architecture of MSI}
\label{MSI-arch}
\end{figure}

\section{Query Processing}
\label{impl}

In \cite{medmaker-no-oid} we describe how the {\em Mediator
Specification Interpreter (MSI)}
processes queries in the absence of object-id's and fusion.  In this
section we focus on the system extensions for processing specifications
with object-id's (and hence fusion).
The extended MSI has the following four components (see
Figure~\ref{MSI-arch}):
\begin{enumerate}
%
\item The {\em Normalizer} reduces the query and the specification into
a normal form that facilitates the next steps when semantic ids
are involved.
%
\item The {\em Query Decomposer and Algebraic Optimizer (QD\&AO)} 
reads the query and the mediator specification and produces a {\em
logical datamerge program} that determines, at a logical level, how the source
objects are combined to construct the required query.
%
\item The {\em Plan Generator}
develops 
%an {\em execution plan} for obtaining and combining the
%objects specified by the datamerge program.  The plan, called 
the {\em physical datamerge program}, which specifies in detail the execution
strategy that will be used, i.e., what queries will be sent to the
sources, and so on.
%in what order they will be sent, and how the results of the
%queries will be combined in order to derive the result.
%
\item The {\em Datamerge Engine} executes the physical datamerge 
program and produces the result.
%
\end{enumerate}
%
In the rest of this section we show how the first three components
operate, using extensions of resolution, unification and subsumption
from classical deductive systems.  We do not discuss here how the
fourth component (datamerge engine) works, since object-id based
fusion does not require any major changes.  In
Section~\ref{incomplete-schema} we discuss novel optimization
techniques for the algebraic optimizer and plan generator.  These
techniques are specific to dealing with fusion of semi-structured
information.  As stated earlier, our goal here is to explain the
fundamental ideas mainly through examples, leaving the full details
for ~\cite{medmaker-extended} (or in the actual implementation code
that will be ftp-available soon).

\subsection{Normalization, Query Decomposition, and Algebraic Optimization}
\label{qd-ao}
The top two components of our system formulate a {\em logical
datamerge program} from a query and a mediator specification.  Recall,
the query refers to mediator objects. The QD\&AO transforms the query
into a logical datamerge program that refers to source objects
only. More precisely, a logical datamerge program is a collection of
rules whose tails refer to the source object structures and whose
heads describe the object structure of the answer objects.

Before the QD\&AO is invoked, the normalizer transforms queries and
mediators into {\em normal form MSL}.  Normal form MSL 
patterns always have three fields and certain
constructs (like {\tt V:\{<title 'a'>\}}) are not allowed.  Having
fewer and more regular constructs simplifies the query processing work
that follows.  In the extended version of the paper
\cite{medmaker-extended} we give the syntax of full and reduced MSL
and present an algorithm for converting expressions into normal form
MSL.  As an example, the algorithm converts the query (Q\ref{q-abc})
into the query (Q\ref{qn-abc}).
%
\vspace{-2mm}
\begin{tabbing}
{\tt <X tr V> :- <X tr V:\{<title 'a'>\}>@m} \`\refstepcounter{query}\label{q-abc}(Q\ref{q-abc}) \\
{\tt <X }\={\tt tr \{<Void Vl Vv>\}> :-} \`\refstepcounter{query}\label{qn-abc}(Q\ref{qn-abc})\\
\>{\tt <X tr \{<T2 title 'a'> <Void Vl Vv>\}>@m}
\end{tabbing}
\vspace{-2mm}
%
Then QD\&AO generates a logical datamerge
program by matching the query tail conditions with rule heads.  The
process considers each condition $c$ in the query tail, starting from
the leftmost.  
%(In our initial example there is only one condition,
%but later examples will show multiple conditions.)  
Condition $c$ is compared against rule heads; $c$ matches a rule $r$
if the rule can produce objects that satisfy the condition.  Each
successful match produces a {\em unifier} that describes the match
between $c$ and $r$.  For each unifier, we replace the condition $c$
by conditions on the sources specified in $r$ (see below).  In the
tail of this datamerge rule we still have the remaining query tail
conditions which may refer to mediator objects.  For each of these, we
repeat the process of unifying them against some mediator rule until
the tail of the datamerge rule only refers to objects at the
sources.\footnote{It is easy to see that in the absence of recursion
this process terminates. In the presence of recursion more complex
resolution strategies are required.  Also, note that the matching of query
conditions with rules corresponds to resolution of Horn clauses,
whereas the unifiers that we use are extensions of unifiers of first
order clauses.}

To illustrate consider the following mediator (MS\ref{m1}) that
contains a single rule.
%(Note, there is no information fusion in this example.)
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt (RN) tr \{<O L X>\}>@m1 :-} \` \refstepcounter{query}\label{m1}(MS\ref{m1}) (R\ref{m1}.1)\\
\>{\tt <r \{<rn RN> <O L X>\}>@s1}
\end{tabbing}
\vspace{-2mm}
%
Let us now consider the query (Q\ref{q123}) that retrieves the {\tt tr}
objects where the object-id is {\tt trep('123')}.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt ('123') tr V> :-} \`\refstepcounter{query}\label{q123}(Q\ref{q123}) \\
\>{\tt <trep('123') tr V>@m1}
\end{tabbing}
\vspace{-2mm}
%
The match of this query and
specification~(MS\ref{m1}) results in the single unifier $\theta$ where
\[\theta=[ (R\ref{m1}.1): {\tt RN} \mapsto {\tt '123'}, {\tt V} \mapsto \{{\tt <O\ L\ X>}\} ]\]
$\theta$ maps the variables to the left of $\mapsto$ to the
constructs to the right of $\mapsto$. In general, variables map to
constants, variables, terms, or set patterns of the form $\{<o_1\ l_1\
v_1>\ldots <o_n\ l_n\ v_n>\}$.  Note, the latter case (mapping to set
patterns) differentiates our unifiers from unifiers of first-order
logic.  The unifier also contains the name~(R\ref{m1}.1) of the rule
that matched to the query.

After the unification, we apply $\theta$ to the query and the rule
and we replace the transformed query condition with the transformed rule tail
of~(R\ref{m1}.1).
When $\theta$ is applied to the query head
{\tt V} is substituted by {\tt \{<O L X>\}}.  Similarly,
applying $\theta$ to the rule tail of (R\ref{m1}.1),
we replace {\tt RN} by {\tt '123'}. Thus, we derive datamerge rule
(DR\ref{m1-dr}).
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt ('123') tr \{<O L X>\}> :-} \`\refstepcounter{dr}\label{m1-dr}(DR\ref{m1-dr})\\
\>{\tt <r \{<rn '123'> <O L X>\}>@s1}
\end{tabbing}
\vspace{-2mm}
%

{\bf Formal Specification of Unifiers:}
To define the matching process more precisely,
we give a few additional details.
The notation $\theta(e)$ represents the expression $e$ where
the substitutions indicated by unifier $\theta$ have been performed.
A condition $e_1$, where each set pattern contains at most
one subobject pattern, {\em matches with the head} $e_2$ of rule $r$
if there is {\em a unifier $\theta$ from
$e_1$ to $e_2$}, as described by Definition~\ref{defn:unifier} below.
(Note, both $e_1$ and $e_2$ are MSL patterns.)

\begin{definition}{Unifier $\theta$ from $e_1$ to $e_2$}
\label{defn:unifier}
A mapping $\theta$ is a unifier from $e_1$ to $e_2$
if the pattern $\theta(e_1)$ {\em is included in} the
pattern $\theta(e_2)$, as described by Definition~\ref{defn:included}.
\end{definition}

\begin{definition}{Pattern $e_1$ is included in $e_2$}
\label{defn:included}
A pattern $e_1$ is included in a pattern $e_2$ if and only if
\begin{tabbing}
(a) \=$e_1$ has identical object-id and label fields as $e_2$ \\
(b) \>{\em if} the value field of $e_1$ is {\tt \{$e_1^1$\}}\\
\>{\em then }\= the value field of $e_2$ is {\tt \{$e_2^1$,$\ldots$,$e_2^m$\}}\\
\>\> and there is a pattern $e_2^j,j=0,\ldots,m$ such that\\
\>\> $e_1^1$ is included in $e_2^j$. \\
\>{\em else} $e_1$ and $e_2$ have the same value field \\
\>{\em or} the value field of $e_1$ is {\tt \{\}} and \\
\>\> the value field of $e_2$ is a set pattern \\
\end{tabbing}\vspace{-0.3in}
\end{definition}

%For example, the condition of query~(Q\ref{q123}) matches
%with~(R\ref{m1}.1) because the unifier $\theta$ maps the condition to
%the rule head.
%This is because the pattern
%{\tt $\theta($<trep('123') tr V>$)=$<trep('123') tr \{<O L X>\}>}
%is included in the pattern {\tt $\theta($<trep(RN) tr \{<O L X>\}>$)=$
%<trep('123') tr \{<O L X>\}>}.
%(In this example the patterns are
%identical but this is not necessary in general.)

The algorithm for computing the unifiers
from a pattern $s$ to a pattern $r$ and the algorithm for
applying a unifier $\theta$ to a pattern $p$ are given in the extended
version of this paper \cite{medmaker-extended}. Using these algorithms it is
straightforward to develop datamerge programs (as described above).
Note, computing unifiers is important not only for developing
datamerge programs but also for performing the subsumption based
optimizations described later.


\subsection{Resolution in the Presence of Fusion}
\label{extend}

Object-id based fusion introduces additional complexity to the QD\&AO process
because multiple rules or multiple instantiations of the same rule may
contribute to the same mediator object. 
This is more challenging because we have to simultaneously match
the query tail conditions with the heads of more than one rule.
In this section, we generalize our QD\&AO algorithm to cover this case.

Let us consider mediator (MS\ref{med:simple}) of Section~\ref{group-oid}
that merges information from sources {\tt s1} and {\tt s2}.
The first step is to convert the rules to normal form MSL.
At the same time we
rename variables so that no two rules have common variables.
%this is to avoid confusion when rules are merged into
%a single datamerge rule.
We have also abbreviated some labels;
this is just to have more compact patterns in this paper.
\vspace{-2mm}
\begin{tabbing}
{\tt <t}\={\tt rep(RN1) tr }\={\tt \{<T1 title T>\}>@m} \`\refstepcounter{query}\label{simple}(MS\ref{simple}) (R\ref{simple}.1) \\
\>{\tt :- <Ro1 r \{<RNo1 rn RN1> <T1 title T>\}>@s1} \\
{\tt <t}\={\tt rep(RN2) tr \{<Poid postscript P>\}>@m} \`(R\ref{simple}.2)\\
\>{\tt :- <Ro2 r \{}\={\tt <RNo2 rn RN2>}\\ 
\>\>{\tt <Poid postscript P>\}>@s2}
\end{tabbing}
\vspace{-2mm}
%
Rules~(R\ref{simple}.1) and~(R\ref{simple}.2) contribute information
to the same {\tt tr} objects. Furthermore, different instantiations of
the same rule may contribute information to the same {\tt tr} object.
For example, assume that {\tt s1} has two {\tt r} objects for the
same report number (the source may have duplicates for the same report).
Then rule~(R\ref{simple}.1) will have two different
instantiations with the same {\tt RN1} binding and
possibly different {\tt T} bindings.
These two instantiations will both contribute information to
the same {\tt tr}.

Let us now submit to {\tt m} query (Q\ref{qn-abc}) which asks for all
the subobjects of the {\tt tr} objects where the title is {\tt 'a'}.
Since the subobjects of the query may come from different rules, the normalizer
rewrites query (Q\ref{qn-abc}) as (Q\ref{qn-abc-split}):
%
\vspace{-2mm}
\begin{tabbing}
{\tt <X }\={\tt tr \{<Void Vl Vv>\}> :- } \`\refstepcounter{query}\label{qn-abc-split}(Q\ref{qn-abc-split})\\
\>{\tt <X r \{<T2 title 'a'>\}>@m} \\
\>{\tt \& <X r \{<Void Vl Vv>\}>@m}
\end{tabbing}
\vspace{-2mm}
%
In this transformed form, we break up the tail so that
every set pattern {\tt \{ ... \}} contains exactly
one object pattern {\tt < ... >}.
%Such a transformation is straightforward.\footnote{It
%is sometimes possible to avoid this step,
%e.g., if QD\&AO finds that no object id
%fusion is performed on objects with a given label.}

Now we can match the two patterns that appear in the
(Q\ref{qn-abc-split}) query tail to different rule heads.  Suppose
that we start by matching the first pattern of the tail, i.e., {\tt <X
r \{<T2 title 'a'>\}>}.
%\footnote{In general, the order in which we match conditions
%does not affect the final result.} 
It matches only with the head of
(R\ref{simple}.1).  This produces the unifier
$\theta_1 = [ (R\ref{simple}.1) : {\tt X}\mapsto {\tt trep(RN1)}, {\tt
T1}\mapsto {\tt T2}, {\tt T}\mapsto {\tt 'a'} ]$.
Applying $\theta_1$ to the query and the rule and replacing
the query condition, we produce 
%the following rule.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <tr}\={\tt ep(RN1) tr \{<Void Vl Vv>\}> :- } \`\refstepcounter{query}\label{dm-temp}(Q\ref{dm-temp}) \\
\>{\tt <Ro1 r \{<RNo1 rn RN1> <T1 title 'a'>\}>@s1}\\
\>{\tt \& <trep(RN1) r \{<Void Vl Vv>\}>@m}  
\end{tabbing}
\vspace{-2mm}
%
Observe that this new query has only one condition referring to
mediator {\tt m}.  To complete the process, we match the remaining
condition that refers to {\tt m} with the mediator rules.  Pattern
{\tt <trep(RN1) r \{<Void Vl Vv>\}>@m} matches with either one of the
rules of our specification.

First, it matches with
rule~(R\ref{simple}.2) thus producing the unifier $\theta_2=
[ (R\ref{simple}.2) : {\tt RN2}\mapsto {\tt RN1}, {\tt Void}\mapsto {\tt Poid}, {\tt Vl}\mapsto {\tt postscript}, {\tt Vv}\mapsto {\tt P}]$.
Second, {\tt <trep(RN1) r \{<Void Vl Vv>\}>} matches with
(R\ref{simple}.1). 
%In this case we have to take into
%consideration that multiple instantiations of rule
%(R\ref{simple}.1) may contribute {\tt title} subobjects to the same
%{\tt tr} object. 
Since we have already used (R\ref{simple}.1) for
matching the first condition of the query tail, we must not use
(R\ref{simple}.1) again for matching the second condition.
Thus, we introduce an instance of
(R\ref{simple}.1) with renamed variables (see rule~(R\ref{simple}.1.b) below) 
and we match
{\tt <trep(RN1) r \{<Void Vl Vv>\}>} against it, producing the unifier
$\theta_3 = [ (R\ref{simple}.1.b): {\tt RNb}\mapsto {\tt RN1}, {\tt Void}\mapsto {\tt T1b}, {\tt Vl}\mapsto {\tt title}, {\tt Vv}\mapsto {\tt T1b} ]$.
%Note, the second instance of rule~(R\ref{simple}.1) must
%not have the same variable names as the first one.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <tr}\={\tt ep(RNb) tr \{<T1b title Tb>\}>@m} \`(R\ref{simple}.1.b)\\
\>{\tt :- <Ro1b r \{}\={\tt <RNo1b rn RNb>}\\
\>\>{\tt <T1b title Tb>\}>@s1}
\end{tabbing}
\vspace{-2mm}
% 

Finally, for each one of the two unifiers $\theta_2$ and $\theta_3$ we
develop one datamerge rule, shown below in datamerge
program~(DP\ref{dp:simple}).  Rule (DR\ref{dp:simple}.1) is obtained
by replacing the {\tt m} condition of (Q\ref{dm-temp}) with the rule
tail of (R\ref{simple}.2) and subsequently applying $\theta_2$.
Similarly, (DR\ref{dp:simple}.2) is derived using the rule tail of
(R\ref{simple}.1.b) and unifier $\theta_3$.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <}\={\tt trep(RN1) }\={\tt tr}\`\refstepcounter{query}\label{dp:simple}(DP\ref{dp:simple}) (DR\ref{dp:simple}.1)\\
\>\>{\tt \{<Poid postscript P>\}> :-} \\
\>{\tt <Ro1 r \{<RNo1 rn RN1><T2 title 'a'>\}>@s1 \&} \\
\>{\tt <Ro2 r \{}\={\tt <RNo2 rn RN1>}\\
\>\>{\tt <Poid postscript P>\}>@s2} \\
{\tt <trep(RN1) tr \{<T1b title Tb>\}> :-} \`(DR\ref{dp:simple}.2)\\
\>{\tt <Ro1 r \{<RNo1 rn RN1> <T2 title 'a'>\}>@s1 \&} \\
\>{\tt <Ro1b r\{<RNo1b rn RN1> <T1b title Tb>\}>@s1} 
\end{tabbing}
\vspace{-2mm}
%
In this particular case one query condition matched with only one rule
head.  In the worst case each condition matches with many rule heads
potentially yielding an exponential number of datamerge rules.  More
precisely, if each of the $m$ query conditions unify with $n$ rules,
we produce $n^m$ datamerge rules.  This explosion can occur, for
instance, if the mediator specification has variables in label
positions.  We will study techniques for reducing the number of
datamerge rules in Section~\ref{incomplete-schema}.  The extended
version
\cite{medmaker-extended} presents formally the general query
decomposition and unification steps necessary for object fusion.

\subsection{Subsumption-Based Optimizations}
\label{subsumption}
Datamerge rules are evaluated by sending queries to the sources,
yielding bindings for the rule variables.  Since querying sources may
be expensive, we want to reduce the number of queries to a minimum.
QD\&AO uses two subsumption-based optimizations for this purpose.
First, QD\&AO {\em eliminates} any datamerge rule that produces data
that are subsumed by the data produced by another rule.  Second,
QD\&AO {\em reuses} rules.
That is, we may avoid issuing a query if all of its bindings
for {\em necessary} variables are obtained by another rule. Note, not all
variables are necessary for constructing the fused object.  Only
variables that appear in the rule head, or variables that join
conditions in the tail, are {\em necessary}. 

Due to space limitations
we illustrate only {\em rule reuse} and not {\em rule elimination}.
Consider datamerge rule (DR\ref{dp:simple}.1).  To
evaluate it, we need to send a query to {\tt s1} to evaluate the
condition {\tt <Ro1 r \{<RNo1 rn RN1> <T2 title 'a'>\}>@s1}.  This
query only contains one necessary variable, {\tt RN1}.  Notice that all
{\tt RN1} bindings in the above condition are also bindings of {\tt
RN1} in rule~(DR\ref{dp:simple}.2). Hence, instead of accessing {\tt
s1} twice, we can reuse the bindings retrieved for
(DR\ref{dp:simple}.2) by rewriting the datamerge program as
follows. Note, (DR\ref{dp:simple}.2.b) and (DR\ref{dp:simple}.1.b)
correspond to the rewritten versions of (DR\ref{dp:simple}.2) and
(DR\ref{dp:simple}.1).
%
\vspace{-2mm}
\begin{tabbing}
{\tt [}\={\tt <trep(RN1) tr \{<T1b title Tb>\}>} \`(DR\ref{dp:simple}.2.b)\\
\>{\tt b}\={\tt ind1(RN1)] :- } \\
\>\>{\tt <Ro1 r \{<RNo1 rn RN1> <T2 title 'a'>\}>@s1} \\
\>\>{\tt \& <Ro1 r \{<RNo1b rn RN1><T1b title Tb>\}>@s1} \\
{\tt <trep(RN) tr \{<Poid postscript P>\}>} \`(DR\ref{dp:simple}.1.b)\\
\>{\tt :- }\={\tt bind1(RN1)}\\
\>\>{\tt \& <Ro2 r \{}\={\tt <RNo2 rn RN1>} \\
\>\>\>{\tt <Poid postscript P>\}>@s2}
\end{tabbing}
\vspace{-2mm}
%
The notation {\tt [ ... ]} specifies multi-head
rules. Thus, the data retrieved from the tail of
(DR\ref{dp:simple}.2.b) is used for constructing {\tt <trep(RN) tr
\{<T1b title Tb>\}>} objects, as well as collecting the {\tt RN1}
bindings in relation {\tt bind1(RN1)} (the name {\tt bind1} is a
unique name generated by the QD\&AO.) Then, the {\tt RN1} bindings are
used by (DR\ref{dp:simple}.1.b).

We can detect the applicability of subsumption using unifiers. In
particular, a datamerge rule condition $c$ can reuse a datamerge rule
$r$ if there is a unifier $\theta$ such that every condition $c_i$ of
the tail of $r$ is included in $c$ (after we apply $\theta$) and every
useful variable of $c$ appears in the head of $r$.

{\bf Subsumption-based Optimizations in Plan Generation:}
Some subsumption-based optimizations are applied during or after
physical plan generation.  Thus, we start by briefly describing how
physical plans are obtained.
Then, in the remainder of the paper we discuss
subsumption-based optimizations to the physical plans.

Let us consider mediator (MS\ref{ms:no-schema}) (that also appeared in
non-normal form as (MS\ref{group-oid-simple}) in
Section~\ref{group-oid}). (MS\ref{ms:no-schema}) integrates documents
without explicitly mentioning their non-key attributes.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <tr}\={\tt ep(RN1) tr \{<O1 A1 X1>\}>@all} \`\refstepcounter{query}\label{ms:no-schema}(MS\ref{ms:no-schema}) (R\ref{ms:no-schema}.1) \\ 
\>{\tt :- <Ro1 r \{<RNo1 rn RN1> <O1 A1 X1>\}>@s1} \\
{\tt <trep(RN2) tr \{<O2 A2 X2>\}>@all} \`(R\ref{ms:no-schema}.2) \\
\>{\tt :- <Ro2 r \{<RNo2 rn RN2> <O2 A2 X2>\}>@s2}
\end{tabbing}
\vspace{-2mm}
%
Let us assume that query (Q\ref{year-95}) is sent to mediator 
(MS\ref{ms:no-schema}).
%
\vspace{-2mm}
\begin{tabbing}
abc\= \kill
{\tt <X }\={\tt tr \{<Void Vl Vv>\}> :-} \`\refstepcounter{query}\label{year-95}(Q\ref{year-95}) \\
\>{\tt <X tr \{<Y year '95'> <Void Vl Vv>\}>@m} 
\end{tabbing}
\vspace{-2mm}
%
The label {\tt year} may come either from {\tt s1} or {\tt s2}.
This intuition is captured by the standard query/rule matching process
(see Section~\ref{qd-ao})
that results in the datamerge program (DP\ref{dp:no-schema}) of
Figure~\ref{fig:dp:no-schema}.
%

\begin{figure}
\vspace{-2mm}
\begin{tabbing}
{\tt [}\={\tt <trep(RN1) tr \{<O1 A1 X1>\}> } \`\refstepcounter{query}\label{dp:no-schema}(DP\ref{dp:no-schema}) (DR\ref{dp:no-schema}.1) \\
\>{\tt b}\={\tt ind1(RN1)] :- } \\
\>\>{\tt <Ro1 r \{<RNo1 rn RN1> <Y year '95'>\}>@s1} \\
\>\>{\tt \& <Ro1b r \{}\={\tt <RNo1b rn RN1> <O1 A1 X1>\}>@s1} \\
{\tt <trep(RN1) tr \{<O2 A2 X2>\}> :-} \`(DR\ref{dp:no-schema}.2) \\
\>\>{\tt bind1(RN1)} \\
\>\>{\tt \& <Ro2 r \{<RNo2 rn RN1> <O2 A2 X2>\}>@s2} \\
{\tt [<}\={\tt trep(RN2) tr \{<O2 A2 X2>\}>} \`(DR\ref{dp:no-schema}.3)\\
\>{\tt bi}\={\tt nd2(RN2) ] :- } \\
\>\>{\tt <Ro2 r \{<RNo2 rn RN2> <O2 A2 X2>\}>@s2} \\
\>\>{\tt \& <Ro2b r \{}\={\tt <RNo2b rn RN2>}\\ 
\>\>\>{\tt <Y year '95'>\}>@s2} \\

{\tt <trep}\={\tt (RN2) tr \{<O1 A1 X1>\}> :-} \`(DR\ref{dp:no-schema}.4)\\
\>{\tt bind2(RN2)} \\
\>{\tt \& <Ro1 r \{<RNo1 rn RN2> <O1 A1 X1>\}>@s1}
\end{tabbing}
\vspace{-2mm}
\caption{Datamerge Program}
\label{fig:dp:no-schema}
\end{figure}

The cost based optimizer receives the logical datamerge program and
creates a {\em physical datamerge program} that consists of a list of
(possibly parameterized) queries that will be sent to the sources,
along with a description of how to combine query results.  To
illustrate, let us consider the datamerge
program~(DP\ref{dp:no-schema}).  (PDP\ref{pdp:ns}), in
Figure~\ref{fig:pdp:no-schema}, is one of the possible physical datamerge
programs (from now on referred as physical programs) for
(DP\ref{dp:no-schema}).

%Our goals are to formulate queries for obtaining from the sources the
%bindings required by the rules and to decide how to join related data
%of two sources (e.g., use nested loops join or local join).  
The notation {\tt @(Q\ref{ns-q1},s1)} in physical rule
(PDR\ref{pdp:ns}.1) indicates that
query (Q\ref{ns-q1}) should be sent to {\tt s1} and
the result should be treated as a ``data source'' for the rule.
The query obtains from {\tt s1} all data about
reports with year {\tt '95'}.
Rule (PDR\ref{pdp:ns}.1) then saves
the retrieved reports and stores the {\tt RN} bindings in {\tt bind1}.

The {\tt =>} annotation
in rule (PDR\ref{pdp:ns}.2) indicates that we perform a
nested-loops join of {\tt bind1(RN)} and {\tt <trep(RN) L
V>@(Q\ref{ns-q2},s2)}.
That is, for every binding $r$ of {\tt RN}
in {\tt bind1}, we instantiate a
parameterized query~(Q\ref{ns-q2}), by replacing {\tt RN} with $r$,
and we send the instantiated query to {\tt s2}.
Similarly, the {\tt
local} annotation
that appears in (PDR\ref{pdp:ns}.4) indicates that we perform a
local join of {\tt bind2(RN)} with {\tt <trep(RN) L
V>@(Q\ref{ns-q4},s1)}.
The join policy decision is made by
estimating the cost of each option using information about the sources.
%(e.g., ``does the source have an index on report number?'', ``what is
%the expected cardinality of {\tt bind1(RN)}?'', and so on.)  
We will not deal in this paper with these cost-based optimization problems.

\begin{figure}
\begin{tabbing}
{\tt [<t}\={\tt rep(RN) L V>, bind1(RN)]} \`\refstepcounter{query}\label{pdp:ns}(PDP\ref{pdp:ns}) (PDR\ref{pdp:ns}.1)\\
\>{\tt :- <trep(RN) L V>@(Q\ref{ns-q1},s1)} \\
{\tt <trep(RN) L V> :- } \`(PDR\ref{pdp:ns}.2)\\
\>{\tt bind1(RN)} \\
\>{\tt \&(=>) <trep(RN) L V>@(Q\ref{ns-q2},s2)} \\
{\tt [<trep(RN) L V>, bind2(RN)] :-} \`(PDR\ref{pdp:ns}.3)\\
\>{\tt <trep(RN) L V>@(Q\ref{ns-q3},s2)} \\
{\tt <trep(RN) L V> :- } \`(PDR\ref{pdp:ns}.4)\\
\>{\tt bind2(RN)} \\
\>{\tt \&(local) <trep(RN) L V>@(Q\ref{ns-q4},s1)} \\

{\tt <trep(RN) tr \{<O1 A1 X1>\}> :-} \`\refstepcounter{query}\label{ns-q1}(Q\ref{ns-q1})\\
\>{\tt <r \{<rn RN> <Y year '95>\}>@s1} \\
\>{\tt \& <r \{<rn RN> <O1 A1 X1>\}>@s1} \\

{\tt <trep(RN) tr \{<O2 A2 X2>\}> :-} \`\refstepcounter{query}\label{ns-q2}(Q\ref{ns-q2})\\
\>{\tt <r \{<rn \$RN> <O2 A2 X2>\}>@s2} \\

{\tt <trep(RN) tr \{<O2 A2 X2>\}> :-} \`\refstepcounter{query}\label{ns-q3}(Q\ref{ns-q3})\\
\>{\tt <r \{<rn RN> <Y year '95'>\}>@s2} \\
\>{\tt \& <r \{<rn RN> <O2 A2 X2>\}>@s2} \\
{\tt <trep(RN) tr \{<O1 A1 X1>\}> :-} \`\refstepcounter{query}\label{ns-q4}(Q\ref{ns-q4})\\
\>{\tt <r \{<rn RN> <O1 A1 X1>\}>@s1}
\end{tabbing}
\vspace{-2mm}
\caption{Physical Datamerge Programs}
\label{fig:pdp:no-schema}
\end{figure}
%

{\bf Applying Query Subsumption on the Plan:} Earlier we showed how
to eliminate redundant rules from a datamerge program and how to reuse
the results of some rules. We now revisit subsumption and demonstrate
that once the actual queries have been formulated some query calls may
be saved by reusing the results of other queries.

For example, query~(Q\ref{ns-q1}) is subsumed by query~(Q\ref{ns-q4})
because (Q\ref{ns-q4}) retrieves all the reports of {\tt s1} whereas
(Q\ref{ns-q1}) retrieves only the reports with year {\tt '95'}. Furthermore,
once we have the result of (Q\ref{ns-q4}) we may locally apply
the condition on {\tt year} and hence compute the result of (Q\ref{ns-q1}).
The optimizer captures this relationship between (Q\ref{ns-q1}) and
(Q\ref{ns-q4}), eliminates (Q\ref{ns-q1}), and modifies
rule~(PDR\ref{pdp:ns}.1) to use the subsuming query~(Q\ref{ns-q4}).
Note the condition on {\tt year} that is applied on the result 
of~(Q\ref{ns-q4}).
%
\vspace{-2mm}
\begin{tabbing}
{\tt [<trep}\={\tt(RN) L V>, bind1(RN)] :-} \`(PDR\ref{pdp:ns}.1.b)\\
\>{\tt <trep(RN) L \{<Y year '95'>\}>@(Q\ref{ns-q4},s1)}
\end{tabbing}
\vspace{-2mm}
%
Detecting query subsumption is again done through unifiers.
In particular, a query $q$ is subsumed by a query $q'$ if there is
a unifier $\theta$ that maps the tail of $q'$ to the tail $q$ 
and furthermore all variables that appear in $\theta({\em head}(q))$
also appear in $\theta({\em head}(q'))$. With a few extensions to
the unification process, we can also derive the condition that has to
be applied on the subsuming query.

Note that query subsumption optimization can only be performed after
we know which queries will be sent to sources, i.e., after the
physical plan is generated.  The subsumption optimizations
of QD\&AO could also be performed at this latter stage, but
it is much better to do them as early as possible to simplify plan
generation.  This leads to the following strategy: first do in QD\&AO as many
subsumption optimizations as possible, then generate plans, and finally
perform the remaining subsumption optimizations.



\section{Advanced Optimization Techniques}
\label{incomplete-schema}

In this section we describe further optimizations that are performed by
the algebraic optimizer and the plan generator.
The first two techniques (Section~\ref{learning}) are
useful for reducing the exponential number of datamerge rules that can
be generated when there is incomplete information about the sources.
The third technique (Section~\ref{negation}) deals with
negation and blocking operations.

\subsection{Reducing the number of datamerge rules}
\label{learning}
Mediator (MS\ref{ms:no-schema}) and query (Q\ref{year-95})
illustrated the problem of exploding conditions.
Since the label {\tt year} could come either from {\tt s1} or
{\tt s2}, the condition on {\tt year} had to be pushed to both
{\tt s1} and {\tt s2}.
One of the nice features of MSL is that it does not {\em force} us to specify
where data might come from, but this flexibility then forces
the system to explore all possible options.

In the general case we may have a query requiring fused objects
satisfying a conjunction of conditions $c_1,...,c_n$,
where the object components come from sources
$s_1,\ldots,s_m$.
If the specification does not state what conditions should
be pushed to what sources, resolution leads
to an exponential number of datamerge
rules, corresponding to all possible ways of splitting $c_1,...,c_n$
between the sources.
The subsumption techniques of Section~\ref{impl} can help reduce
the amount of work, but we may still have too many queries for the sources.

One way to reduce the number of queries is to determine in
advance those that will return an empty answer because no source
objects could ever match.
For instance, in our example,
if we know that {\tt year}
information may not come from {\tt s1} then we can remove
rules~(DR\ref{dp:no-schema}.1) and~(DR\ref{dp:no-schema}.2)
from (DP\ref{dp:no-schema})
since they both require that {\tt year} is found at {\tt s1}. 

Even though the mediator does not have a ``schema'' dictating
what type of information a source may have,
it could achieve the same effect by {\em asking at run time}
if source {\tt s1} has any objects with {\tt year} label.
If no such objects exist at {\tt s1},
the mediator can eliminate all datamerge rules that require a
{\tt year} at {\tt s1}. (In practice,
we can interleave query decomposition with this label checking,
so the rules would never have to be created.)

The label queries we have described could be addressed to a {\em
lexicon service} residing either at the source or the wrapper for the
source.  The service could answer label queries based on its knowledge
of the domain (e.g., only medical terms defined in a known dictionary
are used as labels in a given structure), based on index structures
(e.g., the source provides a label index for speeding up queries), or
based on a local schema if there happens to be one (e.g., the data at
this source is stored in a relational database.)  There are many
variations to the idea of lexicon services;
\cite{medmaker-extended} presents some.

\subsection{Refraining from Simultaneously Pushing Conditions}
We now briefly consider a second technique for reducing the number of
datamerge rules.  The key observation is that pushing {\em all}
conditions to the sources may not be (and most often is not) the best
plan.  At first sight this appears counter-intuitive because in
conventional query optimization it is always beneficial to evaluate
selection conditions as early as possible.  However, the absence of
complete knowledge about the structure of the sources prompts us
to try all possible ways of splitting the conditions among the sources,
hence producing a potentially inefficient plan.

Let us present an alternative for processing a query with $n$
conditions to $m$ sources without pushing all conditions.  We can
answer the query by (i) fetching from each source all objects
satisfying any one of the $c_i$ conditions and (ii) fusing these
objects at the mediator, and (iii) selecting those fused objects that
satisfy all the $c_i$ conditions.  For example, suppose that in a
query like (Q\ref{year-95}) we look both for reports with {\tt year}
equal to 95 and {\tt topic} equal to ``databases.''  Our original
policy, that we call conjunctive, would involve datamerge rules that
split the two conditions among the sources in all possible
ways. Instead, we send a single query to each source asking for all
documents that either have {\tt year} 95 or {\tt topic} databases.
After constructing the fused objects, we filter out those that do not
meet both conditions.  This policy, which we call disjunctive (we are
sending disjunction of atomic conditions to the sources), beats the
original conjunctive policy when the number of sources is larger than
the number of conditions.  

In \cite{medmaker-extended} we present more alternatives. Currently we
are working on the evaluation of these alternatives and the implementation
of an optimizer that efficiently chooses among these alternatives.

\subsection{Optimization of Negation Operations}
\label{negation}

In Section~\ref{block-and-inc} we argued that information blocking is
effective for removing inconsistencies and establishing
priorities between information drawn from various sources. In
general, all specifications involving information blocking contain
{\tt NOT} conditions that guide blocking. The
performance challenge is to avoid issuing queries that retrieve
information that is blocked. The interpreter can
reduce to a minimum the number of queries sent to the sources
and the amount of retrieved data, for a wide class of queries
and information blocking mediator specifications. Due to space
limitations, here we only sketch the techniques that are used.

Let us consider mediator specification~(MS\ref{ms:priority}) that exports all
{\tt s1} reports and {\tt s2} reports
with numbers that do not appear in {\tt s1}.
In the simplest
case, the query specifies the required report
number {\tt RN}, say {\tt '123'}.
In this case we develop a physical datamerge program
that contains (PDR\ref{not-123}). The important point is that we
evaluate the {\tt NOT provides('123')} condition of (PDR\ref{not-123})
before we emit the query {\tt Q} that obtains data for {\tt '123'}
from {\tt s2}.  (We omit {\tt Q}.) . Thus, if {\tt '123'} is provided
by {\tt s1} we avoid sending {\tt Q} to {\tt s2}.
%
\vspace{-2mm}
\begin{tabbing}
{\tt <trep}\={\tt (RN) tr \{<O2 A2 X2>\}> :- } \`\refstepcounter{query}\label{not-123}(PDR\ref{not-123})\\ 
\>{\tt NOT provides('123') \&} \\
\>{\tt <trep(RN) tr \{<O2 A2 X2>\}>@(Q,s2)} 
\end{tabbing}
\vspace{-2mm}
%
In other cases, avoiding the retrieval of ``blocked data'' is more
complicated, or even impossible.  For example, consider
query~(Q\ref{qn-abc}) that requests reports with title {\tt 'a'}.
The best strategy here depends on the expected number of matching
reports at each site.  For instance, assume that the number of {\tt
'a'} reports retrieved from {\tt s1} is not large.  To be specific,
say that only reports {\tt '123'} and {\tt '136} have title {\tt
'a'}.  In this case the best strategy is probably to send to {\tt
s2} query~(Q\ref{not-binding}) with explicit negation conditions for
each one of the {\tt s1} reports. (In general it has a {\tt NOT
RN=$b$} for every $b$ that is a member of {\tt provides}.)
%
\vspace{-2mm}
\begin{tabbing}
{\tt <tr}\={\tt ep(RN) tr \{<O2 A2 X2>q\}> :-} \`\refstepcounter{query}\label{not-binding}(Q\ref{not-binding})\\
\>{\tt <Ro2 r \{<RNo2 rn RN> <O2 A2 X2>\}>@s2} \\
\> {\tt \& NOT RN='123' AND \& RN='136'}
\end{tabbing}
\vspace{-2mm}
%
If the number of reports retrieved from {\tt s1} is large
it may be preferable to ship relation {\tt provides}
to {\tt s2} and then send to {\tt s2} a query that requests all reports
whose report numbers do not appear in {\tt provides}.
If {\tt s2} is not willing to accept a full relation from the
mediator, another option is to retrieve from {\tt s2} all reports with 
title {\tt 'a'} and test locally whether these reports are also 
provided from {\tt s1}.
If they are, the {\tt s2} version can be discarded.
In this last case, blocking could not really be exploited to
reduce the data retrieved from {\tt s2}.

\section{Discussion and Related Work}
\label{conc}

In this paper we have shown that the OEM data model and the MSL
mediator specification language, each extended with semantic
object-ids, provide a conceptually simple yet powerful framework for
object fusion. The rules use a small but general set of features that
consists of: (a) semantic object-id's, (b) negation, and (c) variables
that can range over object-id's, labels, and values.  Multiple MSL
rules can monotonically and independently add information to fused
objects by specifying the semantic object-id of the fused object. The
combined use of negation and attribute variables allows the
specification of complex conflict resolution schemes.  
%Finally, fusion
%specifications can be {\em adapted} to various levels of knowledge about the
%sources.  At one end, the designer knows little about the contents and
%structure (if any) of a source, so he writes ``generic''
%specifications that can handle any structure.  At the other end, the
%source has some known regularity, so the designer can improve the
%quality and run-time efficiency of object fusion.

Our work builds on many prior results and experiences,
and we briefly review here some of them.
Many projects have dealt with data integration and fusion (e.g., 
\cite{LitwinMarkRoussopoulos,Pegasus,Garlic,HERMES,HammerMcLeod,DISCO,KimResolve}.) Most of
them base fusion on a precise description of the schemas exported by
the sources and present classifications and resolution techniques for
the various schematic and semantic conflicts that may be found in the
schemas \cite{KimResolve}.  Unlike these approaches, in the present
paper, we assume minimal knowledge of the structure and contents of
the sources.

% query and integration for semi-structured data

%Querying and integrating semistructured data is also considered in
%\cite{Garlic,LOREL,AbiteboulCluetMilo,BunemanDavidsonSuciu}.
%We believe that approaches based on the relational model (and
%corresponding view definition languages) are not applicable here.
%(Indeed, one may argue that they are insufficient even for relational
%database integration
%\cite{KrishnamurthyLitwinKent}.)  Object-oriented database systems
%do provide more flexibility.  However, their strict type system
%sometimes is a handicap \cite{Garlic,BunemanSusan}.  Also, primitives
%for data integration found in these systems are still quite limited,
%with some exceptions like work on views in the context of OQL (e.g.,
%\cite{AbiteboulSouzaDelobel}).

MSL is an object-oriented logic, but has certain simplifying features.
In particular, a number of problems are avoided by not considering
sets as first-class citizens.  (Variables may explicitly refer only to
existing sets of objects.)  Indeed, in absence of negation and
semantic object-id's, MSL can be viewed simply as a variant of datalog
(see \cite{PDKS2}).  In the extended version of paper
\cite{medmaker-extended} we present the reduction of MSL to datalog
with function symbols and negation.  In absence of recursion, MSL can
be viewed as a variant of OQL \cite{ODMG}.  However, unlike datalog
and OQL, MSL makes it possible to handle both unstructured and
structured data.

MSL's handling of semantic object-ids is based on a particular use of
Skolem functions as first introduced in object-oriented systems in
\cite{O-Logic} and refined in
\cite{KiferKimSagiv,HiLog}. Automatic creation and
manipulation of object-id's based on Skolem functors are considered in
depth in \cite{HullYoshikawa}.
\cite{LakshmananSadriSubramanian,KrishnamurthyLitwinKent} 
propose logics and languages with higher-order syntax and first-order
semantics for schema integration and evolution and also demonstrates
the need for higher order views. MSL achieves the same effects with
the use of label variables.

Finally, though MSL can be reduced to a variant of Datalog
\cite{PDKS2}, query execution against mediators cannot be achieved by
a simple modification of datalog evaluation mechanisms because the
environment (i.e., remote heterogeneous sources) is radically
different from a conventional database.  
%In this paper we presented a
%variant of top-down depth-first resolution to formulate the queries
%that will be sent to the sources and also push conditions to the
%sources.  Beyond this, we also investigated optimizations needed for
%reducing the number and volume of data that are retrieved from the
%sources during object fusion.

%In closing this paper we briefly comment on some interesting cases
%that require further study: First, objects sometimes do not have well
%defined keys.  In this case, deciding if two objects match requires
%complex ``similarity'' predicates.  We can use MSL (and external
%predicates) to define this type of fusion, but it introduces many
%problems that are beyond the scope of this paper.  Second, information
%fusion operations often require features such as aggregation, that are
%outside the scope of conjunctive rules that MSL supports.  
%Finally, MSL is not a language for the end-user.  It is a language for
%succinctly describing mediators using very few primitives.

{\bf Implementation Status:} We have developed a prototype
system that fully implements the query decomposition and evaluation
algorithm described here. It also features the subsumption based
optimizations and some of the optimization techniques of
Section~\ref{negation}.  The system has been demonstrated on a
collection of heterogeneous bibliographic sources.  We are currently
working on including the rest of the optimization techniques we have
described into the prototype. At the same time we are evaluating the
performance of the proposed plans.







{\small
\bibliography{oem}
}

\end{document}


=== sample.tex END =================================================
