\documentclass{article}

%\documentclass[10pt,twocolumn]{article}          % LaTeX 2e 
%\usepackage{mylatex8}                              % LaTeX 2e 

%\usepackage{times}                               % LaTeX 2e 

\usepackage{a4wide}

% IEEE stuff
%\usepackage{latex8}                              % LaTeX 2e 
%\usepackage{times}                               % LaTeX 2e 

%\usepackage{latexsym}
\usepackage{url}
\usepackage{pstricks,pst-node,epsf}
\usepackage{psfig}
\usepackage{fl-macros}
\usepackage[thmmarks,standard]{ntheorem}
%\usepackage[standard]{ntheorem}

\usepackage{no-bib-shortcuts}




\begin{document}

\newcommand{\myif}{\,\textsf{\textbf{if}}\,}
\newcommand{\IF}{\,\textsf{\textbf{if}}\,}


\newcommand{\ANATOM}{\textsc{anatom}}
\newcommand{\CCDB}{\ensuremath{\mathsf{CCDB}}}
\newcommand{\CM}{\ensuremath{\mathsf{CM}}}
\newcommand{\CON}{\ensuremath{\mathsf{CON}}}
\newcommand{\CS}{\textrm{CS}}
\newcommand{\Const}{\ensuremath{\mathcal{C}}}
\newcommand{\DM}{\textrm{DM}}
\newcommand{\D}{\textrm{D}}
\newcommand{\EDB}{\ensuremath{\mathsf{EDB}}}
\newcommand{\GCM}{\textrm{GCM}}
\newcommand{\IC}{\ensuremath{\mathcal{IC}}}
\newcommand{\IDB}{\ensuremath{\mathsf{IDB}}}
\newcommand{\IVD}{\ensuremath{\mathsf{IVD}}}
\newcommand{\KB}{\textrm{KB}}
\newcommand{\KIND}{\textsc{Kind}}
\newcommand{\MapD}[1]{\ensuremath{\mathrm{\Phi(\mbox{$#1$})}}}
\newcommand{\Map}{\ensuremath{\mathrm{\Psi}}}
\newcommand{\NCMIR}{\textsc{ncmir}}
\newcommand{\NI}{\noindent}
\newcommand{\OM}{\ensuremath{\mathsf{OM}}}
\newcommand{\ONTG}{\ensuremath{\mathsf{ONTG}}}
\newcommand{\ONT}{\ensuremath{\mathsf{ONT}}}
\newcommand{\QC}{\textrm{QC}}
\newcommand{\RS}{\textrm{RS}}
\newcommand{\SEM}{\textrm{SEM}}
\newcommand{\SI}{\textrm{SI}}
\newcommand{\SYNAPSE}{\textsc{synapse}}
\newcommand{\Var}{\ensuremath{\mathcal{V}}}
\newcommand{\V}{\ensuremath{\mathcal{V}}}
\newcommand{\XML}{\textrm{XML}}
\newcommand{\abstr}{\ensuremath{\mathsf{abstract}}}
\newcommand{\assoc}[1]{\ensuremath{\mathsf{#1}}}
\newcommand{\attribute}[1]{\textsf{#1}}
\newcommand{\bnot}{\texttt{\textbf{not}}}
\newcommand{\class}[1]{\textsc{#1}}
%\newcommand{\class}{\texttt{\textbf{class}}}
\newcommand{\concepts}{\ensuremath{\mathcal{C}}}
\newcommand{\concept}[1]{\ensuremath{\mathsf{#1}}}
\newcommand{\edges}{\ensuremath{\mathcal{E}}}
\newcommand{\eg}{\textit{e.g.}}
\newcommand{\elab}{\ensuremath{\mathsf{elab}}}
\newcommand{\fluents}{\ensuremath{\mathcal{F}}}
\newcommand{\func}[1]{\textsf{#1}}
\newcommand{\ghasastar}{\texttt{has\_a\_star}}
\newcommand{\ghasa}{\texttt{has\_a}}
\newcommand{\gisa}{\texttt{isa}}
\newcommand{\ic}{\texttt{\textbf{ic}}}
\newcommand{\ie}{\textit{i.e.}}
\newcommand{\instance}{\textit{instance}}
\newcommand{\map}{\texttt{map}}
\newcommand{\mc}{\ensuremath{\mathit{mc}}}
\newcommand{\method}{\textit{method}}
\newcommand{\model}[1]{\textsf{#1}}
\newcommand{\mpar}[1]{\marginpar{!!! \tiny #1}}
\newcommand{\mytexttt}[1]{\texttt{\small #1}}
\newcommand{\proc}{\ensuremath{\mathcal{P}}}
\newcommand{\relation}[1]{\ensuremath{\mathit{#1}}}
%\newcommand{\relation}{\textit{relation}}
\newcommand{\roles}{\ensuremath{\mathcal{R}}}
\newcommand{\states}{\ensuremath{\mathcal{S}}}
\newcommand{\subclass}{\textit{subclass}}
\newcommand{\tuple}{\textit{relation$_{inst}$}}
% \pagestyle{empty}


\title{\vspace*{-3em}
\bf A Model-Based Mediator System for Scientific Data Management
%\bf Scientific Data Management with Model-Based Mediators
}


\author{Bertram Lud\"ascher$^\star$ \quad \quad  Amarnath Gupta$^\star$ 
  \quad \quad Maryann E.  Martone$^\ddagger$
  \smallskip\\
  \normalsize
  \begin{tabular}{l@{~~~}c}
    $^\star$San Diego Supercomputer Center, U.C. San Diego &  {\small
    \texttt{\{ludaesch,gupta\}@sdsc.edu}} \\
  \normalsize $^\ddagger$Department of Neurosciences, U.C. San Diego&
   {\small \texttt{mmartone@ucsd.edu}}   \\
  \end{tabular}}


\date{\relax}

\maketitle




\begin{abstract}
  When federating scientific data, one is often confronted with
  ``complex multiple-world scenarios'', \ie, in which both the
  semantics of individual sources as well as the knowledge to link
  them require ``deeper modeling'' than offered by current database
  mediator systems. Based on experiences with federation of brain
  data, we present an extension called \emph{model-based mediation}
  (MBM).  In MBM data sources not only export raw data and schema
  information but \emph{conceptual models} (CMs) including domain
  semantics to the mediator, effectively lifting data sources to
  ``knowledge sources''.  This allows integrated view definitions at
  the mediator based on (i) the local CMs of registered sources and
  (ii) auxiliary domain knowledge sources called \emph{domain maps}
  (DMs) and \emph{process maps} (PMs), respectively, which act as
  ``glue knowledge sources''.  For complex scientific data sources,
  semantically rich CMs are indeed \emph{necessary} in order to
  represent and reason with scientific rationale for linking a wide
  variety of heterogeneous experimental assumptions, observations, and
  conclusions that together constitute an experimental study.  We
  illustrate the challenges using real-world examples from a complex
  neuroscience integration problem and present the methodology and
  some of our tools for model-based mediation of scientific data.
\end{abstract}





\section{Introduction}\label{sec-intro}
%\item overview, motivation: why we are different from the main stream
%  bioinf. stuff  (focus on sequence alignment, structural analysis and
%  prediction, algorithms, ...cf. TAMBIS, Carole stuff in the SIGMODREC):

%  multi-scale: senselab example vs. NCMIR, physiological
%  vs. anatomical (1 stylized image, vs. 10 terms for dendrites)

%  multi-species: human, primate, mouse, cricket

%  multi-modal: 2D images, lightmicroscopic, fMRI, 3D reconstructions,
%  ...
  
%  it is now common place that the crux is not availability of
%  information, but versatile, flexible ways to interrelate, and
%  associate data in meaningful ways ``connecting the dots''
  
%  the ``glue knowledge'' is NOT in any individual DB, but in the
%  combination of expert (``background/contex'') knowledge and DBs.
%  The goal of MBM is to take advantage of the experts' domain
%  knowledge and make it usable for queries and computations: thus, KR
%  is needed. In fact, rougly speaking: MBM = KR+DB 



Seamless data access and sharing, handling of large amounts of data,
federation and integration of heterogeneous data, distributed query
processing and application integration, data mining, and visualization
are among the common and recurring broad themes of scientific data
management in many disciplines.  A main stream of activity in the
bioinformatics domain is concerned with sequence and structural
databases such as GenBank, NCBI, PDB, SwissProt, etc.\ and much work
is devoted to algorithmic challenges stemming from problems, \eg,
efficient sequence alignment and structure prediction.  However, in
addition to the well-known challenges of main stream bioinformatics
applications such as algorithmic complexity and scalability (\eg, in
genomics), there are other major challenges that are sometimes
overlooked. These challenges arise in the context of \emph{information
  integration of scientific data} and have to do with the inherent
{semantic complexity} of (i) the actual source data, and (ii) the
``glue knowledge'' that is necessary to link the source data in
meaningful ways. We argue that traditional federated database system
architectures and those of the more recent database mediators
developed by the database community are not adequate for information
integration of complex scientific data from multiple sources. Instead,
a combination of knowledge representation and mediator technology is
necessary -- in a nutshell:

\begin{center}
  \emph{Model-Based Mediation = Knowledge Representation + Database Mediation}
\end{center}


With respect to their \emph{semantic heterogeneity} (ignoring
syntactic and system aspect), we can roughly classify information
integration/mediation scenarios (scientific or otherwise) along a
spectrum as follows. On the one end, we have \emph{simple one-world
  scenarios} such as \emph{comparison shopping} (\eg, find cheapest
books from a number of sources like \texttt{amazon.com} and
\texttt{bn.com}). Towards the middle there are \emph{simple
  multiple-world scenarios} (\eg, integrate realtor and census data in
order to annotate and rank real estate by neighborhood quality).
Further at the other end of the spectrum, we find \emph{complex
  one/multiple-world scenarios}. These are often found in scientific
data management and are the subject of this chapter.  Here ``simple''
and ``complex'' refers to the degree in which specific \emph{domain
  semantics} is required in order to be able to formalize or even
state meaningful associations and linkages between data objects of
interest -- it does {not} mean that the database and mediation
technology for realizing such mediators is simple.\footnote{quite the
  opposite: such ``simple'' mediation scenarios often pose very
  difficult technical challenges, \eg, query processing in the
  presence of limited source capabilities
  \cite{papakonstantinou-gupta-haas-DAPD-98,li-yerneni-vassalos-SIGMODDEMO-98}.}
For example, to {state} the problem what the result of an integrated
comparison shopping view should be, a basic understanding of a ``books
schema'' (title, authors, publisher, price, etc.) is sufficient. In
particular, the association operation that links objects of interest
across sources can be executed (at least in principle) as a
\emph{syntactic join} on the ISBN. Similarly, in the realtor example,
data can be joined based on ZIP code, latitude/longitude, or street
address, \ie, by \emph{spatial joins} which can be modeled as atomic
function calls to a ``spatial oracle''. To understand the basic
linkage of information objects, no ``insight'' into the details of the
spatial join is required.


This is fundamentally different for complex multiple-world scenarios
as found in many scientific domains. There, even if data is stored in
state-of-the-art (often web-accessible) databases, significant domain
knowledge is required in order to even articulate meaningful queries
{across} disciplines (or within different micro-worlds of a single
discipline); cf.\ the examples in the next section.




\paragraph{Overview.}

In this chapter, we illustrate these challenges using examples from
our ongoing collaborations with users and providers of scientific data
sets, in particular, from the Neuroscience domain
(Section~\ref{sec-neuro}). We then present a methodology called
\emph{model-based mediation} which extends current database mediator
technology by incorporating knowledge representation (KR) techniques
in order to create explicit representations of domain experts'
knowledge that can be used in various ways by ``mediation engineers''
and by the model-based mediator system itself (Section~\ref{sec-mbm}).
The goal of model-based mediation could be paraphrased as
\begin{center}
  \emph{Turning scientists' \textbf{questions} into executable
    database \textbf{queries}.}
\end{center}
In Section~\ref{sec-kr} we introduce some of the KR formalisms, \eg,
for domain maps and process maps and describe their use in model-based
mediation.  In Section~\ref{sec-tools} we present the KIND mediator
prototype and other tools being developed at SDSC and UCSD, primarily
in the context of the Neuroscience domain.  We discuss some related
work and conclude in Section~\ref{sec-conclusions}.


\section{Scientific Data Integration Across Multiple Worlds:\\  Examples
  and Challenges from the Neurosciences}\label{sec-neuro} 
% Federation of Neuroscience Data: examples, challenges, 

In this section we illustrate some of the challenges of scientific
data integration in complex multiple-world scenarios using examples
that involve different ``Neuroscience worlds''. Such examples occur
regularly when trying to federate brain data across multiple sites,
scales, and even species \cite{NPACI-Neuro}, and have led to new
research and development projects aimed at overcoming the current
limitations of biomedical data sharing and mediation \cite{BIRN-CC}.

  
\begin{figure}[t]
  \mbox{\psfig{figure=dotfiles/final_icde_example1.ps}}
\hspace*{-2em}  \fbox{\small
    \begin{tabular}[b]{l}
      Neuron $\sqsubseteq$ $\exists$has.Compartment\\
      Axon, Dendrite, Soma $\sqsubseteq$ Compartment\\
      Spiny\_Neuron $\equiv$ Neuron $\sqcap$ $\exists$has.Spine  \\
      Purkinje\_Cell, Pyramidal\_Cell $\sqsubseteq$ Spiny\_Neuron\\
      Dendrite $\sqsubseteq$ $\exists$has.Branch\\
      Shaft $\sqsubseteq$ Branch $\sqcap$ $\exists$has.Spine \\
      Spine $\sqsubseteq$ $\exists$contains.Ion\_Binding\_Protein\\
      Spine $\sqsubseteq$ Ion\_Regulating\_Component \\
      Ion\_Activity $\sqsubseteq$ $\exists$subprocess\_of.Neurotransmission\\
      Ion\_Binding\_Protein $\sqsubseteq$ Protein $\sqcap$ $\exists$controls.Ion\_Activity\\
      Ion\_Regulating\_Component $\equiv$ $\exists$regulates.Ion\_Activity\\
    \end{tabular}}
  \caption{A \emph{domain map} for \SYNAPSE\ and \NCMIR\
    {(unlabeled, gray edges $\approx$ ``isa'' $\approx$
      ``$\sqsubseteq$'')} and its formalization in description logic}
  \label{fig-two-worlds}
                                %\vspace*{-1.0em}
\end{figure}

\begin{example}[Two Neuroscience Worlds]\label{ex-two-worlds} Consider
  two Neuroscience laboratories\footnote{see \url{synapses.bu.edu}
    (\SYNAPSE) and \url{www-ncmir.ucsd.edu} (\NCMIR)} that perform
  experiments on two different brain regions.  The first laboratory,
  \SYNAPSE, studies dendritic spines of pyramidal cells in the
  hippocampus. The primary schema elements are thus the anatomical
  entites that are reconstructed from 3-dimensional serial-sections.
  For each entity (e.g., spines, dendrites), researchers make a number
  of measurements, and study how these measurements change across age
  and species under several experimental conditions.
  
  In contrast, the \NCMIR\ laboratory studies the Purkinje Cells of
  the cerebellum, inspecting the branching patterns from the dendrites
  of filled neurons, and localization of various proteins in neuron
  compartments.  The schema used by this group consists of a number of
  measurements of the dendrite branches (e.g., segment diameter) and
  the amount of different proteins found in each of these
  subdivisions.  Let us assume each of the two schemas has a class
  \mytexttt{C} having a \mytexttt{location} attribute which can have a
  value like \mytexttt{"Pyramidal Cell dendrite"} and \mytexttt{"Purkinje
    Cell"}, respectively.

How are the schemas of \SYNAPSE\ and \NCMIR\ related?  Evidently they
carry {distinctly different information} and do not even enter the
purview of the schema conflicts usually studied in databases
\cite{kashyap96:_seman_schem_simil_datab_objec}. To the scientist
however, they are related because of the following reason: Release of
calcium from spiny dendrites occurs as a result of neurotransmission
and results in changes in spine morphology (sizes and shapes obtained
from \SYNAPSE).  Propagation of calcium signals throughout a neuron
depends upon the morphology of the dendrites, the distribution of
calcium stores in a neuron and the distribution of calcium binding
proteins, whose subcellular distribution for Purkinje cells are
measured by \NCMIR.
\end{example}

Thus, a researcher who wanted to model the effects of
neurotransmission in hippocampal spines would get structural
information on hippocampal spines from \SYNAPSE\ and information about
the types of calcium binding proteins found in spines from \NCMIR.
Note that neither of the sources contains information that would allow
a mediator system to bridge the ``semantic gap'' between them.
Therefore we need, independent of the observed experimental raw data
of each source, \emph{additional domain knowledge} in order to connect
the two sources. The domain expert, here a neuroscientist has no
problem providing us with the necessary ``glue knowledge'':
\begin{quote}
  {\it Purkinje cells and Pyramidal cells have dendrites that have
    higher-order branches that contain spines. Dendritic spines are
    ion (calcium) regulating components.  Spines have ion binding
    proteins.  Neurotransmission involves ionic activity (release).
    Ion-binding proteins control ion activity (propagation) in a cell.
    Ion-regulating components of cells affect ionic activity
    (release).  }
\end{quote}

In order to capture this knowledge and make it available to the
system, we employ \emph{domain maps} such as the one in
Figure~\ref{fig-two-worlds} and formalize them in logic -- here, using
statements in \emph{Description Logic} (DL); see Section~\ref{sec-dm}
for details.
%e.g.,\cite{calvanese98:_descr_logic_concep_data_model})\footnote{see 
%  Definition~\ref{def-dm-sem} for details}.  
Together with additional inference rules (\eg\ capturing transitivity
of ``\mytexttt{has}''), DL axioms like these formally capture the
domain knowledge.  Domain maps not only provide a concept-oriented
browsing and data exploration tool for the end user, but -- even more
importantly -- can be used for defining and executing integrated view
definitions (IVDs) at the mediator.  The above real-world example
illustrates a fundamental difference in the nature of information
integration as studied in most of the database literature and as
necessary for scientific data management.  In the latter, seemingly
unconnected schema can be semantically close \emph{when situated in
  the scientific context}, which in this case is the neuroanatomy and
neurophysiological setting described above. Therefore we call this
\emph{mediation across multiple worlds} and facilitate it using domain
maps as the one shown.


\subsubsection*{From Terminology and Static Knowledge to ``Process Context''}

While domain maps are useful to put data into a terminological and
thus somewhat ``static'' knowledge context, a different knowledge
representation has to be devised when trying to put data into a
dynamic or ``process context''.  Consider, for example, groups of
neuroscientists who study the science of mammalian memory and
learning. Many of these groups study a phenomena called
\emph{long-term potentiation} (LTP) in nerve cells, where repeated or
sustained input to nerves in specific brain regions (such as the
hippocampus) conditions them in such a manner that after some time,
the neuron produces a large output even with a small amount of
``known'' (or learnt) input. Given this general commonality of
purpose, however, individual scientists study and collect
observational data for very different aspects of the phenomena.

\begin{figure}[t]
  ~\hfill\mbox{\psfig{figure=dotfiles/process_map_intro.ps,height=7cm}}\hfill~
    \caption{A simple \emph{process map}.  Blue and  red edges depict
      processes about which two data sources/research groups have
      observational data; dashed edges indicate abstractions (``short
      cuts'').}
    \label{fig-example-1}
\end{figure}

\begin{example}[Capturing Process Knowledge]\label{ex-intro}% ~\\
  Consider a group \cite{bozdagi00:_increas_number_synap_punct_durin}
  that studies the role of a specific protein \emph{N-Cadherin} in the
  context of \emph{synpase formation} during \emph{late-phase
    long-term potentiation} (L-LTP), a subprocess of LTP. The data
  collected by the group consists of measurements that illustrate how
  the amount of \emph{N-Cadherin} and the number of synapses (nerve
  junctions) both simultaneously increase in cells during L-LTP. A
  different group,
  \cite{kasahara01:_activ_calcium_calmod_protein_kinas}, studies a new
  enzyme called CAMK-IV and its impact on a chemical reaction called
  phosphorylation of a protein called CREB. Their data is collected to
  show how modulating the amounts of CAMK-IV, and other related
  enzymes affect the amount of CREB production, and how this in turn,
  affects other products in the nucleus of the neurons. Ideally, the
  goal of ``mediating'' between experimental information from these
  two sources would be to produce an integrated view that enables an
  end-user scientist to get a deeper understanding of the LTP
  phenomena. Specifically, the end-user should be able to ask queries
  (and get answers) that exploit the scientific interrelationship
  between these experiments.
  
  At the risk of oversimplification, we can state that the first
  source looks at synapse-formation, and is only interested in the
  fact that some proteins (including \emph{N-Cadherin}) bring about
  the formation of synapses. They do not look at the processes leading
  to the production of these proteins. The second source looks at a
  specific chain of events leading up to the production of the
  proteins, but does not care which proteins are produced. The
  \emph{semantic connection} between these two sources can be
  constructed in terms of the underlying ``event structure'' and how
  they elaborate on different parts of it. Figure \ref{fig-example-1}
  depicts a simplified view of the relationship explained above and
  shows the cyclic progression of events leading to synapse formation
  during LTP: Red edges situate the first source with respect to the
  overall process, while blue edges situate the second source.  In
  either case, the dashed lines show the subsequence of events the
  sources ``glossed over'' or abstracted.  Thus the first source does
  not have any information pertaining to \emph{phosphorylates(CAMK-IV,
    CREB)}, and the second source does not have any data related to
  \emph{forms(protein, synapse)}. Neither source has any data about
  the (black) edge \emph{synthesizes(gene, protein)}.
\end{example}

Domain maps allow data providers to put their source data into a
static/terminological context, while process maps allow them to do the
same for a dynamic/process context. Together they capture valuable
``glue knowledge'' that resides at the mediator and facilitates
integration of hard-to-correlate sources; in particular,
concept-oriented data discovery (``semantic browsing'')
\cite{gupta-ludaescher-martone-ICDE-demo-01}, view definition, and
semantic query optimization
\cite{chakravarthy90:_logic_based_approac_seman_query_optim}.  To make
model-based mediation effective, it is also necessary to ``hook'' the
elements of the source schema to the domain map and the process map.
This process, which we call the \emph{contextualization} mechanism, is
central to the MBM framework.




% As a consequence of our extensions in DMs and PMs,
%we also extend the methods by which an experimental schema can be
%connected to the glue-knowledge.

%For such highly complex (wrt.\ required domain expertise) mediation
%scenarios, conventional syntax-oriented XML-based mediation
%architectures are not adequate. While the latter use XML query
%languages such as XQuery for the specification of integrated views, we
%propose a novel extension called \emph{model-based mediation} (MBM) in
%which domain semantics, encoded as logic rules, can be used to define
%integrated views. 

%The basic idea of MBM is to employ (i) \emph{conceptual models} (CMs)
%for exporting more domain semantics of data sources to the mediator,
%and (ii) secondary ``glue knowledge sources'' called \emph{domain
%  maps} (DMs), in order to make complex integration scenarios from
%scientific data domains amenable to mediation in the first place. As
%an intuitive example, the DM for the running example would hold the
%information that \emph{CA1}, \emph{CA3} and \emph{dentate gyrus} are
%three subregions of the brain region called the \emph{hippocampus}.
%This glue knowledge helps to situate the two sources in a common
%anatomical context. The reason for performing the ``situating'' step
%is necessary because the observational ``data'' from the experiments
%is often purely empirical and does not explicitly record the context
%of the experiment.



\section{Model-Based Mediation}\label{sec-mbm}
% model-based mediation: the framework, sources, wrappers,
%  mediators, conceptual models (figure from ER02), integrated views,
%  F-logic, registration 


In mediator systems, differences in syntax and data models of sources
$S_1,S_2,\dots$ are resolved by wrappers that translate the raw data
into a common generic data format, typically XML.  In most current
mediator systems, all other differences, in particular schema
heterogeneities are then handled by an appropriate integrated view
definition (IVD) which is defined using an XML query language
\cite{ludaescher-papakonstantinou-velikhov-EDBT-00,papakonstantinou01:_enosy_market_data_integ_platf}.
We extend this architecture by ``lifting'' exported source data from
the level of uninterpreted, semistructured data in XML syntax to the
semantically rich level of \emph{conceptual models with domain
  knowledge} (CMs).  Then, the mediator's IVDs can be defined in terms
of CMs (\emph{global-as-view}) and thus make use of a semantically
richer model involving class hierarchies, complex object structure,
properties of relationships (relational constraints, cardinalities,
...) etc. 


\subsubsection*{Model-Based Mediation: The Protagonists}


The underlying methodology and procedures of MBM involve users in
different roles and at different levels:

$\bullet$ \textbf{\emph{Data providers}} are typically domain experts,
\eg, bench scientists who would like to make their data from
experimental studies available to the community.  In MBM, a data
provider can not only export an XML-queryable version of her data, but
also \emph{domain semantics} by lifting the exported data and schema
information from a structural level (\eg, XML DTDs) to the level of
conceptual models.\footnote{XML Schema and similar efforts like RELAX
  NG play an intermediate role between purely structure-based models
  (DTDs) and richer semantic models with constraint mechanisms etc.}.
Allowing data providers to {situate} or ``\emph{contextualize}''
(Example~\ref{ex-dm-hook}) their primary data themselves
has significant benefits. First, data providers know best where their
data fits on the glue maps. Second, even without the IVDs defined by
special ``mediation engineers'', data is automatically associated
across different sources via their domain/process map contexts.

$\bullet$ \textbf{\emph{View providers}} specify integrated view
definitions (IVDs), \ie, program complex views in an expressive
declarative rule-language. The IVDs are defined over the registered
complex sources $\CM(S_1), \CM(S_2), \dots$ and the ``glue knowledge''
sources in the mediator's repository. Thus view providers are the
actual ``mediation engineers'' and bring together (as a team or
individually) expertise in the application domain and in databases and
knowledge-representation.

In order to make the virtual databases defined through IVDs
``first-class citizens'', view providers should contextualize their
result views. When defining new ``fused'' objects as part of an IVD,
view contextualization is facilitated by the fact that the raw data
already comes with its context (see
Figure~\ref{fig-mbm-architecture}).


$\bullet$ \textbf{\emph{End users}} can start by \emph{semantic
  browsing} of GMs, \ie, by navigating the domain and process
ontologies in the style of topic maps, where a user navigates through
a concept space by following certain relationships, going up and down
concept hierarchies etc.  A user may also focus her view by issuing
graph queries over domain or process maps which return only the
subgraphs of interest.  Eventually, the user can access raw data from
different sources, which is (due to contextualization) automatically
organized by context \cite{gupta-ludaescher-martone-ICDE-demo-01}, and
access derived data resulting from user queries against the mediated
views.






\subsubsection*{Conceptual Models and Registration of Sources at the Mediator}


In the sequel, by \emph{ontology} we mean formal representations of
``glue knowledge'', in particular domain maps and process maps.  We
can distinguish the following components of the conceptual model CM of
a source $S$:
\begin{displaymath}
  \CM(S) = \OM(S) \cup \ONT(S) \cup \CON(S)
\end{displaymath}  
The different logical components an their dependencies are depicted in
Figure~\ref{fig-dependencies}:

\begin{itemize}
\item $\OM(S)$ is the \emph{object model} of the source $S$ and
  provides signatures for \emph{classes}, \emph{associations} between
  classes, and \emph{functions}.  $\OM(S)$ structures can be defined
  extensionally by facts (\EDB), or intensionally via rules
  (\IDB).
  
\item $\ONT(S)$ is the \textit{local ontology} of the source $S$, \ie,
  defines {concepts} and their {relationships} from the {source's
    perspective}.
  
\item $\ONTG(S)$ is the \emph{ontological grounding} of $\OM(S)$ in
  $\ONT(S)$;  it links the object model $\OM(S)$ (classes,
  attributes, associations) to the concepts and relationships of
  $\ONT(S)$.
  
\item $\CON(S)$ is the \emph{contextualization} of the local source
  ontology relative to a mediator ontology $\ONT(M)$.
  
\item $\IVD(M)$ is the mediator's \emph{integrated view definition}
  and comprises logic view definitions in terms of the sources' object
  models $\OM(S)$ and the mediator's ontology $\ONT(M)$. By posing
  queries against the mediator's $\IVD(M)$, the user has the illusion
  to interact with a single, semantically integrated source instead of
  interacting with independent, unrelated sources.
\end{itemize}


\begin{figure}[t]
   \centerline{\fbox{\psfig{figure=dependencies.ps,width=.55\textwidth}}}
    \caption{Model-based mediation: dependencies between logical components}
    \label{fig-dependencies}
\end{figure}


\NI In the following, we present the local parts of $\CM(S)$, \ie,
$\OM(S)$, $\ONT(S)$, and $\ONTG(S)$ through a running example. For
details on the contextualization $\CON(S)$ see
Example~\ref{ex-dm-hook} and
\cite{gupta02:_regis_scien_infor_sourc_seman_mediat}.



% BL: for keywords
\renewcommand{\textsl}[1]{\textsc{#1}}



\begin{example}[Cell-Centered Database: CCDB]\label{ex-ccdb}
  Figure~\ref{figure-OM-source1} shows pieces of a simplified version
  of the conceptual model $\CM(\CCDB)$ of a real-world scientific
  information source called the \textit{Cell-Centered Database},
  \cite{CCDB-paper02}.  The database consists of a set of
  \class{experiment} objects.  Each experiment collects a number of
  cell \textsl{images} from one or more instruments.  For each image,
  the scientists mark out cellular \textsl{structures} in the image
  and perform measurements on them \cite{CCDB-paper02}. They also
  identify a second set of regions, called \class{deposit}s, in images
  that show the deposition of molecules of proteins or genetic
  markers. In general, a region marked as deposit does not necessarily
  coincide with a region marked as a structure.
\end{example}

\begin{figure}[t]
  \begin{center}
    {\sf\scriptsize
  \begin{tabular}[t]{|l|}
    \hline
    \textbf{Classes in $\OM(\CCDB)$} \\
    \hline
    \hline
    \class{experiment}(\underline{id}:\attribute{id}, date:\attribute{date},
cell\_type:\attribute{string}, images:\textsc{set}(image)).\\
    \class{image}(\underline{id}:\attribute{id},
    instrument:\textsc{enum}\{c\_microscope, e\_microscope\},
    resolution:\attribute{float}, size\_x:\attribute{int}, size\_y:\attribute{int},
    \\
    \qquad     depth:\attribute{int}, structures:\textsc{set}(structure),
regions:\textsc{set}(deposit)).\\
    \class{structure}(\underline{id}:\attribute{id}, name:\attribute{string},
length:\attribute{float},
    surface\_area:\attribute{float}, volume:\attribute{float},
bounding\_box:\attribute{Cube}). \\
    \class{deposit}(\underline{id}:\attribute{id},
substance\_name:\attribute{string},
    deposit\_type:\attribute{string},
    relative\_intesity:\textsc{enum}\{dark,normal,bright\},\\
    \qquad     amount:\attribute{float}, bounding\_box:\attribute{Cube}). \\
    $\cdots$ \medskip\\
                                %
   \hline
    \textbf{Associations in $\OM(\CCDB)$} \\
    \hline
    \hline
    \assoc{co\_localizes\_with}(\class{deposit}.substance\_name,
    \class{deposit}.substance\_name, \class{structure}.name).\\
    \assoc{surrounds}(s1:\class{structure}, s2:\class{structure}).\\
    $\cdots$ \medskip \\
                                %
    \hline
    \textbf{Functions in $\OM(\CCDB)$} \\
    \hline
    \hline
    \func{deposit\_in\_structure}(\class{deposit}.id)
    $\rightarrow$ \textsc{set}(\class{structure}.name)\\
    $\cdots$\medskip \\
                                %
    \hline
    \textbf{Source Ontology -- $\ONT(\CCDB)$} \\
    \hline
    \hline
    \textsf{brain $\stackrel{has(co)}{\longrightarrow}$ cerebellum
      $\stackrel{has(co)}{\longrightarrow}$ cerebellar cortex
      $\stackrel{has(co)}{\longrightarrow}$ vermis} \hfill (ONT1)\\
    \textsf{dendrite $\stackrel{has(co)}{\longrightarrow}$ spine process
      $\stackrel{has(pm)}{\longrightarrow}$ spine} \hfill (ONT2)\\
    \textsf{cell $\stackrel{projects\_to}{\longrightarrow}$ brain\_region}\\
    globus\_pallidus$\stackrel{isa}{\longrightarrow}$brain\_region. \qquad $\dots$
    \qquad  denaturation$\stackrel{isa}{\longrightarrow}$process. \hfill (ONT3)\\
    \hline
    \relation{tc\_has(co)} := \textbf{\textsf{transitive\_closure}}(\relation{has(co)}). \qquad \qquad
    \relation{tc\_has(pm)} := \textbf{\textsf{transitive\_closure}}(\relation{has(pm)}). \hfill
    (ONT4)\\
    \relation{has\_co\_pm} :=
    \textbf{\textsf{chain}}(\relation{tc\_has(co), tc\_has(pm)})
    \hfill (ONT5)\\
    $\cdots$ \medskip \\
                                %
    \hline
    \textbf{Ontological Grounding -- $\ONTG(\CCDB)$} \\
    \hline
    \hline
    \textsf{\textbf{domain}(\class{structure}.volume) \textbf{in}  [0,300]} \\
    \textsf{\textbf{domain}(\class{structure}.name) \textbf{in} \relation{tc\_has(co)}(cerebellum)} \hfill (OG1)\\
    \textsf{\textbf{domain}(\class{experiment}.cell\_type) \textbf{in}
      \relation{tc\_has(co)}(cerebellum)} \hfill (OG2)\\
    \textsf{\class{experiment}.cell\_type
      $\stackrel{projects\_to}{\longrightarrow}$ globus\_pallidus}
    \hfill (OG3)\\
    \class{denatured\_protein}$\stackrel{exhibits}{\longrightarrow}$denaturation. \hfill (OG4)\\
    $\cdots$ \\
%    \hline
%    \textbf{CONTEXT of CCDB -- $\CON(\CCDB)$} \\
%    \hline
%    \hline
%     \textbf{domain}(\class{deposit}.id) \textbf{in}
%       get\_expasy\_protein\_id(\class{deposit}.\attribute{substance\_name})
%      \qquad \myif
%        \class{deposit}.\attribute{deposit\_type}=``protein'' \\
%     $\cdots$
  \end{tabular}}
\end{center}
\caption{Conceptual model for registering the
   Cell-Centered Database \cite{CCDB-paper02}}
 \label{figure-OM-source1} 
\end{figure}

Note that $\OM(\CCDB)$ in Figure~\ref{figure-OM-source1} includes
classes that are instantiated with observed data, \ie, the extensional
database \EDB(\CCDB).  In addition to {classes}, $\OM(\CCDB)$ stores
\emph{associations}, \ie, $n$-ary relationships between object
classes.  The association \textsf{co\_localizes\_with} specifies which
pairs of substances occur together in a specific structure. The object
model also contains \emph{functions}, such as the domain specific
methods that can be invoked by a user as part of a query. For example,
when the mediator or another client calls the function
$\CCDB$.\textsf{deposit\_in\_structure}(), and supplies the \emph{id}
of a deposit object, the function returns a set of \textsl{structure}
objects that spatially overlap with the specified deposit object.

Next, we describe the source's local ontology, $\ONT(\CCDB)$.  Here,
an ontology $\ONT(S)$ consists of a set of \emph{concepts} and
inter-concept \emph{relationships}, possibly augmented with additional
inference rules and constraints.\footnote{\eg, ONT4, ONT5 in
  Figure~\ref{figure-OM-source1} define virtual relations such as
  \emph{transitive closure} over the base relations} The {ontological
  grounding} $\ONTG(S)$ links the object model $\OM(S)$ to the source
ontology $\ONT(S)$.
                                %
The source ontology serves a number of different purposes:

\paragraph{Creating a Terminological Frame of Reference.}


For defining the terminology of a specific scientific information
source, the source declares its own controlled vocabulary through
$\ONT(S)$. More precisely, $\ONT(S)$ comprises the terms (\ie,
\emph{concepts}) of this vocabulary and the \emph{relationships} among
them.  The concepts and relationships are often represented as nodes
and edges of a directed graph, respectively.  Two examples of
interconcept relations are \textsf{has(co)} and \textsf{has(pm)} which
are different kinds of part-whole relationships \footnote{By standards
  of meronyms, there are different kinds of the \textsf{has} relation:
  component-object \textsf{has(co)}, portion-mass \textsf{has(pm)},
  member-collection \textsf{has(mc)}, stuff-object \textsf{has(so)},
  place-area \textsf{has(pa)} etc.
  \cite{artale96:_part_relat_objec_center_system}}.  In
Figure~\ref{figure-OM-source1}, items ONT1 and ONT2 show fragments of
such a concept graph. Once a concept graph is created for a source,
one may use it to define additional constraints on object classes and
associations.

\paragraph{Semantics of Relationships.}

The edges in the concept graph of the source ontology represent
inter-concept relationships. Often these relationships have their own
semantics that have to be specified within $\ONT(S)$. Item ONT4
declares two new relationships \textsf{tc\_has(co)} and
\textsf{tc\_has(pm)}.  After registration, the mediator interprets
this declaration and creates the new (possibly materialized)
transitive relations on top of the base relations \textsf{has(co)} and
\textsf{has(pm)} provided by the source $S$.  Similarly, the item ONT5
is interpreted by the mediator using a higher-order rule for chaining
binary relations:
\begin{itemize}
\item \textsf{chain(R1,R2)(X,Y) \myif R1(X,Z), R2(Z,Y)}
\end{itemize}
With this, ONT5 creates a new relationship \textsf{has\_co\_pm(X,Y)}
provided that there is a \textsf{Z} such that
\textsf{tc\_has(co)(X,Z)}, \emph{and} \textsf{tc\_has(pm)(Z,Y)}.

\paragraph{Ontological Grounding of $\OM(S)$.}

A local domain constraint specifies additional properties of the given
extensional database, and thereby establishes an \textit{ontological
  grounding} $\ONTG(S)$ between the {local ontology} $\ONT(S)$ and the
{object model} $\OM(S)$ (Figure~\ref{fig-dependencies}).  Items
(OG1--OG2) in Figure~\ref{figure-OM-source1} refines the domains of
the attributes {\class{experiment}.cell\_type} and
{\textsl{structure}.name} from the original type declaration
(\textsl{string}). The refinement constrains them to take values from
those nodes of the concept graph that are \emph{descendants} of the
concept \textsf{cerebellum} through the \textsf{has(co)} relationship.
%``LO.cerebellum'' declares ``cerebellum'' to be a term from the local
%ontology (as opposed to a class name from $\OM(S)$).

This constraint illustrates an important role of the local ontology in
a ``conceptually lifted" source.  By constraining the domain of an
attribute to be concept name $C$, the corresponding object instance
$o$ is ``semantically about'' $C$. In addition, this also implies that
$o$ is about any ancestor concept $C'$ of $C$ where ancestor is
defined via \textsf{has(co)} edges only.  Similarly, if a specific
instance, \textsf{\textsl{structure}.name} has the value
`\textsf{spine process}', it is also about `\textsf{dendrite}' (ONT2
in Figure~\ref{figure-OM-source1}).

In addition to linking attributes to concept names, a constraint may
also involve inter-concept relationships.  Let us assume
\textsf{projects\_to(cell, brain\_region)} is a relationship in the
source ontology \ONT(\CCDB). A constraint may assert that for all
instances $e$ of class \class{experiment},
\textsf{projects\_to($e$.cell\_type, 'globus\_pallidus')} holds (OG3).
The constraint thus \textit{refines} the original relationship
\textsf{projects\_to} to suit the specific semantics of $\OM(\CCDB)$.
Such constraint-defined correspondences between $\OM(S)$ and $\ONT(S)$
are used in the contextualization process \cite{gupta02:_regis_scien_infor_sourc_seman_mediat}.

\paragraph{Intensional Definitions.}

In the CM wrapper of a source $S$, we can define virtual classes and
associations that can be exported to the mediator as first-class,
queriable items by means of an intensional database (view definition)
$\IDB(S)$.  For example, we can create a new virtual class called
\textsl{denatured\_protein} in \IDB(\CCDB) via the rule:
\begin{quote}
{\sf \begin{tabular}[t]{l}
      \class{denatured\_protein}(ProtName) \IF \\
      \qquad \class{deposit}(ID, ProtName, protein, dark, \_, \_), \func{deposit\_in\_structure}(ID) $\neq \emptyset$
%      \qquad \func{deposit\_in\_structure}(ID) $\neq \emptyset$.
    \end{tabular}}    
\end{quote}
%\begin{itemize}
%\item
%  {\sf \begin{tabular}[t]{l}
%      \class{denatured\_protein}(ProtName) \IF \\
%      \qquad \class{deposit}(ID, ProtName, protein, dark, \_, \_), \func{deposit\_in\_structure}(ID) $\neq \emptyset$
%%      \qquad \func{deposit\_in\_structure}(ID) $\neq \emptyset$.
%    \end{tabular}}    
%\end{itemize}
Thus, an instance of a \class{denatured\_protein} is created when a
``dark'' protein deposit is recorded in an instance of
\class{deposit}, and there is some structure in which this deposit is
found. As a general principle of creating a CM wrapper, such a
definition will be supplemented by additional constraints to connect
it to the local ontology. For example, assume that $\ONT(\CCDB)$
already contains a concept called \concept{process}.  Item (ONT3)
defines \concept{denaturation} as a specialization of
\concept{process}. We can now add the constraint (OG4) to complete the
semantic specification about the new \class{denatured\_protein}
object.

\paragraph{Contextual References.}

It is a standard practice for scientific data sources to tag object
instances with controlled vocabulary from a public standard.  For
example, the source can specify that the domain of the
\class{deposit}.\textsf{id} field can be accessed through an internal
method, which, given a protein name, gets its \textsf{id} from a
specific database. For example, we can use
\func{get\_expasy\_protein\_id} to retrieve this information from the
SWISS-PROT database on the web.\footnote{\url{http://www.expasy.ch}}
How the source enforces this integrity constraint is internal to the
source and not part of its conceptual export schema.


\subsubsection*{Interplay between Mediator and Sources}

In order to address the source registration issue, we have to specify
which components of an existing $n$-source federation can be ``seen'',
\ie, accessed by the new, $n{+}1^{st}$ source.  A federation at the
mediator consists of: (i) currently \emph{registered conceptual
  models} $\CM(S)$ of each participating source $S$, (ii) one or more
\emph{global ontologies} $\ONT(M)$ residing at the mediator that have
been used in the federation, and (iii) \emph{integrated views}
$\IVD(M)$ defined in a global-as-view (GAV) fashion.

Typical mediator ontologies $\ONT(M)$ are \textit{public}, \ie, serve
as domain-specific expert knowledge and thus can be used to ``glue''
conceptual models from multiple sources. Examples of such ontologies
are the Unified Medical Language System (UMLS) from the National
Library of
Medicine\footnote{\url{http://www.nlm.nih.gov/research/umls/};
  strictly speaking a metathesaurus, \ie, a ``semi-formal'' ontology }
and the Biological Process Ontology from the GeneOntology
Consortium\footnote{\url{http://www.geneontology.org/process.ontology}}.
In the presence of multiple ontologies, \emph{articulations}, \ie,
mappings between different source ontologies
\cite{mitra00graphoriented} can be used to register with the mediator
information about inter-source relationships.  Note that a source $S$
usually cannot ``see'' all of the above components (i--iii) when
defining its conceptual model: While $S$ sees the mediator's
ontologies $\ONT(M)$ and thus can define its own conceptual model
$\CM(S)$ relative to the mediator's ontology in a \emph{local-as-view}
(LAV) fashion, it cannot directly employ \emph{another} source's
conceptual model $\CM(S')$, nor can it query the mediator's integrated
view $\IVD(M)$ which is defined \emph{global-as-view} (GAV) on top of
the sources.  The former is no restriction, since $S'$ can register
$\CM(S')$, in particular $\ONT(S')$ with the mediator, at which point
$S$ can indirectly refer to registered concepts of $S'$ via $\ONT(M)$.
The latter guarantees that query processing in this setting does not
involve ``recursion through the web'', \ie, between a source $S$ and
the mediator $M$ (the dependency graph in
Figure~\ref{fig-dependencies} is acyclic).\footnote{At the cost of
  loss of efficiency, the restriction ``no recursion through the web''
  could be lifted.}

\begin{figure*}[t]
  ~\hfill\mbox{\psfig{figure=dotfiles/icde_example_context2.ps}}\hfill~
  \caption{A domain map DM after situating new concepts
    \mytexttt{MyNeuron} and \mytexttt{MyDendrite} (dark)}
  \label{fig-registering}
\end{figure*}


\begin{example}[Contextualization: Local as View]\label{ex-dm-hook}~\\
  Consider the domain map in Figure~\ref{fig-registering}.
  Lighter-colored nodes correspond to concepts that the mediator
  ``understands'' and which a source can see. Now assume a source $S$
  wants to register information about specific neurons and their
  dendrites, but the mediator ontology (domain map) does not have
  dedicated names for those specific kinds of neurons and dendrites.
  In MBM this problem is solved by contextualising the new local
  source concepts as views on the mediator's global concepts: In
  Figure~\ref{fig-registering} the darker-colored source concepts are
  ``hooked'' to the mediator's domain map, thereby defining their
  meaning relative to the mediator's concepts.  This is achieved by
  sending the following first-order axioms (here in description logic
  syntax) to the mediator:
\begin{flquote}
MyDendrite $\equiv$ Dendrite $\sqcap$ $\exists$exp.Dopamine\_R \smallskip\\
MyNeuron $\sqsubseteq$ Medium\_Spiny\_Neuron\\
\qquad \qquad\qquad $\sqcap$ $\exists$proj.Globus\_pallidus\_external\\
\qquad \qquad\qquad $\sqcap$ $\forall$has.MyDendrite
\end{flquote}
Thus instances of \mytexttt{MyDendrite} are exactly those dendrites
that express Dopamine R(eceptor), and \mytexttt{MyNeuron} objects are
medium spiny neurons projecting to Globus Pallidus External and
\emph{only} have \mytexttt{MyDendrite}s. Assuming properties are
\emph{inherited} along the transitive closure of \mytexttt{isa}, it
follows that \mytexttt{MyNeuron}, like any
\mytexttt{Medium\_Spiny\_Neuron} projects to certain structures
(\mytexttt{OR} in Figure~\ref{fig-registering}).  With the newly
registered knowledge, it follows that \mytexttt{MyNeuron} definitely
projects to Globus Pallidus External. If we want to specify that it
\emph{only} projects to the latter, a \emph{nonmonotonic inheritance},
\eg, using FL with well-founded semantics can be employed.
\end{example}

Note that the intuitive graphical contextualization depicted in
Figure~\ref{fig-registering} is not unique, \ie, logically equivalent
domain maps may have different graph representations.\footnote{Similar
  to the fact that the same query can have many different syntactic
  representations. In general, equivalence of first-order (or SQL)
  queries is not decidable.}  For domain maps that can be completely
axiomatized using a description logic, a reasoning system such as FaCT
\cite{horrocks98using} can be employed in order to compute the
deductive closure, in particular, to derive a unique concept hierarchy
and to check consistency of a domain map.







\section{Knowledge Representation for Model-Based Mediation}\label{sec-kr}
% Knowledge Representation for MBM: domain maps, process maps,
%  F-logic, GCM, description logics, ontologies,

We now take a closer look at the principal mechanisms for specifying
``glue knowledge'', \ie, ontologies in the form of domain maps (DMs)
and process maps (PMs).

%When data providers register a source with the mediator, they can
%situate their data in a semantic context by means of \emph{domain
%  maps} and \emph{process maps}, which thus act as ``glue knowledge
%sources''.


\subsection{Domain Maps}\label{sec-dm}

As is standard for ontologies, domain maps name and specify relevant
concepts by describing the characteristic relationships among them. In
this way, DMs provide the basic domain semantics which is needed to
glue data across different sources in multiple-world scenarios.  DMs
can be depicted more intuitively in the form of labeled directed
graphs. In contrast to many other graph-based notations, however, DMs
have a solid formal semantics via a translation to logic rules (see
below). The graph form of DMs is defined as follows.


% In particular, DMs borrow from, but also extend {description
%  logics}, a family of decidable fragments of {first-order logic}
%\cite{calvanese98:_descr_logic_concep_data_model}.

%In model-based mediation, concepts provide the semantic anchor points
%from which sources can ``hang off'', \ie, contextualize their data.
%Concept descriptions are obtained by linking an atomic concept $C$ to
%other atomic concepts via roles or to certain boolean combinations of
%concept descriptions. 







\begin{definition}[Domain Maps]\label{def-domain-maps}
  Let \concepts\ be a set of symbols called \emph{concepts}, \roles\ a
  set of \emph{roles}.  A \emph{domain map} DM is a directed labeled
  graph with nodes $\concepts$.  A concept $C\in\concepts$ can be
  understood as denoting a class of objects sharing a set of common
  properties.  In order to understand how a concept $C$ is defined
  relative to other concepts, we have to inspect its outgoing edges.
  We write $c\in C$ to denote that $c$ is an \emph{instance} of
  concept $C$.\footnote{Thus, we can view $C$ and $D$ as unary
    predicates.}  We distinguish the following types of edges in DMs:
\begin{enumerate}
\item $C\stackrel{\mathit{isa}}{\to}D$ (short: $C\to D$) defines that
  \emph{every} $C$ \emph{isa} $D$, \ie, $c\in C$ implies $c\in D$.
  
  Since this subconcept/subclass relation is very common in DMs, we
  usually omit the \emph{isa} label and use the shorthand notation
  $C\to D$ instead.
\item $C\stackrel{\mathit{ex}:r}{\to}D$ defines that for every
  $c\in C$, there \emph{exists some} $r$-related   $d\in D$.
  
  Here, $r\in\roles$ is a \emph{role}, \ie, a \emph{binary relation}
  $r(c,d)$ between instances of $C$ and $D$.
\item $C\stackrel{\mathit{all}:r}{\to}D$ defines that for every $c\in
  C$ and \emph{all} $x$ which are $r$-related to $c$ (\ie, for which
  $r(c,x)$ holds), we have $x\in D$.
\item $C\stackrel{r}{\to}D$ defines that if $c\in C$ and $d\in D$,
  then they are $r$-related, \ie, $r(c,d)$ holds.
\item $\mytexttt{AND}{\to_i} \{D_1,\dots,D_n\}$, \ie, an
  \mytexttt{AND}-node with $n$ outgoing edges to $D_1,\dots,D_n$,
  respectively, defines an anonymous concept, the \emph{intersection} of
  concepts $D_1,\dots,D_n$.
\item $\mytexttt{OR}{\to_i}\{D_1,\dots,D_n\}$, \ie, an
  \mytexttt{OR}-node with $n$ outgoing edges to  $D_1,\dots,D_n$,
  respectively, defines an anonymous concept, the \emph{union} of
  concepts $D_1,\dots,D_n$.
\item $C\stackrel{=}{\to}D$ defines that $C$ is \emph{equivalent} to
  $D$, \ie, every $C$ \emph{isa} $D$ and vice versa. We could have
  denoted this also as ``$C{\leftrightarrow}D$'', however, the directed
  edge keeps the distinction between $C$ (the definiendum) and its
  definition $D$ (definiens).
\end{enumerate}
\end{definition}

\NI Note that $D$ can be an atomic or a defined concept.  When unique,
\mytexttt{AND} nodes are omitted and outgoing arcs directly attached
to the concept being defined.  In Figure~\ref{fig-registering},
unlabeled, grey edges and edges labeled ``proj'' (\emph{projects-to})
correspond to ``\emph{isa}''-edges and ``\emph{ex}:proj''-edges,
respectively.



\paragraph{Reified Roles as Concepts.}

In DMs, as in description logics, it is the concepts that are being
defined, whereas the roles are only a means to that end. In order to
``talk about'' the roles, \ie, define their properties in terms of
each other, we have to turn them into concepts themselves.  In logic
this ``quoting mechanism'' is known as reification.


\begin{example}[Roles as Concepts]\label{ex-roles-as-concepts-a}
  Consider a DM involving the roles \emph{regulates},
  \emph{activates}, and \emph{inhibits} and assume that in the given
  domain, \emph{activates}$(C,D)$ and \emph{inhibits}$(C,D)$ are
  special cases of \emph{regulates}$(C,D)$. Instead of introducing a
  special notation for ``sub-roles''\footnote{RDF(S) has such a notion
    called \emph{subproperty}.}, and then defining the mechanics of
  how roles can be related to one another, we turn roles into
  ``first-class citizens'' by making them concepts using a operator
  \mc\ (``make-concept'').  Now we can apply the modeling capabilities
  of DMs to roles and, \eg, simply state that
  $\mc(\emph{activates})\stackrel{\mathit{isa}}{\to}\mc(\emph{regulates})$.
\end{example}

\NI By modeling roles a concepts, more domain semantics can be
formalized, leading to better ``knowledge engineering''. In
particular, during \emph{query processing}, such formalized knowledge
can be automatically employed by the system: Given a DM (formalized as
logic rules), an MBM query or view definition involving
\emph{activates} and \emph{regulates} ``knows'' that the former is a
subconcept of the later. If during query processing, \eg, a goal
\mytexttt{regulates('cAMP',Protein)} is evaluated, the logic rules
correponding to the DM knowledge allow the system to deduce that any
result for \mytexttt{activates('cAMP',Protein)} is also an answer for
\mytexttt{regulates('cAMP',Protein)}.  This is correct since a
\emph{substitutability principle} holds which allows the system to
replace a concept $D$ with any of its subconcepts $C$, \ie, for which
$C\stackrel{\mathit{isa}}{\to}D$ holds.


\paragraph{Generating the Role Hierarchy.}

When making a role into a concept, the \emph{isa}
hierarchy\footnote{Strictly speaking, the \emph{isa} does not have to
  be a hierarchy but can be any directed acyclic graph.} on concepts
induces an \emph{isa} hierarchy on roles.

\begin{example}[Roles as Concepts,
  \emph{Cont'd}]\label{ex-roles-as-concepts-b}%~\\ 
  Consider a DM stating that
  $\mytexttt{NProt}\stackrel{\mathit{isa}}{\to}\mytexttt{Protein}$,
  \mytexttt{NProt} \mytexttt{regulates} some \mytexttt{Gene}, and
  $\mytexttt{cfos}\stackrel{\mathit{isa}}{\to}\mytexttt{Gene}$.\footnote{Here,
    \texttt{NProt} stands for \emph{nuclear protein}.}
%\begin{verbatim}
%    NProt isa Protein.
%    NProt ex:regulates Gene.
%    cfos isa Gene.
%\end{verbatim}
  The role \mytexttt{regulates} is conceptualized by asserting
  $\mc(\mytexttt{regulates})$. When making its hidden arguments
  visible, we note that $\mc(\mytexttt{regulates}(C,D))$ really
  denotes a \emph{family} of \mytexttt{regulates} concepts. The
  \emph{isa} hierarchy on \mytexttt{regulates} concepts is derived
  from the \emph{isa} hierarchy of its arguments. For example, we have:
  \begin{displaymath}\small
    \mc(\mytexttt{regulates}(\mytexttt{NProt,cfos}))\stackrel{\mathit{isa}}{\to}  
    \mc(\mytexttt{regulates}(\mytexttt{NProt,Gene}))\stackrel{\mathit{isa}}{\to}  
    \mc(\mytexttt{regulates}(\mytexttt{Protein,Gene}))
  \end{displaymath}
\end{example}



%Description logics are (decidable) fragments of first-order logic
%(FO). For example, for (2) above, the following are equivalent:
%  \begin{itemize}
%  \item $C\stackrel{\mathit{ex}:r}{\to}D \quad \Leftrightarrow \quad
%    C\sqsubseteq\exists r.D \quad \Leftrightarrow \quad \forall x ~
%    (C(x) \to \exists y ~ ({r}(x,y) \land D(y) ~)$ \hfill (\emph{ex})
%\end{itemize}

% \NI Figure~\ref{fig-registering} shows an example of a DM.


\subsubsection*{Domain Maps as Logic Rules} 

Domain maps borrow from description logics (DLs) the notions of
\emph{concept} and \emph{roles}. Indeed, while some of the above
constructs of DMs have equivalent formalizations in DL
\cite{ludaescher-gupta-martone-ICDE-01}, the fact that we need
additional mechanisms like \emph{roles as concepts}, \emph{recursive}
and \emph{parameterized} roles and concepts, and the fact that we want
``executable'' DMs during {query processing}, requires a translation
into a more general logic framework.

In the following, we formalize DMs in a minimal subset of F-logic (FL)
\cite{kifer-lausen-wu-JACM-95}. The semantics of DMs could be
formalized in other languages, in particular in other deductive
database languages. The use of FL is convenient since a small subset
of it already matches nicely the minimal requirements established for
a model-based mediator system \cite{ludaescher-gupta-martone-ICDE-01}.
Moreover, implementations of FL are readily available
\cite{flora,florid} and have been used by the authors in different
mediator prototypes before
\cite{ludaescher-gupta-martone-VLDB-00,himmeroeder-lausen-ludaescher-schlepphorst-EDBT-DEMO-98,ludaescher-himmeroeder-IS-98}.


% \paragraph{Compiling DMs into Logic.}
In FL, ``$c\isa C$'' and ``$C\subcl D$'' denote class membership
($c\in C$) and subclassing ($C\subseteq D$), respectively.  Thus,
there are logic rules of the form ``\emph{head}\la\emph{body}'' that
express the FL semantics of ``\isa'' and ``\subcl'', say that
``\subcl'' is a reflexive, transitive, and
antisymmetric\footnote{Since concepts are implemented as FL classes,
  this avoids terminological cycles.}  relation.
\begin{definition}[Compilation of Domain Maps]\label{def-DM-to-FL}%~\\
  The mapping $\Map:$ DM $\to$ FL of domain maps to F-logic is defined
  as follows:
\begin{enumerate}\small
\item $\Map(C) := \{\mathtt{C\isa concept}\}$, for all atomic concepts
  $C\in\concepts$
\item $\Map(r) := \{\mathtt{r\isa role}\}$, for all roles $r\in\roles$
\item $\Map(C\stackrel{\mathit{isa}}{\to} D) :=
  \{\mathtt{C\subcl\MapD{D}}\}\cup \Map(D)$
\item $\Map(C\stackrel{\mathit{ex}:r}{\to}D) := $
  \begin{enumerate}
  \item\label{skolD} $\{\mathtt{r(c,\_d), \_d\isa \MapD{D} ~\la~ c\isa
      C, \_d = skol_D(c)}\} \cup \Map(D) $
  \item $\{\mathtt{False ~\la~ c\isa C, \neg (r(c,\_d), \_d\isa
      \MapD{D})}\} \cup \Map(D) $
  \end{enumerate}
\item $\Map(C\stackrel{\mathit{all}:r}{\to}D) := $
  \begin{enumerate}
  \item\label{coerce} $\{\mathtt{d\isa \MapD{D} ~\la~ c\isa C,
      r(c,d)}\} \cup \Map(D) $
  \item $\{\mathtt{False ~\la~ c\isa C, r(c,d), \neg d\isa \MapD{D}}\}
    \cup \Map(D) $
  \end{enumerate}
\item $\Map(C\stackrel{r}{\to}D) := \{\mathtt{r(c,d) ~\la~ c\isa C,
    d\isa \MapD{D}}\}\cup \Map(D)$
\item $\Map(\mytexttt{AND}{\to_i} \{D_1,\dots,D_n\}) :=
  \{\mathtt{d\isa skol_{AND} ~\la~ d\isa \MapD{D_1}},\dots,
  \mathtt{d\isa\MapD{D_n}}\} \cup \Map(D_1)\cup\cdots\cup\Map(D_n)$
\item $\Map(\mytexttt{OR}{\to_i} \{D_1,\dots,D_n\}) := \{\mathtt{d\isa
    skol_{OR} ~\la~ d\isa \MapD{D_1}} \lor \dots \lor
  \mathtt{d\isa\MapD{D_n}}\} \cup \Map(D_1)\cup\cdots\cup\Map(D_n)$
  
\item $\Map(C\stackrel{=}{\to}D) := \{\mathtt{C\subcl\MapD{D},
    \MapD{D}\subcl C ~\la~ \MapD{D}}\}\cup\Map(D)$
\end{enumerate}
\end{definition}

\paragraph{Remarks.}
Here, $\MapD D$ is defined similar to $\Map(D)$, but returns for a
compound concept description $D$, a new auxiliary symbol $\MapD D$
representing the compound. For atomic $D$, we simply have
$\MapD{D}=\Map(D)$.  The symbols ``$\mathtt{skol}_X$'' produce new
Skolem function symbols everytime they are used in the translation
\Map: \eg, in (\ref{skolD}), we invent a symbolic representation for
the existentially quantified variable ``$\mathtt{\_d}$''. Note that
$\mathtt{c}, \mathtt{d}, \mathtt{\_d}$ are logic \emph{variables},
while $\mathtt{C,D,D_i,False}$ are \emph{constants}.\footnote{This is
  reversed from the usual convention used in the rest of the paper in
  order to match our DM notation.}
                                %
The different variants (a) and (b) in the translations of DMs
correspond to different intended uses: in (\ref{skolD}), we
\emph{create} an anonymous object for the $\exists$-quantified
variable, in (\ref{coerce}), we \emph{type coerce} all $C.r$ objects
into instances of $D$. In contrast, the (b) translations only
\emph{check} whether the constraints induced by the DM edges are
indeed satisfied, and signal an inconsistency (``\mytexttt{False}'')
otherwise.


\paragraph{Deriving the Role Hierarchy.}
Above we introduced the unary operator \mc\ which turns role literals
into concepts. We implement it in FL as a subclass of the (meta-)class
\mytexttt{concept} by asserting ``\mytexttt{mc\subcl concept}'' and
adding further rules for deriving the role hierarchy from the concept
hierarchy, given as set of \mc-declarations such as
$\mathtt{r(C,D)\isa mc}$ by the user:
\begin{itemize}\small
\item  $\mathtt{r(C,D)\isa mc, r(C',D')\isa mc, r(C,D)\subcl r(C',D')
    ~\la~ (r(C,D)\isa mc \lor r(C',D')\isa mc), C\subcl C', D\subcl
    D'}$ \hfill(\emph{up/down})
\item  $\mathtt{r(C,D)\isa mc, r(C',D')\isa mc, r(C,D)\subcl r(C',D')
    ~\la~ (r(C,D')\isa mc \lor r(C',D)\isa mc), C\subcl C', D\subcl
    D'}$ \hfill(\emph{mixed})
%\item $\mathtt{r(C',D')\isa mc, r(C,D)\subcl r(C',D') ~\la~
%    r(C,D)\isa mc, C\subcl C', D\subcl D'}$ \hfill (\emph{upward
%    propagation})
%\item $\mathtt{r(C,D)\isa mc, r(C,D)\subcl r(C',D') ~\la~ r(C',D')\isa
%    mc, C\subcl C', D\subcl D'}$ \hfill (\emph{downward propagation})
\end{itemize}
Observe that with the rules, we get indeed the desired result in
Example~\ref{ex-roles-as-concepts-b}.


\paragraph{Recursive Concepts.} Consider the part-of relationship
\mytexttt{has\_a} and its interaction with \mytexttt{isa}. For
example, since \mytexttt{MyNeuron} \mytexttt{isa}
\mytexttt{Medium\_Spiny\_Neuron} which in turn \mytexttt{has\_a}
\mytexttt{Neostriatum}, we conclude that \mytexttt{MyNeuron}
\mytexttt{has\_a} \mytexttt{Neostriatum} (Figure~\ref{fig-registering}).
In the general case, this gives rise to a recursive rule ``if
$C\stackrel{\mathit{isa}}{\to}D$ and $D\stackrel{\mathit{has\_a}}{\to}
E$ then $C\stackrel{\mathit{has\_a}}{\to} E$''.
                                %
Similarly, one can define that \mytexttt{isa} and \mytexttt{has\_a}
are independently transitive and that \mytexttt{isa} is antisymmetric.
For such recursive definitions, an intuitive graph notation can be
devised, \eg, using a dashed edge for the concept being defined (cf.\ 
\cite[pp.601]{ludaescher-himmeroeder-IS-98}) to its recursive
definition.
% (in Figure~\ref{fig-registering} a recursive
%definition of \mytexttt{MyDendrite}...
In a declarative rule-based query language like FL, an executable
specification is:
\begin{itemize}\small
\item \begin{math} \mathtt{{has\_a}(X,Z) ~\la~ X\subcl Y,
      {has\_a}(Y,Z)} . \end{math}
\end{itemize}
Note that here $\mathtt{X,Y,Z}$ are concept variables. Such FL rules
can also be used at the mediator to handle inductive definitions such
as (ONT4) in Figure~\ref{figure-OM-source1}, in particular, when the
source does not have the capability to evaluate recursive definitions.


\paragraph{Parameterized Roles and Concepts.}
Part-of relationships like \mytexttt{has\_a} come in different flavors
$F$, \eg, $F\in \{\emph{member/collection}, \emph{portion/mass},
\emph{phase/activity}, \dots\}$ and transitivity does not necessarily
carry over across flavors
\cite{artale96:_part_relat_objec_center_system}.\footnote{For example,
  \emph{orchestra has\_a musiscian} and \emph{musician has\_a arm},
  but not \emph{orchestra has\_a arm}.} This is most naturally modeled
by a \emph{parameterized role} \mytexttt{has\_a($F$)} which is
transitive \emph{within} each flavor $F$ but which may interact in
other ways \emph{across} flavors. It is straightforward to extend
Definition~\ref{def-DM-to-FL} for parameterized roles and concepts:
\eg, assume the parameterized role \mytexttt{has\_a($F$)} should hold
between concepts $C$ and $D$ only for some flavors $F$ satisfying a
condition $\varphi(F)$. We can extend $\Psi$ and compile such a
parameterized DM edge into FL as follows:
\begin{itemize}\small
\item \begin{math}
    \Map(C\stackrel{\mathit{has\_a(F)}\parallel\varphi(F)}{\longrightarrow}D)
    = \{ \mathtt{\mathtt{has\_a}(F)(c,d) ~\la~ c\isa C, d\isa
      \MapD{D}, \varphi(F)} \} \cup \Map(D).
  \end{math}
\end{itemize}
Note that a parameterized role like \mytexttt{has\_a(F)} has a
first-order semantics in FL despite its higher-order syntax
\cite{kifer-lausen-wu-JACM-95}.



\subsection{Process Maps}

%While DMs are abstractions of expert knowledge for gluing data sources
%through common ontologies, 
%
{Process maps} (PMs) provide abstractions of ``process knowledge'',
\ie, temporal and/or causal relationships between events that can be
used for situating and linking data across different sources.  Like
DMs, PMs are directed labeled graphs, albeit with a very different
semantics: Nodes are used to model \emph{states} while edges
correspond to \emph{state transitions} which are labeled with a
process name describing the transition.  In this way, data providers,
\eg, bench scientists can not only hook their raw data to the (given
or refined) DMs, but also to processes that are witnessed in their
experimental studies databases.


\paragraph{Initial Process Semantics PM$_0$.}
Intuitively, an edge of the form $e_{\pi} =
s\stackrel{\{\varphi\}\pi\{\psi\}}{\longrightarrow}s'$ of a PM means
that the process $\pi$ leads from state $s$ to $s'$; $\varphi$ is a
necessary \emph{precondition} that must hold in $s$ for $\pi$ to
happen, $\psi$ is a \emph{postcondition} which holds in $s'$ as a
result of $\pi$. By PM$_0$ we denote the set of all initial process
semantics.

We call the edge $e_{\pi}$ of a PM, a \emph{process occurrence} of
$\pi$ in PM. Thus, a process occurrence specifies where in a PM a
process occurs, and which pre- and postconditions $\varphi$ and $\psi$
this occurrence satisfies.  In addition to the semantics implied by
the occurrence of $e_{\pi}$ in PM, a process $\pi$ can have an
\emph{initial semantics} associated with the process name $\pi$. 


 To
allow for \emph{parameterization} of processes, we consider edge
labels where process names are \emph{first-order atoms}, \ie, $\pi =
\pi(T_1,\dots,T_n)$ where each term $T_i$ is a logic variable or
constant. For example, consider $\pi = \mathtt{opens(Channel)}$
describing the opening process of an ion channel. We can define its
initial semantics by the expression
\begin{displaymath}\small
  \{\neg \mathtt{open(Channel)\}\  {opens}(Channel)\ 
  \{{open}(Channel)} \}
\end{displaymath}
meaning that \emph{any} transition along a process occurrence of
$\pi=\mathtt{opens(Channel)}$ in a PM must be from a state where
$\mathtt{open(Channel)}$ was \emph{false}. In the successor state,
however, \ie, after $\pi$ has happened, we have that
$\mathtt{open(Channel)}$ is \emph{true}.


\paragraph{From  Process Maps  to Domain Maps.} We call
the first-order predicates occurring in $\varphi$ and $\psi$ like
``$\mathtt{open(Channel)}$'' \emph{fluents}, since their truth is
{state dependent}. We require that the set of \emph{fluent predicate
  symbols} \fluents\ is disjoint from the set $\proc$ of \emph{process
  names} and the sets of concept and role names \concepts\ and \roles,
respectively. In contrast, the constant parameters used in process
occurrences, like ``$\mathtt{Channel}$'' \emph{are} allowed to be
concepts from \concepts.

For example, a DM may have that
$\mathtt{NMDA\_receptor}\stackrel{\mathit{isa}}{\to}
\mathtt{Calcium\_channel} \stackrel{\mathit{isa}}{\to}
\mathtt{Channel}$ in which case the process knowledge about the
opening of channels and the ``static'' knowledge from a DM are
directly linked through the common concept $\mathtt{Channel}$.

Similarly, just as we have made roles ``first-class'' citizens by
reifying them into concepts, we can do the same for processes, thereby
being able to specify additional semantics of processes using domain
maps.

\begin{example}[Processes as Concepts] Consider the
  $\mathtt{binds\_to(X,Y)}$ process with the  initial semantics 
  \begin{displaymath}\small
    \mathtt{\{\neg bound(X,Y)\}\ binds\_to(X,Y)\ \{bound(X,Y)\}}
  \end{displaymath}
  Now consider a DM in which we have reified processes as concepts as
  follows: 
  \begin{displaymath}\small
    \mathtt{dimerizes(X)\stackrel{\mathit{isa}\parallel X=Y}{\longrightarrow}binds\_to(X,Y)}
  \end{displaymath}
  It is easy to see that this (parameterized) DM edge, when translated
  into FL, allows the system to conclude in the combined knowledge
  base DM $\cup$ PM$_0$  that
  \begin{displaymath}\small
    \mathtt{\{\neg bound(X,X)\}\ dimerizes(X)\ \{bound(X,X)\}} .
  \end{displaymath}
\end{example}


\paragraph{Process Elaboration and Abstraction.} 
The edge $e_{\pi}$ of a process occurrence can be seen as an
\emph{abstraction} of a real process. In addition to its initial
semantics PM$_0$, and the semantics induced by its concrete
occurrence in a specific PM, we can \emph{elaborate} this abstraction
by replacing the $e_{\pi}$ with a (sub-)process map $\elab(e_{\pi})$
whose initial and final states are $s$ and $s'$.  The newly created
nodes and edges of the elaboration $\elab(e_{\pi})$ are annotated with
the same unique \emph{elaboration identifier} $eid$.  The $eid$
includes at least a reference to $e_{\pi}$ indicating the edge being
elaborated, and the \emph{author} (\eg, data provider) of the
elaboration.

The converse of elaboration, \emph{abstraction}, takes a connected
subgraph $\Pi(S,s_0,s_f,E)$ with nodes $S$, edges $E$, and
distinguished nodes $s_0, s_f\in S$ (initial and final state), and
abstracts $\Pi$ into a single edge $e_{\pi} =
\abstr(\Pi(S,s_0,s_f,E))$.  The abstracted edges $E$ of $\Pi$ are
marked with a unique \emph{abstraction identifier} $aid$, which
includes a reference to the new abstraction edge $e_{\pi}$, and the
author of the abstraction.





\begin{definition}[Process Maps]\label{def-pms} %~\\
%  Consider a set of nodes \States\ (\emph{states}) and edge labels
%  \Proc\ (\emph{processes}). 
  A \emph{process map} $\Pi(S,s_0,s_f,E)$ is a connected, directed
  graph with nodes $S$, labeled edges $E$, and initial and final
  states $s_0,s_f\in S$.  The edges $e_{\pi}$ of $E$ are of the form
  \begin{itemize}
  \item $s \stackrel{\{\varphi\}\pi\{\psi\}}{\to} s'$ \hfill
    ($e_{\pi}$)
  \end{itemize}
  where the \emph{process name} $\pi$ is a first-order atom and
  $\varphi$ and $\psi$ are first-order formulas, called the
  \emph{precondition} and \emph{postcondition} of $e_{\pi}$,
  respectively.
  
  Given an edge $e= s_a\stackrel{\dots}{\to}s_b$ of a process map
  $\Pi(S,s_0,s_f,E)$, the \emph{elaboration} $\elab(e)$ of $e$ is a
  process map $\Pi'(S',s_a,s_b,E')$ such that (i) the initial and
  final states are $s_a,s_b$, (ii) $S'\cap S = \{s_a,s_b\}$, and (iii)
  all $e'\in E'$ are linked to $e$ via a common, unique identifier
  $eid(e',e)$. 
  
  A connected subgraph of a PM with distinguished initial and final
  state is called a \emph{subprocess map} (sub-PM).  Given a PM
  $\Pi(S,s_0,s_f,E)$, the \emph{abstraction} of a sub-PM
  $\Pi'(S',s_a,s_b,E')$ of $\Pi$, denoted $\abstr(\Pi')$, is a {new}
  edge $e_{\pi'} = s_a\stackrel{\dots}{\to}s_b$, where (i)
  $e_{\pi'}\notin E$, and (ii) all $e'\in E'$ are linked to $e_{\pi'}$
  via a common, unique identifier $aid(e',e_{\pi'})$.
\end{definition}





\begin{figure*}[t]
  ~\hfill\mbox{\psfig{figure=dotfiles/process_map3.ps,height=7cm}}\hfill~
  \vspace*{-2em}
  \caption{Process maps with elaborations and abstractions}
  \label{fig-process-map}
\end{figure*}


\NI Marking edges with elaboration and abstraction identifiers,
guarantees one-to-one mappings between an edge and its elaboration,
and similarly, between a subprocess map and its abstraction.  In this
way, a data provider can ``double-click'' on an edge $e_{\pi}$ and
elaborate the processes into a PM $\Pi$ in order to provide more
precise links to her data. Conversely, she may ``collapse'' a
subprocess map $\Pi$ into a single edge $e_{\pi}$, if her data does
not provide information at the detailed level of $\Pi$, hence is more
adequately hooked to the overall process $e_{\pi}$.


\subsubsection*{Process Maps as Logic Rules}

Similar to DMs, we can translate PMs into a logic representation
$\Map$(PM).  The difference is that for DMs our formalization in
description logic or F-logic yields a {first-order logic semantics},
whose unique minimal model $\mathcal M$(DM), interprets concepts and
roles as unary and binary predicates over a set of individuals. The
model $\mathcal M$ implies that data objects, which are linked as
concept instances to a DM, have the properties defined by the domain
map (\eg, the neurons in the images linked to \mytexttt{MyNeuron} in
Example~\ref{ex-dm-hook} project to
\mytexttt{Globus\_Pallidus\_External}).  In constrast, the logic
representation of a PM specifies only some process properties via pre-
and postconditions in PM, and PM's graph structure. We omit the
details of the semantics, due to lack of space. The basic idea is that
the graph structure of PMs (with its embedded hierarchy of
elaborations and abstractions) is formalized via a nested Kripke
structure in which the nodes of PM (states) have associated
first-order models, and in which labeled process edges specify a
\emph{temporal accessibility relation} between states.\footnote{see,
  \eg, \cite[Sec.~6]{lausen-ludaescher-may-MOC-98} for a
  formalization of hierarchical processes using nested Kripke
  structures.} In particular, a process elaboration of an edge
$e_{\pi}$ adds to the initial semantics PM$_0$, and the semantics of
the pre- and postconditions of the concrete occurrence of $e_{\pi}$ in
PM, an \emph{elaboration semantics}, \ie, a sequence of intermediate
states with first-order constraints along the paths of the elaboration.









\section{Model-Based Mediator System and Tools}\label{sec-tools}
%  Tools and systems: CCDB, KIND prototype, Know-ME, BNCOD, SciDAC
%  Workflow tool



\subsubsection*{The KIND Mediator Prototype}


\begin{figure}[t]
  \hspace*{-1em}{\psfig{figure=mbm-arch.ps,width=.6\textwidth}}
  \hspace*{-2em}
  \fbox{\psfig{figure=icde-kind2.ps,width=.45\textwidth}}
  \caption{\footnotesize \textbf{Left}: architecture of the  KIND model-based mediator.   \textbf{Right}: snapshot of the prototype: \emph{background left}:
    meditor shell for issuing ad-hoc queries against CM($M$);
    \emph{background right}: generated subgraph having the requested
    result data shown in its anatomical context; clicking on a
    (diamond) result node retrieves the actual result data
    (\emph{foreground center}).}
    \label{fig-mbm-architecture}
\end{figure}

The architecture of the KIND (Knowledge-based Integration of
Neuroscience Data) mediator system is depicted on the left in
Figure~\ref{fig-mbm-architecture}.  On the right a snapshot of the
prototype execution is shown: after the user issues a query against
the integrated view, the system ``situates'' the results on a domain
map, in this case \textsc{Anatom} (simple ontology of brain anatomy).
By clicking on the orange ``diamonds'', the user can retrieve the
actual result objects, grouped by concept (foreground).


In our first prototype
\cite{ludaescher-gupta-martone-VLDB-00,gupta-ludaescher-martone-ICDE-demo-01}
we have used the F-logic implementation \textsc{Flora}
\cite{yang00:_flora} as the only query processing and deduction
engine.  As part of a large collaborative project \cite{BIRN-CC} we
are currently reimplementing our prototype as a modular, distributed
mediator system that includes several additional components, for
example:

\begin{itemize}
\item \emph{Logic plan generator}: Given a user query $Q$ and an
  integrated view definition \IVD, $Q\circ\IVD$ is translated into a
  plan generator program $PG(Q\circ\IVD)$ which, when executed,
  produces an initial logic query plan for $Q\circ\IVD$.
\item \emph{Query rewriter}: This module takes a logic query plan and
  rewrites it into an executable, distributed plan based on the
  capabilities of a source (\eg, complete SQL or conjunctive queries
  with limited binding patterns).
\item \emph{Execution plan compiler}: For final execution, the
  rewritten plan is compiled into a logic program whose runtime
  execution sends the corresponding subqueries to wrapped sources,
  retrieves results, and post-processes them (\eg, joins, group-bys,
  and unions across sources) before sending them to the user.
\item \emph{SQL plan generator}: For relational sources, \ie, having
  SQL query capabilities, this wrapper module translates a logic query
  plan into an equivalent SQL statement, similar to
  \cite{draxler92:_power_prolog_sql_compil}.
\end{itemize}
A preliminary version of this new system has been recently
demonstrated \cite{gupta02:_regis_scien_infor_sourc_seman_mediat} and
includes all of the above modules. Plan generation and rewriting is
implemented using logic programming technology
\cite{ludaescher02:_mediat_query_proces_prolog_techn}, the SQL plan
generator has been implemented in Java. It is planned that the final
system will include specialized inference engines such as
\textsc{Flora} and \textsc{Xsb} \cite{sagonas-swift-warren-SIGMOD-94}
for handling deductive and object-oriented database capabilities, and
{FaCT} \cite{horrocks98using} for reasoning tasks over domain maps
which are formalized in description logics.




\subsubsection*{SMART Atlas and the Cell-Centered Database: Retrieval
  and Navigation Through Multi-Scale Data}


The Cell-Centered Database (CCDB) mentioned earlier in
Example~\ref{ex-ccdb} houses different types of high resolution 3D
light and electron microscopic reconstructions of cells and
subcellular structures produced at the National Center for Microscopy
and Imaging Research\footnote{\url{http://www.ncmir.ucsd.edu}}
\cite{CCDB-paper02}.  It contains structural and protein distribution
information derived from confocal, multiphoton and electron
microscopy, including correlated microscopy.  Many of the data sets
are derived from electron tomography, a powerful technique for
deriving 3D information from electron microscopic specimens.  Electron
tomography is similar in concept to medical imaging techniques like
CAT scans and MRI in that it derives a 3D volume from a series of 2D
projections through a structure.  In this case, the structures are
contained in sections prepared for electron microscopy, which are
tilted through a limited angular range. On the left of
Figure~\ref{fig-ccdb-smart} examples of datasets in the CCDB are
shown. 

\begin{figure}[t]
  \centerline{
    \fbox{
      \begin{minipage}[t]{.98\textwidth}
       ~ \\[6cm]
       ~
      \end{minipage}}
  }
  \caption{\footnotesize \textbf{Left}: Examples of tomographic data
    sets in the CCDB. A and B show a selectively stained spiny
    dendrite from a Purkinje cell. A is a projection of the volume
    reconstruction (dendrite appears as white against dark
    background). B is the segmented dendrite. C and D show a
    tomographic reconstruction of the node of Ranvier. C is a single
    computed slice through the volume. D is a surface reconstruction
    of the various components comprising the node. Scale bar in
    B$=1\mu m$; in C $= 0.5\mu m$. \textbf{Right}: Registration of a
    data set with the Smart Atlas.  The user draws a polygon
    representing the location of a data set, in this case a filled
    Purkinje neuron.  The user specifies the data base containing this
    data, then enters an annotation and selects a concept from the
    UMLS or some other ontology.  The concept ID is stored back in the
    database.}
  \label{fig-ccdb-smart}
\end{figure}

A screenshot of the \textsc{Smart Atlas} (Spatial Markup and Rendering
Tool) is shown on the right of Figure~\ref{fig-ccdb-smart}. The tool
is based on a geographic mapping tool
\cite{zaslavsky00:_new_techn_inter_onlin_mappin} and allows users to
define polygons on a series of 2D vector images and annotate them with
names, relationships, and concept IDs from an ontology such as UMLS.
This tool provides another kind of ``glue map'' (in addition to domain
and process maps); here, in the literal sense: First, a brain atlas
such as Paxinos and Watson \cite{paxinos98:_rat_brain_stereot_coord}
is translated into a spatial format (\eg, Scalable Vector Graphics:
SVG). The user then ``marks up'' the atlas using the \textsc{Smart
  Atlas} tool, \eg, with concepts names from UMLS.  Once the atlas has
been (partially) marked up, it can be queried from the same browser:
Clicking on any point in the atlas will return the stereotaxic
coordinates; clicking on a brain region will return the name of that
region, along with any synonyms, and highlight all planes containing
that structure.  The \textsc{Smart Atlas} can now be used to register
a researcher's data to a specific spatial location. This also links
the registered data automatically to the UMLS ontology by virtue of
the earlier semantic markup of spatial objects.  To register source
data, the user draws an arbitrary polygon representing the approximate
data location on one of the atlas planes (Figure~\ref{fig-ccdb-smart}:
right).  The user is then presented with a form which can be used to
add annotations or to provide additional links to concepts of an
ontology.  Although the UMLS is used in the examples shown here, the
user will eventually be able to use multiple ontologies, including
those of their own creation, for semantically indexing data. Tools are
also being developed to define new terms and relationships in existing
ontologies.  In \cite{gupta02:_system_manag_alter_model_model_mediat}
we have shown how spatial and conceptual information can be used
together in a mediator system; see also
\cite{maryann02:_feder_brain_data_knowl_guided_mediat} for further
details on the use of the \textsc{Smart Atlas}.



\section{Related Work and Conclusions} \label{sec-conclusions}

\subsubsection*{Related Work} 


Significant progress has been made in the general area of data
mediation in recent years, and several prototype mediator
architectures have been designed by projects like TSIMMIS
\cite{garcia-molina-papakonstantinou-quass-NGITS-95}, SIMS
\cite{knoblock98modeling}, Information Manifold
\cite{levy-rajaraman-ordille-VLDB-96}, Garlic \cite{haas97optimizing},
and MIX \cite{MIX-SIGMOD-99}.  While these approaches focus mostly on
structural and schema aspects, the problem of \emph{semantic
  mediation} has also been addressed:
                                %
In the DIKE system \cite{DIKE}, the focus is on automatic extraction
of mappings between semantically analogous elements from different
schemas.  A global schema is defined in terms of a conceptual model
(SDR network) where the nodes represent concepts and the (directed)
edge labels represent their semantic distances and a score called
\emph{semantic relevance} that measures the number of instances of the
target node that are also instances of the source node. The
correspondence between objects are defined in terms of
\textit{synonymies}, \textit{homonymies} and \textit{sub-source
  similarities}, defined by finding maximal matching between the two
graphs.


ODB-Tools \cite{beneventano-bergamaschi-2001} is a system developed on
top of the MOMIS \cite{bergamaschi99semantic} system for modeling and
reasoning about the common knowledge between two to-be-integrated
schemas.  They present the object-oriented language ODL$_{I^3}$
derived from a description logic (OCDL). The language allows a user to
create complex objects with finite nesting of values, union and
intersection types, integrity constraints and quantified paths. These
constructs are used to define a class in one schema as a
\textit{generalization}, \textit{aggregation}, or \textit{equivalent}
with respect to another; \textit{subsumption} of a class by another
can be inferred.
%With this machinery, semantic mediation is achieved by computing
%terminological and structural affinities between schema elements, 
An integrated schema is obtained by clustering schema elements that
are close to one another in terms of an affinity metric.

Calvanese et al.\ \cite{Calvanese-KRDB-2001} perform semantic
information integration using an LAV approach by expressing the
conceptual schema by a description logic language called $\cal{DLR}$,
and subsequently defining non-recursive Datalog views to express
source data elements in terms of the conceptual model.  The language
$\cal{DLR}$ represents concepts $C$, relations $R$, and a set of
assertions of the form $C_1 \sqsubset C_2$ or $R_1 \subset R_2$, where
$R_1, R_2$ are $\cal{DLR}$ relations with the same arity. Mediation is
accomplished by defining ``reconciliation correspondences",
specifications that a query rewriter uses to match a conceptual level
term to data in different sources.

Recently Peim et al.\ \cite{peim02:_query_proces_descr_logic_ontol}
have proposed to extend the well-known TAMBIS system
\cite{goble01:_trans_acces_multip_bioin_infor_sourc}. Their approach
is similar to ours
\cite{gupta-ludaescher-martone-SSDBM-00,ludaescher-gupta-martone-ICDE-01}
in that a logic-based ontology (in their case the $\mathcal{ALCQI}$
description logic) interfaces with an ``object-wrapped'' source. Their
work focuses on how a query on the ontology is transformed to monoid
comprehensions for semantic query optimization. In contrast, this
paper addresses the issue of how to \textit{dynamically} register a
new object source with pre-existing ontologies at the mediator.

%\paragraph{{Ontology Merging.}}
%The problem of ontology matching and merging stems from AI and KRDB
%research, and is now revisited by the Semantic Web community. Work on
%the Cyc Upper Ontology \cite{cycupper97hovy}, the Ontomorph system
%\cite{chalupsky00ontomorph}, the Chimaera system
%\cite{mcguiness00chimaera}, the PROMPT algorithm
%\cite{noymusen00prompt} and the FCA-MERGE algorithm
%\cite{stumme01fcamerge} are all different techniques to represent and
%find term-matching relationships so that they can be put into a
%concept lattice.

%The ONION system \cite{mitra00graphoriented} performs
%\textit{algebraic composition of ontologies}.  They use a special
%``semantic implication'' relation $P \Rightarrow Q$ which relates
%graph patterns $P$ and $Q$ by making the assertion that the object $Q$
%\textit{semantically belongs to} the class $P$.  Bridge rules for
%semantic implications are typically expressed as simple Horn clauses,
%and are translated to graph operations.  The system also admits
%functional rules, permitting simple functions to be executed as part
%of the ontology correlation process.

\subsubsection*{Summary: Model-Based Mediation and ``Reason-able'' Metadata}

%  multi-scale: senselab example vs. NCMIR, physiological
%  vs. anatomical (1 stylized image, vs. 10 terms for dendrites)

%  multi-species: human, primate, mouse, cricket

%  multi-modal: 2D images, lightmicroscopic, fMRI, 3D reconstructions,
%  ...
  
%  it is now common place that the crux is not availability of
%  information, but versatile, flexible ways to interrelate, and
%  associate data in meaningful ways ``connecting the dots''
  
%  the ``glue knowledge'' is NOT in any individual DB, but in the
%  combination of expert (``background/contex'') knowledge and DBs.
%  The goal of MBM is to take advantage of the experts' domain
%  knowledge and make it usable for queries and computations: thus, KR
%  is needed. In fact, rougly speaking: MBM = KR+DB 




We have presented model-based mediation as a methodology that supports
information integration of scientific data across complex
multiple-world scenarios as found, \eg, in the Neuroscience domain.
In this framework, object-oriented and conceptual models, domain maps
and process maps all provide means to capture more domain semantics
and thus can act as ``glue knowledge sources'' to link
hard-to-correlate sources.  We have presented mechanisms to formally
contextualize source data.  The graph structures thus constructed have
been shown to be useful for navigating across related concepts and
querying local data during navigation
\cite{qian02:_navig_virtual_infor_sourc_know_me}.  

Logic formalizations of domain and process maps can be seen as
``reason-able'' or ``executable'' metadata (cf.\ 
\cite{horrocks02:_daml_oil}): Unlike conventional, descriptive
metadata which is primarily used for data discovery, formal ontologies
such as domain maps and process maps can support much more versatile
computational tasks in a mediator system as illustrated in this
chapter. For example, different and apparently unrelated data objects
can be associated and retrieved together or even ``fused'' by the
mediator's integrated view definition (IVD), since IVDs can be defined
as deductive rules over domain maps and process maps
(Figure~\ref{fig-dependencies}). In this way, in model-based
mediation, logic rules play the role of ``executable'' or
``computational'' metadata for scientific data integration. The latter
is a challenging application and benchmark for combined database and
knowledge representation techniques.


\small 
\bibliographystyle{alpha-initials-big}
\bibliography{lst.string,lst,2put_in_lst,bl,lst.conf}

\end{document}


