\chapter{Background \& Related Work}

\label{ch:background}

In order to design a federation engine for Semantic Web data sources,
it is first necessary to compare Semantic Web technologies to their
relational counterparts. Moreover, many insights for the engine's design
can be found in the existing literature on federated databases. In the
following sections, these results of this two pronged investigation is
described.
\section{Relational Databases}

Most of the research related to database federation has been conducted
on relational databases. This is no surprise because the relational
model has been the dominant model since it was first described by by
E.F. Codd in~\cite{Codd70relmodel}. A relational database has a
tabular structure, with each column in the table signifying a
different attribute. A relation is defined as a set of tuples that
contain a set of elements, one each from each attribute. In Tables
~\ref{tbl:hostcities}, ~\ref{tbl:eventdetails}, and
~\ref{tbl:athletedetails} are sections of three tables that are part of a
relational database for the Olympic games. Table ~\ref{tbl:hostcities}
contains a list of host cities and their geolocation
information. Table ~\ref{tbl:eventdetails} contains the dates of the
events and their mottoes. Table ~\ref{tbl:athletedetails} has
the details of athletes attending the events.

%%Add: one or two more paragraphs on the structure and features of SQL
%%databases.

\subsection{Limitations of the Relational Model}

The relational model has a number of shortcomings. First, from Tables
~\ref{tbl:hostcities}, ~\ref{tbl:eventdetails}, and
~\ref{tbl:athletedetails}, it is evident that there is a clear
separation between the data structure (the attributes) and the data
itself. This means that the relationship between the data and the
attributes are not persistent.  Second, the database has a rigid
structure, which means that it is necessary to have NULL values for
those attributes that do not exist in a relationship. For
instance, the 1896 Olympic games did not have a motto but it is
necessary to specify that fact explicitly.  Third, the relationships
between the tables are not explicitly stated and have to be
inferred. To gather all the non-athlete information on a particular
Olympic games, it is necessary to do a join on Tables 1 \& 2 using
{\em idville}.  Fourth, all data and attribute identifiers are local
to a given database. This means that they lack meaning outside the
database and therefore cannot easily used for data manipulations
across different data sources~\cite{bertails08semwebadv}.

\begin{table}
\caption{Example of Relational Database Table: Host Cities}
\centering
\begin{tabular}{c c c c}
\hline\hline
idville & label-en & longitude & latitude \\
\hline
1 & Athens & 23.7166667 & 37.966667 \\
2 & Beijing & 116.400002 & 39.900002 \\ [1ex]
\hline
\end{tabular}
\label{tbl:hostcities}
\end{table}

\begin{table}
\addtolength{\tabcolsep}{-2pt}
\small
\caption{Example of Relational Database Table: Event Details}
\centering
\begin{tabular}{c c c c c c c c}
\hline\hline
id & idville & year & Opening Ceremony Date & Closing Ceremony Date & Motto \\
\hline
1 & 1 & 1896 & 1896/04/06 & 1896/04/15 & NULL \\
2 & 2 & 2008 & 2008/08/08 & 2008/08/24 & One World, One Dream \\ [1ex]
\hline
\end{tabular}
\label{tbl:eventdetails}
\end{table}

\begin{table}
\caption{Example of Relational Database Table: Athlete Details}
\centering
\begin{tabular}{c c c c}
\hline\hline
Athlete ID & label-en & Birth Date & Death Date \\
\hline
2 & Beijing & 116.400002 & 39.900002 \\ [1ex]
\hline
\end{tabular}
\label{tbl:athletedetails}
\end{table}

\section{Database Federation}

The research on federated database systems dates back to the 1980s when McLeod
and Heimbigner first detailed a federated approach to managing decentralized
database systems. They defined a decentralized database as a collection of
structured information that may be logically and/or physically
distributed. Logical decentralization is the division into components for
allowing separate access, and physical decentralization is about the allocation
of data to different nodes. A federated system consists of a number of logical
components, such as endpoints, related, but independent, and each with its own
component schema, defined by a component Database Administrator (DBA). A schema
describes the structure of a database in formal language. The principal goal of
each component is to satisfy the needs of its most frequent and important users,
which are usually the local ones. These disparate components are held together
by a federal schema, which contains a federal controller and is administered by
a federal DBA. The federal DBA resolves conflicts between components and defines
federal schema(s), relate them to component schemas, and specifies each
component’s interface.

\begin{figure}
\begin{center} 
\scalebox{0.5}{\includegraphics{images/database_federation.jpg}}
\rule[5pt]{12cm}{1pt}
\caption{A Database Federation \cite{ibm}}
\label{fig:federation}
\end{center}
\end{figure}

There are many options available for logical distribution - a single, global
federal schema, a separate federal schema for each pair of components,
associating a federal schema with each component, or a hierarchy of federal
schemas. Given a federated setup, there is a range of possible views that a
given component user can have. At one end, the federal and local schemas are so
well integrated that the user cannot tell which data is being accessed. In this
setup, the user could be oblivious to potentially expensive non-local
references. On the other end, the federal schema is separate from the local one
and therefore the user would have to address each one separately.
 
With physical distribution, better performance would result as a result of
placing the data close to principal sources and users. Moreover, redundantly
storing data would provide reliability and survivability. In such implementations, the complexity that
exists from the presence of duplicate data as well as that which results from
the combination of logical and physical decentralization must be addressed.

The federal controller (or engine) is the entity that is charge of the
federation. The controller needs to perform several steps for each request from a
client.
\begin{enumerate}
\item The request is checked for validity against the federal schema and access
rights are verified.
\item The request is decomposed into several subrequests, each of which can be
satisfied by a single component.
\item Each subrequest, if applicable, is translated from the federal schema to the
target component schema.
\item The subrequests are sent to the corresponding components.
\item The results from each component is collected and, if applicable, translated from the
component schema to the federal schema.
\item The results are combined and returned to the client.
\end{enumerate} There are three approaches to federal controller
placement - as a special node on the network, co-located on a node
with another component, or parts of it may be distributed across
different components. The component controllers should have three
important features: allow local users and the federal controller
concurrent access to data, communicate results back to federal
controller, and recognize locally-issued requests for which the
federal schema is needed and forward those to the federal
controller~\cite{ mcleod80fedarch}. In this thesis work, the objective
was to create an independent, stand-alone federation engine that could
be interfaced with any combination of components. As a result, the
first approach was chosen.

\section{Semantic Web} 

\label{se:semweb}

The Semantic Web is touted and increasingly accepted as
the next generation of the Web. The inventor of the the World Wide Web described
the Semantic Web as an extension of the current Web in which information has
well-defined meaning that is machine readable~\cite{lee01semweb}. As such,
Semantic Web technologies provide a framework for sharing information between
decentralized sources using data interpretation, integration, and
management capabilities. In such an environment, there would be significant
reductions in the hours spent on decision-making, organizing, and filtering
useful knowledge from the human-only-readable, large data repository that is the
Web today.

A number of features enable the structure and machine readability of the
Semantic Web. Unique Resource Identifiers (URI) enable unique meaning, the
Resource Description Framework (RDF) facilitate the meta data layer, and SPARQL -
a query language for RDF - permits the efficient and descriptive querying of
Semantic Web sources.

\subsection{Uniform Resource Identifier (URI)}

URIs can be Uniform Resource Locators (URLs), such as web addresses, or Uniform
Resource Names (a unique name within a given namespace)~\cite{uriurl}. A URL, such as {\em
http://dig.csail.mit.edu}, identifies the homepage of the Decentralized
Information Group and also indicates the location of that information. A URN, on
the other hand identifies a resource, so that there is no ambiguity in its
reference. It does not necessarily give any information on the resource's
location. For example, {\em dig:source\_descriptions}, identifies the namespace
for the source description ontology for the system described in this thesis. URIs ensure that a given name will always
correspond to the same resource across domains such that disparate information
may be brought together for integration~\cite{watugula06thesis}.

\subsection{Resource Description Framework (RDF)} 

RDF is a directed, labeled graph data format for knowledge
representation on the Web~\cite{rdfw3c}. RDF is used to describe the
attributes of resources and establish relationships between different
resources. Relationships are established via subject-predicate-object
triples, in which the predicate identifies a relationship between two
resources - the subject and the object. The various components of a
triple would ideally made up of URIs so that the triples maybe easily
processed and manipulated. Listing ~\ref{lst:rdf} shows part of an RDF
Graph, expressed as a set of triples. These triples together contain
the name and/or email information for three individuals.

\begin{center}
\begin{lstlisting}[caption={Sample RDF},label={lst:rdf},float]
@prefix foaf:  <http://xmlns.com/foaf/0.1/> .

_:a  foaf:name   "Johnny Lee Outlaw" .
_:a  foaf:mbox   <mailto:jlow@example.com> .
_:b  foaf:name   "Peter Goodguy" .
_:b  foaf:mbox   <mailto:peter@example.org> .
_:c  foaf:mbox   <mailto:carol@example.org> .
\end{lstlisting}
\end{center}

\subsection{SPARQL Protocol and RDF Query Language (SPARQL)} 

SPARQL is an RDF query language~\cite{sparqlw3c}. It can be used to
express queries to a single data source or across multiple data
sources. SPARQL is capable of querying required and optional graph
patterns along with their conjunctions and disjunctions. The results
of a SPARQL query may be returned as a result set or RDF graphs. The
expressive power of SPARQL is perhaps best demonstrated by an
example. Suppose that we have are interested in querying the data in
Listing ~\ref{lst:rdf}.  We could create a query that would pull pairs
of names and e-mail addresses from this data set. In SPARQL, this
query would have the syntax shown in Listing ~\ref{lst:sparql}.

\begin{center}
\begin{lstlisting}[caption={Sample SPARQL Query},label={lst:sparql},float] 
PREFIX foaf:   <http://xmlns.com/foaf/0.1/>
SELECT ?name ?mbox
WHERE
  { ?x foaf:name ?name .
    ?x foaf:mbox ?mbox }
\end{lstlisting}
\end{center}

The real power of SPARQL is the fact that it is already conveniently
encoded in an RDF language. When a query is executed, an attempt is
made to match the Basic Graph Pattern (BGP), i.e. the combination of
triples, in a SPARQL query to any part of the RDF Graph it is trying
to query.

The result of this particular query would be names and mboxes of
individuals for whom both pieces of information is in the RDF
Graph. Hence, Carol's information would not be returned as she does
not have a {\em foaf:name} attribute associated with her in the Graph.

\subsection{Advantages of RDF Data Sources}

A juxtaposition of the features of the Semantic Web and the aforementioned limitations of
the relational mode illustrates how the RDF model makes up for these deficiencies. The use of
URIs mean that the reference to a data element has meaning across multiple
domains. Such persistence makes data integration, interpretation, and management
across different data sources seamless. Moreover, the graph structure of the
data is very flexible. The DBA is free to choose any shape for the data she is
in charge of. Also, the use of triples ensure that the relationships between
database elements are explicit and easy to discern with appropriate SPARQL
queries. 

\section{Related Work}

Much of the research on database federation has focused on relational
databases. Some of this also includes work on secure relational
federations. For example, HERMES (HEterogeneous Reasoning and MEdiator
System) developed at the University of Maryland was a platform that
was developed to design and implement such
systems~\cite{candan96smd}. There has been little work done on such
comprehensive environments for Semantic Web, especially secure ones,
due to the relative newness of such technologies. However, marked
progress has been made in the development of various components that
make up a federation engine for the Semantic Web.

Some work has been done on the semantic integration of relational data using
SPARQL~\cite{weng08semrel}. In this particular example, a mediator-wrapper
architecture is used for data integration, which is divided into three sub-parts
- mediated schema, query language, and query rewriting algorithms. Ontology is
used for mediated schema and conjunctive queries are rewritten using Views
through the implementation of the MiniCon algorithm. However, since MiniCon uses
Datalog, the query processor translates SPARQL queries to Datalog to perform all
steps involved in data integration – optimization, query rewriting, and query
optimization. Moreover, this system only interacts with relational databases and
not SPARQL endpoints. Without SPARQL, most queries will lack expressivity and
the full potential of the Semantic Web will remain untapped.

Virtual integration of distributed, heterogeneous data sources based on the
Semantic Web technology to facilitate scientific collaboration was described
in~\cite{langegger07distsprql}. The authors propose a middleware based on a
mediator-wrapper architecture that can map local data models and schemas to
several global domain ontologies. Clients submit SPARQL queries corresponding to
the global domain ontologies to the mediator. The mediator, which holds
information on registered data sources and global domain ontologies, generates
the query plan using an iterative dynamic programming algorithm. The wrappers
help overcome the model and schema heterogeneity by providing specific access
methods. While this system is promising, little performance data of the
optimizer and the engine is available that sheds light on the effectiveness of
this approach.

Kolas has developed a query rewriting algorithm that attempts to apply lessons
learned from relational information integration systems to Semantic Web
technologies~\cite{kolas07queryrewrite}. However, the focus of this paper is
only on one aspect of query rewriting - mapping between local and target
schemas. Two approaches are presented and one is chosen (Global-as-View) based
only on a number of factors associated with local to global mapping - independent
domain ontology, mutually independent data source to domain ontology mappings,
extracting all meaning from source to domain ontology, etc. Very little focus is
placed on the rewriting process once the mappings are performed.

The OptArq system has implemented a SPARQL optimizer based on triple pattern
selectivity. The optimizer aims to reduce the size of the intermediate result
sets of triple patterns. An overall cost function, which is a function of the
costs of subject, predicate, and object, is used to rank triple patterns. The
elementary cost functions are calculated based on statistical data of endpoints
that the OptARQ system has cached~\cite{bernstein07optarq}. Although the
statistical models are basic and imprecise, this system provides a good
framework for optimizing SPARQL queries for use in federated Semantic Web
environments.

The only known federated system that uses SPARQL to query RDF data
sources that we are aware of is the DARQ. It is a full-fledged engine
that performs query parsing, query planning, query optimization, and
query execution. Planning and optimization are done using the source
descriptions that the system has on file for those systems that have
registered with it ahead of time. DARQ adapts much of the research on
federation of relational databases to perform SPARQL queries on RDF
sources. However, DARQ only operates on open data sources and does not
offer any support for secure SPARQL
federation~\cite{quilitz08querying}. Secure data sources are often
necessary in scientific, business, and socio-political fields for
economic and legal reasons, as we will see in chapter
~\ref{ch:usecase}.
